• 论文 • 上一篇    

一类不可微二次规划逆问题

李丽丹1, 张立卫2, 张宏伟2   

  1. 1. 辽宁工程技术大学理学院, 阜新 123000;
    2. 大连理工大学数学科学学院, 大连 116024
  • 收稿日期:2019-11-18 发布日期:2021-05-13
  • 基金资助:
    国家自然科学基金(No.11971089,11731013)和辽宁省教育厅项目(No.LJ2020QNL008)资助.

李丽丹, 张立卫, 张宏伟. 一类不可微二次规划逆问题[J]. 计算数学, 2021, 43(2): 227-240.

Li Lidan, Zhang Liwei, Zhang Hongwei. A TYPE OF NON-DIFFERENTIABLE INVERSE QUADRATIC PROGRAMMING PROBLEMS[J]. Mathematica Numerica Sinica, 2021, 43(2): 227-240.

A TYPE OF NON-DIFFERENTIABLE INVERSE QUADRATIC PROGRAMMING PROBLEMS

Li Lidan1, Zhang Liwei2, Zhang Hongwei2   

  1. 1. College of Science, Liaoning Technical University, Fuxin 123000, China;
    2. School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China
  • Received:2019-11-18 Published:2021-05-13
本文求解了一类二次规划的逆问题,具体为目标函数是矩阵谱范数与向量无穷范数之和的最小化问题.首先将该问题转化为目标函数可分离变量的凸优化问题,提出用G-ADMM法求解.并结合奇异值阈值算法,Moreau-Yosida正则化算法,matlab优化工具箱的quadprog函数来精确求解相应的子问题.而对于其中一个子问题的精确求解过程中发现其仍是目标函数可分离变量的凸优化问题,由于其变量都是矩阵,所以采用适合多个矩阵变量的交替方向法求解,通过引入新的变量,使其每个子问题的解都具有显示表达式.最后给出采用的G-ADMM法求解本文问题的数值实验.数据表明,本文所采用的方法能够高效快速地解决该二次规划逆问题.
In this paper, a type of inverse quadratic programming problem is considered, which is a minimization problem of the sum of the matrix spectrum norm and the vector infinite norm. Firstly, the problem is transformed into a convex optimization problem with the objective function separable, and G-ADMM method is proposed to solve it. Then, we use the singular value threshold method, Moreau-Yosida regularization algorithm and the quadprog function in MATLAB optimization toolbox to solve the corresponding subproblem accurately. It is found that one subproblem is still a convex optimization problem with separable variables objective function. Because its variables are all matrices, so we adopt the alternative direction method suitable for multiple matrix variables to solve it. By introducing a new variable, we obtain that the solution of each subproblem has a display expression. Finally, the convergence analysis and numerical experiments of the G-ADMM method are given. The numerical experiments show that this method can solve the inverse quadratic programming problem efficiently and quickly.

MR(2010)主题分类: 

