仿射变换内点Levenberg-Marquardt法解KKT系统

Abstract

Abstract: We develop and analyze a new affine scaling Levenberg-Marquardt method with nonmonotonic interior backtracking line search technique for solving Karush-Kuhn-Tucker (KKT) system. By transforming the KKT system into an equivalent minimization problem with nonnegativity constraints on some of the variables, we establish the Levenberg-Marquardt equation based on this reformulation. Theoretical analysis are given which prove that the proposed algorithm is globally convergent and has a local superlinear convergent rate under some reasonable conditions. The results of numerical experiments are reported to show the effectiveness of the proposed algorithm.

Key words: KKT systems, Levenberg-Marquardt method, affine scaling, interior point, convergence

CLC Number:

O221.2

WANG Yunjuan,ZHU Detong. Affine scaling interior Levenberg-Marquardt method for KKT systems[J]. Operations Research Transactions, 2013, 17(2): 89-106.

References

Facchinei F, Fischer A, Kanzow C. Regularity properties of a semismooth reformlation of variational inequalities [J]. SIAM Journal on Optimization, 1998, 8(3): 850-869.
Fischer A. A special Newton-type optimization method [J]. Optimization, 1992, 24(3-4): 269-284.
Facchinei F, Fischer A, Kanzow C. A semismooth Newton method for variational inequalities: The case of box constraints [C]//{it Complementarity and Variational Problems: State of the Art, Philadelphia: [s.n.], 1997: 76-90.
Qi L Q, Jiang H Y. Semismooth Karush-Kuhn-Tucker equations and convergence analysis of Newton and Quasi-Newton methods for solving these equations [J]. Mathematics of Operations Research, 1997, 22(2): 301-325.
Coleman T F, Li Y Y. An interior trust region approach for nonlinear minimization subject to bounds [J]. SIAM Journal on Optimization, 1996, 6(2): 418-445.
Clarke F H. Optimization and nonsmooth analysis [M]. New York: John Wiley and Sons, 1983.
Zhu D T. Affine scaling interior Levenberg-Marquardt method for bound-constrained semismooth equations under local error bound conditions [J]. Journal of Compututional and Applied Mathematics, 2008, 219(1): 198-215.
Gripp L, Lampariello F, Lucidi L. A nonmonotone line search technique for Newton's methods [J]. SIAM Journal on Numerical Analysis, 1986, 23(4): 707-716.
Qi L Q. Convergence analysis of some algorithms for solving nonsmooth equations [J]. Mathematics of Operations Research, 1993, 18(1): 227-244.
Qi L Q, Sun J. A nonsmooth version of Newton's method [J]. Mathematical Programming, 1993, 58(1-3): 353-367.
Pang J S, Qi L Q. Nonsmooth equations: motivation and algorithms [J]. SIAM Journal on Optimization, 1993, 3(3): 443-465.
Fischer A. Solution of monotone complementarity problems with locally Lipschitzian functions [J]. Mathematical Programming, 1997, 76(3): 513-532.
Robinson S M. Strongly regular generalized equations [J]. Mathematics of Operations Research, 1980, 5(1): 43-62.
Liu J M. Strong stability in variational inequalities [J]. SIAM Journal on Control and Optimization, 1995, 33(3): 725-749.
Bertsekas D P. Constrained optimization and Lagrange multiplier methods [M]. New York: Academic Press, 1982.
Yuan Y Y. A modified BFGS algorithm for unconstrained optimization [J]. IMA Journal of Numerical Analysis, 1991, 11(3): 325-332.

[1]	MIAO Xiaonan, GU Jian, XIAO Xiantao. A cubic regularization method for solving nonsmooth equations [J]. Operations Research Transactions, 2019, 23(2): 17-30.
[2]	LI Jianling, ZHANG Hui, YANG Zhenping, JIAN Jinbao. A globally convergent SSDP algorithm without a penalty function or a filter for nonlinear semidefinite programming [J]. Operations Research Transactions, 2018, 22(4): 1-16.
[3]	TIAN Mingyu, YANG Yongjian. A global optimization algorithm for polynomial programming [J]. Operations Research Transactions, 2018, 22(4): 79-88.
[4]	CHEN Xiangping. Spectral HS projection algorithm for solving nonlinear monotone equations [J]. Operations Research Transactions, 2018, 22(3): 15-27.
[5]	. A sufficient descent conjugate gradient method for nonlinear unconstrained optimization problems [J]. Operations Research Transactions, 2018, 22(3): 59-68.
[6]	SHAO Shuting, DU Shouqiang. Smoothing cautious DPRP conjugate gradient method for solving a kind of special nonsmooth equations with max-type function [J]. Operations Research Transactions, 2018, 22(3): 69-78.
[7]	HE Bingsheng. My 20 years research on alternating directions method of multipliers [J]. Operations Research Transactions, 2018, 22(1): 1-31.
[8]	LIANG Na, DU Shouqiang. Nonsmooth Newton method for solving symmetrical tensor absolute value equations [J]. Operations Research Transactions, 2017, 21(3): 95-102.
[9]	CHEN Zhongwen, ZHAO Qi, BIAN Kai. A successive linearization method with flexible penalty for nonlinear semidefinite programming [J]. Operations Research Transactions, 2017, 21(2): 84-100.
[10]	CHEN Yuanyuan, GAO Yan, LIU Zhimin, DU Shouqiang. The smoothing gradient method for a kind of special optimization problem [J]. Operations Research Transactions, 2017, 21(2): 119-125.
[11]	TIAN Zhaowei, ZHANG Liwei. A look at the convergence of the augmented Lagrange method for nondifferentiable convex programming from the view of a gradient method with constant stepsize [J]. Operations Research Transactions, 2017, 21(1): 111-117.
[12]	HANG Dan, YAN Shijian. Convergence of nonmonotonic Perry-Shanno's memoryless quasi-Newton method with parameters [J]. Operations Research Transactions, 2016, 20(4): 85-92.
[13]	HUO Yongliang. Stability of optimal solution set and optimal value for minimax stochastic programming approximation problems [J]. Operations Research Transactions, 2016, 20(1): 75-83.
[14]	L\"{U} Wei, SUI Ruirui, FENG Enmin. A modification of Newton method with convergence of order 2+\sqrt{6} [J]. Operations Research Transactions, 2015, 19(4): 83-96.
[15]	MA Guodong, JIAN Jinbao. A feasible sequential systems of linear equations algorithm for inequality constrained optimization [J]. Operations Research Transactions, 2015, 19(4): 48-58.

Affine scaling interior Levenberg-Marquardt method for KKT systems

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments