Generic Optimality Conditions for Semialgebraic Convex Programs

• 成果类型: Article
• 署名作者: Bolte, Jerome; Daniilidis, Aris; Lewis, Adrian S.
• 署名单位: Universite de Toulouse; Universite Toulouse 1 Capitole; Toulouse School of Economics; Autonomous University of Barcelona; Cornell University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.1110.0481
• 发表日期: 2011
• 页码: 55-70
• 关键词: proximal point algorithm; constraint nondegeneracy; active constraints; optimization; sets

摘要

We consider linear optimization over a nonempty convex semialgebraic feasible region F. Semidefinite programming is an example. If F is compact, then for almost every linear objective there is a unique optimal solution, lying on a unique active manifold, around which F is partly smooth, and the second-order sufficient conditions hold. Perturbing the objective results in smooth variation of the optimal solution. The active manifold consists, locally, of these perturbed optimal solutions; it is independent of the representation of F and is eventually identified by a variety of iterative algorithms such as proximal and projected gradient schemes. These results extend to unbounded sets F