Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 90C22, 90C26; Secondary: 90C30.

 Citation:

•  [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.