Article Contents
Article Contents

# An alternating direction method for solving a class of inverse semi-definite quadratic programming problems

• In this paper, we propose an alternating-direction-type numerical method to solve a class of inverse semi-definite quadratic programming problems. An explicit solution to one direction subproblem is given and the other direction subproblem is proved to be a convex quadratic programming problem over positive semi-definite symmetric matrix cone. We design a spectral projected gradient method for solving the quadratic matrix optimization problem and demonstrate its convergence. Numerical experiments illustrate that our method can solve inverse semi-definite quadratic programming problems efficiently.
Mathematics Subject Classification: Primary: 90C20, 90C22; Secondary: 49M20.

 Citation:

•  [1] M. Afonso, J. Bioucas-Dias and M. Figueiredo, Fast image recovery using variable splitting and constrained optimization, IEEE Transactions on image processing, 19 (2010), 2345-2356.doi: 10.1109/TIP.2010.2047910. [2] R. Ahuja and J. Orlin, Inverse optimization, Operations Research, 49 (2001), 771-783.doi: 10.1287/opre.49.5.771.10607. [3] R. Ahuja and J. Orlin, Combinatorial algorithms for inverse network flow problems, Networks, 40 (2002), 181-187.doi: 10.1002/net.10048. [4] J. Barzilai and J. M. Borwein, Two point step size gradient methods, IMA Journal of Numerical Analysis, 8 (1988), 141-148.doi: 10.1093/imanum/8.1.141. [5] D. Bertsekas, On the Goldstein-Levitin-Polyak gradient projection method, IEEE Transactions on Automatic Control, 21 (1976), 174-184.doi: 10.1109/TAC.1976.1101194. [6] E. Birgin, J. Martínez and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM Journal on Optimization, 10 (2000), 1196-1211.doi: 10.1137/S1052623497330963. [7] E. Birgin, J. Martínez and M. Raydan, Spectral projected gradient methods: reviews and perspective, Available from: http://www.ime.usp.br/~egbirgin/publications/bmr5.pdf. [8] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends in Machine Learning, 3 (2011), 1-122.doi: 10.1561/2200000016. [9] W. Burton and P. Toint, On an instance of the inverse shortest paths problem, Mathematical Programming, 53 (1992), 45-61.doi: 10.1007/BF01585693. [10] M. Cai, X. Yang and J. Zhang, The complexity analysis of the inverse center location problem, Journal of Global Optimization, 15 (1999), 213-218.doi: 10.1023/A:1008360312607. [11] Y. Dai and L. Liao, R-linear convergence of the Barzilai and Borwein gradient method, IMA Journal on Numerical Analysis, 22 (2002), 1-10.doi: 10.1093/imanum/22.1.1. [12] J. Douglas and H. Rachford, On the numerical solution of the heat conduction problem in two and three space variables, Transactions of the American Mathematical Society, 82 (1956), 421-439.doi: 10.1090/S0002-9947-1956-0084194-4. [13] A. Friedlander, J. M. Martínez, B. Molina and M. Raydan, Gradient method with retards and generalizations, SIAM Journal on Numerical Analysis, 36 (1999), 275-289.doi: 10.1137/S003614299427315X. [14] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite-element approximations, Computers & Mathematics with Applications, 2 (1976), 17-40.doi: 10.1016/0898-1221(76)90003-1. [15] R. Glowinski and P. Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics, SIAM, Philadelphia, 1989.doi: 10.1137/1.9781611970838. [16] T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems, SIAM Journal on Imaging Sciences, 2 (2009), 323-343.doi: 10.1137/080725891. [17] C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results, Journal of Combinatorial Optimization, 8 (2004), 329-361.doi: 10.1023/B:JOCO.0000038914.26975.9b. [18] B. He, L. Liao, D. Han and H. Yang, A new inexact alternating direction method for monotone variational inequalities, Mathematical Programming, 92 (2002), 103-118.doi: 10.1007/s101070100280. [19] B. He, M. Tao and X. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM Journal on Optimization, 22 (2012), 313-340.doi: 10.1137/110822347. [20] G. Iyengar and W. Kang, Inverse conic programming and applications, Operations Research Letters, 33 (2005), 319-330.doi: 10.1016/j.orl.2004.04.007. [21] D. Peaceman and H. Rachford, The numerical solution of parabolic elliptic differential equations, Journal of the Society for Industrial and Applied Mathematics, 3 (1955), 28-41.doi: 10.1137/0103003. [22] M. Raydan, On the Barzilai and Borwein choice of steplength for the gradient method, IMA Journal of Numerical Analysis, 13 (1993), 321-326.doi: 10.1093/imanum/13.3.321. [23] M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem, SIAM Journal on Optimization, 7 (1997), 26-33.doi: 10.1137/S1052623494266365. [24] R. Rockafellar and R. Wets, Variational Analysis, Springer-Verlag, New York, 1998.doi: 10.1007/978-3-642-02431-3. [25] D. Sun, J. Sun and L. Zhang, The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming, Mathematical Programming, 114 (2008), 349-391.doi: 10.1007/s10107-007-0105-9. [26] P. Tseng, Applications of a splitting algorithm to decomposition in convex programming and variational inequalities, SIAM Journal on Control and Optimization, 29 (1991), 119-138.doi: 10.1137/0329006. [27] P. Tseng, Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming, Mathematical Programming, 48 (1990), 249-263.doi: 10.1007/BF01582258. [28] X. Xiao, L. Zhang and J. Zhang, A smoothing Newton method for a type of inverse semi-definite quadratic programming problem, Journal of Computational and Applied Mathematics, 223 (2009), 485-498.doi: 10.1016/j.cam.2008.01.028. [29] X. Xiao, L. Zhang and J. Zhang, On convergence of augmented Lagrange method for inverse semi-definite quadratic programming problems, Journal of Industrial and Management Optimization, 5 (2009), 319-339.doi: 10.3934/jimo.2009.5.319. [30] J. Yang and Y. Zhang, Alternating direction algorithms for $l_1$-problems in compressive sensing, SIAM Journal on Scientific Computing, 33 (2011), 250-278.doi: 10.1137/090777761. [31] J. Zhang and Z. Liu, Calculating some inverse linear programming problems, Journal of Computational and Applied Mathematics, 72 (1996), 261-273.doi: 10.1016/0377-0427(95)00277-4. [32] J. Zhang and Z. Liu, A further study on inverse linear programming problems, Journal of Computational and Applied Mathematics, 106 (1999), 345-359.doi: 10.1016/S0377-0427(99)00080-1. [33] J. Zhang, Z. Liu and Z. Ma, Some reverse location problems, European Journal of Operations Research, 124 (2000), 77-88.doi: 10.1016/S0377-2217(99)00122-8. [34] J. Zhang and Z. Ma, Solution structure of some inverse combinatorial optimization problems, Journal of Combinatorial Optimization, 3 (1999), 127-139.doi: 10.1023/A:1009829525096. [35] J. Zhang and L. Zhang, An augmented Lagrangian method for a class of inverse quadratic programming problems, Applied Mathematics and Optimization, 61 (2010), 57-83.doi: 10.1007/s00245-009-9075-z.