Strong duality and minimal representations for cone optimization
AbstractThe elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. In addition, preprocessing is an essential step for efficiency in both simplex type and interior-point methods. However, the theory and preprocessing techniques can fail for cone programming over nonpolyhedral cones. We take a fresh look at known and new results for duality, optimality, constraint qualifications, CQ, and strict complementarity, for linear cone optimization problems in finite dimensions. One theme is the notion of minimal representation of the cone and the constraints. This provides a framework for preprocessing cone optimization problems in order to avoid both the theoretical and numerical difficulties that arise due to the (near) loss of the strong CQ, strict feasibility. We include results and examples on the surprising theoretical connection between duality gaps in the original primal-dual pair and lack of strict complementarity in their homogeneous counterpart. Our emphasis is on results that deal with Semidefinite Programming, SDP. Copyright Springer Science+Business Media, LLC 2012
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by Springer in its journal Computational Optimization and Applications.
Volume (Year): 53 (2012)
Issue (Month): 2 (October)
Contact details of provider:
Web page: http://www.springer.com/math/journal/10589
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Halická, M. & Klerk, E. de & Roos, C., 2002. "On the convergence of the central path in semidefinite optimization," Open Access publications from Tilburg University urn:nbn:nl:ui:12-226112, Tilburg University.
- Jibetean, D. & Laurent, M., 2005. "Semidefinite approximations for global unconstrained polynomial optimization," Open Access publications from Tilburg University urn:nbn:nl:ui:12-3959914, Tilburg University.
- Helmberg, C., 2002. "Semidefinite programming," European Journal of Operational Research, Elsevier, vol. 137(3), pages 461-482, March.
- Maria Gonzalez-Lima & Hua Wei & Henry Wolkowicz, 2009. "A stable primal–dual approach for linear programming under nondegeneracy assumptions," Computational Optimization and Applications, Springer, vol. 44(2), pages 213-247, November.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Guenther Eichhorn) or (Christopher F Baum).
If references are entirely missing, you can add them using this form.