Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved

Previous Article
An efficient distributed optimization and coordination protocol: Application to the emergency vehicle management
JIMO Home
This Issue
Next Article
Optimization analysis of the machine repair problem with multiple vacations and working breakdowns

January 2015, 11(1): 65-81. doi: 10.3934/jimo.2015.11.65

Convergence analysis of a nonlinear Lagrangian method for nonconvex semidefinite programming with subproblem inexactly solved

Yang Li ^1, , Yonghong Ren ^2, , Yun Wang ^3, and Jian Gu ^4,

1.	School of Science, Dalian Nationalities University, Dalian, 116600, China
2.	School of Mathematics, Liaoning Normal University, Dalian, 116029, China
3.	College of Information Science and Engineering, Shandong Agricultural University, Taian, 271018, China
4.	School of Science, Dalian Ocean University, Dalian, 116023, China

Received August 2012 Revised December 2013 Published May 2014

Abstract
Related Papers

In this paper, we analyze the convergence properties of a nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming (NCSDP) problems. It is different from other convergence analysis, because the subproblem in our algorithm is inexactly solved. Under the constraint nondegeneracy condition, the strict complementarity condition and the second order sufficient conditions, it is obtained that the nonlinear Lagrangian algorithm proposed is locally convergent by choosing a proper stopping criterion and the error bound of solution is proportional to the penalty parameter when the penalty parameter is less than a threshold.

Keywords: nonconvex semidefinite programming, Löwner operator, nonlinear Lagrangian method, Log-Sigmoid function., Inexact solution.

Mathematics Subject Classification: Primary: 90C22, 90C26; Secondary: 90C3.

Citation: 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

References:

[1]	F. Alizadeh, Interior point methods in semidefinite programming with application to combinatorial optimization,, SIAM J. Optim., 5 (1995), 13. doi: 10.1137/0805002.
[2]	P. Apkarian, D. Noll and H. D. Tuan, Fixed-order $H_\infty$ control design via a partially augmented lagrangian method,, International Journal of Robust and Nonlinear Control, 13 (2003), 1137. doi: 10.1002/rnc.807.
[3]	J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, Springer-Verlag, (2000). doi: 10.1007/978-1-4612-1394-9.
[4]	S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory,, SIAM, (1994). doi: 10.1137/1.9781611970777.
[5]	C. Chen, T. C. Edwin Cheng, S. Li and X. Yang, Nonlinear augmented Lagrangian for nonconvex multiobjective optimization,, Journal of Industrial and Management Optimization, 7 (2011), 157. doi: 10.3934/jimo.2011.7.157.
[6]	M. Doljansky and M. Teboulle, An interior proximal algorithm and the exponential multiplier method for semidefinite programming,, SIAM J. Optim., 9 (1999), 1. doi: 10.1137/S1052623496309405.
[7]	B. Fares, P. Apkarian and D. Noll, An augmented Lagrangian method for a class of LMI-constrained problems in robust control theory,, International Journal of Control, 74 (2001), 348. doi: 10.1080/00207170010010605.
[8]	B. Fares, D. Noll and P. Apkarian, Robust control via sequential semidefinite programming,, SIAM J. on Control and Optimization, 40 (2002), 1791. doi: 10.1137/S0363012900373483.
[9]	S. He and Y. Nie, A class of nonlinear Lagrangian algorithms for minimax problems,, Journal of Industrial and Management Optimization, 9 (2013), 75. doi: 10.3934/jimo.2013.9.75.
[10]	C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM J. Optim., 10 (2000), 673. doi: 10.1137/S1052623497328987.
[11]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis,, Cambridge University Press, (1991). doi: 10.1017/CBO9780511840371.
[12]	M. Kočvara and M. Stingl, Pennon: A code for convex nonlinear and semidefinite programming,, Optimization Methods and Software, 18 (2003), 317. doi: 10.1080/1055678031000098773.
[13]	Y. Li and L. Zhang, A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming,, Journal of Industrial and Management Optimization, 5 (2009), 651. doi: 10.3934/jimo.2009.5.651.
[14]	J. Lin, H. Chen and R. Sheu, Augmented Lagrange primal-dual approach for generalized fractional programming problems,, Journal of Industrial and Management Optimization, 9 (2013), 723. doi: 10.3934/jimo.2013.9.723.
[15]	L. Mosheyev and M. Zibulevsky, Penalty/Barrier multiplier algorithm for semidefinite programming,, Optimization Methods and Software, 13 (2000), 235. doi: 10.1080/10556780008805787.
[16]	D. Noll, Local convergence of an augmented Lagrangian method for matrix inequality constrained programming,, Optimization Methods and Software, 22 (2007), 777. doi: 10.1080/10556780701223970.
[17]	D. Noll and P. Apkarian, Spectral bundle methods for non-convex maximum eigenvalue functions: first-order methods,, Math. Programming Series B, 104* (2005), 701.*
[18]	D. Noll, M. Torki and P. Apkarian, Partially augmented Lagrangian method for matrix inequality constraints,, SIAM Journal on Optimization, 15 (2004), 161. doi: 10.1137/S1052623402413963.
[19]	A. Shapiro, First and second order analysis of nonlinear semidefinite programs,, Mathematical Programming, 77 (1997), 301. doi: 10.1007/BF02614439.
[20]	A. Shapiro and J. Sun, Some properties of the augmented Lagrangian in cone constrained optimization,, Mathematics of Operations Research, 29 (2004), 479. doi: 10.1287/moor.1040.0103.
[21]	M. Stingl, On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods,, Ph.D thesis, (2006).
[22]	D. Sun, J. Sun and L. Zhang, The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming,, Mathematical Programming, 114* (2008), 349. doi: 10.1007/s10107-007-0105-9.*
[23]	M. J. Todd, Semidefinite optimization,, Acta Numerica, 10 (2001), 515. doi: 10.1017/S0962492901000071.
[24]	L. Vanderberghe and S. Boyd, Semidefinite programming,, SIAM Rev., 38 (1996), 49. doi: 10.1137/1038003.
[25]	H. Wolkkowicz, R. Saigal and L. Vanderberghe, Handbook of Semidefinite Programming-Theory, Algorithms, and Applications,, Kluwer Academic Publishers, (2000). doi: 10.1007/978-1-4615-4381-7.
[26]	L. Zhang, Y. Li and J. Wu, Nonlinear rescaling Lagrangians for nonconvex semidefinite programming,, Optimization, (2013). doi: 10.1080/02331934.2013.848861.
[27]	L. Zhang, J. Gu and X. Xiao, A class of nonlinear Lagrangians for nonconvex second order cone programming,, Comput. Optim. Appl., 49 (2011), 61. doi: 10.1007/s10589-009-9279-9.
[28]	L. Zhang, Y. Ren, Y. Wu and X. Xiao, A class of nonlinear Lagrangians: Theory and algorithm,, Asia-Pacific Journal of Operational Research, 25 (2008), 327. doi: 10.1142/S021759590800178X.
[29]	M. Zibulevski, Penalty Barrier Multiplier Methods for Large-Scale Nonlinear and Semidefinite Programming,, Ph.D thesis, (1996).

