非线性半定规划若干算法介绍

doi:10.15960/j.cnki.issn.1007-6093.2016.02.001

摘要/Abstract

摘要：

介绍近几年国际上求解非线性半定规划的若干有效新算法, 包括增广Lagrangian函数法、序列半定规划法、序列线性方程组法以及交替方向乘子法. 最后, 对非线性半定规划的算法研究前景进行了探讨.

关键词: 非线性半定规划, 增广Lagrangian函数法, 序列半定规划法, 序列线性方程组法, 交替方向乘子法

Abstract:

In this paper, some important and effective numerical methods developed in recent years for nonlinear semidefinite programming are introduced, which included augmented Lagrangian methods, sequential semidefinite programming algorithms, sequence of linear equations algorithms and alternating direction multiplier methods. At the end of this paper, some future research perspectives of algorithms for nonlinear semidefinite programming are discussed.

Key words: nonlinear semidefinite programming, augmented Lagrangian methods, sequential semidefinite programming algorithms, sequence of systems linear equations algorithms, alternating direction multiplier methods

黎健玲, 杨振平, 简金宝. 非线性半定规划若干算法介绍[J]. 运筹学学报, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.001.

LI Jianling, YANG Zhenping, JIAN Jinbao. Introduction of some algorithms for nonlinear semidefinite programming[J]. Operations Research Transactions, doi: 10.15960/j.cnki.issn.1007-6093.2016.02.001.

参考文献

[1] Ben-Tal A, Jarre F, Kocvara M, et al. Optimal design of trusses under a nonconvex global buckling constraint [J]. Optimization and Engineering, 2000, 1: 189-213.

[2] Fares B, Noll D, Apkarian P. Robust control via sequential semidefinite programming [J]. SIAM Journal on Control and Optimization, 2002, 40: 1791-1820.

[3] Kocvara M, Stingl M. Solving nonconvex SDP problems of structural optimization with stability control [J]. Optimization Methods and Software, 2004, 19: 595-609.

[4] Jarre F. An interior method for nonconvex semidefinite programs [J]. Optimization and Engineering, 2000, 1: 347-372.

[5] Fares B, Apkarian P, Noll D. An augmented Lagrangian method for a class of LMI-constrained problems in robust control theory [J]. International Journal of Control, 2001, 74: 348-360.

[6] Sayed E L, Mostafa M E. An augmented Lagrangian SQP method for solving some special class of nonlinear semidefinite programming problems [J]. Computational and Applied Mathematics, 2005, 24: 461-486.

[7] Kocvara M, Stingl M. PENNON---A code for convex nonlinear and semidefinite programming [J]. Optimization Methods and Software, 2003, 18: 317-333.

[8] Sun J, Zhang L W, Wu Y. Properties of the augmented Lagrangian in nonlinear semidefinite optimization [J]. Journal of Optimization Theory and Applications, 2006, 129: 437-456.

[9] Sun J. On methods for solving nonlinear semidefinite optimization problems [J]. Numerical Algebra, Control and Optimization, 2011, 1: 1-14.

[10] Noll D. Local convergence of an augmented Lagrangian method for matrix inequality constrained programming [J]. Optimization Methods and Software, 2007, 22: 777-802.

[11] Sun D F, Sun J, Zhang L W. The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming [J]. Mathematical Programming, 2008, 114: 349-391.

[12] Huang X X, Yang X Q, Teo K L. Augmented Lagrangian and nonlinear semidefinite programs [J]. Variational Analysis and Applications, Nonconvex Optimization and Its Applications, 2005, 79: 513-529.

[13] Luo H Z, Wu H X, Chen G T. On the convergence of augmented Lagrangian methods for nonlinear semidefinite programming [J]. Journal of Global Optimization, 2012, 54: 599-618.

[14] Wu H X, Luo H Z, Ding X D, et al. Global convergence of modified augmented Lagrangian methods for nonlinear semidefinite programming [J]. Computational Optimization and Applications, 2012, 56: 531-558.

