二次规划逆问题的牛顿方法

运筹学学报 ›› 2014, Vol. 18 ›› Issue (3): 60-70.

二次规划逆问题的牛顿方法

程聪^1,*, 张立卫²

1.东北大学物流优化与控制研究所, 沈阳 110819, 2.大连理工大学数学科学学院, 辽宁大连 116024

出版日期:2014-09-15 发布日期:2014-09-15
通讯作者: 程聪 E-mail:ccheng@tli.neu.edu.cn
基金资助:
国家自然科学基金 (No. 71032004)

Newton methods for inverse problems of quadratic programming

CHENG Cong^1,*, ZHANG Liwei²

1. The Logistics Institute, Northeastern University, Shenyang 110819, China, 2. School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, Liaoning, China

Online:2014-09-15 Published:2014-09-15

摘要/Abstract

摘要： 针对二次规划逆问题, 将其表达为带有互补约束的锥约束优化问题. 借助于对偶理论, 将问题转化为变量更少的线性互补约束非光滑优化问题. 通过扰动的方法求解转化后的问题并证明了收敛性. 采用非精确牛顿法求解扰动问题, 给出了算法的全局收敛性与局部二阶收敛速度. 最后通过数值实验验证了该算法的可行性.

关键词: 二次规划逆问题, 扰动方法, 收敛性, 非精确牛顿法

Abstract: This paper is devoted to the study of the inverse quadratic programming. The problem can be formulated as a cone constrained optimization problem with a complementary constrain. Based on the theory of duality, we reformulate this problem as a linear complementarity constrained nonsmooth optimization problem with fewer variables than the original one. We introduce a perturbation approach to solve the reformulated problem and demonstrate the global convergence. An inexact Newton method is constructed to solve the perturbation problem and its global convergence and local quadratic rate can be obtained. In the end, our numerical experiment results show the feasibility of this method.

Key words: inverse semi-definite quadratic programming problems, perturbation approach, the convergence, inexact Newton method

中图分类号:

O221

程聪, 张立卫. 二次规划逆问题的牛顿方法[J]. 运筹学学报, 2014, 18(3): 60-70.

CHENG Cong, ZHANG Liwei. Newton methods for inverse problems of quadratic programming[J]. Operations Research Transactions, 2014, 18(3): 60-70.

参考文献

Rockafellar R T, Wets R J-B. Variational Analysis [M]. Berlin: Springer-Verlag, 1998.

Marlow B. Inverse problems [EB/OL]. [2013-10-21]. http://www. inverse-problems. com.
Engl H W, Hanke M, Neubauer A. Regularization of Inverse Problems [M]. Dordrecht: Kluwer Academic Publisher Group, 1996.
Tarantola A. Inverse Problem Theory: Methods for Data Fitting and Model Parameter Estimation [M]. Amsterdam: Elsevier, 1987.
Burton D, Toint Ph L. On an instance of the inverse shortest paths problem [J]. Mathematical Programming, 1992, 53: 45-61.
Burton D, Toint Ph L. On the use of an inverse shortest paths algorithm for recovering linearly correlated costs [J]. Mathematical Programming, 1994, 63: 1-22.
Carr S C, Lovejoy W S. The inverse newsvendor problem: choosing an optimal demand portfolio for capacitated resources [J]. Management Science, 2000, 46(7): 912-927.
Dembo R, Merkoulovitch L, Rosen D. Images from a portfolio [R]. Vancouver: Algorithmics Research center, 1998.
Ahuja R K, Orlin J B. A faster algorithm for the inverse spanning tree problem [J]. J Algorithms, 2000, 34: 177-193.
Ahuja R K, Orlin J B. Combinatorial algorithms for inverse network flow problems [J]. Networks, 2002, 40: 181-187.
Zhang J, Liu Z. Calculating some inverse linear programming problems [J]. J Comput Appl Math, 1996, 72: 261-273.
Huang S, Liu Z. On the inverse problem of linear programming and its application to minimum weight perfect k-matching [J]. Eur J Oper Res, 1999, 112: 421-426.
Ahuja R K, Orlin J B. Inverse optimization [J]. Operations Research, 2001, 49: 771-783.
Zhang J, Liu Z. A further study on inverse linear programming problems [J]. J Comput Appl Math, 1999, 106: 345-359.
Zhang Y, Zhang L W, Wu Y. The augmented Lagrangian method for a type of inverse quadratic programming problems over second-order cones [J]. Top, 2011.
Qi L, Sun D, Zhou G. A new look at smoothing Newton methods for nonlinear complementarity problems and box constrained variational inequalities [J]. Mathematical Programming, 2000, 87: 1-35.
Rockafellar R T, Wets R J-B. Variational Analysis [M]. Berlin: Springer-Verlag, 1998.

[1]	黎健玲, 张辉, 杨振平, 简金宝. 非线性半定规划一个全局收敛的无罚无滤子SSDP算法[J]. 运筹学学报, 2018, 22(4): 1-16.
[2]	田明雨, 杨永建. 求解多项式规划的一个全局最优化算法[J]. 运筹学学报, 2018, 22(4): 79-88.
[3]	陈香萍. 谱HS投影算法求解非线性单调方程组[J]. 运筹学学报, 2018, 22(3): 15-27.
[4]	Tsegay Giday Woldu, 张海斌, 张鑫, 张芳. 一种求解非线性无约束优化问题的充分下降的共轭梯度法[J]. 运筹学学报, 2018, 22(3): 59-68.
[5]	邵淑婷, 杜守强. 求解一类特殊非光滑极大值函数方程的光滑保守DPRP共轭梯度法[J]. 运筹学学报, 2018, 22(3): 69-78.
[6]	陈中文, 赵奇, 卞凯. 非线性半定规划的逐次线性化柔性惩罚法[J]. 运筹学学报, 2017, 21(2): 84-100.
[7]	杭丹, 颜世建. 非单调带参数Perry-Shanno无记忆拟牛顿法的收敛性[J]. 运筹学学报, 2016, 20(4): 85-92.
[8]	霍永亮. 极大极小随机规划逼近问题最优解集和最优值的稳定性[J]. 运筹学学报, 2016, 20(1): 75-83.
[9]	马国栋, 简金宝. 不等式约束优化一个可行序列线性方程组算法[J]. 运筹学学报, 2015, 19(4): 48-58.
[10]	濮定国, 尚有林, 王关琳. 无罚函数和滤子的一个新的QP-free方法[J]. 运筹学学报, 2015, 19(3): 48-56.
[11]	陈宁, 孙文瑜, 袁锦昀. 解线性等式约束优化问题的模式搜索过滤集方法[J]. 运筹学学报, 2015, 19(3): 96-107.
[12]	党亚峥, 薛中会. 凸可行问题的平行近似次梯度投影算法[J]. 运筹学学报, 2015, 19(1): 117-124.
[13]	刘媛媛, 欧宜贵. 基于非单调技术的ODE型混合方法[J]. 运筹学学报, 2013, 17(3): 11-22.
[14]	濮定国，刘爱兰，尚有林，冯爱芬，孙振洋. 无罚函数和滤子的QP-free非可行域方法[J]. 运筹学学报, 2013, 17(1): 106-116.
[15]	濮定国, 尚有林, 冯爱芬, 孙振洋. 非凸非精确线搜索时Broyden算法的收敛性[J]. 运筹学学报, 2012, 16(3): 100-108.