##
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