zbMATH — the first resource for mathematics

A simple characterization of solutions sets of convex programs. (English) Zbl 0653.90055
The author shows that for any convex program \(\min_{x\in X}f(x)\), where X is a convex set in R n and f(x) is a convex function on R n, the subdifferential \(\partial f(x)\) is constant on the relative interior of the set \(\bar X=\arg \min_{x\in X}f(x)\) (solution set of the problem) and equals the intersection of the subdifferentials of the function f(x) at all points of \(\bar X.\) In addition, \(\bar X\) lies in the intersection with the feasible set X of an affine subspace orthogonal to some subgradient of f(x) at a relative interior point of \(\bar X.\) As a consequence a simple polyhedral characterization is given for the solution set of a convex quadratic program and that of a monotone linear complementarity problem.
Reviewer: H.Tuy

90C25 Convex programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C20 Quadratic programming
Full Text: DOI
[1] Adler, I.; Gale, D., On the solutions of the positive semidefinite complementarity problem, ()
[2] Auslender, A., Optimisation Méthodes numériques, (1976), Masson Paris · Zbl 0326.90057
[3] Cottle, R.W.; Dantzig, G.B., Complementary pivot theory in mathematical programming, Linear algebra and its applications, 1, 103-125, (1968) · Zbl 0155.28403
[4] Demyanov, V.F.; Vasilev, L.V., Nondifferentiable optimization, (1987), Optimization Software, Inc New York, (translated from Russian)
[5] Mangasarian, O.L., Nonlinear programming, (1969), McGraw-Hill New York · Zbl 0194.20201
[6] Mangasarian, O.L., Characterization of bounded solutions of linear complementarity problems, Mathematical programming study, 19, 153-166, (1982) · Zbl 0487.90088
[7] Mangasarian, O.L.; Shiau, T.-S., Error bounds for monotone linear complementarity problems, Mathematical programming, 36, 81-89, (1986) · Zbl 0613.90095
[8] Polyak, B.T., Introduction to optimization, (1987), Optimization Software, Inc New York, (translated from Russian) · Zbl 0652.49002
[9] Rockafeller, R.T., Convex analysis, (1970), Princeton University Press Princeton, NJ
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.