×

Recourse-based stochastic nonlinear programming: properties and Benders-SQP algorithms. (English) Zbl 1270.90038

Summary: We study recourse-based stochastic nonlinear programs and make two sets of contributions. The first set assumes general probability spaces and provides a deeper understanding of feasibility and recourse in stochastic nonlinear programs. A sufficient condition for equality between the sets of feasible first-stage decisions arising from two different interpretations of almost sure feasibility is provided. This condition is an extension to nonlinear settings of the “\(W\)-condition,” first suggested by D. W. Walkup and R. J.-B. Wets [SIAM J. Appl. Math. 15, 1299–1314 (1967; Zbl 0203.21806)]. Notions of complete and relatively-complete recourse for nonlinear stochastic programs are defined and simple sufficient conditions for these to hold are given. Implications of these results on the L-shaped method are discussed. Our second set of contributions lies in the construction of a scalable, superlinearly convergent method for solving this class of problems, under the setting of a finite sample-space. We present a novel hybrid algorithm that combines sequential quadratic programming (SQP) and Benders decomposition. In this framework, the resulting quadratic programming approximations while arbitrarily large, are observed to be two-period stochastic quadratic programs (QPs) and are solved through two variants of Benders decomposition. The first is based on an inexact-cut L-shaped method for stochastic quadratic programming while the second is a quadratic extension to a trust-region method suggested by J. Linderoth and S. Wright [Comput. Optim. Appl. 24, No. 2–3, 207–250 (2003; Zbl 1094.90026)]. Obtaining Lagrange multiplier estimates in this framework pose a unique challenge and are shown to be cheaply obtainable through the solution of a single low-dimensional QP. Globalization of the method is achieved through a parallelizable linesearch procedure. Finally, the efficiency and scalability of the algorithm are demonstrated on a set of stochastic nonlinear programming test problems.

MSC:

