American Institute of Mathematical Sciences

Advanced
  • Previous Article
    A game theoretic approach to coordination of pricing, advertising, and inventory decisions in a competitive supply chain
  • JIMO Home
  • This Issue
  • Next Article
    Finite-time stabilization and $H_\infty$ control of nonlinear delay systems via output feedback
January  2016, 12(1): 317-336. doi: 10.3934/jimo.2016.12.317

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

Yue Lu 1, , Ying-En Ge 2, and  Li-Wei Zhang 1,

1. 

Institute of Operations Research and Control Theory, School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China, China
2. 

School of Transportation and Logistics, Faculty of Infrastructure Engineering, Dalian University of Technology, Dalian 116024, China

Received  April 2013 Revised  January 2015 Published  April 2015

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.
Keywords: Inverse semi-definite programming, spectral projected gradient method, BB-step, alternating direction method, convex semi-definite quadratic programming..
Mathematics Subject Classification: Primary: 90C20, 90C22; Secondary: 49M2.
Citation: Yue Lu, Ying-En Ge, Li-Wei Zhang. An alternating direction method for solving a class of inverse semi-definite quadratic programming problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 317-336. doi: 10.3934/jimo.2016.12.317
References:
[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.  doi: 10.1109/TIP.2010.2047910.  Google Scholar

[2]

R. Ahuja and J. Orlin, Inverse optimization,, Operations Research, 49 (2001), 771.  doi: 10.1287/opre.49.5.771.10607.  Google Scholar

[3]

R. Ahuja and J. Orlin, Combinatorial algorithms for inverse network flow problems,, Networks, 40 (2002), 181.  doi: 10.1002/net.10048.  Google Scholar

[4]

J. Barzilai and J. M. Borwein, Two point step size gradient methods,, IMA Journal of Numerical Analysis, 8 (1988), 141.  doi: 10.1093/imanum/8.1.141.  Google Scholar

[5]

D. Bertsekas, On the Goldstein-Levitin-Polyak gradient projection method,, IEEE Transactions on Automatic Control, 21 (1976), 174.  doi: 10.1109/TAC.1976.1101194.  Google Scholar

[6]

E. Birgin, J. Martínez and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets,, SIAM Journal on Optimization, 10 (2000), 1196.  doi: 10.1137/S1052623497330963.  Google Scholar

[7]

E. Birgin, J. Martínez and M. Raydan, Spectral projected gradient methods: reviews and perspective,, Available from: , ().   Google Scholar

[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.  doi: 10.1561/2200000016.  Google Scholar

[9]

W. Burton and P. Toint, On an instance of the inverse shortest paths problem,, Mathematical Programming, 53 (1992), 45.  doi: 10.1007/BF01585693.  Google Scholar

[10]

M. Cai, X. Yang and J. Zhang, The complexity analysis of the inverse center location problem,, Journal of Global Optimization, 15 (1999), 213.  doi: 10.1023/A:1008360312607.  Google Scholar

[11]

Y. Dai and L. Liao, R-linear convergence of the Barzilai and Borwein gradient method,, IMA Journal on Numerical Analysis, 22 (2002), 1.  doi: 10.1093/imanum/22.1.1.  Google Scholar

[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.  doi: 10.1090/S0002-9947-1956-0084194-4.  Google Scholar

[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.  doi: 10.1137/S003614299427315X.  Google Scholar

[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.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[15]

R. Glowinski and P. Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics,, SIAM, (1989).  doi: 10.1137/1.9781611970838.  Google Scholar

[16]

T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems,, SIAM Journal on Imaging Sciences, 2 (2009), 323.  doi: 10.1137/080725891.  Google Scholar

[17]

C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results,, Journal of Combinatorial Optimization, 8 (2004), 329.  doi: 10.1023/B:JOCO.0000038914.26975.9b.  Google Scholar

[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.  doi: 10.1007/s101070100280.  Google Scholar

[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.  doi: 10.1137/110822347.  Google Scholar

[20]

G. Iyengar and W. Kang, Inverse conic programming and applications,, Operations Research Letters, 33 (2005), 319.  doi: 10.1016/j.orl.2004.04.007.  Google Scholar

[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.  doi: 10.1137/0103003.  Google Scholar

[22]

M. Raydan, On the Barzilai and Borwein choice of steplength for the gradient method,, IMA Journal of Numerical Analysis, 13 (1993), 321.  doi: 10.1093/imanum/13.3.321.  Google Scholar

[23]

M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem,, SIAM Journal on Optimization, 7 (1997), 26.  doi: 10.1137/S1052623494266365.  Google Scholar

[24]

R. Rockafellar and R. Wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[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.  doi: 10.1007/s10107-007-0105-9.  Google Scholar

[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.  doi: 10.1137/0329006.  Google Scholar

[27]

P. Tseng, Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming,, Mathematical Programming, 48 (1990), 249.  doi: 10.1007/BF01582258.  Google Scholar

[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.  doi: 10.1016/j.cam.2008.01.028.  Google Scholar

[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.  doi: 10.3934/jimo.2009.5.319.  Google Scholar

[30]

J. Yang and Y. Zhang, Alternating direction algorithms for $l_1$-problems in compressive sensing,, SIAM Journal on Scientific Computing, 33 (2011), 250.  doi: 10.1137/090777761.  Google Scholar

[31]

J. Zhang and Z. Liu, Calculating some inverse linear programming problems,, Journal of Computational and Applied Mathematics, 72 (1996), 261.  doi: 10.1016/0377-0427(95)00277-4.  Google Scholar

[32]

J. Zhang and Z. Liu, A further study on inverse linear programming problems,, Journal of Computational and Applied Mathematics, 106 (1999), 345.  doi: 10.1016/S0377-0427(99)00080-1.  Google Scholar

[33]

J. Zhang, Z. Liu and Z. Ma, Some reverse location problems,, European Journal of Operations Research, 124 (2000), 77.  doi: 10.1016/S0377-2217(99)00122-8.  Google Scholar

[34]

J. Zhang and Z. Ma, Solution structure of some inverse combinatorial optimization problems,, Journal of Combinatorial Optimization, 3 (1999), 127.  doi: 10.1023/A:1009829525096.  Google Scholar

[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.  doi: 10.1007/s00245-009-9075-z.  Google Scholar

show all references

References:
[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.  doi: 10.1109/TIP.2010.2047910.  Google Scholar

[2]

R. Ahuja and J. Orlin, Inverse optimization,, Operations Research, 49 (2001), 771.  doi: 10.1287/opre.49.5.771.10607.  Google Scholar

[3]

R. Ahuja and J. Orlin, Combinatorial algorithms for inverse network flow problems,, Networks, 40 (2002), 181.  doi: 10.1002/net.10048.  Google Scholar

[4]

J. Barzilai and J. M. Borwein, Two point step size gradient methods,, IMA Journal of Numerical Analysis, 8 (1988), 141.  doi: 10.1093/imanum/8.1.141.  Google Scholar

[5]

D. Bertsekas, On the Goldstein-Levitin-Polyak gradient projection method,, IEEE Transactions on Automatic Control, 21 (1976), 174.  doi: 10.1109/TAC.1976.1101194.  Google Scholar

[6]

E. Birgin, J. Martínez and M. Raydan, Nonmonotone spectral projected gradient methods on convex sets,, SIAM Journal on Optimization, 10 (2000), 1196.  doi: 10.1137/S1052623497330963.  Google Scholar

[7]

E. Birgin, J. Martínez and M. Raydan, Spectral projected gradient methods: reviews and perspective,, Available from: , ().   Google Scholar

[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.  doi: 10.1561/2200000016.  Google Scholar

[9]

W. Burton and P. Toint, On an instance of the inverse shortest paths problem,, Mathematical Programming, 53 (1992), 45.  doi: 10.1007/BF01585693.  Google Scholar

[10]

M. Cai, X. Yang and J. Zhang, The complexity analysis of the inverse center location problem,, Journal of Global Optimization, 15 (1999), 213.  doi: 10.1023/A:1008360312607.  Google Scholar

[11]

Y. Dai and L. Liao, R-linear convergence of the Barzilai and Borwein gradient method,, IMA Journal on Numerical Analysis, 22 (2002), 1.  doi: 10.1093/imanum/22.1.1.  Google Scholar

[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.  doi: 10.1090/S0002-9947-1956-0084194-4.  Google Scholar

[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.  doi: 10.1137/S003614299427315X.  Google Scholar

[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.  doi: 10.1016/0898-1221(76)90003-1.  Google Scholar

[15]

R. Glowinski and P. Tallec, Augmented Lagrangian and Operator-Splitting Methods in Nonlinear Mechanics,, SIAM, (1989).  doi: 10.1137/1.9781611970838.  Google Scholar

[16]

T. Goldstein and S. Osher, The split Bregman method for L1-regularized problems,, SIAM Journal on Imaging Sciences, 2 (2009), 323.  doi: 10.1137/080725891.  Google Scholar

[17]

C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results,, Journal of Combinatorial Optimization, 8 (2004), 329.  doi: 10.1023/B:JOCO.0000038914.26975.9b.  Google Scholar

[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.  doi: 10.1007/s101070100280.  Google Scholar

[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.  doi: 10.1137/110822347.  Google Scholar

[20]

G. Iyengar and W. Kang, Inverse conic programming and applications,, Operations Research Letters, 33 (2005), 319.  doi: 10.1016/j.orl.2004.04.007.  Google Scholar

[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.  doi: 10.1137/0103003.  Google Scholar

[22]

M. Raydan, On the Barzilai and Borwein choice of steplength for the gradient method,, IMA Journal of Numerical Analysis, 13 (1993), 321.  doi: 10.1093/imanum/13.3.321.  Google Scholar

[23]

M. Raydan, The Barzilai and Borwein gradient method for the large scale unconstrained minimization problem,, SIAM Journal on Optimization, 7 (1997), 26.  doi: 10.1137/S1052623494266365.  Google Scholar

[24]

R. Rockafellar and R. Wets, Variational Analysis,, Springer-Verlag, (1998).  doi: 10.1007/978-3-642-02431-3.  Google Scholar

[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.  doi: 10.1007/s10107-007-0105-9.  Google Scholar

[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.  doi: 10.1137/0329006.  Google Scholar

[27]

P. Tseng, Further applications of a splitting algorithm to decomposition in variational inequalities and convex programming,, Mathematical Programming, 48 (1990), 249.  doi: 10.1007/BF01582258.  Google Scholar

[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.  doi: 10.1016/j.cam.2008.01.028.  Google Scholar

[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.  doi: 10.3934/jimo.2009.5.319.  Google Scholar

[30]

J. Yang and Y. Zhang, Alternating direction algorithms for $l_1$-problems in compressive sensing,, SIAM Journal on Scientific Computing, 33 (2011), 250.  doi: 10.1137/090777761.  Google Scholar

[31]

J. Zhang and Z. Liu, Calculating some inverse linear programming problems,, Journal of Computational and Applied Mathematics, 72 (1996), 261.  doi: 10.1016/0377-0427(95)00277-4.  Google Scholar

[32]

J. Zhang and Z. Liu, A further study on inverse linear programming problems,, Journal of Computational and Applied Mathematics, 106 (1999), 345.  doi: 10.1016/S0377-0427(99)00080-1.  Google Scholar

[33]

J. Zhang, Z. Liu and Z. Ma, Some reverse location problems,, European Journal of Operations Research, 124 (2000), 77.  doi: 10.1016/S0377-2217(99)00122-8.  Google Scholar

[34]

J. Zhang and Z. Ma, Solution structure of some inverse combinatorial optimization problems,, Journal of Combinatorial Optimization, 3 (1999), 127.  doi: 10.1023/A:1009829525096.  Google Scholar

[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.  doi: 10.1007/s00245-009-9075-z.  Google Scholar

[1]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[2]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[3]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[4]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[5]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[6]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[7]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327
[8]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[9]

Boris Kramer, John R. Singler. A POD projection method for large-scale algebraic Riccati equations. Numerical Algebra, Control & Optimization, 2016, 6 (4) : 413-435. doi: 10.3934/naco.2016018
[10]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[11]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[12]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[13]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[14]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056
[15]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[16]

Jean-François Biasse. Improvements in the computation of ideal class groups of imaginary quadratic number fields. Advances in Mathematics of Communications, 2010, 4 (2) : 141-154. doi: 10.3934/amc.2010.4.141
[17]

Marcelo Messias. Periodic perturbation of quadratic systems with two infinite heteroclinic cycles. Discrete & Continuous Dynamical Systems - A, 2012, 32 (5) : 1881-1899. doi: 10.3934/dcds.2012.32.1881
[18]

Tuan Hiep Pham, Jérôme Laverne, Jean-Jacques Marigo. Stress gradient effects on the nucleation and propagation of cohesive cracks. Discrete & Continuous Dynamical Systems - S, 2016, 9 (2) : 557-584. doi: 10.3934/dcdss.2016012
[19]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[20]

Charles Fulton, David Pearson, Steven Pruess. Characterization of the spectral density function for a one-sided tridiagonal Jacobi matrix operator. Conference Publications, 2013, 2013 (special) : 247-257. doi: 10.3934/proc.2013.2013.247

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (53)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences