American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Filtering solution of nonlinear stochastic optimal control problem in discrete-time with model-reality differences
  • NACO Home
  • This Issue
  • Next Article
    On some inverse singular value problems with Toeplitz-related structure
2012, 2(1): 193-206. doi: 10.3934/naco.2012.2.193

A filter successive linear programming method for nonlinear semidefinite programming problems

Yi Xu 1, and  Wenyu Sun 1,

1. 

School of Mathematical Sciences, Jiangsu Key Laboratory for NSLSCS, Nanjing Normal University, Nanjing 210046, China, China

Received  September 2011 Revised  November 2011 Published  March 2012

In this paper we present a successive linear programming method with filter technique for nonlinear semidefinite programming. Such a method is characterized by use of the dominance concept of multiobjective optimization,~instead of a penalty parameter. The Successive Linear Programming with Filter (SLP-Filter) was used to solve the nonlinear programming (see [8]). In this paper, we extend it to deal with nonlinear semidefinite programming, and prove the convergence of the SLP-Filter for nonlinear semidefinite programming. We report numerical experiments to show the validity of the SLP-Filter method for nonlinear semidefinite programming.
Keywords: global convergence, Nonlinear programming, optimization, successive linear programming, nonlinear semidefinite programming, filter method.
Mathematics Subject Classification: 65k05, 90c3.
Citation: Yi Xu, Wenyu Sun. A filter successive linear programming method for nonlinear semidefinite programming problems. Numerical Algebra, Control & Optimization, 2012, 2 (1) : 193-206. doi: 10.3934/naco.2012.2.193
References:
[1]

A. Auslender and H. Ramírez, Penalty and barrier methods for convex semidefinite progranmming, Mathematical Methods of Operations Research, 63 (2006), 195-219. doi: 10.1007/s00186-005-0054-0.  Google Scholar

[2]

M. S. Bazaraa and C. M. Shetty, "Nonlinear Programming Theory and Algorithms," John Wiley & Sons, New York, 1979.  Google Scholar

[3]

C. Chin and R. Flercher, On the global convergence of an SLP-Filter algorithm that takes EQP steps, SIAM Journal on Optimization, 96 (2003), 161-177.  Google Scholar

[4]

R. Correa and H. Ramírez, A global algorithm for nonlinear semidefinite programming, Math. Program., 15 (2004), 303-318.  Google Scholar

[5]

B. Fares, D. Noll and P. Apkarian, Robust control via sequential semidefinite programming, SIAM Journal on Control and Optimization, 40 (2002), 1791-1820. doi: 10.1137/S0363012900373483.  Google Scholar

[6]

R. Fletcher, N. I. M. Gould, S. Leyffer and A. Wächter, Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming, SIAM J. Optim., 13 (2002), 635-659. doi: 10.1137/S1052623499357258.  Google Scholar

[7]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269. doi: 10.1007/s101070100244.  Google Scholar

[8]

R. Fletcher, S. Leyffer and Ph.L. Toint, On the global convergence of an SLP-Filter Algorithm,, Numerical Analysis Report, ().   Google Scholar

[9]

R. Fletcher, S. Leyffer and Ph.L. Toint, On the global convergence of a Filter-SQP Algorithm, SIAM J. Optim., 13 (2002), 44-59. doi: 10.1137/S105262340038081X.  Google Scholar

[10]

N. I. M. Gould, C. Sainvitu and Ph. L. Toint, A filter-trust-region method for unconstraint optimization, SIAM J. Optim., 16 (2005), 341-357. doi: 10.1137/040603851.  Google Scholar

[11]

C. Helmberg, Semidefinite programming for combinatorial optimization, Technical Report ZIB-Report ZR-00-34, Konrad-Zuse-Zentrum Berlin, 2000. Google Scholar

[12]

X. X. Huang, K. L. Teo and X. Q. Yang, Approximate augmented Lagrangian functions and nonlinear semidefinite programs, Technical Report, Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China, 2003. Google Scholar

[13]

F. Jarre, An interior method for nonconvex semidefinite programs, Optimization and Engineering, 1 (2000), 347-372. doi: 10.1023/A:1011562523132.  Google Scholar

[14]

C. Kanzow, C. Nagel, H. Kato and M. Fukushima, Succseeive linearization methods for nonlinear semidefinite programs, Comput. Optim. Appl., 31 (2005), 251-273. doi: 10.1007/s10589-005-3231-4.  Google Scholar

[15]

C. Li and W. Sun, On filter-successive linearization methods for nonlinear semidefinite programming, Science in China Series A, 52 (2009), 2341-2361. doi: 10.1007/s11425-009-0168-6.  Google Scholar

[16]

W. Miao and W. Sun, A filter-trust-region method for unconstrained optimization, Numerical Mathematics, A Journal of Chinese Universities, 29 (2007), 88-96.  Google Scholar

