Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Optimality conditions for nonlinear semidefinite programming via squared slack variables

  • Full Length Paper
  • Series B
  • Published:
Mathematical Programming Submit manuscript

Abstract

In this work, we derive second-order optimality conditions for nonlinear semidefinite programming (NSDP) problems, by reformulating it as an ordinary nonlinear programming problem using squared slack variables. We first consider the correspondence between Karush-Kuhn-Tucker points and regularity conditions for the general NSDP and its reformulation via slack variables. Then, we obtain a pair of “no-gap” second-order optimality conditions that are essentially equivalent to the ones already considered in the literature. We conclude with the analysis of some computational prospects of the squared slack variables approach for NSDP.

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
$34.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 excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Notes

  1. Although we will also use \(\langle \cdot ,\cdot \rangle \) to denote the inner product in \(\mathbb {R}^n\), there will be no confusion.

  2. Take \(A = \bigl ({\begin{matrix} 1 &{}0\\ 0&{}-1 \end{matrix}} \bigr )\), for example.

  3. We refer to this condition as SOSC-NLP in order to distinguish it from SOSC for SDP.

References

  1. Barvinok, A.: Problems of distance geometry and convex properties of quadratic maps. Discrete Comput. Geom. 13(1), 189–202 (1995)

    Article  MathSciNet  MATH  Google Scholar 

  2. Bernstein, D.S.: Matrix Mathematics: Theory, Facts, and Formulas, 2nd edn. Princeton University Press, Princeton (2009)

  3. Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific (1999)

  4. Bonnans, J.F., Cominetti, R., Shapiro, A.: Second order optimality conditions based on parabolic second order tangent sets. SIAM J. Optim. 9(2), 466–492 (1999)

    Article  MathSciNet  MATH  Google Scholar 

  5. Burer, S., Monteiro, R.D.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Progr. 95(2), 329–357 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  6. Burer, S., Monteiro, R.D.: Local minima and convergence in low-rank semidefinite programming. Math. Progr. 103(3), 427–444 (2005)

    Article  MathSciNet  MATH  Google Scholar 

  7. Cominetti, R.: Metric regularity, tangent sets, and second-order optimality conditions. Appl. Math. Optim. 21(1), 265–287 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  8. Fiala, J., Kočvara, M., Stingl, M.: PENLAB: a matlab solver for nonlinear semidefinite optimization. ArXiv e-prints (2013)

  9. Forsgren, A.: Optimality conditions for nonconvex semidefinite programming. Math. Progr. 88(1), 105–128 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  10. Fukuda, E.H., Fukushima, M.: The use of squared slack variables in nonlinear second-order cone programming. J. Optim. Theory Appl. (2016). doi:10.1007/s10957-016-0904-3

  11. Hock, W., Schittkowski, K.: Test examples for nonlinear programming codes. J. Optim. Theory Appl. 30(1), 127–129 (1980)

    Article  MATH  Google Scholar 

  12. Jarre, F.: Elementary optimality conditions for nonlinear SDPs. In: Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research and Management Science (vol. 166, pp. 455–470). Springer, Berlin (2012)

  13. Kawasaki, H.: An envelope-like effect of infinitely many inequality constraints on second-order necessary conditions for minimization problems. Math. Progr. 41(1–3), 73–96 (1988)

    Article  MathSciNet  MATH  Google Scholar 

  14. 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 

  15. Nocedal, J., Wright, S.J.: Numerical Optimization, 1st edn. Springer, New York (1999)

    Book  MATH  Google Scholar 

  16. Pataki, G.: On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Math. Oper. Res. 23(2), 339–358 (1998)

    Article  MathSciNet  MATH  Google Scholar 

  17. Pataki, G.: The geometry of semidefinite programming. In: Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.) Handbook of Semidefinite Programming: Theory, Algorithms, and Applications. Kluwer Academic Publishers, Dordrecht (2000)

  18. Robinson, S.M.: Stability theory for systems of inequalities, part II: differentiable nonlinear systems. SIAM J. Numer. Anal. 13(4), 497–513 (1976)

    Article  MathSciNet  MATH  Google Scholar 

  19. Schittkowski, K.: Test examples for nonlinear programming codes—all problems from the Hock-Schittkowski-collection. Department of Computer Science, University of Bayreuth, Tech. rep. (2009)

  20. Shapiro, A.: First and second order analysis of nonlinear semidefinite programs. Math. Progr. 77(1), 301–320 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  21. Sturm, J.F.: Similarity and other spectral relations for symmetric cones. Linear Algebra Appl. 312(1–3), 135–154 (2000)

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Computer and Information Science, Faculty of Science and Technology, Seikei University, 3-3-1 Kichijojikitamachi, Musashino-shi, Tokyo, 180-8633, Japan

    Bruno F. Lourenço

  2. Department of Applied Mathematics and Physics, Graduate School of Informatics, Kyoto University, Kyoto, 606-8501, Japan

    Ellen H. Fukuda

  3. Department of Systems and Mathematical Science, Faculty of Science and Engineering, Nanzan University, Nagoya, Aichi, 486-8673, Japan

    Masao Fukushima

Authors
  1. Bruno F. Lourenço
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ellen H. Fukuda
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Masao Fukushima
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Masao Fukushima.

Additional information

This work was supported by Grant-in-Aid for Young Scientists (B) (26730012) and for Scientific Research (C) (26330029) from Japan Society for the Promotion of Science.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Lourenço, B.F., Fukuda, E.H. & Fukushima, M. Optimality conditions for nonlinear semidefinite programming via squared slack variables. Math. Program. 168, 177–200 (2018). https://doi.org/10.1007/s10107-016-1040-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10107-016-1040-4

Keywords

Mathematics Subject Classification

Search

Navigation