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]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247
[2]

Saima Rashid, Fahd Jarad, Zakia Hammouch. Some new bounds analogous to generalized proportional fractional integral operator with respect to another function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021020
[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[4]

Jiangxing Wang. Convergence analysis of an accurate and efficient method for nonlinear Maxwell's equations. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2429-2440. doi: 10.3934/dcdsb.2020185
[5]

Yuri Chekanov, Felix Schlenk. Notes on monotone Lagrangian twist tori. Electronic Research Announcements, 2010, 17: 104-121. doi: 10.3934/era.2010.17.104
[6]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[7]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907
[8]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[9]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[10]

Sara Munday. On the derivative of the $\alpha$-Farey-Minkowski function. Discrete & Continuous Dynamical Systems - A, 2014, 34 (2) : 709-732. doi: 10.3934/dcds.2014.34.709
[11]

Ritu Agarwal, Kritika, Sunil Dutt Purohit, Devendra Kumar. Mathematical modelling of cytosolic calcium concentration distribution using non-local fractional operator. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021017
[12]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[13]

Ralf Hielscher, Michael Quellmalz. Reconstructing a function on the sphere from its means along vertical slices. Inverse Problems & Imaging, 2016, 10 (3) : 711-739. doi: 10.3934/ipi.2016018
[14]

Zaihong Wang, Jin Li, Tiantian Ma. An erratum note on the paper: Positive periodic solution for Brillouin electron beam focusing system. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1995-1997. doi: 10.3934/dcdsb.2013.18.1995
[15]

Shanjian Tang, Fu Zhang. Path-dependent optimal stochastic control and viscosity solution of associated Bellman equations. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5521-5553. doi: 10.3934/dcds.2015.35.5521
[16]

Changpin Li, Zhiqiang Li. Asymptotic behaviors of solution to partial differential equation with Caputo–Hadamard derivative and fractional Laplacian: Hyperbolic case. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021023
[17]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[18]

Zhiming Guo, Zhi-Chun Yang, Xingfu Zou. Existence and uniqueness of positive solution to a non-local differential equation with homogeneous Dirichlet boundary condition---A non-monotone case. Communications on Pure & Applied Analysis, 2012, 11 (5) : 1825-1838. doi: 10.3934/cpaa.2012.11.1825
[19]

Dayalal Suthar, Sunil Dutt Purohit, Haile Habenom, Jagdev Singh. Class of integrals and applications of fractional kinetic equation with the generalized multi-index Bessel function. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021019
[20]

Davide La Torre, Simone Marsiglio, Franklin Mendivil, Fabio Privileggi. Public debt dynamics under ambiguity by means of iterated function systems on density functions. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021070

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences