Abstract
A problem of minimizing a sum of many convex piecewise-linear functions is considered. In view of applications to two-stage linear programming, where objectives are marginal values of lower level problems, it is assumed that domains of objectives may be proper polyhedral subsets of the space of decision variables and are defined by piecewise-linear induced feasibility constraints. We propose a new decomposition method that may start from an arbitrary point and simultaneously processes objective and feasibility cuts for each component. The master program is augmented with a quadratic regularizing term and comprises an a priori bounded number of cuts. The method goes through nonbasic points, in general, and is finitely convergent without any nondegeneracy assumptions. Next, we present a special technique for solving the regularized master problem that uses an active set strategy and QR factorization and exploits the structure of the master. Finally, some numerical evidence is given.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
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.
M.J. Best, “Equivalence of some quadratic programming algorithms,”Mathematical Programming 30 (1984) 71–87.
J. Bisschop and A. Meeraus, “Matrix augmentation and partitioning in the updating of the basis inverse,”Mathematical Programming 13 (1977) 241–254.
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.
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.
G. Dantzig and R. Van Slyke, “Generalized upper bounding techniques,”Journal of Computer System Science 1 (1967) 213–226.
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.
P.E. Gill and W. Murray, “Numerically stable methods for quadratic programming,”Mathematical Programming 14 (1978) 349–372.
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.
P. Kall and D. Stoyan, “Solving stochastic programming problems with recourse including error bounds,”Mathematische Operationsforschung und Statistik, Ser. Optimization 13 (1982) 431–447.
K.C. Kiwiel, “An aggregate subgradient method for nonsmooth convex minimization,”Mathematical Programming 27 (1983) 320–341.
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).
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).
L.S. Lasdon,Optimization Theory for Large Systems (Macmillan, New York, 1970).
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.
R.E. Marsten, W.W. Hogan and J.W. Blankenship, “The boxstep method for large scale optimization,”Operations Research 23 (1975) 389–405.
R. Mifflin, “A stable method for solving certain constrained least squares problems,”Mathematical Programming 16 (1979) 141–158.
B.A. Murtagh and M.A. Saunders, “Large-scale linearly constrained optimization,”Mathematical Programming 14 (1978) 41–72.
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, 1970).
R.T. Rockafellar, “Monotone operators and the proximal point algorithm,”SIAM Journal of Control and Optimization 14 (1976) 877–898.
J.B. Rosen, “Primal partition programming for block diagonal matrices,”Numerische Mathematik 6 (1964) 250–260.
A. Ruszczyński, “QDECOM: The regularized decomposition method. User manual,” Technical Report, Institut für Operations Research, Universität Zürich, Zürich, 1985.
N.Z. Shor,Minimization Methods for Non-Differentiable Functions (Springer-Verlag, Berlin, 1985).
D.M. Topkis, “A cutting-plane algorithm with linear and geometric rates of convergence,”Journal of Optimization Theory and Applications 36 (1982) 1–22.
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.
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.
R.J.-B. Wets, “Large scale linear programming techniques in stochastic programming,” WP-84-90, IIASA, Laxenburg, 1984.
P. Wolfe, “A method of conjugate subgradients for minimizing nondifferentiable functions,”Mathematical Programming Study 3 (1975) 145–173.
P. Wolfe, “Finding the nearest point in a polytope,”Mathematical Programming 11 (1976) 128–149.
Author information
Authors and Affiliations
Additional information
On leave from Instytut Automatyki, Politechnika Warszawska, Poland.
Rights and permissions
About this article
Cite this article
Ruszczyński, A. A regularized decomposition method for minimizing a sum of polyhedral functions. Mathematical Programming 35, 309–333 (1986). https://doi.org/10.1007/BF01580883
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01580883