C. Fabian

The material of this talk is based on joint projects with the collaboration of Edit Csizmas, Rajmund Drenyovszki, Eldon F.D. Ellison, Achim Koberstein, Gautam Mitra, Olga Papp, Diana Roman, Claudia Sagastizabal, Leena Suhl, Tamas Szantai, Zoltan Szoke, Win van Ackooij, Tibor Vajnai, Christian Wolf, Victor Zverovich.

Functions involving expectations, probabilities and risk measures typically occur in stochastic programming problems. This means large amounts of data to be organized, and inaccuracy in function evaluations. In this talk we discuss computational issues of decomposing two-stage problems, and of handling probabilistic constraints in static problems. We overview different solution approaches with a focus on convex problems. Interestingly, similar solution methods proved effective for these very different problems: enhanced cutting- plane methods in primal and dual forms.
To compare methods, we present several computational studies that were carried through in collaboration with different research teams. The importance of efficiency will be demonstrated in a case study.

Cutting-plane methods in their pure forms are notorious for zigzagging and other numerical difficulties. Numerical behaviour is generally improved by regularization. We mention bundle and level methods; [14], [16]. A further enhancement is the use of inexact cuts. These allow a close coordination between optimization and function evaluation, and may substantially decrease the computational effort. An inexact form of the level method was proposed in [9], and an inexact bundle method in [15]. A common generalization, level bundle methods for oracles with on-demand accuracy, was developed by Oliveira and Sagastizabal [19]. (In convex optimization, the part of the algorithm that provides function evaluations is generally called oracle.) In [12], the on-demand accuracy approach was extended to constrained convex problems.

In two-stage stochastic programming models, decisions are made in two stages and the observation of some random event takes place in between. The first decision must be made when the outcome of the random event is not yet known. For example, the first stage may represent the decision on the design of a system; and the second stage, a decision on the operation of the system under certain circumstances. Traditionally, the aim is to find a balance between investment cost and long-term operation costs (the latter formulated as the expectation of the second-stage optimum).
We discuss two-stage stochastic programming problems with discrete distribution of the random param- eters. Decomposition results a master problem formulated with the first-stage variables. The objective is a weighted sum of the recourse functions belonging to the different scenarios. Having fixed a first-stage decision, recourse function values and subgradients are obtained by solving the appropriate second-stage problems. These are then added to the master problem. Hence the problem is solved by a cutting-plane method. Traditional implementations fall into two categories: the disaggregate approach builds separate models for each recourse function, while aggregate one builds a single model for the expected recourse function; see [3,26]. The former one results a huge master problem. The latter one keeps the master problem of a tractable size, at the cost of losing part of the information. Experience shows that disaggregate approaches are more effective for solving small or medium-sized problems. On the other hand, aggregate approaches have better scale-up properties, see [2,29]. The threshold of breaking even depends on the implementation, and may be high. Regularized cutting-plane methods have been developed for both the disaggregate and the aggregate approaches: [24,17,11]. As discussed in [19], oracles of on-demand accuracy allow a novel setup: the master problem contains only aggregate information (and hence it remains tractable), but all information is retained in the oracle. We discuss in some detail a special form which integrates the advantages of the disaggregate and aggregate variants while avoiding their disadvantages; see [28].

Risk-averse variants of two-stage stochastic programming problems include a risk constraint on the recourse; see [1,7,8]. In the terms of the system design/operation example, it means reducing the risk of excessive operational costs arising in certain situations. Recent applications of such models can be found in [27,25]. Risk-averse variants can be decomposed in a way analogous to the traditional forms of two-stage problems. The resulting first-stage problem contains a special constraint function. We adapt the on-demand accuracy approach to risk-averse setting; see [12]. Risk aversion formulated using conditional value-at-risk and second-order stochastic dominance will be discussed, the latter handled through a dominance measure [10].

A probabilistic constraint prescribes that some requirement should be satisfied with a high probability. It is an intuitive way of avoiding bad (or catastrophic) situations. A joint probabilistic constraint [20] prescribes that several elementary requirements should be simultaneously satisfied with a high probability. In this talk we discuss joint probabilistic constraints in case of logconcave distributions, which result convex problems. Convexity statements are based on the theory of logconcave measures, developed by Prekopa; see [22] for an overview. Cutting-plane methods are traditionally used for probabilistic constrained problems. The method of Prekopa and Szantai [23] applies a Slater point to determine where to construct the next cut. Mayer [18] proposed a central cutting plane method. The difficulty is that gradient computation is noisy, and a practicable implementation requires sophisticated tolerance handling, see also [13].

Dual approaches were developed in the past decades: [4,5,6]. These are based on the concept of p-level efficient points [21] and progressively approximate a level set of the probabilistic function. In the talk we present an analogous approach, but we approximate the epigraph of the constraint function, instead of a level set. The present scheme yields very convenient duals, simple formulations using conjugate functions. The subproblems to be solved during the process are easier than those occurring in course of the classic schemes. Comparing the dual approach with the traditional primal cutting-plane approach, increased stability of the dual model is noticeable.

References

[1] Ahmed, S. (2006). Convexity and decomposition of mean-risk stochastic programs. Mathematical Programming 106, 433-446.

[2] Birge, J.R. and F.V. Louveaux (1988). A multicut algorithm for two-stage stochastic linear pro- grams. European Journal of Operational Research 34, 384-392.

