A primal-dual symmetric relaxation for homogeneous conic systems

We address the feasibility (existence of non-trivial solutions) of the pair of alternative conic systems of constraintsAx = 0, x ∈ Cand- A^T y ∈ C^*,where A ∈ R^{m ×n}, m < n, is a full row-rank matrix, and C ⊆ Rⁿ is a closed convex cone. To this end, we reformulate the above pair of conic systems as a primal-dual pair of conic programs. Each of the conic programs corresponds to a natural relaxation of each of the two conic systems. When C is a self-scaled cone with a known self-scaled barrier, the conic programming reformulation can be solved via an interior-point algorithm. For a well-posed instance A, a strict solution to one of the two original conic systems can be obtained in O (sqrt(ν_C) log (ν_C C (A)) interior-point iterations. Here ν_C is the complexity parameter of the self-scaled barrier of C and C (A) is Renegar's condition number of A. A central feature of our approach is the conditioning of the system of equations that arise at each interior-point iteration. The condition number of such system of equations grows in a controlled manner and remains bounded by a constant factor of C (A)² throughout the entire algorithm. © 2007 Elsevier Inc. All rights reserved.