[17]

W. Sun, On filter methods for optimization, The 3rd Australia-China Optimization Workshop, Shanghai University. Invited talk, 2007. Google Scholar

[18]

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

[19]

W. Sun and Y. Yuan, "Optimzation Theory and Methods: Nonlinear Programming," Springer, New York, 2006. Google Scholar

[20]

M. J. Todd, Semidefinite optimization, Numerical Mathematics, A Journal of Chinese Universities, 10 (2001), 515-560.  Google Scholar

[21]

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

[22]

K. C. Toh, R. H. Tutuncu and M. J. Todd, On the implementation and usage of SDPT3 - a MATLAB software package for semidefinite-quadratic-linear programming version 4.0, 17 July, 2006. http://www.math.nus.edu.sg/~mattohkc/sdpt3.html. Google Scholar

[23]

R. H. Tutuncu, K. C. Toh and M. J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Math. Prog., 95 (2003), 189-217. Google Scholar

[24]

H. Wolkowicz, R. Saigal and L. Vandenberghe, "Handbook of Semidefinite Programming," Boston: Kluwer Academic Publishers, 2000.  Google Scholar

[25]

Z. Yang, W. Sun and L. Qi, On global convergence of a filter-trust-region algorithm for solving nonsmooth equations, International Journal of Computer Mathematics, 87 (2010), 788-796.  Google Scholar

[26]

Y. Zhang, W. Sun and L. Qi, A nonmonotone filter Barzilai-Borwein method for optimization, Asia-Pacific Journal of Operational Research, 27 (2010), 55-69.  Google Scholar

show all references

References:
[1]

A. Auslender and H. Ramírez, Penalty and barrier methods for convex semidefinite progranmming, Mathematical Methods of Operations Research, 63 (2006), 195-219. doi: 10.1007/s00186-005-0054-0.  Google Scholar

[2]

M. S. Bazaraa and C. M. Shetty, "Nonlinear Programming Theory and Algorithms," John Wiley & Sons, New York, 1979.  Google Scholar

[3]

C. Chin and R. Flercher, On the global convergence of an SLP-Filter algorithm that takes EQP steps, SIAM Journal on Optimization, 96 (2003), 161-177.  Google Scholar

[4]

R. Correa and H. Ramírez, A global algorithm for nonlinear semidefinite programming, Math. Program., 15 (2004), 303-318.  Google Scholar

[5]

B. Fares, D. Noll and P. Apkarian, Robust control via sequential semidefinite programming, SIAM Journal on Control and Optimization, 40 (2002), 1791-1820. doi: 10.1137/S0363012900373483.  Google Scholar

[6]

R. Fletcher, N. I. M. Gould, S. Leyffer and A. Wächter, Global convergence of a trust-region SQP-filter algorithm for general nonlinear programming, SIAM J. Optim., 13 (2002), 635-659. doi: 10.1137/S1052623499357258.  Google Scholar

[7]

R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Mathematical Programming, 91 (2002), 239-269. doi: 10.1007/s101070100244.  Google Scholar

[8]

R. Fletcher, S. Leyffer and Ph.L. Toint, On the global convergence of an SLP-Filter Algorithm,, Numerical Analysis Report, ().   Google Scholar

[9]

R. Fletcher, S. Leyffer and Ph.L. Toint, On the global convergence of a Filter-SQP Algorithm, SIAM J. Optim., 13 (2002), 44-59. doi: 10.1137/S105262340038081X.  Google Scholar

[10]

N. I. M. Gould, C. Sainvitu and Ph. L. Toint, A filter-trust-region method for unconstraint optimization, SIAM J. Optim., 16 (2005), 341-357. doi: 10.1137/040603851.  Google Scholar

[11]

C. Helmberg, Semidefinite programming for combinatorial optimization, Technical Report ZIB-Report ZR-00-34, Konrad-Zuse-Zentrum Berlin, 2000. Google Scholar

[12]

X. X. Huang, K. L. Teo and X. Q. Yang, Approximate augmented Lagrangian functions and nonlinear semidefinite programs, Technical Report, Department of Applied Mathematics, The Hong Kong Polytechnic University, Hong Kong, China, 2003. Google Scholar

[13]

F. Jarre, An interior method for nonconvex semidefinite programs, Optimization and Engineering, 1 (2000), 347-372. doi: 10.1023/A:1011562523132.  Google Scholar

[14]

C. Kanzow, C. Nagel, H. Kato and M. Fukushima, Succseeive linearization methods for nonlinear semidefinite programs, Comput. Optim. Appl., 31 (2005), 251-273. doi: 10.1007/s10589-005-3231-4.  Google Scholar

[15]

