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

Contact: e.deklerk@twi.tudelft.nl