Condition-measure bounds on the behavior of the central trajectory of a semidefinite program

作     者：Nunez, MA Freund, RM 

作者机构：Chapman Univ Argyros Sch Business & Econ Orange CA 92866 USA MIT Alfred P Sloan Sch Management Cambridge MA 02139 USA 

出 版 物：《SIAM JOURNAL ON OPTIMIZATION》 (工业与应用数学会最优化杂志)

年 卷 期：2001年第11卷第3期

页      面：818-836页

核心收录：

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：semidefinite programming perturbation of convex programs central trajectory interior-point methods ill-posed problems condition numbers 

摘      要：We present bounds on various quantities of interest regarding the central trajectory of a semidefinite program, where the bounds are functions of Renegar s condition number C(d) and other naturally occurring quantities such as the dimensions n and m. The condition number C ( d) is defined in terms of the data instance d = (A,b,C) for a semidefinite program;it is the inverse of a relative measure of the distance of the data instance to the set of ill-posed data instances, that is, data instances for which arbitrary perturbations would make the corresponding semidefinite program either feasible or infeasible. We provide upper and lower bounds on the solutions along the central trajectory, and upper bounds on changes in solutions and objective function values along the central trajectory when the data instance is perturbed and/or when the path parameter defining the central trajectory is changed. Based on these bounds, we prove that the solutions along the central trajectory grow at most linearly and at a rate proportional to the inverse of the distance to ill-posedness, and grow at least linearly and at a rate proportional to the inverse of C(d)(2), as the trajectory approaches an optimal solution to the semidefinite program. Furthermore, the change in solutions and in objective function values along the central trajectory is at most linear in the size of the changes in the data. All such bounds involve polynomial functions of C (d), the size of the data, the distance to ill-posedness of the data, and the dimensions n and m of the semidefinite program.