A primal-dual symmetric relaxation for homogeneous conic systems

Juan Vera (jveraandrew.cmu.edu)
Juan Rivera (juanrandrew.cmu.edu)
Javier Pena (jfpandrew.cmu.edu)

Abstract: 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.

Keywords: conic systems, primal-dual methods, interior-point methods

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Citation:

Download: [Postscript][PDF]

Entry Submitted: 04/27/2002
Entry Accepted: 04/29/2002
Entry Last Modified: 04/27/2002

Modify/Update this entry