SpringerLink
Log in

A stabilized sequential quadratic semidefinite programming method for degenerate nonlinear semidefinite programs

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

Abstract

In this paper, we propose a new sequential quadratic semidefinite programming (SQSDP) method for solving degenerate nonlinear semidefinite programs (NSDPs), in which we produce iteration points by solving a sequence of stabilized quadratic semidefinite programming (QSDP) subproblems, which we derive from the minimax problem associated with the NSDP. Unlike the existing SQSDP methods, the proposed one allows us to solve those QSDP subproblems inexactly, and each QSDP is feasible. One more remarkable point of the proposed method is that constraint qualifications or boundedness of Lagrange multiplier sequences are not required in the global convergence analysis. Specifically, without assuming such conditions, we prove the global convergence to a point satisfying any of the following: the stationary conditions for the feasibility problem, the approximate-Karush–Kuhn–Tucker (AKKT) conditions, and the trace-AKKT conditions. Finally, we conduct some numerical experiments to examine the efficiency of the proposed method.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (France)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4

Similar content being viewed by others

Data availability

Not applicable.

References

  1. Andreani, R., Fukuda, E.H., Haeser, G., Santos, D.O., Secchin, L.D.: Optimality conditions for nonlinear second-order cone programming and symmetric cone programming. Optimization (2019). http://www.optimization-online.org/DB_HTML/2019/10/7436.html

  2. Andreani, R., Gómez, W., Haeser, G., Mito, L.M., Ramos, A.: On optimality conditions for nonlinear conic programming. Technical report. http://www.optimization-online.org/DB HTML/2020/03/7660.html (2020)

  3. Andreani, R., Haeser, G., Viana, D.S.: Optimality conditions and global convergence for nonlinear semidefinite programming. Math. Program. 180, 203–235 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  4. Boggs, P.T., Tolle, J.W.: Sequential quadratic programming. Acta Numer. 4, 1–51 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  5. Correa, R., Ramírez, H.: A global algorithm for nonlinear semidefinite programming. SIAM J. Optim. 15(1), 303–318 (2004)

    Article  MathSciNet  MATH  Google Scholar 

  6. Fares, B., Noll, D., Apkarian, P.: Robust control via sequential semidefinite programming. SIAM J. Control. Optim. 40(6), 1791–1820 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  7. Freund, R.W., Jarre, F., Vogelbusch, C.H.: Nonlinear semidefinite programming: sensitivity, convergence, and an application in passive reduced-order modeling. Math. Program. Ser. B 109(2–3), 581–611 (2007)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fukuda, E.H., Lourenço, B.F.: Exact augmented Lagrangian functions for nonlinear semidefinite programming. Comput. Optim. Appl. 71(2), 457–482 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  9. Gill, P.E., Kungurtsev, V., Robinson, D.P.: A stabilized SQP method: global convergence. IMA J. Numer. Anal. 37(1), 407–443 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  10. Gill, P.E., Kungurtsev, V., Robinson, D.P.: A stabilized SQP method: superlinear convergence. Math. Program. 163, 369–410 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  11. Gill, P.E., Robinson, D.P.: A globally convergent stabilized SQP method. SIAM J. Optim. 23(4), 1983–2010 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  12. Gómez, W., Ramírez, H.: A filter algorithm for nonlinear semidefinite programming. Comput. Appl. Math. 29(2), 297–328 (2010)

    MathSciNet  MATH  Google Scholar 

  13. Gruber, G., Rendl, F.: Computational experience with ill-posed problems in semidefinite programming. Comput. Optim. Appl. 21, 201–212 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hager, W.W.: Stabilized sequential quadratic programming. Comput. Optim. Appl. 12(1–3), 253–273 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  15. Huang, X.X., Teo, K.L., Yang, X.Q.: Approximate augmented Lagrangian functions and nonlinear semidefinite programs. Acta Math. Sin. Engl. Ser. 22(5), 1283–1296 (2006)

    Article  MathSciNet  MATH  Google Scholar 

  16. Izmailov, A.F., Solodov, M.V.: A truncated SQP method based on inexact interior-point solutions of subproblems. SIAM J. Optim. 20(5), 2584–2613 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  17. Izmailov, A.F., Solodov, M.V., Uskov, E.I.: Combining stabilized SQP with the augmented Lagrangian algorithm. Comput. Optim. Appl. 62(2), 405–429 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  18. Izmailov, A.F., Uskov, E.I.: Subspace-stabilized sequential quadratic programming. Comput. Optim. Appl. 67, 129–154 (2017)

    Article  MathSciNet  MATH  Google Scholar 

  19. Jarre, F.: An interior method for nonconvex semidefinite programs. Optim. Eng. 1(4), 347–372 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  20. Kanzow, C., Nagel, C., Kato, H., Fukushima, M.: Successive linearization methods for nonlinear semidefinite programs. Comput. Optim. Appl. 31(3), 251–273 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  21. Kočvara, M., Stingl, M.: PENNON: a code for convex nonlinear and semidefinite programming. Optim. Methods Softw. 18(3), 317–333 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  22. Leibfritz, F., Mostafa, E.M.E.: An interior point constrained trust region method for a special class of nonlinear semidefinite programming problems. SIAM J. Optim. 12(4), 1048–1074 (2002)

    Article  MathSciNet  MATH  Google Scholar 

  23. Okuno, T.: Local convergence of primal-dual interior point methods for nonlinear semi-definite optimization using the family of Monteiro–Tsuchiya directions. https://arxiv.org/pdf/2009.03020.pdf (2020)

  24. Stingl, M.: On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods. Ph.D. Thesis, Institute of Applied Mathematics II, Friedrich-Alexander University of Erlangen-Nuremberg (2005) (submitted)

  25. Sun, D., Sun, J., Zhang, L.: The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. Math. Program. Ser. A 114(2), 349–391 (2008)

    Article  MathSciNet  MATH  Google Scholar 

  26. Toh, K.C., Todd, M.J., Tütüncü, R.H.: SDPT3—a Matlab software package for semidefinite programming, version 1.3. Optim. Methods Softw. 11(1–4), 545–581 (1999)

  27. 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)

    Article  MathSciNet  MATH  Google Scholar 

  28. Wright, S.J.: Superlinear convergence of a stabilized SQP method to a degenerate solution. Comput. Optim. Appl. 11(3), 253–275 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  29. Wu, H., Luo, H., Ding, X., Chen, G.: Global convergence of modified augmented Lagrangian methods for nonlinear semidefinite programming. Comput. Optim. Appl. 56(3), 531–558 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  30. Yamakawa, Y., Yamashita, N.: A two-step primal-dual interior point method for nonlinear semidefinite programming problems and its superlinear convergence. J. Oper. Res. Soc. Jpn. 57(3–4), 105–127 (2014)

    MathSciNet  MATH  Google Scholar 

  31. Yamakawa, Y., Yamashita, N.: A differentiable merit function for shifted perturbed Karush–Kuhn–Tucker conditions of the nonlinear semidefinite programming. Pac. J. Optim. 11(3), 557–579 (2015)

    MathSciNet  MATH  Google Scholar 

  32. Yamashita, H., Yabe, H.: Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming. Math. Program. Ser. A 132(1–2), 1–30 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  33. Yamashita, H., H, Yabe: A survey of numerical methods for nonlinear semidefinite programming. J. Oper. Res. Soc. Jpn. 58(1), 24–60 (2015)

    MathSciNet  MATH  Google Scholar 

  34. Yamashita, H., Yabe, H., Harada, K.: A primal-dual interior point method for nonlinear semidefinite programming. Math. Program. Ser. A 135(1–2), 89–121 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  35. Yang, L., Yu., B.: A homotopy method for nonlinear semidefinite programming. Comput. Optim. Appl. 56, 81–96 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  36. Zhang, S., Ang, J., Sun, J.: An alternating direction method for solving convex nonlinear semidefinite programming problem. Optimization 62(4), 527–543 (2013)

    Article  MathSciNet  MATH  Google Scholar 

  37. Zhao, Q., Chen, Z.: On the superlinear local convergence of a penalty-free method for nonlinear semidefinite programming. J. Comput. App. Math. 308(15), 1–19 (2016)

    Article  MathSciNet  MATH  Google Scholar 

  38. Zhao, Q., Chen, Z.W.: An SQP-type method with superlinear convergence for nonlinear semidefinite programming. Asia-Pac. J. Oper. Res. 35, 1850009 (2018)

    Article  MathSciNet  MATH  Google Scholar 

  39. Zhao, Q., Chen, Z.W.: A line search exact penalty method for nonlinear semidefinite programming. Comput. Optim. Appl. 75, 467–491 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  40. Zhu, Z.B., Zhu, H.L.: A filter method for nonlinear semidefinite programming with global convergence. Acta Math. Sin. 30(10), 1810–1826 (2014)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

