A condition number theorem in convex programming

• 成果类型: Article
• 署名作者: Zolezzi, Tullio
• 署名单位: University of Genoa
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-014-0745-5
• 发表日期: 2015
• 页码: 195-207
• 关键词: quadratic optimization; STABILITY

摘要

A finite-dimensional mathematical programming problem with convex data and inequality constraints is considered. A suitable definition of condition number is obtained via canonical perturbations of the given problem, assuming uniqueness of the optimal solutions. The distance among mathematical programming problems is defined as the Lipschitz constant of the difference of the corresponding Kojima functions. It is shown that the distance to ill-conditioning is bounded above and below by suitable multiples of the reciprocal of the condition number, thereby generalizing the classical Eckart-Young theorem. A partial extension to the infinite-dimensional setting is also obtained.