show all references

References:

[1]	F. Alizadeh, Interior point methods in semidefinite programming with application to combinatorial optimization,, SIAM J. Optim., 5 (1995), 13. doi: 10.1137/0805002.
[2]	P. Apkarian, D. Noll and H. D. Tuan, Fixed-order $H_\infty$ control design via a partially augmented lagrangian method,, International Journal of Robust and Nonlinear Control, 13 (2003), 1137. doi: 10.1002/rnc.807.
[3]	J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, Springer-Verlag, (2000). doi: 10.1007/978-1-4612-1394-9.
[4]	S. Boyd, L. El Ghaoui, E. Feron and V. Balakrishnan, Linear Matrix Inequalities in System and Control Theory,, SIAM, (1994). doi: 10.1137/1.9781611970777.
[5]	C. Chen, T. C. Edwin Cheng, S. Li and X. Yang, Nonlinear augmented Lagrangian for nonconvex multiobjective optimization,, Journal of Industrial and Management Optimization, 7 (2011), 157. doi: 10.3934/jimo.2011.7.157.
[6]	M. Doljansky and M. Teboulle, An interior proximal algorithm and the exponential multiplier method for semidefinite programming,, SIAM J. Optim., 9 (1999), 1. doi: 10.1137/S1052623496309405.
[7]	B. Fares, P. Apkarian and D. Noll, An augmented Lagrangian method for a class of LMI-constrained problems in robust control theory,, International Journal of Control, 74 (2001), 348. doi: 10.1080/00207170010010605.
[8]	B. Fares, D. Noll and P. Apkarian, Robust control via sequential semidefinite programming,, SIAM J. on Control and Optimization, 40 (2002), 1791. doi: 10.1137/S0363012900373483.
[9]	S. He and Y. Nie, A class of nonlinear Lagrangian algorithms for minimax problems,, Journal of Industrial and Management Optimization, 9 (2013), 75. doi: 10.3934/jimo.2013.9.75.
[10]	C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM J. Optim., 10 (2000), 673. doi: 10.1137/S1052623497328987.
[11]	R. A. Horn and C. R. Johnson, Topics in Matrix Analysis,, Cambridge University Press, (1991). doi: 10.1017/CBO9780511840371.
[12]	M. Kočvara and M. Stingl, Pennon: A code for convex nonlinear and semidefinite programming,, Optimization Methods and Software, 18 (2003), 317. doi: 10.1080/1055678031000098773.
[13]	Y. Li and L. Zhang, A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming,, Journal of Industrial and Management Optimization, 5 (2009), 651. doi: 10.3934/jimo.2009.5.651.
[14]	J. Lin, H. Chen and R. Sheu, Augmented Lagrange primal-dual approach for generalized fractional programming problems,, Journal of Industrial and Management Optimization, 9 (2013), 723. doi: 10.3934/jimo.2013.9.723.
[15]	L. Mosheyev and M. Zibulevsky, Penalty/Barrier multiplier algorithm for semidefinite programming,, Optimization Methods and Software, 13 (2000), 235. doi: 10.1080/10556780008805787.
[16]	D. Noll, Local convergence of an augmented Lagrangian method for matrix inequality constrained programming,, Optimization Methods and Software, 22 (2007), 777. doi: 10.1080/10556780701223970.
[17]	D. Noll and P. Apkarian, Spectral bundle methods for non-convex maximum eigenvalue functions: first-order methods,, Math. Programming Series B, 104* (2005), 701.*
[18]	D. Noll, M. Torki and P. Apkarian, Partially augmented Lagrangian method for matrix inequality constraints,, SIAM Journal on Optimization, 15 (2004), 161. doi: 10.1137/S1052623402413963.
[19]	A. Shapiro, First and second order analysis of nonlinear semidefinite programs,, Mathematical Programming, 77 (1997), 301. doi: 10.1007/BF02614439.
[20]	A. Shapiro and J. Sun, Some properties of the augmented Lagrangian in cone constrained optimization,, Mathematics of Operations Research, 29 (2004), 479. doi: 10.1287/moor.1040.0103.
[21]	M. Stingl, On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods,, Ph.D thesis, (2006).
[22]	D. Sun, J. Sun and L. Zhang, The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming,, Mathematical Programming, 114* (2008), 349. doi: 10.1007/s10107-007-0105-9.*
[23]	M. J. Todd, Semidefinite optimization,, Acta Numerica, 10 (2001), 515. doi: 10.1017/S0962492901000071.
[24]	L. Vanderberghe and S. Boyd, Semidefinite programming,, SIAM Rev., 38 (1996), 49. doi: 10.1137/1038003.
[25]	H. Wolkkowicz, R. Saigal and L. Vanderberghe, Handbook of Semidefinite Programming-Theory, Algorithms, and Applications,, Kluwer Academic Publishers, (2000). doi: 10.1007/978-1-4615-4381-7.
[26]	L. Zhang, Y. Li and J. Wu, Nonlinear rescaling Lagrangians for nonconvex semidefinite programming,, Optimization, (2013). doi: 10.1080/02331934.2013.848861.
[27]	L. Zhang, J. Gu and X. Xiao, A class of nonlinear Lagrangians for nonconvex second order cone programming,, Comput. Optim. Appl., 49 (2011), 61. doi: 10.1007/s10589-009-9279-9.
[28]	L. Zhang, Y. Ren, Y. Wu and X. Xiao, A class of nonlinear Lagrangians: Theory and algorithm,, Asia-Pacific Journal of Operational Research, 25 (2008), 327. doi: 10.1142/S021759590800178X.
[29]	M. Zibulevski, Penalty Barrier Multiplier Methods for Large-Scale Nonlinear and Semidefinite Programming,, Ph.D thesis, (1996).