The authors would like to thank Professor Ellen Hidemi Fukuda for her helpful comments. We would also like to express our gratitude to the three reviewers for their valuable suggestions. This research was in part supported by the Japan Society for the Promotion of Science KAKENHI for 20K19748, 20H04145, and 21K17709.

Author information

Authors and Affiliations

  1. Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Yoshida-Honmachi, Sakyo-ku, Kyoto, 606-8501, Japan

    Yuya Yamakawa

  2. Faculty of Science and Technology, Seikei University, Kichijouji 1-3-1, Musashino, Tokyo, 180-8633, Japan

    Takayuki Okuno

  3. Center for Advanced Intelligence Project, RIKEN, Nihonbashi 1-chome Mitsui Building, 15th Floor, 1-4-1 Nihonbashi, Chuo-ku, Tokyo, 103-0027, Japan

    Takayuki Okuno

Authors
  1. Yuya Yamakawa
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Takayuki Okuno
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Yuya Yamakawa.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

A Supplementary for the numerical experiments

A Supplementary for the numerical experiments

In Appendix A, we give the existing augmented Lagrangian (AL) method [3].

figure e

Rights and permissions

Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Yamakawa, Y., Okuno, T. A stabilized sequential quadratic semidefinite programming method for degenerate nonlinear semidefinite programs. Comput Optim Appl 83, 1027–1064 (2022). https://doi.org/10.1007/s10589-022-00402-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-022-00402-x

Keywords

Search

Navigation