A regularized decomposition method for minimizing a sum of polyhedral functions.(English)Zbl 0599.90103
Motivated by the two-stage stochastic programming problem with recourse for the case of a discrete distribution of the involved random elements, the author proposes an algorithm for the solution of nonlinear programming problems where the objective function to be minimized is the sum of many convex piecewise-linear functions, the constraints are linear and convex piecewise-linear functions, too. The method generates two sequences: main iterates \(\{x^ k\}\) and trial points \(\{y^ k\}\). At each iteration each of the functions are approximated from below by a pointwise maximum of a finite collection of linear functions and an approximate problem is constructed to find the next trial point. The objective of the approximate problem contains a quadratic term to stabilize it and to keep the number of the elements in the finite collection limited.
The approximate problem is solved in each iteration by a special algorithm based on an active set strategy. Convergence analysis is provided together with computational experiences.
The approximate problem is solved in each iteration by a special algorithm based on an active set strategy. Convergence analysis is provided together with computational experiences.
Reviewer: B.Strazicky
MSC:
| 90C30 | Nonlinear programming |
| 90C06 | Large-scale problems in mathematical programming |
| 65K05 | Numerical mathematical programming methods |
| 49M37 | Numerical methods based on nonlinear programming |
Keywords:
regularized decomposition method;sum of polyhedral functions;convex piecewise-linear functions;semidefinite quadratic programming;subgradient methods;sum of many convex piecewise-linear functions;main iterates;trial points;approximate problem;active set strategy;Convergence analysis;computational experiencesCite
Full Text:DOI
References:
| [1] | J. Birge and R.J.-B. Wets, ”Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse,” WP-83-111, IIASA, Laxenburg, 1983. ·Zbl 0603.90104 |
| [2] | M.J. Best, ”Equivalence of some quadratic programming algorithms,”Mathematical Programming 30 (1984) 71–87. ·Zbl 0551.90074 ·doi:10.1007/BF02591799 |
| [3] | J. Bisschop and A. Meeraus, ”Matrix augmentation and partitioning in the updating of the basis inverse,”Mathematical Programming 13 (1977) 241–254. ·Zbl 0372.90083 ·doi:10.1007/BF01584341 |
| [4] | J.W. Daniel, W.P. Gragg, L.C. Kaufman and G.W. Stewart, ”Reorthogonalization and stable algorithm for updating the Gram-Schmidt QR factorization,”Mathematics of Computation 30 (1976) 772–795. ·Zbl 0345.65021 |
| [5] | G. Dantzig and A. Madansky, ”On the solution of two-stage linear programs under uncertainty,” in:Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, vol. I, University of California Press, Berkeley, 1961, pp. 165–176. ·Zbl 0104.14401 |
| [6] | G. Dantzig and R. Van Slyke, ”Generalized upper bounding techniques,”Journal of Computer System Science 1 (1967) 213–226. ·Zbl 0162.23003 ·doi:10.1016/S0022-0000(67)80015-1 |
| [7] | P.E. Gill, N.I.M. Gould, W. Murray, M.A. Saunders and M. Wright, ”A weighted Gram-Schmidt method for convex quadratic programming,”Mathematical Programming 30 (1984) 176–195. ·Zbl 0545.90080 ·doi:10.1007/BF02591884 |
| [8] | P.E. Gill and W. Murray, ”Numerically stable methods for quadratic programming,”Mathematical Programming 14 (1978) 349–372. ·Zbl 0374.90054 ·doi:10.1007/BF01588976 |
| [9] | P. Kall, K. Frauendorfer and A. Ruszczyński, ”Approximation techniques in stochastic programming,” Technical Report, Institut für Operations Research, Universität Zürich, Zürich, 1984. ·Zbl 0665.90067 |
| [10] | P. Kall and D. Stoyan, ”Solving stochastic programming problems with recourse including error bounds,”Mathematische Operationsforschung und Statistik, Ser. Optimization 13 (1982) 431–447. ·Zbl 0507.90067 |
| [11] | K.C. Kiwiel, ”An aggregate subgradient method for nonsmooth convex minimization,”Mathematical Programming 27 (1983) 320–341. ·Zbl 0525.90074 ·doi:10.1007/BF02591907 |
| [12] | K.C. Kiwiel, ”A decomposition method of descent for minimizing a sum of convex nonsmooth functions,” Technical Report, Systems Research Institute, Warsaw, 1984 (to appear inJournal of Optimization Theory and Applications). |
| [13] | K.C. Kiwiel, ”A method for solving certain quadratic programming problems arising in nonsmooth optimization,” Technical Report, Systems Research Institute, Warsaw, 1984 (to appear inIMA Journal of Numerical Analysis). |
| [14] | L.S. Lasdon,Optimization Theory for Large Systems (Macmillan, New York, 1970). ·Zbl 0224.90038 |
| [15] | C. Lemaréchal, J.J. Strodiot and A. Bihain, ”On a bundle algorithm for nonsmooth optimization,” in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear Programming 4 (Academic Press, New York, 1981) pp. 245–282. ·Zbl 0533.49023 |
| [16] | R.E. Marsten, W.W. Hogan and J.W. Blankenship, ”The boxstep method for large scale optimization,”Operations Research 23 (1975) 389–405. ·Zbl 0372.90078 ·doi:10.1287/opre.23.3.389 |
| [17] | R. Mifflin, ”A stable method for solving certain constrained least squares problems,”Mathematical Programming 16 (1979) 141–158. ·Zbl 0407.90065 ·doi:10.1007/BF01582105 |
| [18] | B.A. Murtagh and M.A. Saunders, ”Large-scale linearly constrained optimization,”Mathematical Programming 14 (1978) 41–72. ·Zbl 0383.90074 ·doi:10.1007/BF01588950 |
| [19] | R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, 1970). ·Zbl 0193.18401 |
| [20] | R.T. Rockafellar, ”Monotone operators and the proximal point algorithm,”SIAM Journal of Control and Optimization 14 (1976) 877–898. ·Zbl 0358.90053 ·doi:10.1137/0314056 |
| [21] | J.B. Rosen, ”Primal partition programming for block diagonal matrices,”Numerische Mathematik 6 (1964) 250–260. ·Zbl 0129.34102 ·doi:10.1007/BF01386073 |
| [22] | A. Ruszczyński, ”QDECOM: The regularized decomposition method. User manual,” Technical Report, Institut für Operations Research, Universität Zürich, Zürich, 1985. |
| [23] | N.Z. Shor,Minimization Methods for Non-Differentiable Functions (Springer-Verlag, Berlin, 1985). ·Zbl 0561.90058 |
| [24] | D.M. Topkis, ”A cutting-plane algorithm with linear and geometric rates of convergence,”Journal of Optimization Theory and Applications 36 (1982) 1–22. ·doi:10.1007/BF00934337 |
| [25] | R. Van Slyke and R.J.-B. Wets, ”L-shaped linear programs with applications to optimal control and stochastic programming,”SIAM Journal on Applied Mathematics 17 (1969) 638–663. ·Zbl 0197.45602 ·doi:10.1137/0117061 |
| [26] | R.J.-B. Wets, ”Stochastic programming: solution techniques and approximation schemes,” in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming: The State of the Art (Springer-Verlag, Berlin, 1983) pp. 507–603. ·Zbl 0551.90070 |
| [27] | R.J.-B. Wets, ”Large scale linear programming techniques in stochastic programming,” WP-84-90, IIASA, Laxenburg, 1984. |
| [28] | P. Wolfe, ”A method of conjugate subgradients for minimizing nondifferentiable functions,”Mathematical Programming Study 3 (1975) 145–173. ·Zbl 0369.90093 |
| [29] | P. Wolfe, ”Finding the nearest point in a polytope,”Mathematical Programming 11 (1976) 128–149. ·Zbl 0352.90046 ·doi:10.1007/BF01580381 |
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.
