Skip to main content
SpringerLink
Log in

On filter-successive linearization methods for nonlinear semidefinite programming

  • Published:
Science in China Series A: Mathematics Aims and scope Submit manuscript

Abstract

In this paper we present a filter-successive linearization method with trust region for solutions of nonlinear semidefinite programming. Such a method is based on the concept of filter for nonlinear programming introduced by Fletcher and Leyffer in 2002. We describe the new algorithm and prove its global convergence under weaker assumptions. Some numerical results are reported and show that the new method is potentially efficient.

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. Todd M J. Semidefinite optimization. Acta Numer, 10: 515–560 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  2. Vandenberghe L, Boyd S. Semidefinite programming. SIAM Review, SIAM Review: 49–95 (1996)

  3. Wolkowicz H, Saigal R, Vandenberghe L, eds. Handbook of Semidefinite Programming. Boston-Dordrecht-London: Kluwer Academic Publishers, 2000

    Google Scholar 

  4. Helmberg C. Semidefinite programming for combinatorial optimization. Semidefinite programming home page: http://www.zib.de/helmberg/semidef.html (2000)

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

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  7. Kanzow C, Nagel C, Kato H, et al. Successive linearization methods for nonlinear semidefinite programs. Comput Optim Appl, 31: 251–273 (2005)

    Article  MATH  MathSciNet  Google Scholar 

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

    Article  MATH  MathSciNet  Google Scholar 

  9. Sun J, Sun D, Qi L. A squared smoothing Newton method for nonsmooth matrix equations and its applications in semidefinite optimization problems. SIAM J Optim, 14: 783–806 (2004)

    Article  MATH  MathSciNet  Google Scholar 

  10. Li C, Sun W. Some properties for nonconvex semidefinite programming. Numer Math J Chinese Univ, 30: 184–192 (2008)

    MATH  MathSciNet  Google Scholar 

  11. Li C, Sun W. A class of nonsmooth Newton-type methods for nonlinear semidefinite programming. J Nanjing Norm Univ Nat Sci Ed, 31: 1–7 (2008)

    MathSciNet  Google Scholar 

  12. Li C, Sun W. A filter-sequential semidefinite programming method for nonlinear semidefinite programming. Technical Report Opt-07-03, School of Mathematics and Computer Science, Nanjing Normal University, 2007

  13. Nie J, Yuan Y. A potential reduction algorithm for an extended SDP problem. Sci China Ser A, 43: 35–46 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  14. Yamashita H, Yabe H, Harada K. A primal-dual interior point method for nonlinear semidefinite programming. Technical report, Department of Mathematical Information Science, Faculty of Science, Tokyo University of Science, 2007

  15. Liu Z, Sun W. A filter primal-dual interior point method for nonlinear semidefinite programming. Technique report, School of Mathematics and Computer Science, Nanjing Normal University, 2008

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

    Google Scholar 

  17. Sun D. The strong second order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications. Math Oper Res, 31: 761–776 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  18. Bonnans J F, Shapiro A. Perturbation Analysis of Optimization Problems. New York: Springer, 2000

    MATH  Google Scholar 

  19. Bonnans J F, Commintti R, Shapiro A. Sensitivity analysis of optimization problem under second order regularity constraints. Math Oper Res, 23: 803–832 (1998)

    Article  Google Scholar 

  20. Xu D C, Xu S Z. Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation. Sci China Ser A, 50: 1583–1596 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  21. Fletcher R, Leyffer S. Nonlinear programming without a penalty function. Math Program, 91: 239–269 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  22. Fletcher R, Gould N I M, Leyffer S, et al. Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming. SIAM J Optim, 13: 635–659 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  23. Fletcher R, Leyffer S, Toint Ph L. On the global convergence of an SLP-filter algorithm. Numerical Analysis Report NA/183, Department of Mathematics, University of Dundee, Scotland, 1998

    Google Scholar 

  24. Fletcher R, Leyffer S, Toint Ph L. On the global convergence of a filter-SQP algorithm. SIAM J Optim, 13: 44–59 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  25. Gould N I M, Sainvitu C, Toint Ph L. A filter-trust-region method for unconstrained optimization. SIAM J Optim, 16: 341–357 (2005)

    Article  MATH  MathSciNet  Google Scholar 

  26. Chen Y N, Sun W. A dwindling filter line-search method for unconstrained optimization. Technical Report Opt-06-11, School of Mathematics and Computer Science, Nanjing Normal University, 2006

  27. Miao W. On Filter and Nonmonotone Techniques in Numerical Optimization. PhD dissertation. School of Mathematics and Computer Science, Nanjing Normal University, 2006

  28. Miao W, Sun W. A filter-trust-region method for unconstrained optimization. Numer Math J Chinese Univ, 29: 88–96 (2007)

    MATH  MathSciNet  Google Scholar 

  29. Sun W. On filter-type methods for optimization: motivation and development. An invited talk, 4th Sino-Japanese Optimization Meeting (SJOM2008), August 26–31, 2008. Cheng Kung University, Taiwan.

    Google Scholar 

  30. Toh K C, Tutuncu R H, Todd M J. SDPT3 version 4.0 (beta) — a MATLAB software for semidefinitequadratic-linear programming. http://www.math.nus.edu.sg/˜mattohkc/sdpt3.html, updated in 17 July, 2006

  31. Toh K C, Tutuncu R H, Todd M J. On the implementation and usage of SDPT3-a MATLAB software package for semidefinite-quadratic-linear programming version 4.0 (Draft). http://www.math.nus.edu.sg/˜mattohkc/guide4-0-draft.pdf, 17 July, 2006

  32. Tutuncu R H, Toh K C, Todd M J. Solving semidefinite quadratic-linear programs using SDPT3. Math Program, 95: 189–217 (2003)

    Article  MathSciNet  Google Scholar 

  33. Sun W, Yuan Y. Optimization Theory and Methods: Nonlinear Programming. New York: Springer, 2006

    MATH  Google Scholar 

  34. Sun W, Zhou Q Y. An unconstrained optimization method using nonmonotone second order Goldstein’s line search. Sci China Ser A, 50: 1389–1400 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  35. Ke X W, Han J Y. A nonmonotone trust region algorithm for equality constrained optimization. Sci China Ser A, 38: 683–695 (1995)

    MATH  MathSciNet  Google Scholar 

  36. Ben-Tal A, Nemirovski A. Lectures On Modern Convex Optimization-Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization. Philadelphia: SIAM, 2001

    MATH  Google Scholar 

  37. Bazaraa M S, Shetty C M. Nonlinear Programming: Theory and Algorithms. New York: John Wiley and Sons, 1979

    MATH  Google Scholar 

  38. Borchers B. SDPLIB 1.2, a library of semidefinite programming test problems. Optim Methods Softw, 11: 597–611 (1999)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical and Computer Science, Nanjing Normal University, Nanjing, 210097, China

    ChengJin Li & WenYu Sun

  2. School of Mathematical and Computer Science, Fujian Normal University, Fuzhou, 350108, China

    ChengJin Li

Authors
  1. ChengJin Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. WenYu Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to WenYu Sun.

Additional information

This work was supported by National Natural Science Foundation of China (Grant No. 10871098) and Science Foundation of Jiangsu Province (Grant No. BK2006214)

Rights and permissions

Reprints and permissions

About this article

Cite this article

Li, C., Sun, W. On filter-successive linearization methods for nonlinear semidefinite programming. Sci. China Ser. A-Math. 52, 2341–2361 (2009). https://doi.org/10.1007/s11425-009-0168-6

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11425-009-0168-6

Keywords

MSC(2000)

Search

Navigation