Skip to main content
SpringerLink
Log in

Invariance and efficiency of convex representations

  • FULL LENGTH PAPER
  • Published:
Mathematical Programming Submit manuscript

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2001)

  2. Braams, B.J.: Dual descriptions of semidefinite and other non-polyhedral cones. Manuscript, September (2002)

  3. Chua, C.B.: A new notion of weighted centers for semidefinite programming. SIAM J. Optim. (in press)

  4. Chua C.B. (2004). Relating homogeneous cones and positive definite cones via T-algebras. SIAM J. Optim. 14: 500–506

    Article  MathSciNet  Google Scholar 

  5. Chua, C.B.: An algebraic perspective on homogeneous cone programming, and the primal–dual second order cone approximations algorithm for symmetric cone programming. Ph.D. Thesis, Cornell University, May 2003

  6. Faraut J. and Korányi A. (1994). Analysis on Symmetric Cones. Oxford University Press, New York

    MATH  Google Scholar 

  7. Faybusovich L. (2002). On Nesterov’s approach to semi-infinite programming. Acta Appl. Math 74: 195–215

    Article  MATH  MathSciNet  Google Scholar 

  8. Güler O. (1997). Hyperbolic polynomials and interior point methods for convex programming. Math. Oper. Res. 22: 350–377

    MATH  MathSciNet  Google Scholar 

  9. Helton, J.W., Vinnikov, V.: Linear matrix inequality representation of sets. Technical Report (2002)

  10. Lewis A.S., Parrilo P.A. and Ramana M.V. (2005). The Lax conjecture is true. Proc. Amer. Math. Soc. 133: 2495–2499

    Article  MATH  MathSciNet  Google Scholar 

  11. Monteiro R.D.C. and Tsuchiya T. (1999). Polynomial convergence of a new family of primal-dual algorithms for semidefinite programming. SIAM J. Optim. 9: 551–577

    Article  MATH  MathSciNet  Google Scholar 

  12. Monteiro R.D.C. and Zanjácomo P. (2000). General interior-point maps and existence of weighted paths for nonlinear semidefinite complementarity problems. Math. Oper. Res. 25: 381–399

    Article  MATH  MathSciNet  Google Scholar 

  13. Monteiro R.D.C. and Zanjácomo P. (1999). Implementation of primal-dual methods for semidefinite programming based on Monteiro and Tsuchiya Newton directions and their variants. Optim. Method. Soft. 11/12: 91–140

    Google Scholar 

  14. Nesterov Yu.E. and Nemirovskii A.S. (1994). Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia, PA

    MATH  Google Scholar 

  15. Nesterov Yu.E. and Todd M.J. (1997). Self-scaled barriers and interior-point methods for convex programming. Math. Oper. Res. 22: 1–46

    Article  MATH  MathSciNet  Google Scholar 

  16. Pataki, G.: Cone LP’s and semidefinite programs: Geometry and a simplex type method. In: Cunningham, W.H., McCormick, S.T., Queyranne, M. Proceedings of the Fifth IPCO Conference, (eds.) pp. 161–174. Springer, Berlin Heidelberg New York (1996)

  17. Renegar J. (2006). Hyperbolic programs and their derivative relaxations. Found. Comput. Math. 6: 59–79

    Article  MATH  MathSciNet  Google Scholar 

  18. Rockafellar R.T. (1970). Convex Analysis. Princeton University Press, Princeton

    MATH  Google Scholar 

  19. Truong V.A. and Tunçel L. (2004). Geometry of homogeneous convex cones, duality mapping and optimal self-concordant barriers. Math. Prog. A 100: 295–316

    Article  MATH  Google Scholar 

  20. Tunçel L. and Wolkowicz H (2005). Strengthened existence and uniqueness conditions for search directions in semidefinite programming. Linear Algebra Appl. 400: 31–60

    Article  MATH  MathSciNet  Google Scholar 

  21. Tunçel L. and Xu S. (2001). On homogeneous convex cones, the Carathéodory number and the duality mapping. Math. Oper. Res. 26: 234–247

    Article  MATH  MathSciNet  Google Scholar 

  22. Vinberg È.B. (1965). The theory of homogeneous cones. Trans. Moscow Math. Soc. 12: 340–403

    Google Scholar 

  23. Vinnikov V. (1993). Self-adjoint determinantal representations of real plane curves. Math. Ann. 296: 453–479

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Combinatorics and Optimization, Faculty of Mathematics, University of Waterloo, Waterloo, ON N2L 3G1, Canada

    Chek Beng Chua & Levent Tunçel

Authors
  1. Chek Beng Chua
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Levent Tunçel
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Levent Tunçel.

Additional information

Dedicated to Clovis Gonzaga on the occasion of his 60th birthday.

Research of the first author was supported in part by a grant from the Faculty of Mathematics, University of Waterloo and by a Discovery Grant from NSERC. Research of the second author was supported in part by a Discovery Grant from NSERC and a PREA from Ontario, Canada.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Chua, C.B., Tunçel, L. Invariance and efficiency of convex representations. Math. Program. 111, 113–140 (2008). https://doi.org/10.1007/s10107-006-0072-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-006-0072-6

Keywords

Mathematics Subject Classification (2000)

Search

Navigation