A filter successive linear programming method for nonlinear semidefinite programming problems

Previous Article
On some inverse singular value problems with Toeplitz-related structure
NACO Home
This Issue
Next Article
Filtering solution of nonlinear stochastic optimal control problem in discrete-time with model-reality differences

2012, 2(1): 193-206. doi: 10.3934/naco.2012.2.193

A filter successive linear programming method for nonlinear semidefinite programming problems

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

Abstract
Related Papers

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. 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, (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. Google Scholar
[4]	R. Correa and H. Ramírez, A global algorithm for nonlinear semidefinite programming,, Math. Program., 15 (2004), 303. 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. 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. doi: 10.1137/S1052623499357258. Google Scholar
[7]	R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Mathematical Programming, 91 (2002), 239. 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. 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. doi: 10.1137/040603851. Google Scholar
[11]	C. Helmberg, Semidefinite programming for combinatorial optimization,, Technical Report ZIB-Report ZR-00-34, (2000), 00. Google Scholar
[12]	X. X. Huang, K. L. Teo and X. Q. Yang, Approximate augmented Lagrangian functions and nonlinear semidefinite programs,, Technical Report, (2003). Google Scholar
[13]	F. Jarre, An interior method for nonconvex semidefinite programs,, Optimization and Engineering, 1 (2000), 347. 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. 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. 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, 29 (2007), 88. Google Scholar
[17]	W. Sun, On filter methods for optimization,, The 3rd Australia-China Optimization Workshop, (2007). Google Scholar
[18]	W. Sun, On filter-type methods for optimization: motivation and development,, An invited talk, (2008), 26. Google Scholar
[19]	W. Sun and Y. Yuan, "Optimzation Theory and Methods: Nonlinear Programming,", Springer, (2006). Google Scholar
[20]	M. J. Todd, Semidefinite optimization,, Numerical Mathematics, 10 (2001), 515. 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). 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). 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. 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. 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. 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. 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, (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. Google Scholar
[4]	R. Correa and H. Ramírez, A global algorithm for nonlinear semidefinite programming,, Math. Program., 15 (2004), 303. 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. 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. doi: 10.1137/S1052623499357258. Google Scholar
[7]	R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function,, Mathematical Programming, 91 (2002), 239. 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. 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. doi: 10.1137/040603851. Google Scholar
[11]	C. Helmberg, Semidefinite programming for combinatorial optimization,, Technical Report ZIB-Report ZR-00-34, (2000), 00. Google Scholar
[12]	X. X. Huang, K. L. Teo and X. Q. Yang, Approximate augmented Lagrangian functions and nonlinear semidefinite programs,, Technical Report, (2003). Google Scholar
[13]	F. Jarre, An interior method for nonconvex semidefinite programs,, Optimization and Engineering, 1 (2000), 347. 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. 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. 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, 29 (2007), 88. Google Scholar
[17]	W. Sun, On filter methods for optimization,, The 3rd Australia-China Optimization Workshop, (2007). Google Scholar
[18]	W. Sun, On filter-type methods for optimization: motivation and development,, An invited talk, (2008), 26. Google Scholar
[19]	W. Sun and Y. Yuan, "Optimzation Theory and Methods: Nonlinear Programming,", Springer, (2006). Google Scholar
[20]	M. J. Todd, Semidefinite optimization,, Numerical Mathematics, 10 (2001), 515. 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). 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). 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. 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. 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. 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]	Li Jin, Hongying Huang. Differential equation method based on approximate augmented Lagrangian for nonlinear programming. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-15. doi: 10.3934/jimo.2019053
[6]	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
[7]	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
[8]	Charles Fefferman. Interpolation by linear programming I. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 477-492. doi: 10.3934/dcds.2011.30.477
[9]	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
[10]	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
[11]	Jiani Wang, Liwei Zhang. Statistical inference of semidefinite programming with multiple parameters. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2019015
[12]	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
[13]	Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-14. doi: 10.3934/jimo.2019075
[14]	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
[15]	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
[16]	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
[17]	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
[18]	Jean Creignou, Hervé Diet. Linear programming bounds for unitary codes. Advances in Mathematics of Communications, 2010, 4 (3) : 323-344. doi: 10.3934/amc.2010.4.323
[19]	Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585
[20]	Gianni Di Pillo, Giampaolo Liuzzi, Stefano Lucidi. A primal-dual algorithm for nonlinear programming exploiting negative curvature directions. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 509-528. doi: 10.3934/naco.2011.1.509

Impact Factor:

American Institute of Mathematical Sciences