[15] Wu H X, Luo H Z, Yang J F. Nonlinear separation approach for the augmented Lagrangian in nonlinear semidefinite programming [J]. Journal of Global Optimization, 2014, 59: 695-727.

[16] Luo H Z, Wu H X, Liu J Z. On saddle points in semidefinite optimization via separation scheme [J]. Journal of Optimization Theory and Applications, 2015, 165: 113-150.

[17] Shapiro A, Sun J. Some properties of the augmented Lagrangian in cone constrained optimization [J]. Mathematics of Operations Research, 2004, 29: 479-491.

[18] Correa R, Ramirez H. A global algorithm for nonlinear semidefinite programming [J]. SIAM Journal on Optimization, 2004, 15: 303-318.

[19] Gomez W, Ramirez H. A filter algorithm for nonlinear semidefinite programming [J]. Computational and Applied Mathematics, 2010, 29: 297-328.

[20] Zhu Z B, Zhu H L. A filter method for nonlinear semidefinite programming with global convergence [J]. Acta Mathematica Sinica(English Series), 2014, 30: 1810-1826.

[21] Chen Z W, Miao S C. A penalty-free method with trust region for nonlinear semidefinite programming [J]. Asia-Pacific Journal of the Operations Research, 2015, 32(1): 1540006.
[22] Zhao Q. Global convergence of a new method for semi-definite programming [J]. South Asian Journal of Mathematical, 2013, 3: 189-198.

[23] Mostafa E M E, Hamdi A, Aboutahoun A. A proximal-point SQP trust region method for solving some special class of nonlinear semi-definite programming problems [J]. Applied Mathematics and Computation, 2006, 174: 810-832.

[24] Leibfritz F, Mostafa E M E. An interior point constrained trust region method for a special class of nonlinear semidefinite programming problems [J]. SIAM Journal on Optimization, 2002, 12: 1048-1074.

[25] Qi H D. Local duality of nonlinear semidefinite programming [J]. Mathematics of Operations Research, 2009, 34: 124-141.

[26] Yamashita H, Yabe H, Harada K. A primal-dual interior point method for nonlinear semidefinite programming [J]. Mathematical Programming(Series A), 2012, 135: 89-121.

[27] Yamashita H, Yabe H. Local and superlinear convergence of a primal-dual interior point method for nonlinear semidefinite programming [J]. Mathematical Programming(Series A), 2012, 132: 1-30.

[28] Katoa A, Yabe H, Yamashita H. An interior point method with a primal-dual quadratic barrier penalty function for nonlinear semidefinite programming [J]. Journal of Computational and Applied Mathematics, 2015, 275: 148-161.

[29] Aroztegui M, Herskovits J, Roche J R, et al. A feasible direction interior point algorithm for nonlinear semidefinite programming [J]. Structural and Multidisciplinary Optimization, 2014, 50: 1019-1035.

[30] Li J L, Yang Z P, Jian J B. A globally convergent SSLE algorithm for nonlinear semidefinite programming [R]. Nanning: College of Mathematics and Information Science, Guangxi University, 2015.

[31] Sun J, Zhang S. A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs [J]. European Journal of Operations Research, 2010, 207: 1210-1220.

[32] Zhang S, Ang J, Sun J. An alternating direction method for solving convex nonlinear semidefinite programming problems [J]. Optimization, 2013, 62: 527-543.

[33] Lu Y, Ge Y E, Zhang L W. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems [J]. Journal of Industrial and Management Optimization, 2016, 12: 317-336.

[34] Bonnans J F, Shapiro A. Perturbation Analysis of Optimization Problems [M]. New York: Springer-Verlag, 2000.

[35] Hiriart-Urruty J B, Lemarechal C. Convex Analysis and Minimization Algorithms [M]. Berlin: Springer-Verlag, 1993.

[36] Shapiro A. First and second order analysis of nonlinear semidefinite programs [J]. Mathematical Programming(Series B), 1997, 77: 301-320.

[37] De Klerk E. Aspects of Semidefinite Programming Interior Point Algorithms and Selected Applications [M]. Dordrecht：Kluwer Academic Publishers, 2002.

