Semidefinite Programs whithout feasible interior points

G. Gruber, F. Rendl

Many theoretical and algorithmic results in Semidefinite Programming are based on the assumption that Slater's constraint qualification is satisfied for the primal and the associated dual problem. We consider semidefinite problems with zero duality gap for which Slaters condition fails for at least one of the primal and dual problem. We propose a numerically feasible way of dealing with such semidefinite programs. The new method is based on a standard search direction with damped Newton steps towards primal and dual feasibility.

University of Klagenfurt