一类二次规划逆问题的交替方向数值方法

运筹学学报 ›› 2014, Vol. 18 ›› Issue (2): 1-16.

• 运筹学 • 下一篇

一类二次规划逆问题的交替方向数值方法

卢越¹, 张继宏¹, 张立卫^1,*

1. 大连理工大学数学科学学院, 辽宁大连 116024

出版日期:2014-06-15 发布日期:2014-06-15
通讯作者: 张立卫 E-mail:lwzhang@dlut.edu.cn
基金资助:
国家自然科学基金 (Nos. 91130007, 91330206)

An alternating direction numerical method for a type of inverse quadratic programming problem

LU Yue¹, ZHANG Jihong¹, ZHANG Liwei^1,*

1. Institute of Operations Research and Control Theory, School of Mathematics Sciences, Dalian University of Technology, Dalian 116024, Liaoning, China

Online:2014-06-15 Published:2014-06-15

摘要/Abstract

摘要： 考虑求解一类二次规划逆问题的交替方向数值算法. 首先给出矩阵变量子问题解的显示表达式，而后构造了两个求解向量变量子问题近似解的数值算法，其中一个算法基于不动点原理，另一算法则应用半光滑牛顿法. 数值实验表明，所提出的算法能够快速高效地求解二次规划逆问题.

关键词: 逆问题, 交替方向法, 二次规划, 半光滑牛顿法

Abstract: An alternating direction numerical method for a type of inverse quadratic programming problem is considered, we first give an explicit formula of the solution to the matrix-variable sub-problem, and provide two algorithms for finding an approximate solution to the vector-variable subproblem. One of these two algorithms is based on the fixed point theorem and the other is a semi-smooth Newton method. Numerical experiments show the efficiency and effectiveness of the proposed algorithm for inverse quadratic programming problems.

Key words: inverse problem, alternating direction method, quadratic programming, semi-smooth Newton method

中图分类号:

O221

卢越, 张继宏, 张立卫. 一类二次规划逆问题的交替方向数值方法[J]. 运筹学学报, 2014, 18(2): 1-16.

LU Yue, ZHANG Jihong, ZHANG Liwei. An alternating direction numerical method for a type of inverse quadratic programming problem[J]. Operations Research Transactions, 2014, 18(2): 1-16.

参考文献

Tarantola A. Inverse Problem Theory: Method for Data Fatting 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, 467: 912-927.
Dembo R, Merkoulovitch L, Rosen D. Images from a portfolio [R]. Toronto: Algorithmics, 1998.
Ahuja R K, Orlin J B. A faster algorithm for the inverse spanning tree problem [J]. Journal of Algorithms, 2000, 34: 177-193.
Ahuja R K, Orlin J B. Combinatorial algorithms for inverse network flow problems [J]. Networks, 2002, 40: 181-187.
Heuberger C. Inverse combinatorial optimization: a survey on problem, methods and results [J]. Journal of Combinatorial Optimization, 2004, 8: 329-361.
Zhang J, Liu Z. Calculating some inverse linear programming problems [J]. Journal of Computational and Applied Mathematics, 1996, 72: 261-273.
Zhang J, Liu Z. A further study on inverse linear programming problems [J]. Journal of Computational and Applied Mathematics, 1999, 106: 345-359.
Ahuja R K, Orlin J B. Inverse optimization [J]. Operations Research, 2001, 49: 771-783.
Zhang J, Zhang L W. An augmented Lagrangian method for a class of inverse quadratic programming problems [J]. Applied Mathematics & Optimization, 2010, 61: 57-83.
Xiao X, Zhang L W. A smoothing Newton method for a type of IQP problems [J]. Journal of Computational Mathematics, 2009, 27: 787-801.

肖现涛. 求解半定约束二次规划逆问题的数值方法 [D]. 大连: 大连理工大学，2009.
张立卫, 单峰. 最优化方法 [M]. 北京: 科学出版社, 2010.
Xiao X, Zhang L W. A smoothing Newton method for a type of IQP problems [J]. Journal of Computational Mathematics, 2009, 27: 787-801.
Facchinei F, Pang J S. Finite-Dimensional Variational Inequalities and Complementarity Problem [M]. New York: Springer-Verlag, 2003.
Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers [J]. Foundations and Trends in Machine Learning, 2010, 3: 1-122.
Grant M, Boyd S. CVX: Matlab software for disciplined convex programming, version 1.22 [EB/OL]. [2013-11-21]. http://cvxr.com/cvx.
Grant M, Boyd S, Graph implementations for nonsmooth convex programs [M]//Recent Advances in Learning and Control, London: Springer-Verlag, 2008, 95-110.
Xiao X, Zhang L W. A smoothing Newton method for a type of IQP problems [J]. Journal of Computational Mathematics, 2009, 27: 787-801.
Strum J F. Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones [J]. Optimization Methods and Software, 1999, 11: 625-653.
Tutuncu R H, Toh K C, Todd M J. Solving semidefinite-quadratic-linear programs using SDPT3 [J]. Mathematical Programming, 2005, 95: 189-217.

[1]	黎超琼, 李锋. 一种求解单调变分不等式的部分并行分裂LQP交替方向法[J]. 运筹学学报, 2020, 24(1): 101-114.
[2]	简金宝, 劳译娴, 晁绵涛, 马国栋. 线性约束两分块非凸优化的ADMM-SQP算法[J]. 运筹学学报, 2018, 22(2): 79-92.
[3]	冯俊锴, 张海斌, 秦嫒, 张凯丽. 解一类结构变分不等式问题的非精确并行交替方向法[J]. 运筹学学报, 2018, 22(2): 18-30.
[4]	何炳生. 我和乘子交替方向法20年[J]. 运筹学学报, 2018, 22(1): 1-31.
[5]	张艳丽, 马新顺. 一类带有MaxEMin评判的补偿型随机规划算法[J]. 运筹学学报, 2016, 20(4): 52-60.
[6]	万芮, 徐姿. 广义交替近似梯度算法的线性收敛分析[J]. 运筹学学报, 2014, 18(3): 1-12.
[7]	程聪, 张立卫. 二次规划逆问题的牛顿方法[J]. 运筹学学报, 2014, 18(3): 60-70.
[8]	孙小玲，李端. 整数规划新进展[J]. 运筹学学报, 2014, 18(1): 39-68.
[9]	张雨浓, 李学忠, 张智军, 李钧. 一种基于LVI求解二次规划问题的数值算法[J]. 运筹学学报, 2012, 16(1): 21-30.
[10]	王华. 解非线性互补问题的非单调可行SQP方法[J]. 运筹学学报, 2011, 15(2): 85-94.

一类二次规划逆问题的交替方向数值方法

An alternating direction numerical method for a type of inverse quadratic programming problem

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 10

编辑推荐

Metrics

本文评价