[38] Boyd S, Vandenberghe L. Convex Optimization [M]. Cambridge: Cambridge University Press, 2004.

[39] Sun D F. The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications [J]. Mathematics of Operations Research, 2006, 31: 761-776.

[40] Freund R W, Jarre F, Vogelbusch C H. Nonlinear semidefinite programming sensitivity, convergence, and an application in passive reduced-order modeling [J]. Mathematical Programming (Series B), 2007, 109: 581-611.

[41] Robinson S M. Stability theorems for systems of inequalities, Part II: Differentiable nonlinear systems [J]. SIAM Journal on Numerical Analysis, 1976, 13: 497-513.

[42] 修乃华, 罗自炎. 半定规划 [M]. 北京: 北京交通大学出版社, 2014.

[43] Hestenes M R. Multiplier and gradient methods [J]. Journal of Optimization Theory and Applications, 1969, 6: 303-320.

[44] Powell M J D. A method for nonlinear constraints in minimization problems [M]//Optimization. London: Academic Press, 1969: 283-298.

[45] Gould N I M, Loh Y, Robinson D P. A filter method with unified step computation for nonlinear optimization [J]. SIAM Journal on Optimization, 2014, 24: 175-209.

[46] Wang X, Yuan Y X. An augmented Lagrangian trust region method for equality constrained optimization [J]. Optimization Methods and Software, 2014, 16: 1-24.

[47] Wilson R B. A simplicial algorithm for concave programming [D]. Boston: Harvard Business School, 1963.

[48] Han S P. Superlinearly convergent variable metric algorithms for general nonlinear programming problems [J]. Mathematical Programming, 1976, 11: 263-282.

[49] Powell M J D. Algorithms for nonlinear constraints that use Lagrangian functions [J]. Mathematical Programming, 1978, 14: 224-248.

[50] Lawrence C T, Tits A L. A computationally efficient feasible sequential quadratic programming algorithm [J]. SIAM Journal on Optimization, 2001, 11: 1092-1118.

[51] Jian J B, Chen Q F, Huang Z W. A superlinearly convergent SQP method without boundedness assumptions on any of the iterative sequences [J]. Journal of Computational and Applied Mathematics, 2014, 262: 115-128.

[52] Jian J B, Li J, Zheng H Y, et al. A superlinearly convergent norm-relaxed method of quasi-strongly sub-feasible direction for inequality constrained minimax problems [J]. Applied Mathematics and Computation, 2014, 226: 673-690.

[53] Fletcher R, Leyffer S. Nonlinear programming without a penalty function [J]. Mathematical Programming, 2002, 91: 239-269.

[54] Gould N I M, Toint P H L. Nonlinear programming without a penalty function or a filter [J]. Mathematical Programming, 2009, 122: 155-196.

[55] Liu X W, Yuan Y X. A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained [J]. SIAM Journal on Optimization, 2011, 21: 545-571.

[56] Bazaraa M S, Sherali H D, Shetty C M. Nonlinear Programming: Theory and Algorithms [M]. New York: John Wiley and Sons, 1993.

[57] Gao Z Y, He G P, Wu F. Sequential systems of linear equations algorithm for nonlinear optimization problems with general constraints [J]. Journal of Optimization Theory and Applications, 1997, 95: 371-397.

[58] Qi H D, Qi L Q. A new QP-free, globally convergent, locally superlinearly convergent algorithm for inequality constrained optimization [J]. SIAM Journal on Optimization, 2000, 11: 113-132.

[59] Yamashita H. A globally convergent primal-dual interior point method for constrained optimization [J]. Optimization Methods and Software, 1998, 11: 443-469.

[60] Jian J B, Guo C H, Tang C M, et al. A new superlinearly convergent algorithm of combining QP subproblem with system of linear equations for nonlinear optimization [J]. Journal of Computational and Applied Mathematics, 2014, 273: 88-102.

[61] Li J L, Huang R S, Jian J B. A superlinearly convergent QP-free algorithm for mathematical programs with equilibrium constraints [J]. Applied Mathematics and Computation, 2015, 269: 885-903.