Optimization Online


Invariance and efficiency of convex representations

Chek Beng Chua (cbchua***at***math.uwaterloo.ca)
Levent Tuncel (ltuncel***at***math.uwaterloo.ca)

Abstract: We consider two notions for the representations of convex cones: $G$-representation and lifted-$G$-representation. The former represents a convex cone as a slice of another; the latter allows in addition, the usage of auxiliary variables in the representation. We first study the basic properties of these representations. We show that some basic properties of convex cones are invariant under one notion of representation but not the other. In particular, we prove that lifted-$G$-representation is closed under duality when the representing cone is self-dual. We also prove that strict complementarity of a convex optimization problem in conic form is preserved under $G$-representations. Then we move to study efficiency measures for representations. We evaluate the representations of homogeneous convex cones based on the ``smoothness'' of the transformations mapping the central path of the representation to the central path of the represented optimization problem.

Keywords: convex optimization, semidefinite programming, semidefinite representations, interior-point methods, central path, weighted central path, homogeneous cones, duality theory, strict complementarity

Category 1: Linear, Cone and Semidefinite Programming

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Research Report CORR 2004-18, Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, Ontario, Canada, June 2004.

Download: [Postscript][PDF]

Entry Submitted: 06/29/2004
Entry Accepted: 06/29/2004
Entry Last Modified: 06/29/2004

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society