Complexity of an Algorithm for Finding an Approximate Solution of a Semi-Definite Program, with no Regularity Condition

Robert M. Freund

A semi-definite program (SDP) is an optimization problem of the form minimize C * X subject to Ai * X = bi , i = 1 , . . . , m , where the variable X is a matrix in Rnxn and X is restricted to be a symmetric and positive semi-definite matrix ( X > 0 ) , and " * " denotes the inner product on matrices. When an SDP problem satisfies a regularity condition (akin to the Slater condition) on the primal and the dual, it is well-known that interior-point methodologies in linear programming yield theoretically and practically efficient algorithms for SDP. However, a non-regular SDP problem can be poorly behaved, even having a finite duality gap whether or not the primal and/or the dual program attain their optima. We examine the complexity of finding approximate solutions to instances of SDP in the absence of any regularity condition, by an algorithm that is an extension and generalization of infeasible-interior-point path-following algorithms. Our main results, Theorem 6.1 and Theorem 6.2, give complexity bounds on the number of Newton steps needed by the algorithm to find an approximate solution to any instance of SDP, with no regularity assumption. These bounds depend on the desired feasibility and optimality tolerances, the initial feasibility and optimality gaps, the size n of the variable matrix X , and two (relative) condition numbers d1 and d2 . The condition numbers d1 and d2 depend on the problem instance and are measured using a norm induced by the starting point of the algorithm, and so are relative to the initial starting point. When a regularity condition is satisfied, then the algorithm and the bounds obtained specialize to the best complexity bounds known for (well-behaved) instances of SDP. The paper is available by sending a request to rfreund@MIT.EDU

[IP PAGE] [SEARCH AGAIN]