[3] Dantzig, G.B. and A. Madansky (1961). On the solution of two-stage linear programs under uncer- tainty. In: Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability Vol. 1, 165-176. University of California Press, Berkeley.

[4] Dentcheva, D. and G. Martinez (2013). Regularization methods for optimization problems with probabilistic constraints. Mathematical Programming 138, 223-251.

[5] Dentcheva, D., B. Lai and A. Ruszczynski (2004). Dual methods for probabilistic optimization problems. Mathematical Methods of Operations Research 60, 331-346.

[6] Dentcheva, D., A. Prekopa and A. Ruszczynski (2000). Concavity and efficient points of dis- crete distributions in probabilistic programming. Mathematical Programming 89, 55-77.

[7] Dentcheva, D. and A. Ruszczynski (2003). Optimization with stochastic dominance constraints. SIAM Journal on Optimization 14, 548-566.

[8] Dentcheva, D. and A. Ruszczynski (2006). Portfolio optimization with stochastic dominance con- straints. Journal of Banking \& Finance 30, 433-451.

[9] Fabian, C.I. (2000). Bundle-Type Methods for Inexact Data. Central European Journal of Operations Research 8 (special issue, T. Csendes and T. Rapcsak, eds.), 35-55.

[10] Fabian, C.I., G. Mitra, D. Roman, and V. Zverovich (2011). An enhanced model for portfolio choice with SSD criteria: a constructive approach. Quantitative Finance 11, 1525-1534.

[11] Fabian, C.I. and Z. Szoke (2007). Solving two-stage stochastic programming problems with level decomposition. Computational Management Science 4, 313-353.

[12] Fabian, C.I., C. Wolf, A. Koberstein, L. Suhl (2015). Risk-averse optimization in two-stage stochastic models: computational aspects and a study. SIAM Journal on Optimization 25, 28-52.

[13] Henrion, R. (2012). Gradient estimates for Gaussian distribution functions: Application to probabilistically constrained optimization problems. Numerical Algebra, Control and Optimization 2, 655-668.

[14] Hiriart-Urruty, J-B. and C. Lemarechal. (1993). Convex Analysis and Minimization Algorithms Volume II: Advanced Theory and Bundle Methods. Springer-Verlag, Berlin.

[15] Kiwiel, K.C. (2006). A proximal bundle method with approximate subgradient linearizations. SIAM Journal on Optimization 16, 10071023.

[16] Lemarechal, C., A. Nemirovskii, and Yu. Nesterov (1995). New Variants of Bundle Methods. Mathematical Programming 69, 111-147.

[17] Linderoth, J.T. and S.J. Wright (2003). Decomposition Algorithms for Stochastic Programming on a Computational Grid Computational Optimization and Applications 24, 207-250.

[18] Mayer, J. (1998). Stochastic Linear Programming Algorithms: A Comparison Based on a Model Management System. Gordon and Breach Science Publishers.

[19] Oliveira, W. and C. Sagastizabal (2014). Level bundle methods for oracles with on-demand accuracy. Optimization Methods and Software 29 (2014), 1180-1209.

[20] Prekopa, A. (1970). On probabilistic constrained programming. In: Proceedings of the Princeton Symposium on Mathematical Programming (H.W. Kuhn, editor), 113-138. Princeton University Press, Princeton, New Jersey.

[21] Prekopa, A. (1990). Dual method for a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution. ZOR - Methods and Models of Operations Research 34, 441-461.

[22] Prekopa, A. (2003). Probabilistic Programming. In: Stochastic Programming, Handbooks in Opera- tions Research and Management Science 10 (A. Ruszczynski and A. Shapiro, eds.), Elsevier, Amster- dam, 267-351.

[23] Prekopa, A. and T. Szantai (1978). Flood control reservoir system design using stochastic programming. Mathematical Programming Study 9, 138-151.

[24] Ruszczynski, A. (1986). A Regularized Decomposition Method for Minimizing the Sum of Polyhedral Functions. Mathematical Programming 35, 309-333.
3

[25] Skar, C., G.L. Doorman, and A. Tomasgard (2014). Large-scale power system planning using enhanced Benders decomposition. In: Proceedings of the 18th Power System Computations Conference. Wroclaw, Poland; co-sponsored by IEEE.

[26] Van Slyke, R. and R.J.-B. Wets (1969). L-shaped linear programs with applications to optimal control and stochastic programming. SIAM Journal on Applied Mathematics 17, 638-663.

[27] Vespucci, M.T., M. Bertocchi, S. Zigrino, and L.F. Escudero (2013). Stochastic optimization models for power generation capacity expansion with risk management. In: Proceedings of the 10th International Conference on the European Energy Market. Stockholm, Sweden; IEEE.

[28] Wolf, C., C.I. Fabian, A. Koberstein, and L. Suhl (2014). Applying oracles of on-demand ac- curacy in two-stage stochastic programming - a computational study. European Journal of Operational Research 239, 437-448.

[29] Zverovich, V. C.I. Fabian, E.F.D. Ellison, and G. Mitra (2012). A computational study of a solver system for processing two-stage stochastic LPs with enhanced Benders decomposition. Mathematical Programming Computation 4, 211-238.

Keywords: Stochastic Programming, risk measures

P4 Plenary (Csaba Fabian)
June 2, 2016  12:15 PM
Salón de actos