[1]	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
[2]	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
[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]	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
[5]	Chunrong Chen, T. C. Edwin Cheng, Shengji Li, Xiaoqi Yang. Nonlinear augmented Lagrangian for nonconvex multiobjective optimization. Journal of Industrial & Management Optimization, 2011, 7 (1) : 157-174. doi: 10.3934/jimo.2011.7.157
[6]	Jinyan Fan, Jianyu Pan. Inexact Levenberg-Marquardt method for nonlinear equations. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 1223-1232. doi: 10.3934/dcdsb.2004.4.1223
[7]	Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial & Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013
[8]	Liping Pang, Na Xu, Jian Lv. The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints. Journal of Industrial & Management Optimization, 2019, 15 (1) : 59-79. doi: 10.3934/jimo.2018032
[9]	Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 495-508. doi: 10.3934/naco.2011.1.495
[10]	Dan Xue, Wenyu Sun, Hongjin He. A structured trust region method for nonconvex programming with separable structure. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 283-293. doi: 10.3934/naco.2013.3.283
[11]	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
[12]	Qingsong Duan, Mengwei Xu, Yue Lu, Liwei Zhang. A smoothing augmented Lagrangian method for nonconvex, nonsmooth constrained programs and its applications to bilevel problems. Journal of Industrial & Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[13]	Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial & Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[14]	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
[15]	Zhiyou Wu, Fusheng Bai, Guoquan Li, Yongjian Yang. A new auxiliary function method for systems of nonlinear equations. Journal of Industrial & Management Optimization, 2015, 11 (2) : 345-364. doi: 10.3934/jimo.2015.11.345
[16]	Liuyang Yuan, Zhongping Wan, Jingjing Zhang, Bin Sun. A filled function method for solving nonlinear complementarity problem. Journal of Industrial & Management Optimization, 2009, 5 (4) : 911-928. doi: 10.3934/jimo.2009.5.911
[17]	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
[18]	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
[19]	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
[20]	Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences