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

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

CLC Number:

O221

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.

References

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]	LI Chaoqiong, LI Feng. A partial parallel splitting LQP alternating direction method of multipliers for solving monotone variational inequalities [J]. Operations Research Transactions, 2020, 24(1): 101-114.
[2]	JIAN Jinbao, LAO Yixian, CHAO Miantao, MA Guodong. ADMM-SQP algorithm for two blocks linear constrained nonconvex optimization [J]. Operations Research Transactions, 2018, 22(2): 79-92.
[3]	FENG Junkai, ZHANG Haibin, QIN Yuan, ZHANG Kaili. An inexact parallel alternating direction method for structured variational inequalities [J]. Operations Research Transactions, 2018, 22(2): 18-30.
[4]	YANG Junfeng. An algorithmic review for total variation regularized data fitting problems in image processing [J]. Operations Research Transactions, 2017, 21(4): 69-83.
[5]	ZHANG Yanli, MA Xinshun. A class recourse stochastic programs algorithm with MaxEMin evaluation [J]. Operations Research Transactions, 2016, 20(4): 52-60.
[6]	WAN Rui, XU Zi. On the linear convergence of the general alternating proximal gradient method for convex minimization [J]. Operations Research Transactions, 2014, 18(3): 1-12.
[7]	CHENG Cong, ZHANG Liwei. Newton methods for inverse problems of quadratic programming [J]. Operations Research Transactions, 2014, 18(3): 60-70.
[8]	SUN Xiaoling, LI Duan. Recent advances in integer programming [J]. Operations Research Transactions, 2014, 18(1): 39-68.
[9]	DAI Yuhong, LIU Xinwei. Advances in linear and nonlinear programming [J]. Operations Research Transactions, 2014, 18(1): 69-92.
[10]	ZHANG Yu-Nong, LI Xue-Zhong, ZHANG Zhi-Jun, LI Jun. An LVI-based Numerical Algorithm for Solving Quadratic Programming Problems [J]. Operations Research Transactions, 2012, 16(1): 21-30.

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

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 10

Recommended Articles

Metrics

Comments