A method of linearizations for linearly constrained nonconvex nonsmooth minimization.(English)Zbl 0596.90078
Summary: A readily implementable algorithm is given for minimizing a (possibly nondifferentiable and nonconvex) locally Lipschitz continuous function f subject to linear constraints. At each iteration a polyhedral approximation to f is constructed from a few previously computed subgradients and an aggregate subgradient, which accumulates the past subgradient information. This approximation and the linear constraints generate constraints in the search direction finding subproblem that is a quadratic programming problem. Then a stepsize is found by an approximate line search. All the algorithm’s accumulation points are stationary. Moreover, the algorithm converges when f happens to be convex.
MSC:
| 90C30 | Nonlinear programming |
| 49M37 | Numerical methods based on nonlinear programming |
| 65K05 | Numerical mathematical programming methods |
| 90C25 | Convex programming |
| 90C55 | Methods of successive quadratic programming type |
Keywords:
nonsmooth optimization;nondifferentiable programming;descent;methods;locally Lipschitz continuous function;linear constraints;polyhedral approximation;subgradientsCite
Full Text:DOI
References:
| [1] | A. Bihain, ”Optimization of upper-semidifferentiable functions”,Journal of Optimization Theory and Applications 44 (1984) 545–568. ·Zbl 0534.90069 ·doi:10.1007/BF00938396 |
| [2] | F.H. Clarke,Optimization and nonsmooth analysis (Wiley-Interscience, New York, 1983). ·Zbl 0582.49001 |
| [3] | G.B. Dantzig,Linear programming and extensions (Princeton University Press, Princeton, New Jersey, 1963). |
| [4] | K.C. Kiwiel, ”An aggregate subgradient method for nonsmooth convex minimization”,Mathematical Programming 27 (1983) 320–341. ·Zbl 0525.90074 ·doi:10.1007/BF02591907 |
| [5] | K.C. Kiwiel, ”A linearization algorithm for constrained nonsmooth minimization”, in: P. Thoft-Christensen, ed.,System modelling and optimization, Lecture Notes in Control and Information Sciences 59 (Springer-Verlag, Berlin, 1984) pp. 311–320. |
| [6] | K.C. Kiwiel, ”An algorithm for linearly constrained convex nondifferentiable minimization problems”,Journal of Mathematical Analysis and Applications 105 (1985) 111–119. ·Zbl 0564.90053 ·doi:10.1016/0022-247X(85)90061-7 |
| [7] | K.C. Kiwiel,Methods of descent for nondifferentiable optimization, Lecture Notes in Mathematics 1133 (Springer-Verlag, Berlin, 1985). ·Zbl 0561.90059 |
| [8] | K.C. Kiwiel, ”A linearization algorithm for nonsmooth minimization”,Mathematics of Operations Research 10 (1985) 185–194. ·Zbl 0565.90063 ·doi:10.1287/moor.10.2.185 |
| [9] | K.C. Kiwiel, ”A method for minimizing the sum of a convex function and a continuously differentiable function”,Journal of Optimization Theory and Applications, to appear. ·Zbl 0562.90073 |
| [10] | K.C. Kiwiel, ”A method for solving certain quadratic programming problems arising in nonsmooth optimization”,IMA Journal of Numerical Analysis, to appear. |
| [11] | C. Lemarechal, ”Numerical experiments in nonsmooth optimization”, in: E.A. Nurminski, ed.,Progress in nonsmooth optimization, CP-82-S8 (International Institute for Applied Systems Analysis, Laxenburg, Austria, 1982) pp. 61–84. |
| [12] | C. Lemaréchal and R. Mifflin, eds.,Nonsmooth optimization (Pergamon Press, Oxford, 1978). ·Zbl 0398.90090 |
| [13] | C. Lemaréchal, J.-J. Strodiot and A. Bihain, ”On a bundle algorithm for nonsmooth minimization”, in: O.L. Mangasarian, R.R. Meyer and S.M. Robinson, eds.,Nonlinear programming 4 (Academic Press, New York, 1981) pp. 245–281. ·Zbl 0533.49023 |
| [14] | K. Madsen and J. Schjaer-Jacobsen, ”Linearly constrained minimax optimization”,Mathematical Programming 14 (1978) 208–223. ·Zbl 0375.65034 ·doi:10.1007/BF01588966 |
| [15] | R. Mifflin, ”An algorithm for constrained optimization with semismooth functions”,Mathematics of Operations Research 2 (1977) 191–207. ·Zbl 0395.90069 ·doi:10.1287/moor.2.2.191 |
| [16] | R. Mifflin, ”A modification and an extension of Lemaréchal’s algorithm for nonsmooth minimization”,Mathematical Programming Study 17 (1982) 77–90. ·Zbl 0476.65047 |
| [17] | E. Polak, D.Q. Mayne and Y. Wardi, ”On the extension of constrained optimization algorithms from differentiable to nondifferentiable problems”,SIAM Journal on Control and Optimization 21 (1983) 179–203. ·Zbl 0503.49021 ·doi:10.1137/0321010 |
| [18] | R.T. Rockafellar,Convex analysis (Princeton University Press, Princeton, New Jersey,. 1970). ·Zbl 0193.18401 |
| [19] | J.-J. Strodiot, V. Hien Nguyen and N. Heukems, ”{\(\epsilon\)}-Optimal solutions in nondifferentiable convex programming and related questions”,Mathematical Programming 25 (1982) 307–328. ·Zbl 0495.90067 ·doi:10.1007/BF02594782 |
| [20] | J.-J. Strodiot and V. Hien Nguyen, ”An algorithm for minimizing nondifferentiable convex functions under linear constraints”, in: P. Thoft-Christensen, ed.,System modelling and optimization, Lecture Notes in Control and Information Sciences 59 (Springer-Verlag, Berlin, 1984) pp. 338–344. ·Zbl 0551.90075 |
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.
