Strong duality and minimal representations for cone optimization
The 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
If 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.
As the access to this document is restricted, you may want to look for a different version under "Related research" (further below) or search for a different version of it.
Volume (Year): 53 (2012)
Issue (Month): 2 (October)
|Contact details of provider:|| Web page: http://www.springer.com/math/journal/10589|
|Order Information:||Web: http://link.springer.de/orders.htm|
References listed on IDEAS
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.:
- Helmberg, C., 2002. "Semidefinite programming," European Journal of Operational Research, Elsevier, vol. 137(3), pages 461-482, March.
- Halická, M. & de Klerk, E. & Roos, C., 2002. "On the convergence of the central path in semidefinite optimization," Other publications TiSEM 9ca12b89-1208-46aa-8d70-4, Tilburg University, School of Economics and Management.
- 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.
When requesting a correction, please mention this item's handle: RePEc:spr:coopap:v:53:y:2012:i:2:p:619-648. See general information about how to correct material in RePEc.
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.