()
[1] Burton D, Toint P L. On an instance of the inverse shortest paths problem[J]. Math. Prog., 1992, 53:45-61.
[2] Burton D, Toint P L. On the use of an inverse shortest paths algorithm for recovering linearly correlated costs[J]. Math. Prog., 1994, 63:1-22.
[3] Ahuja R K, Orlin J B. A faster algorithm for the inverse spanning tree problem[J]. J.Algorithm., 2000, 34(1):177-193.
[4] Scott C, William L. The inverse newsvendor problem:Choosing an optimal demand portfolio for capacitated resources[J]. Manage. Sci., 2000, 46:912-927.
[5] Heuberger C. Inverse combinatorial optimization:A survey on problems, methods and results[J]. J. Combin. Optim., 2004, 8:329-361.
[6] Zhang J, Liu Z. Calculating some inverse linear programming problems[J]. J. Comput. Appl. Math., 1996, 72:261-273.
[7] Zhang J, Liu Z. A further study on inverse linear programming problems[J]. J. Comput. Appl. Math., 1999, 106:345-359.
[8] Jiang Y, Xiao X, Zhang L, et al. A perturbation approach for a type of inverse linear programming problems[J]. Int. J. Comput. Math., 2011, 88(3):508-516.
[9] Iyengar G, Kang W. Inverse conic programming with applications[J]. Oper. Res. Lett., 2005, 33:319-330.
[10] Zhang J, Zhang L. An augmented lagrangian method for a class of inverse quadratic programming problems[J]. Appl. Math. Optim., 2010, 61:57-83.
[11] 卢越, 张继宏, 张立卫. 一类二次规划逆问题的交替方向数值方法[J]. 运筹学学报, 2014, 18(2):1-16.
[12] Xiao X, Zhang L, Zhang J. A smoothing newton method for a type of inverse semi-definite quadratic programming problem[J]. J. Comput. Appl. Math., 2009, 223:485-498.
[13] Wu J, Zhang Y, Zhang L, et al. A sequential convex program approach to an inverse linear semidefinite programming problem[J]. Asia. Pac. J. Oper. Res., 2016, 33(4):1-26.
[14] Lu Y, Huang M, Zhang Y, et al. A nonconvex admm for a class of sparse inverse semidefinite quadratic programming problems[J]. Optimization, 2019, 68(6):1075-1105.
[15] He B, Tao M, Yuan X. Alternating direction method with gaussian back substitution for separable convex programming[J]. SIAM J. Opiomiz., 2012, 22(2):313-340.
[16] Rockafellar R T. Convex analysis[M]. Princeton:Princeton University Press, 1970.
[17] John D, Shai S S, Yoram S, et al. Efficient projections onto the 1-ball for learning in high dimensions[C]//Proceedings of the 25th International Conference on Machine Learning.[S.l.:s.n.], 2008.
[18] Hestenes M R. Multiplier and gradient methods[J]. J. Optimiz Theory. App., 1969, 4(5):303-320.
[19] Powell M. A method for nonlinear constraints in minimization problems[M]//R. F. Optimization. New York:Academic Press, 1969:283-298.
[20] Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers[M].[S.l.]:NOW, 2011.
[21] Eckstein J, P.Bertsekas D. On the douglas-rachford splitting method and the proximal point algorithm for maximal monotone operators[J]. Math. Prog., 1992, 55:293-318.
[22] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Comput. Math. Appl., 1976, 2(1):17-40.
[23] Han D, Yuan X. A note on the alternating direction method of multipliers[J]. J. Optim. Theory Appl., 2012, 155:227-238.
[24] Cai X, Han D, Yuan X. The direct extension of admm for three-block separable convex minimization models is convergent when one function is strongly convex[J]. Optimization online, 2014.
[25] Li M, Sun D, Toh K C. A convergent 3-block semi-proximal admm for convex minimization problems with one strongly convex block[J]. Asia. Pac. J. Oper. RES., 2015, 32(04):1550024.
[26] He B, Wang S, Yang H. A modified variable-penalty alternating directions method for monotone variational inequalities[J]. J. Comput. Math, 2003, 21:495-504.
[27] He B S, Yang H, Wang S L. Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities[J]. J. Optim. Theory Appl., 2000, 106:337-356.
[28] 李姣芬, 宋丹丹, 李涛, 等. 核范数和谱范数下广义Sylvester方程最小二乘问题的有效算法[J]. 计算数学, 2017, 39:129-150.
[29] 蔡文银, 徐玲玲. 核范数和谱范数下广义Sylvester方程最小二乘问题的一类改进算法[J]. 计算数学, 2018, 40:387-401.
[1] 蔡文银, 徐玲玲. 核范数和谱范数下广义Sylvester方程最小二乘问题的一类改进算法[J]. 计算数学, 2018, 40(4): 387-401.
[2] 李姣芬, 宋丹丹, 李涛, 黎稳. 核范数和谱范数下广义Sylvester方程最小二乘问题的有效算法[J]. 计算数学, 2017, 39(2): 129-150.
[3] 温朝涛, 陈小山. 矩阵极分解新的数值方法[J]. 计算数学, 2017, 39(1): 23-32.
[4] 高岳林, 魏飞. 一类非负二次整数规划问题的分支定界缩减方法[J]. 计算数学, 2011, 33(3): 233-248.
[5] 陈小山,黎稳. 关于矩阵方程X+A~*X~(-1)A=P的解及其扰动分析[J]. 计算数学, 2005, 27(3): 303-310.
[6] 朱志斌,张可村. 不等式约束优化一个新的SQP算法[J]. 计算数学, 2004, 26(4): 413-426.
[7] 卢战杰,魏紫銮. 边界约束二次规划问题的分解方法[J]. 计算数学, 1999, 21(4): 475-482.
阅读次数
全文


摘要