|
Description: |
Polynomial complexity of interior-point methods (IPMs), as well as their practical efficiency have made them the methods of choice for solving a vast number of optimization problems. The first polynomial-time IPM was introduced by Karmarkar for Linear Programming, and later Nesterov and Nemirovski extended the applicability of IPMs to nonlinear problems. Since then, the theory of interior-point methods has advanced even further, and commercial software packages for solving different types of convex conic problems were developed. In particular, interior-point methods can be used to solve convex conic feasibility problems. Such problems consist of deciding whether a solution of a linear system exists on a convex cone. Using a relaxation scheme introduced by Pe\~na and Renegar, the feasibility problem can be reformulated as an optimization one, and then solved by an IPM. However, there are problems with ill-posed data, and solving them numerically is very hard or even impossible. The ``badness'' of data can be characterized by Renegar's condition number, and the explicit bounds on the number of iterations and the finest precision can be expressed in terms of this condition number. The essential ingredients of such complexity analysis for Linear Programming and Second Order Conic feasibility problems will be discussed in this talk.
|
