zbMATH — the first resource for mathematics

Minimum principle sufficiency. (English) Zbl 0760.90076
The authors study the determination of a solution of a convex program by minimizing over the feasible region a linearized form of the objective function at any of its solution points (Minimum Principle Sufficiency, shortly MPS). Thus, for the case of a monotone linear complementarity problem the MPS property is equivalent to the existence of a nondegenerate solution to the problem. For the case of a convex quadratic program, the MPS property is equivalent to the span of the Hessian of the objective function being contained in the normal cone to the feasible region at any solution point, plus the cone generated by the gradient of the objective function at any solution point. This in turn is equivalent to the quadratic program having a weak sharp minimum. An important application of the MPS property is that minimizing on the feasible region a linearization of the objective function at a point in a neighborhood of a solution point gives an exact solution of the convex program.

90C25 Convex programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
Full Text: DOI
[1] F.A. Al-Khayyal and J. Kyparisis, ”Finite convergence of algorithms for nonlinear programs and variational inequalities,” to appear in:Journal of Optimization Theory and Applications. · Zbl 0732.90076
[2] D.P. Bertsekas, ”Necessary and sufficient conditions for a penalty method to be exact,”Mathematical Programming 9 (1975) 8–99. · Zbl 0325.90055 · doi:10.1007/BF01681332
[3] J.V. Burke and M.C. Ferris, ”The sharpness of functions on sets,” in preparation (1991). · Zbl 0719.90055
[4] P.H. Calamai and J.J. Moré, ”Projected gradient methods for linearly constrained problems,”Mathematical Programming 39 (1987) 93–116. · Zbl 0634.90064 · doi:10.1007/BF02592073
[5] J.C. Dunn, ”On the convergence of projected gradient processes to singular critical points,”Journal of Optimization Theory and Applications 55 (1987) 203–216. · Zbl 0616.90060 · doi:10.1007/BF00939081
[6] M.C. Ferris, ”Finite termination of the proximal point algorithm,”Mathematical Programming 50 (1991) 359–366. · Zbl 0741.90051 · doi:10.1007/BF01594944
[7] M.C. Ferris, ”Weak sharp minima and penalty functions in mathematical programming,” Technical Report 779, Computer Sciences Department, University of Wisconsin (Madison, WI, 1988).
[8] A.J. Goldman and A.W. Tucker, ”Theory of linear programming,” in: H.W. Kuhn, and A.W. Tucker, eds.,Linear Inequalities and Related Systems (Princeton University Press, Princeton, NJ. 1956) pp. 53–97. · Zbl 0072.37601
[9] O.L. Mangasarian,Nonlinear Programming (McGraw-Hill, New York, 1969).
[10] O.L. Mangasarian, ”Locally unique solutions of quadratic programs, linear and nonlinear complementarity problems,”Mathematical Programming 19 (1980) 200–212. · Zbl 0442.90089 · doi:10.1007/BF01581641
[11] O.L. Mangasarian, ”Optimal simplex tableau characterization of unique and bounded solutions of linear programs,”Journal of Optimization Theory and Applications 35 (1981) 123–128. · Zbl 0438.90050 · doi:10.1007/BF00934707
[12] O.L. Mangasarian, ”A stable theorem of the alternative: an extension of the Gordan theorem,”Linear Algebra and its Applications 41 (1981) 209–223. · Zbl 0488.90044 · doi:10.1016/0024-3795(81)90100-2
[13] O.L. Mangasarian, ”Error bounds for nondegenerate monotone linear complementarity problems,”Mathematical Programming (Series B) 48 (1990) 437–445. · Zbl 0716.90094 · doi:10.1007/BF01582267
[14] O.L. Mangasarian, ”A simple characterization of solution sets of convex programs,”Operations Research Letters 7(1) (1988) 21–26. · Zbl 0653.90055 · doi:10.1016/0167-6377(88)90047-8
[15] O.L. Mangasarian and R.R. Meyer, ”Nonlinear perturbation of linear programs,”SIAM Journal on Control and Optimization 17(6) (1979) 745–752. · Zbl 0432.90047 · doi:10.1137/0317052
[16] R.R. Meyer, ”Continuity properties of linear programs,” Technical Report 373, Computer Sciences Department, University of Wisconsin (Madison, WI, 1979). · Zbl 0432.90047
[17] B.T. Polyak,Introduction to Optimization (Optimization Software, Inc., Publications Division, New York, 1987). · Zbl 0708.90083
[18] B.T. Polyak and N.V. Tretiyakov, ”Concerning an iterative method for linear programming and its economic interpretation,”Economics and Mathematical Methods 8(5) (1972) 740–751. [English translation:Matekon 10(3) (1974) 81–100.]
[19] S. M. Robinson, ”Local structure of feasible sets in nonlinear programming, Part II: Nondegeneracy,”Mathematical Programming Study 22 (1984) 217–230. · Zbl 0573.90075
[20] T.-H. Shiau, ”Iterative linear programming for linear complementarity and related problems,” Technical Report 507, Computer Sciences Department, University of Wisconsin (Madison, WI, 1983).
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.