Skip to main content
SpringerLink
Log in

Computational Experience with Ill-Posed Problems in Semidefinite Programming

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

Many theoretical and algorithmic results in semidefinite programming are based on the assumption that Slater's constraint qualification is satisfied for the primal and the associated dual problem. We consider semidefinite problems with zero duality gap for which Slater's condition fails for at least one of the primal and dual problem. We propose a numerically reasonable way of dealing with such semidefinite programs. The new method is based on a standard search direction with damped Newton steps towards primal and dual feasibility.

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. F. Alizadeh, “Interior point methods in semidefinite programming with applications to combinatorial optimization,” SIAM Journal on Optimization, vol. 5, no. 1, pp. 13–51, 1995.

    Google Scholar 

  2. F. Alizadeh, J-P.A. Haeberly, and M.L. Overton, “Primal-dual interior-point methods for semidefinite programming: Convergence rates, stability and numerical results,” SIAM Journal on Optimization, vol. 8, no. 3, pp. 746–768, 1998.

    Google Scholar 

  3. A. Ben-Israel, A. Charnes, and K. Kortanek, “Duality and asymptotic solvability over cones,” Bulletin of American Mathematical Society, vol. 75, no. 2, pp. 318–324, 1969.

    Google Scholar 

  4. E. de Klerk, C. Roos, and T. Terlaky, “Infeasible-start semidefinite programming algorithms via self-dual embeddings,” in Topics in Semidefinite and Interior-Point Methods. vol. 18: The Fields Institute for Research in Mathematical Sciences, Communications Series, Providence, Rhode Island, 1998. American Mathematical Society, pp. 215–236.

    Google Scholar 

  5. M.X. Goemans and D.P. Williamson, “.878-approximation algorithms for MAX CUT and MAX 2SAT,” in Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, pages 422–431, Montréal, Québec, Canada, 1994, pp. 422–431.

  6. M.X. Goemans and D.P. Williamson, “Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming,” Journal of the ACM, vol. 42, no. 6, pp. 1115–1145, 1995. preliminary version, see [5].

    Google Scholar 

  7. G. Gruber, “On Semidefinite Programming and Applications in Combinatorial Optimization,” PhD Thesis, University of Technology, Graz, Austria, 2000. Shaker Verlag: Aachen—Maastricht, ISBN 3-8265-7541-5.

    Google Scholar 

  8. C. Helmberg, F. Rendl, R.J. Vanderbei, and H. Wolkowicz, “An interior point method for semidefinite programming,” SIAM Journal on Optimization, vol. 6, no. 2, pp. 342–361, 1996.

    Google Scholar 

  9. S.E. Karisch and F. Rendl, “Semidefinite programming and graph equipartition,” in Topics in Semidefinite and Interior-Point Methods. vol. 18: The Fields Institute for Research in Mathematical Sciences, Communications Series, Providence, Rhode Island, 1998. American Mathematical Society, pp. 77–95.

    Google Scholar 

  10. M. Kojima, S. Shindoh, and S. Hara, “Interior point methods for the monotone linear complementarity problem in symmetric matrices,” SIAM Journal on Optimization, vol. 7, no. 1, pp. 86–125, 1997.

    Google Scholar 

  11. R.D.C. Monteiro, “Primal-dual path-following algorithms for semidefinite programming,” SIAM Journal on Optimization, vol. 7, no. 3, pp. 636–678, 1997.

    Google Scholar 

  12. Yu. E. Nesterov and A.S. Nemirovskii, Interior Point Polynomial Algorithms in Convex Programming, SIAM Publications: SIAM, Philadelphia, USA, 1994.

    Google Scholar 

  13. Yu.E. Nesterov and M.J. Todd, “Primal-dual interior-point methods for self-scaled cones,” SIAM Journal on Optimization, vol. 8, no. 2, pp. 324–364, 1998.

    Google Scholar 

  14. F. Rendl, “Semidefinite programming and combinatorial optimization,” Applied Numerical Mathematics, vol. 29, pp. 255–281, 1999.

    Google Scholar 

  15. J.F. Sturm, “Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones,” Optimization Methods and Software, vol. 11, pp. 625–653, 1999.

    Google Scholar 

  16. K.C. Toh, M.J. Todd, and R. Tutuncu, “SDPT3—a matlab software package for semidefinite programming,” Optimization Methods and Software, vol. 11, pp. 545–581, 1999.

    Google Scholar 

  17. L. Vandenberghe and S. Boyd, “Semidefinite programming,” SIAM Review, vol. 38, no. 1, pp. 49–95, 1996.

    Google Scholar 

  18. S.J. Wright, Primal-Dual Interior-Point Methods, Society for Industrial and Applied Mathematics: 3600 University City Science Center, Philadelphia, 1997.

    Google Scholar 

  19. Q. Zhao, S.E. Karisch, F. Rendl, and H. Wolkowicz, “Semidefinite programming relaxations for the quadratic assignment problem,” Journal of Combinatorial Optimization, vol. 2, no. 1, pp. 71–109, 1998.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institut für Mathematik, Universitöt Klagenfurt, Universitötsstraße 65-67, A-9020, Klagenfurt, Austria

    Gerald Gruber & Franz Rendl

Authors
  1. Gerald Gruber
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Franz Rendl
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Gruber, G., Rendl, F. Computational Experience with Ill-Posed Problems in Semidefinite Programming. Computational Optimization and Applications 21, 201–212 (2002). https://doi.org/10.1023/A:1013716917710

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1013716917710

Search

Navigation