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]

Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117
[2]

Oussama Landoulsi. Construction of a solitary wave solution of the nonlinear focusing schrödinger equation outside a strictly convex obstacle in the $ L^2 $-supercritical case. Discrete & Continuous Dynamical Systems - A, 2021, 41 (2) : 701-746. doi: 10.3934/dcds.2020298
[3]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077
[4]

Zedong Yang, Guotao Wang, Ravi P. Agarwal, Haiyong Xu. Existence and nonexistence of entire positive radial solutions for a class of Schrödinger elliptic systems involving a nonlinear operator. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020436
[5]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462
[6]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101
[7]

Knut Hüper, Irina Markina, Fátima Silva Leite. A Lagrangian approach to extremal curves on Stiefel manifolds. Journal of Geometric Mechanics, 2020  doi: 10.3934/jgm.2020031
[8]

Mostafa Mbekhta. Representation and approximation of the polar factor of an operator on a Hilbert space. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020463
[9]

Javier Fernández, Cora Tori, Marcela Zuccalli. Lagrangian reduction of nonholonomic discrete mechanical systems by stages. Journal of Geometric Mechanics, 2020, 12 (4) : 607-639. doi: 10.3934/jgm.2020029
[10]

Yahia Zare Mehrjerdi. A new methodology for solving bi-criterion fractional stochastic programming. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020054
[11]

Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113
[12]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[13]

Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296
[14]

Wei Ouyang, Li Li. Hölder strong metric subregularity and its applications to convergence analysis of inexact Newton methods. Journal of Industrial & Management Optimization, 2021, 17 (1) : 169-184. doi: 10.3934/jimo.2019105
[15]

Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020443
[16]

Yi An, Bo Li, Lei Wang, Chao Zhang, Xiaoli Zhou. Calibration of a 3D laser rangefinder and a camera based on optimization solution. Journal of Industrial & Management Optimization, 2021, 17 (1) : 427-445. doi: 10.3934/jimo.2019119
[17]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013
[18]

Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363
[19]

Leanne Dong. Random attractors for stochastic Navier-Stokes equation on a 2D rotating sphere with stable Lévy noise. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020352
[20]

Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2020 American Institute of Mathematical Sciences