Skip to main content
SpringerLink
Log in

New stopping criteria for detecting infeasibility in conic optimization

  • Original Paper
  • Published:
Optimization Letters Aims and scope Submit manuscript

Abstract

Detecting infeasibility in conic optimization and providing certificates for infeasibility pose a bigger challenge than in the linear case due to the lack of strong duality. In this paper we generalize the approximate Farkas lemma of Todd and Ye (Math Program 81:1–22, 1998) from the linear to the general conic setting, and use it to propose stopping criteria for interior point algorithms using self-dual embedding. The new criteria can identify if the solutions have large norm, thus they give an indication of infeasibility. The modified algorithms enjoy the same complexity bounds as the original ones, without assuming that the problem is feasible. Issues about the practical application of the criteria are also discussed.

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: Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization. SIAM, Philadelphia (2001)

  2. Borchers B.: SDPLIB 1.2, a library of semidefinite programming test problems. Optim. Methods Softw. 11(1), 683–690 (1999)

    Article  MathSciNet  Google Scholar 

  3. Güler O., Tunçel L.: Characterization of the barrier parameter of homogeneous convex cones. Math. Program. 81, 55–76 (1998)

    Article  Google Scholar 

  4. de Klerk, E., Roos, C., Terlaky, T.: Infeasible-start semidefinite programming algorithms via self-dual embeddings. In: Pardalos, P., Wolkowicz, H. (eds.) Topics in Semidefinite and Interior Point Methods, Fields Institute Communications, vol. 18, pp. 215–236. AMS, Providence (1998)

  5. Luo, Z.Q., Sturn, J.F., Zhang, S.: Duality and self-duality for conic convex programming. Report 9620/A, Econometric Institute, Erasmus University, The Netherlands (1996)

  6. Luo, Z.Q., Sturn, J.F., Zhang, S.: Duality results for conic convex programming. Report 9719/A, Econometric Institute, Erasmus University, The Netherlands (1997)

  7. Luo Z.Q., Sturn J.F., Zhang S.: Conic convex programming and self-dual embedding. Optim. Methods Softw. 14, 169–218 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  8. Nesterov Y., Nemirovski A.: Interior-Point Polynomial Algorithms in Convex Programming. SIAM, Philadelphia (1994)

    MATH  Google Scholar 

  9. Pataki, G., Schmieta, S.: The DIMACS library of semidefinite-quadratic-linear programs. Preliminary draft, Columbia University, Computational Optimization Research Center (2002)

  10. Renegar, J.: A Mathematical View of Interior-Point Methods in Convex Optimization. MPS/SIAM series on optimization. SIAM, Philadelphia (2001)

  11. Sturm, J.F.: Primal–dual interior point approach to semidefinite programming. Ph.D. thesis, Tinbergen Institute Research Series, vol. 156, Erasmus University (1997)

  12. Todd M.J., Ye Y.: Approximate Farkas lemmas and stopping rules for iterative infeasible-point algorithms for linear programming. Math. Program. 81, 1–22 (1998)

    MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, USA

    Imre Pólik & Tamás Terlaky

Authors
  1. Imre Pólik
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tamás Terlaky
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Imre Pólik.

Additional information

The authors were supported by the Canada Research Chairs program, NSERC Discovery Grant #5-48923 and MITACS.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Pólik, I., Terlaky, T. New stopping criteria for detecting infeasibility in conic optimization. Optim Lett 3, 187–198 (2009). https://doi.org/10.1007/s11590-008-0100-y

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11590-008-0100-y

Keywords

Search

Navigation