American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Optimization analysis of the machine repair problem with multiple vacations and working breakdowns
  • JIMO Home
  • This Issue
  • Next Article
    An efficient distributed optimization and coordination protocol: Application to the emergency vehicle management
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

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.  Google Scholar

[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.  Google Scholar

[3]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, Springer-Verlag, (2000).  doi: 10.1007/978-1-4612-1394-9.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM J. Optim., 10 (2000), 673.  doi: 10.1137/S1052623497328987.  Google Scholar

[11]

R. A. Horn and C. R. Johnson, Topics in Matrix Analysis,, Cambridge University Press, (1991).  doi: 10.1017/CBO9780511840371.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

L. Mosheyev and M. Zibulevsky, Penalty/Barrier multiplier algorithm for semidefinite programming,, Optimization Methods and Software, 13 (2000), 235.  doi: 10.1080/10556780008805787.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[19]

A. Shapiro, First and second order analysis of nonlinear semidefinite programs,, Mathematical Programming, 77 (1997), 301.  doi: 10.1007/BF02614439.  Google Scholar

[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.  Google Scholar

[21]

M. Stingl, On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods,, Ph.D thesis, (2006).   Google Scholar

[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.  Google Scholar

[23]

M. J. Todd, Semidefinite optimization,, Acta Numerica, 10 (2001), 515.  doi: 10.1017/S0962492901000071.  Google Scholar

[24]

L. Vanderberghe and S. Boyd, Semidefinite programming,, SIAM Rev., 38 (1996), 49.  doi: 10.1137/1038003.  Google Scholar

[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.  Google Scholar

[26]

L. Zhang, Y. Li and J. Wu, Nonlinear rescaling Lagrangians for nonconvex semidefinite programming,, Optimization, (2013).  doi: 10.1080/02331934.2013.848861.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[29]

M. Zibulevski, Penalty Barrier Multiplier Methods for Large-Scale Nonlinear and Semidefinite Programming,, Ph.D thesis, (1996).   Google Scholar

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.  Google Scholar

[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.  Google Scholar

[3]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems,, Springer-Verlag, (2000).  doi: 10.1007/978-1-4612-1394-9.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

C. Helmberg and F. Rendl, A spectral bundle method for semidefinite programming,, SIAM J. Optim., 10 (2000), 673.  doi: 10.1137/S1052623497328987.  Google Scholar

[11]

R. A. Horn and C. R. Johnson, Topics in Matrix Analysis,, Cambridge University Press, (1991).  doi: 10.1017/CBO9780511840371.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[15]

L. Mosheyev and M. Zibulevsky, Penalty/Barrier multiplier algorithm for semidefinite programming,, Optimization Methods and Software, 13 (2000), 235.  doi: 10.1080/10556780008805787.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[19]

A. Shapiro, First and second order analysis of nonlinear semidefinite programs,, Mathematical Programming, 77 (1997), 301.  doi: 10.1007/BF02614439.  Google Scholar

[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.  Google Scholar

[21]

M. Stingl, On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods,, Ph.D thesis, (2006).   Google Scholar

[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.  Google Scholar

[23]

M. J. Todd, Semidefinite optimization,, Acta Numerica, 10 (2001), 515.  doi: 10.1017/S0962492901000071.  Google Scholar

[24]

L. Vanderberghe and S. Boyd, Semidefinite programming,, SIAM Rev., 38 (1996), 49.  doi: 10.1137/1038003.  Google Scholar

[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.  Google Scholar

[26]

L. Zhang, Y. Li and J. Wu, Nonlinear rescaling Lagrangians for nonconvex semidefinite programming,, Optimization, (2013).  doi: 10.1080/02331934.2013.848861.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[29]

M. Zibulevski, Penalty Barrier Multiplier Methods for Large-Scale Nonlinear and Semidefinite Programming,, Ph.D thesis, (1996).   Google Scholar

[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]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2017, 13 (5) : 0-0. doi: 10.3934/jimo.2019135
[6]

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
[7]

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
[8]

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
[9]

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
[10]

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
[11]

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
[12]

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
[13]

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
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

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
[20]

Daniel Heinlein, Ferdinand Ihringer. New and updated semidefinite programming bounds for subspace codes. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020034

2018 Impact Factor: 1.025

Tools

Metrics

  • PDF downloads (60)
  • HTML views (0)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences