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
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|
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.:
- 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.
- 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.
- Helmberg, C., 2002. "Semidefinite programming," European Journal of Operational Research, Elsevier, vol. 137(3), pages 461-482, March.
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: (Sonal Shukla)or (Christopher F Baum)
If references are entirely missing, you can add them using this form.