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

运筹学学报 ›› 2013, Vol. 17 ›› Issue (2): 89-106.

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

王云娟^1,*，朱德通²

1. 上海立信会计学院数学与信息学院，上海 201620 2. 上海师范大学商学院，上海 200234

收稿日期:2011-03-24 出版日期:2013-06-15 发布日期:2013-06-15
通讯作者: 王云娟 E-mail:yunjuanwang@163.com
基金资助:
国家自然科学基金 (No．10871130)

Affine scaling interior Levenberg-Marquardt method for KKT systems

WANG Yunjuan^1,*,ZHU Detong²

1. School of Mathematics and Information, Shanghai Lixin University of Commerce, Shanghai 201620, China 2. Business School, Shanghai Normal University, Shanghai 200234, China

Received:2011-03-24 Online:2013-06-15 Published:2013-06-15

摘要/Abstract

摘要： 提供了一类新的结合非单调内点回代线搜索技术的仿射变换Levenberg-Marquardt法解Karush-Kuhn-Tucker（KKT）系统. 基于由KKT系统转化得到的等价的部分变量具有非负约束的最小化问题，建立了Levenberg-Marquardt方程. 证明了算法不仅具有整体收敛性，而且在合理的假设条件下，算法具有超线性收敛速率. 数值结果验证了算法的实际有效性.

关键词: KKT系统, Levenberg-Marquardt法, 仿射变换, 内点, 收敛

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

中图分类号:

O221.2

王云娟，朱德通. 仿射变换内点Levenberg-Marquardt法解KKT系统[J]. 运筹学学报, 2013, 17(2): 89-106.

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

参考文献

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]	苗小楠, 顾剑, 肖现涛. 求解非光滑方程组的三次正则化方法[J]. 运筹学学报, 2019, 23(2): 17-30.
[2]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[3]	田明雨, 杨永建. 求解多项式规划的一个全局最优化算法[J]. 运筹学学报, 2018, 22(4): 79-88.
[4]	陈香萍. 谱HS投影算法求解非线性单调方程组[J]. 运筹学学报, 2018, 22(3): 15-27.
[5]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[6]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[7]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[8]	梁娜, 杜守强. 求解对称张量绝对值方程问题的非光滑牛顿法[J]. 运筹学学报, 2017, 21(3): 95-102.
[9]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[10]	陈元媛, 高岩, 刘志敏, 杜守强. 一类特殊优化问题的光滑梯度法[J]. 运筹学学报, 2017, 21(2): 119-125.
[11]	田朝薇, 张立卫. 从常步长梯度方法的视角看不可微凸优化增广Lagrange方法的收敛性[J]. 运筹学学报, 2017, 21(1): 111-117.
[12]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[13]	杨洋, 罗洪林, 罗慧林. 关于半定规划的一种宽邻域不可行内点算法的注记[J]. 运筹学学报, 2016, 20(2): 79-87.
[14]	霍永亮. 极大极小随机规划逼近问题最优解集和最优值的稳定性[J]. 运筹学学报, 2016, 20(1): 75-83.
[15]	刘长河, 尚有林, 李锦睿. 基于一类新方向的宽邻域路径跟踪内点算法[J]. 运筹学学报, 2016, 20(1): 43-53.