AAM  >> Vol. 9 No. 1 (January 2020)

    Gauss Back Substitution Alternating Direction Method for a Class of Inverse Quadratic Programming

  • 全文下载: PDF(311KB) HTML    PP.60-71   DOI: 10.12677/AAM.2020.91008  
  • 下载量: 46  浏览量: 82  


李丽丹:大连理工大学数学科学学院,辽宁 大连;辽宁工程技术大学理学院,辽宁 阜新;
张宏伟,张立卫:大连理工大学数学科学学院,辽宁 大连

谱范数无穷范数二次规划G-ADMM法Spectrum Norm Infinite Norm Quadratic Programming G-ADMM Method


本文求解了目标函数为矩阵谱范数与向量无穷范数之和的一类二次规划的逆问题。先将该问题转化为目标函数可分离变量的凸优化问题,提出用 Gauss 回代交替方向法求解该问题。而对于其中一个子问题的求解过程中发现其仍是目标函数可分离变量的凸优化问题,但无法精确求解每个变量,所以采用非精确方法求解该子问题。最后给出采用的 Gauss 回代交替方向法求解本文问题的数值实验。数据表明,本文所采用的方法能够高效快速地解决该二次规划逆问题。

In this paper, we solve the inverse problem of quadratic programming whose objective function is the sum of matrix spectrum norm and vector infinite norm. We transform the problem into a convex optimization problem with objective function separable and propose Gauss back substitution alternating direction method to solve it. We find that one of its subproblems is still a convex optimization problem with objective function separable, but it is impossible to solve every variable accurately. So we use the inexact method to solve the subproblem. Finally, the numerical experiment of the problem in this paper is given. The data shows that the method in this paper can solve the inverse quadratic programming problem efficiently and quickly.

李丽丹, 张宏伟, 张立卫. Gauss回代交替方向法求解一类二次规划逆问题[J]. 应用数学进展, 2020, 9(1): 60-71. https://doi.org/10.12677/AAM.2020.91008


[1] Rockafellar, R.T. (1970) Convex Analysis. Princeton University Press, Princeton.
[3] John, D., Shai, S.S., Yoram, S., et al. (2008) E?cient Projections onto the ?1-Ball for Learning in High Dimensions. Proceedings of the 25th International Conference on Machine Learning, Helsinki, Finland, July 2008, 272-279.
[4] Boyd, S., Parikh, N., Chu, E., Peleato, B. and Eckstein, J. (2011) Distributed Optimization and Statistic al Learning via the Alternating Direction Method of Multipliers. Foundations and Trends in Machine Learning, 3, 1-122.
[5] Eckstein, J. and Bertsekas, D.P. (1992) On the Douglas—Rachford Splitting Method and the Proximal Point Algorithm for Maximal Monotone Operators. Mathematical Programming, 55, 293-318.
[6] Gabay, D. and Mercier, B. (1976) A Dual Algorithm for the Solution of Nonlinear Variational Problems via Finite Element Approximation. Computers Mathematics with Applications, 2, 17-40.
[7] He, B., Tao, M. and Yuan, X. (2012) Alternating Direction Method with Gaussian Back Substitution for Separable Convex Programming. SIAM Journal on Optimization, 22, 313- 340.
[8] He, B., Wang, S. and Yang, H. (2003) A Modi?ed Variable-Penalty Alternating Directions Method for Monotone Variational Inequalities. Journal of Computational Mathematics, 21, 495-504.
[9] He, B.S., Yang, H. and Wang, S.L. (2000) Alternating Direction Method with Self-Adaptive Penalty Parameters for Monotone Variational Inequalities. Journal of Optimization Theory and Applications, 106, 337-356.
[10] 李姣芬, 宋丹丹, 李涛, 等. 核范数和谱范数下广义 Sylvester 方程最小二乘问题的有效算法 [J].
[11] 计算数学, 2017, 39(2): 129-150.
[12] Ng, M.K., Wang, F. and Yuan, X. (2011) Inexact Alternating Direction Methods for Image Recovery. SIAM Journal on Scienti?c Computing, 33, 1643-1668.
[13] Birgin, E.G., Mario, J. and Raydan, M.M. (2000) Nonmonotone Spectral Projected Gradient Methods on Convex Sets. SIAM Journal on Optimization, 10, 1196-1211.