A primal-dual symmetric relaxation for homogeneous conic systems

We address the feasibility of the pair of alternative conic systems of constraints Ax = 0, x \in C, and -A^T y \in C^*, defined by an m by n matrix A and a cone C in the n-dimensional Euclidean space. We reformulate this 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 interior-point methods. For a well-posed instance A, a strict solution to one of the two original conic systems can be obtained in a number of interior-point iterations proporcional to Renegar's condition number of the matrix A, namely, the reciprocal of the relative distance from A to the set of ill-posed instances.

Article

Download

View A primal-dual symmetric relaxation for homogeneous conic systems