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 and 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-51. 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-1148. doi: 10.1002/rnc.807.

[3]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 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, Philadelphia, PA, 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-174. 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-13. 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-360. 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-1820. 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-97. 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-696. 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-333. 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-669. 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-741. 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-261. 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-802. 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-727.

[18]

D. Noll, M. Torki and P. Apkarian, Partially augmented Lagrangian method for matrix inequality constraints, SIAM Journal on Optimization, 15 (2004), 161-184. doi: 10.1137/S1052623402413963.

[19]

A. Shapiro, First and second order analysis of nonlinear semidefinite programs, Mathematical Programming, 77 (1997), 301-320. 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-491. doi: 10.1287/moor.1040.0103.

[21]

M. Stingl, On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods, Ph.D thesis, University of Erlangen, 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-391. doi: 10.1007/s10107-007-0105-9.

[23]

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

[24]

L. Vanderberghe and S. Boyd, Semidefinite programming, SIAM Rev., 38 (1996), 49-95. 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, published online, 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-99. 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-371. doi: 10.1142/S021759590800178X.

[29]

M. Zibulevski, Penalty Barrier Multiplier Methods for Large-Scale Nonlinear and Semidefinite Programming, Ph.D thesis, Technion, Israel, 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-51. 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-1148. doi: 10.1002/rnc.807.

[3]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 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, Philadelphia, PA, 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-174. 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-13. 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-360. 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-1820. 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-97. 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-696. 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-333. 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-669. 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-741. 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-261. 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-802. 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-727.

[18]

D. Noll, M. Torki and P. Apkarian, Partially augmented Lagrangian method for matrix inequality constraints, SIAM Journal on Optimization, 15 (2004), 161-184. doi: 10.1137/S1052623402413963.

[19]

A. Shapiro, First and second order analysis of nonlinear semidefinite programs, Mathematical Programming, 77 (1997), 301-320. 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-491. doi: 10.1287/moor.1040.0103.

[21]

M. Stingl, On the Solution of Nonlinear Semidefinite Programs by Augmented Lagrangian Methods, Ph.D thesis, University of Erlangen, 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-391. doi: 10.1007/s10107-007-0105-9.

[23]

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

[24]

L. Vanderberghe and S. Boyd, Semidefinite programming, SIAM Rev., 38 (1996), 49-95. 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, published online, 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-99. 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-371. doi: 10.1142/S021759590800178X.

[29]

M. Zibulevski, Penalty Barrier Multiplier Methods for Large-Scale Nonlinear and Semidefinite Programming, Ph.D thesis, Technion, Israel, 1996.

[1]

Yang Li, Liwei Zhang. A nonlinear Lagrangian method based on Log-Sigmoid function for nonconvex semidefinite programming. Journal of Industrial and 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 and 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 and 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 and Management Optimization, 2020, 16 (5) : 2267-2281. 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 and Management Optimization, 2021, 17 (2) : 805-825. 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 and 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 and Continuous Dynamical Systems - B, 2004, 4 (4) : 1223-1232. doi: 10.3934/dcdsb.2004.4.1223
[8]

Liping Pang, Na Xu, Jian Lv. The inexact log-exponential regularization method for mathematical programs with vertical complementarity constraints. Journal of Industrial and Management Optimization, 2019, 15 (1) : 59-79. doi: 10.3934/jimo.2018032
[9]

Zhili Ge, Gang Qian, Deren Han. Global convergence of an inexact operator splitting method for monotone variational inequalities. Journal of Industrial and Management Optimization, 2011, 7 (4) : 1013-1026. doi: 10.3934/jimo.2011.7.1013
[10]

Chunrong Chen. A unified nonlinear augmented Lagrangian approach for nonconvex vector optimization. Numerical Algebra, Control and 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 and 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 and Management Optimization, 2010, 6 (4) : 881-893. doi: 10.3934/jimo.2010.6.881
[13]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control and Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030
[14]

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 and Management Optimization, 2019, 15 (3) : 1241-1261. doi: 10.3934/jimo.2018094
[15]

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 and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[16]

Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585
[17]

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

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

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

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy