Infeasible start, semidefinite programming algorithms via self-dual embeddings

E. de Klerk, C. Roos, T. Terlaky

Semidefinite programming (SDP) has a weaker duality theory than linear programming (LP). Pathological problems can occur in the absence of regularity conditions, e.g. positive duality gaps at optimality, finite optimal values which are not attained, etc. In this paper we give a comprehensive treatment of the initialization strategy of self-dual embeddings for SDP. The original problem is embedded in a larger, self-dual SDP problem, which has a known centered starting solution. The embedding problem can therefore be solved using standard interior point SDP algorithms. We show to what extent the status of the original problem can be classified in terms of properties of the embedding problem. In pathological cases, extended Lagrange Slater dual (ELSD) problems are used in the embedding to detect weak infeasibility or determine optimal objective values. Some open problems in this line of research are stated.

Report 97-10, Reports of the Faculty of Technical Mathematics and Computer Science, Delft University of Technology, Delft, The Netherlands