Skip to main content
SpringerLink
Log in

Generating and measuring instances of hard semidefinite programs

  • FULL LENGTH PAPER
  • Series A
  • Published:
Mathematical Programming Submit manuscript

Abstract

Linear Programming, LP, problems with finite optimal value have a zero duality gap and a primal–dual strictly complementary optimal solution pair. On the other hand, there exist Semidefinite Programming, SDP, problems which have a nonzero duality gap (different primal and dual optimal values; not both infinite). The duality gap is assured to be zero if a constraint qualification, e.g., Slater’s condition (strict feasibility) holds. Measures of strict feasibility, also called distance to infeasibility, have been used in complexity analysis, and, it is known that (near) loss of strict feasibility results in numerical difficulties. In addition, there exist SDP problems which have a zero duality gap but no strict complementary primal–dual optimal solution. We refer to these problems as hard instances of SDP. The assumption of strict complementarity is essential for asymptotic superlinear and quadratic rate convergence proofs. In this paper, we introduce a procedure for generating hard instances of SDP with a specified complementarity nullity (the dimension of the common nullspace of primal–dual optimal pairs). We then show, empirically, that the complementarity nullity correlates well with the observed local convergence rate and the number of iterations required to obtain optimal solutions to a specified accuracy, i.e., we show, even when Slater’s condition holds, that the loss of strict complementarity results in numerical difficulties. We include two new measures of hardness that correlate well with the complementarity nullity.

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. Alizadeh F., Haeberly J.-P.A., Overton M.L.: Primal–dual interior-point methods for semidefinite programming: convergence rates, stability and numerical results. SIAM J. Optim. 8, 746–768 (1998)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  3. Borwein J.M., Wolkowicz H.: Regularizing the abstract convex program. J. Math. Anal. Appl. 83(2), 495–530 (1981)

    Article  MATH  MathSciNet  Google Scholar 

  4. de Klerk E., Roos C., Terlaky T.: Initialization in semidefinite programming via a self-dual skew-symmetric embedding. Oper. Res. Lett. 20(5), 213–221 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  5. Ordóñez F., Ordóñez F., Toh K.C.: Behavioral measures and their correlation with IPM iteration counts on semi-definite programming problems. Math. Program., Ser. A and B 109(2), 445–475 (2007) ISSN:0025-5610

    Article  Google Scholar 

  6. Freund R.M., Vera J.R.: Condition-based complexity of convex optimization in conic linear form via the ellipsoid algorithm. SIAM J. Optim. 10(1), 155–176 (1999) (electronic)

    Article  MATH  MathSciNet  Google Scholar 

  7. Goldfarb D., Scheinberg K.: Interior point trajectories in semidefinite programming. SIAM J. Optim. 8(4), 871–886 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  8. Halická M., de Klerk E., Roos C.: On the convergence of the central path in semidefinite optimization. SIAM J. Optim. 12(4), 1090–1099 (2002) (electronic)

    Article  MATH  MathSciNet  Google Scholar 

  9. Hansen P.C., Yalamov P.Y.: Computing symmetric rank-revealing decompositions via triangular factorization. SIAM J. Matrix Anal. Appl. 23(2), 443–458 (2001) (electronic)

    Article  MATH  MathSciNet  Google Scholar 

  10. Ji J., Potra F.A., Sheng R.: On the local convergence of a predictor-corrector method for semidefinite programming. SIAM J. Optim. 10(1), 195–210 (1999) (electronic)

    Article  MATH  MathSciNet  Google Scholar 

  11. Kojima M., Shida M., Shindoh S.: Local convergence of predictor-corrector infeasible-interior-point algorithms for SDPs and SDLCPs. Technical report, Dept. of Information Sciences, Tokyo Institute of Technology, Tokyo, Japan (1996)

    Google Scholar 

  12. Luo Z.-Q., Sturm J.F., Zhang S.: Superlinear convergence of a symmetric primal–dual path-following algorithm for semidefinite programming. SIAM J. Optim. 8, 59–81 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  13. Marshall A.W., Olkin I.: Inequalities: Theory of Majorization and its Applications. Academic Press, New York, NY (1979)

    MATH  Google Scholar 

  14. Potra F.A., Sheng R.: Superlinear convergence of a predictor-corrector method for semidefinite programming without shrinking central path neighborhood. Bull. Math. Soc. Sci. Math. Roumanie (N.S.) 43(91(2), 107–124 (2000)

    MathSciNet  Google Scholar 

  15. Renegar J.: Some perturbation theory for linear programming. Math. Program., Ser. A 65(1), 73–91 (1994)

    Article  MathSciNet  Google Scholar 

  16. Renegar J.: Linear programming, complexity theory and elementary functional analysis. Math. Program., Ser. A 70(3), 279–351 (1995)

    Article  MathSciNet  Google Scholar 

  17. Stewart G.W.: Updating a rank-revealing ULV decomposition. SIAM J. Matrix Anal. Appl. 14(2), 494–499 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  18. Sturm J.F.: Using SeDuMi 1.02, a MATLAB toolbox for optimization over symmetric cones. Optim. Methods Softw. 11/12(1–4), 625–653 (1999)

    Article  MathSciNet  Google Scholar 

  19. Tütüncü R.H., Toh K.C., Todd M.J.: Solving semidefinite-quadratic-linear programs using SDPT3. Math. Program., Ser. B 95(2), 189–217 (2003) Computational semidefinite and second order cone programming: the state of the art

    Article  MATH  Google Scholar 

  20. Wolkowicz H.: Solving semidefinite programs using preconditioned conjugate gradients. Optim. Methods Softw. 19(6), 653–672 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  21. Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook Of Semidefinite Programming: Theory, Algorithms, and Applications, xxvi+654 p. Kluwer Academic Publishers, Boston, MA (2000)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Combinatorics and Optimization, University of Waterloo, Waterloo, ON, N2L 3G1, Canada

    Hua Wei & Henry Wolkowicz

Authors
  1. Hua Wei
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Henry Wolkowicz
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Henry Wolkowicz.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wei, H., Wolkowicz, H. Generating and measuring instances of hard semidefinite programs. Math. Program. 125, 31–45 (2010). https://doi.org/10.1007/s10107-008-0256-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-008-0256-3

Keywords

Mathematics Subject Classification (2000)

Search

Navigation