90C15 Stochastic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Au, K.T., Higle, J.L., Sen, S.: Inexact subgradient methods with applications in stochastic programming. Math. Program. 63, 65–82 (1994) · Zbl 0807.90089 · doi:10.1007/BF01582059
[2] Aubin, J.-P., Frankowska, H.: Set-valued Analysis. Springer, Berlin (1990) · Zbl 0713.49021
[3] Beale, E.M.L.: On minimizing a convex function subject to linear inequalities. J. R. Stat. Soc. 17B, 173–184 (1955) · Zbl 0068.13701
[4] Benders, J.F.: Partitioning procedures for solving mixed-variables programming problems. Numer. Math. 4, 238–252 (1962) · Zbl 0109.38302 · doi:10.1007/BF01386316
[5] Berkelaar, A., Dert, C., Oldenkamp, B., Zhang, S.: A primal-dual decomposition-based interior point approach to two-stage stochastic linear programming. Oper. Res. 50, 904–915 (2002) · Zbl 1163.90679 · doi:10.1287/opre.50.5.904.360
[6] Bertsekas, D.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999) · Zbl 1015.90077
[7] Birge, J.: Decomposition and partitioning methods for multi-stage stochastic linear programs. Oper. Res. 33, 989–1007 (1985) · Zbl 0581.90065 · doi:10.1287/opre.33.5.989
[8] Birge, J.R., Louveaux, F.: Introduction to Stochastic Programming. Springer Series in Operations Research. Springer, Berlin (1997) · Zbl 0892.90142
[9] Blomvall, J.: A multistage stochastic programming algorithm suitable for parallel computing. Parallel Comput. 29, 431–445 (2003). Parallel computing in numerical optimization (Naples, 2001) · doi:10.1016/S0167-8191(03)00015-2
[10] Blomvall, J., Lindberg, P.O.: A Riccati-based primal interior point solver for multistage stochastic programming. Eur. J. Oper. Res. 143, 452–461 (2002) · Zbl 1058.90074 · doi:10.1016/S0377-2217(02)00301-6
[11] Boggs, P., Tolle, J.: Sequential quadratic programming. Acta Numer. 4, 1–50 (1995) · Zbl 0828.65060 · doi:10.1017/S0962492900002518
[12] Boggs, P., Tolle, J., Wang, P.: On the local convergence of Quasi-Newton methods for constrained optimization. SIAM J. Control Optim. 20, 161–171 (1982) · Zbl 0494.65036 · doi:10.1137/0320014
[13] Byrd, R.H., Hribar, M.E., Nocedal, J.: An interior point algorithm for large-scale nonlinear programming. SIAM J. Optim. 9, 877–900 (1999) (electronic). Dedicated to John E. Dennis, Jr., on his 60th birthday · Zbl 0957.65057 · doi:10.1137/S1052623497325107
[14] Chen, X., Fukushima, M.: Expected residual minimization method for stochastic linear complementarity problems. Math. Oper. Res. 30, 1022–1038 (2005) · Zbl 1162.90527 · doi:10.1287/moor.1050.0160
[15] Chen, X., Womersley, R.S.: Random test problems and parallel methods for quadratic programs and quadratic stochastic programs. Optim. Methods Softw. 13, 275–306 (2000) · Zbl 0980.90060 · doi:10.1080/10556780008805789
[16] Chen, X., Zhang, C., Fukushima, M.: Robust solution of monotone stochastic linear complementarity problems. Math. Program. 117, 51–80 (2009) · Zbl 1165.90012 · doi:10.1007/s10107-007-0163-z
[17] Cottle, R.W., Pang, J.-S., Stone, R.E.: The Linear Complementarity Problem. Academic Press, Boston (1992)
[18] Dantzig, G.B.: Linear programming under uncertainty. Manag. Sci. 1, 197–206 (1955) · Zbl 0995.90589 · doi:10.1287/mnsc.1.3-4.197
[19] Dantzig, G.B., Glynn, P.: Parallel processors for planning under uncertainty. Ann. Oper. Res. 22, 1–21 (1989) · Zbl 0714.90074
[20] Dantzig, G.B., Infanger, G.: Large scale stochastic linear programs: importance sampling and benders decomposition. Tech. rep. (1991) · Zbl 0781.65052
[21] Deng, G., Ferris, M.C.: Variable-number sample-path optimization. Math. Program. 117, 81–109 (2009) · Zbl 1165.90013 · doi:10.1007/s10107-007-0164-y
[22] Dennis, J.E. Jr., Moré, J.J.: A characterization of superlinear convergence and its application to quasi-Newton methods. Math. Comput. 28, 549–560 (1974) · Zbl 0282.65042 · doi:10.1090/S0025-5718-1974-0343581-1
[23] Dolan, E.D., Moré, J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[24] Dorn, W.S.: Duality in quadratic programming. Q. Appl. Math. 18, 155–162 (1960/1961) · Zbl 0101.37003
[25] Facchinei, F., Pang, J.-S.: Finite Dimensional Variational Inequalities and Complementarity Problems: Vols. I and II. Springer, New York (2003) · Zbl 1062.90002
[26] Fletcher, R., Leyffer, S.: User manual for filterSQP, May 21 1998
[27] Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: an SQP algorithm for large-scale constrained optimization. SIAM Rev. 47, 99–131 (2005) (electronic) · Zbl 1210.90176 · doi:10.1137/S0036144504446096
[28] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: User’s guide for NPSOL (version 4.0): A Fortran package for nonlinear programming. Technical Report SOL 86-2, Department of Operations Research, Stanford University, Stanford, CA, USA, Jan. 1986
[29] Gill, P.E., Murray, W., Wright, M.H.: Practical Optimization. Academic Press, Boston (1981)
[30] Goldsmith, M.J.: Sequential quadratic programming methods based on indefinite Hessian approximations. PhD thesis, Stanford University (1999)
[31] Han, S.P.: Superlinearly convergent variable metric algorithms for general nonlinear programming problems. Math. Program. 11, 263–282 (1976) · Zbl 0364.90097 · doi:10.1007/BF01580395
[32] Han, S.P.: A globally convergent method for nonlinear programming. J. Optim. Theory Appl. 22, 297–309 (1977) · Zbl 0336.90046 · doi:10.1007/BF00932858
[33] Higle, J., Sen, S.: Stochastic Decomposition: A Statistical Method for Large Scale Stochastic Linear Programming. Kluwer Academic, Boston (1996) · Zbl 0874.90145
[34] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms, vols. 1, 2. Springer, Berlin (1993)
[35] Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Springer, New York (1981) · Zbl 0452.90038
[36] Hoek, G.: Asymptotic properties of reduction methods applying linearly equality constrained reduced problems. In: Algorithms for Constrained Minimization of Smooth Nonlinear Functions, pp. 162–189 (1982) · Zbl 0477.90060
[37] Homem-De-Mello, T.: Variable-sample methods for stochastic optimization. ACM Trans. Model. Comput. Simul. 13, 108–133 (2003) · doi:10.1145/858481.858483
[38] Infanger, G.: Monte Carlo (importance) sampling within a Benders decomposition algorithms for stochastic linear programs. Ann. Oper. Res. 39, 41–67 (1992) · Zbl 0771.62024 · doi:10.1007/BF02060935
[39] Infanger, G.: Planning Under Uncertainty, Boyd and Fraser (1994) · Zbl 0867.90086
[40] Kiwiel, K.C.: Proximity control in bundle methods for convex nondifferentiable minimization. Math. Program. 46, 105–122 (1990) · Zbl 0697.90060 · doi:10.1007/BF01585731
[41] Leyffer, S.: macMPEC: AMPL collection of MPECs. Tech. rep., University of Dundee (2000)
[42] Lin, G.-H., Fukushima, M.: New reformulations for stochastic nonlinear complementarity problems. Optim. Methods Softw. 21, 551–564 (2006) · Zbl 1113.90110 · doi:10.1080/10556780600627610
[43] Linderoth, J., Wright, S.: Decomposition algorithms for stochastic programming on a computational grid. Comput. Optim. Appl. 24, 207–250 (2003). Stochastic programming · Zbl 1094.90026 · doi:10.1023/A:1021858008222
[44] Linderoth, J., Shapiro, A., Wright, S.: The empirical behavior of sampling methods for stochastic programming. Ann. Oper. Res. 142, 215–241 (2006) · Zbl 1122.90391 · doi:10.1007/s10479-006-6169-8
[45] Liu, X., Zhao, G.: A decomposition method based on SQP for a class of multistage stochastic nonlinear programs. SIAM J. Optim. 14, 200–222 (2003) · Zbl 1043.90058 · doi:10.1137/S1052623402361447
[46] Lucia, A.: An explicit quasi-newton update for sparse optimization calculations. Math. Comput. 40, 317–322 (1983) · Zbl 0516.65045 · doi:10.1090/S0025-5718-1983-0679448-4
[47] Murray, W., Prieto, F.J.: A sequential quadratic programming algorithm using an incomplete solution of the subproblem. SIAM J. Optim. 5, 590–640 (1995) · Zbl 0840.65052 · doi:10.1137/0805030
[48] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer Series in Operations Research. Springer, New York (1999) · Zbl 0930.65067
[49] Powell, M.J.D.: Algorithms for nonlinear constraints that use Lagrangian functions. Math. Program. 14, 224–248 (1978) · Zbl 0383.90092 · doi:10.1007/BF01588967
[50] Powell, M.J.D.: The convergence of variable metric methods for nonlinearly constrained optimization problems. In: Mangasarian, O.L., Meyer, R.R., Robinson, S.M. (eds.) Nonlinear Programming 3, pp. 27–63. Academic Press, New York (1978) · Zbl 0464.65042
[51] Powell, M.J.D.: A fast algorithm for nonlinearly constrained optimization calculations. In: Watson, G.A. (ed.) Lecture Notes in Mathematics, Numerical Analysis, Dundee, 1977, pp. 144–157. Springer, Berlin (1978)
[52] Robinson, S.M.: A quadratically-convergent algorithm for general nonlinear programming problems. Math. Program. 3, 145–156 (1972) · Zbl 0264.90041 · doi:10.1007/BF01584986
[53] Robinson, S.: Analysis of sample-path optimization. Math. Oper. Res. 21, 513–528 (1996) · Zbl 0868.90087 · doi:10.1287/moor.21.3.513
[54] Rockafellar, R.T., Wets, R.J.-B.: Stochastic convex programming: Kuhn-Tucker conditions. J. Math. Econom. 2, 349–370 (1975) · Zbl 0343.90039 · doi:10.1016/0304-4068(75)90003-8
[55] Rockafellar, R., Wets, R.-B.: Scenarios and policy aggregation in optimization under uncertainty. Math. Oper. Res. 16, 1–29 (1991) · Zbl 0747.90051 · doi:10.1287/moor.16.1.1
[56] Ruszczynski, A.: Decomposition methods. In: Handbook in Operations Research and Management Science, vol. 10, pp. 141–212. Elsevier Science, Amsterdam (2003)
[57] Shanbhag, U.V.: Decomposition and sampling methods for stochastic equilibrium problems. PhD thesis, Department of Management Science and Engineering (Operations Research), Stanford University (2006)
[58] Shanbhag, U.V., Infanger, G., Glynn, P.W.: A complementarity framework for forward contracting under uncertainty. Under second revision at Oper. Res. (2007) · Zbl 1235.91074
[59] Shanno, D.F.: On variable metric methods for sparse Hessians. Math. Comput. 34, 499–514 (1980) · Zbl 0424.65027 · doi:10.1090/S0025-5718-1980-0559198-2
[60] Shapiro, A.: Monte Carlo sampling methods. In: Handbook in Operations Research and Management Science, vol. 10, pp. 353–426. Elsevier Science, Amsterdam (2003)
[61] Shapiro, A., de Mello, T.H.: A simulation-based approach to two-stage stochastic programming with recourse. Math. Program., Ser. A 81, 301–325 (1998) · Zbl 0919.90120
[62] Stoer, J., Tapia, R.A.: On the characterization of q-superlinear convergence of quasi-Newton methods for constrained optimization. Math. Comput. 49, 581–584 (1987) · Zbl 0632.90052
[63] Toint, P.L.: On sparse and symmetric matrix updating subject to a linear equation. Math. Comput. 31, 954–961 (1977) · Zbl 0379.65034 · doi:10.1090/S0025-5718-1977-0455338-4
[64] Van Slyke, R.M., Wets, R.: L-shaped linear programs with applications to optimal control and stochastic programming. SIAM J. Appl. Math. 17, 638–663 (1969) · Zbl 0197.45602 · doi:10.1137/0117061
[65] Walkup, D.W., Wets, R.J.-B.: Continuity of some convex-cone-valued mappings. Proc. Am. Math. Soc. 18, 229–235 (1967) · Zbl 0145.38004 · doi:10.1090/S0002-9939-1967-0209806-6
[66] Walkup, D.W., Wets, R.J.-B.: Stochastic programs with recourse. SIAM J. Appl. Math. 15, 1299–1314 (1967) · Zbl 0203.21806 · doi:10.1137/0115113
[67] Wilson, R.B.: A simplicial algorithm for concave programming. PhD thesis, Harvard University, Cambridge, MA (1963)
[68] Zakeri, G., Philpott, A.B., Ryan, D.M.: Inexact cuts in Benders decomposition. SIAM J. Optim. 10, 643–657 (2000) · Zbl 0955.90088 · doi:10.1137/S1052623497318700
[69] Zhao, G.: A log-barrier method with Benders decomposition for solving two-stage stochastic linear programs. Math. Program. 90, 507–536 (2001) · Zbl 1023.90045 · doi:10.1007/PL00011433
[70] Zhao, G.: A Lagrangian dual method with self-concordant barriers for multi-stage stochastic convex programming. Math. Program. 102, 1–24 (2005) · Zbl 1058.90043 · doi:10.1007/s10107-003-0471-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.