C. Li and W. Sun, On filter-successive linearization methods for nonlinear semidefinite programming, Science in China Series A, 52 (2009), 2341-2361. doi: 10.1007/s11425-009-0168-6.  Google Scholar

[16]

W. Miao and W. Sun, A filter-trust-region method for unconstrained optimization, Numerical Mathematics, A Journal of Chinese Universities, 29 (2007), 88-96.  Google Scholar

[17]

W. Sun, On filter methods for optimization, The 3rd Australia-China Optimization Workshop, Shanghai University. Invited talk, 2007. Google Scholar

[18]

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

[19]

W. Sun and Y. Yuan, "Optimzation Theory and Methods: Nonlinear Programming," Springer, New York, 2006. Google Scholar

[20]

M. J. Todd, Semidefinite optimization, Numerical Mathematics, A Journal of Chinese Universities, 10 (2001), 515-560.  Google Scholar

[21]

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

[22]

K. C. Toh, R. H. Tutuncu and M. J. Todd, On the implementation and usage of SDPT3 - a MATLAB software package for semidefinite-quadratic-linear programming version 4.0, 17 July, 2006. http://www.math.nus.edu.sg/~mattohkc/sdpt3.html. Google Scholar

[23]

R. H. Tutuncu, K. C. Toh and M. J. Todd, Solving semidefinite-quadratic-linear programs using SDPT3, Math. Prog., 95 (2003), 189-217. Google Scholar

[24]

H. Wolkowicz, R. Saigal and L. Vandenberghe, "Handbook of Semidefinite Programming," Boston: Kluwer Academic Publishers, 2000.  Google Scholar

[25]

Z. Yang, W. Sun and L. Qi, On global convergence of a filter-trust-region algorithm for solving nonsmooth equations, International Journal of Computer Mathematics, 87 (2010), 788-796.  Google Scholar

[26]

Y. Zhang, W. Sun and L. Qi, A nonmonotone filter Barzilai-Borwein method for optimization, Asia-Pacific Journal of Operational Research, 27 (2010), 55-69.  Google Scholar

[1]

Yang Li, Yonghong Ren, Yun Wang, Jian Gu. Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved. Journal of Industrial & Management Optimization, 2015, 11 (1) : 65-81. doi: 10.3934/jimo.2015.11.65
[2]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 651-669. doi: 10.3934/jimo.2009.5.651
[3]

Yongjian Yang, Zhiyou Wu, Fusheng Bai. A filled function method for constrained nonlinear integer programming. Journal of Industrial & Management Optimization, 2008, 4 (2) : 353-362. doi: 10.3934/jimo.2008.4.353
[4]

Qinghong Zhang, Gang Chen, Ting Zhang. Duality formulations in semidefinite programming. Journal of Industrial & Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[5]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2021012
[6]

Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2267-2281. doi: 10.3934/jimo.2019053
[7]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial & Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[8]

Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2020, 16 (3) : 1527-1538. doi: 10.3934/jimo.2019015
[9]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2020, 14 (4) : 613-630. doi: 10.3934/amc.2020034
[10]

Shouhong Yang. Semidefinite programming via image space analysis. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1187-1197. doi: 10.3934/jimo.2016.12.1187
[11]

Christine Bachoc, Alberto Passuello, Frank Vallentin. Bounds for projective codes from semidefinite programming. Advances in Mathematics of Communications, 2013, 7 (2) : 127-145. doi: 10.3934/amc.2013.7.127
[12]

Chuanhao Guo, Erfang Shan, Wenli Yan. A superlinearly convergent hybrid algorithm for solving nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (2) : 1009-1024. doi: 10.3934/jimo.2016059
[13]

Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[14]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[15]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075
[16]

Mahdi Roozbeh, Saman Babaie–Kafaki, Zohre Aminifard. Two penalized mixed–integer nonlinear programming approaches to tackle multicollinearity and outliers effects in linear regression models. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020128
[17]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177
[18]

Yue Zheng, Zhongping Wan, Shihui Jia, Guangmin Wang. A new method for strong-weak linear bilevel programming problem. Journal of Industrial & Management Optimization, 2015, 11 (2) : 529-547. doi: 10.3934/jimo.2015.11.529
[19]

Yanqun Liu. An exterior point linear programming method based on inclusive normal cones. Journal of Industrial & Management Optimization, 2010, 6 (4) : 825-846. doi: 10.3934/jimo.2010.6.825
[20]

Bao Qing Hu, Song Wang. A novel approach in uncertain programming part II: a class of constrained nonlinear programming problems with interval objective functions. Journal of Industrial & Management Optimization, 2006, 2 (4) : 373-385. doi: 10.3934/jimo.2006.2.373

 Impact Factor: 

Tools

Metrics

  • PDF downloads (43)
  • HTML views (0)
  • Cited by (3)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences