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

Yang Li; Yonghong Ren; Yun Wang; Jian Gu

doi:10.3934/jimo.2015.11.65

Article Contents

2015, Volume 11, Issue 1: 65-81. Doi: 10.3934/jimo.2015.11.65

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

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

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

Received: August 2012

Revised: December 2013

Published: January 2015

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.