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 and 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-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: , (). 

[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.

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-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: , (). 

[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.

[1]

Xiantao Xiao, Liwei Zhang, Jianzhong Zhang. On convergence of augmented Lagrangian method for inverse semi-definite quadratic programming problems. Journal of Industrial and Management Optimization, 2009, 5 (2) : 319-339. doi: 10.3934/jimo.2009.5.319
[2]

Lipu Zhang, Yinghong Xu, Zhengjing Jin. An efficient algorithm for convex quadratic semi-definite optimization. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 129-144. doi: 10.3934/naco.2012.2.129
[3]

Wei Huang, Ka-Fai Cedric Yiu, Henry Y. K. Lau. Semi-definite programming based approaches for real-time tractor localization in port container terminals. Numerical Algebra, Control and Optimization, 2013, 3 (4) : 665-680. doi: 10.3934/naco.2013.3.665
[4]

Yi Xu, Jinjie Liu, Liqun Qi. A new class of positive semi-definite tensors. Journal of Industrial and Management Optimization, 2020, 16 (2) : 933-943. doi: 10.3934/jimo.2018186
[5]

Stephane Chretien, Paul Clarkson. A fast algorithm for the semi-definite relaxation of the state estimation problem in power grids. Journal of Industrial and Management Optimization, 2020, 16 (1) : 431-443. doi: 10.3934/jimo.2018161
[6]

Monika Eisenmann, Etienne Emmrich, Volker Mehrmann. Convergence of the backward Euler scheme for the operator-valued Riccati differential equation with semi-definite data. Evolution Equations and Control Theory, 2019, 8 (2) : 315-342. doi: 10.3934/eect.2019017
[7]

Bingsheng He, Xiaoming Yuan. Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numerical Algebra, Control and Optimization, 2013, 3 (2) : 247-260. doi: 10.3934/naco.2013.3.247
[8]

Zhongming Wu, Xingju Cai, Deren Han. Linearized block-wise alternating direction method of multipliers for multiple-block convex programming. Journal of Industrial and Management Optimization, 2018, 14 (3) : 833-855. doi: 10.3934/jimo.2017078
[9]

Yanqun Liu, Ming-Fang Ding. A ladder method for linear semi-infinite programming. Journal of Industrial and Management Optimization, 2014, 10 (2) : 397-412. doi: 10.3934/jimo.2014.10.397
[10]

Xiaojin Zheng, Zhongyi Jiang. Tighter quadratically constrained convex reformulations for semi-continuous quadratic programming. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2331-2343. doi: 10.3934/jimo.2020071
[11]

Feng Ma, Jiansheng Shu, Yaxiong Li, Jian Wu. The dual step size of the alternating direction method can be larger than 1.618 when one function is strongly convex. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1173-1185. doi: 10.3934/jimo.2020016
[12]

Cheng Ma, Xun Li, Ka-Fai Cedric Yiu, Yongjian Yang, Liansheng Zhang. On an exact penalty function method for semi-infinite programming problems. Journal of Industrial and Management Optimization, 2012, 8 (3) : 705-726. doi: 10.3934/jimo.2012.8.705
[13]

Ke Su, Yumeng Lin, Chun Xu. A new adaptive method to nonlinear semi-infinite programming. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1133-1144. doi: 10.3934/jimo.2021012
[14]

Foxiang Liu, Lingling Xu, Yuehong Sun, Deren Han. A proximal alternating direction method for multi-block coupled convex optimization. Journal of Industrial and Management Optimization, 2019, 15 (2) : 723-737. doi: 10.3934/jimo.2018067
[15]

Wanbin Tong, Hongjin He, Chen Ling, Liqun Qi. A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042
[16]

Zhi Guo Feng, Kok Lay Teo, Volker Rehbock. A smoothing approach for semi-infinite programming with projected Newton-type algorithm. Journal of Industrial and Management Optimization, 2009, 5 (1) : 141-151. doi: 10.3934/jimo.2009.5.141
[17]

Yuan Shen, Lei Ji. Partial convolution for total variation deblurring and denoising by new linearized alternating direction method of multipliers with extension step. Journal of Industrial and Management Optimization, 2019, 15 (1) : 159-175. doi: 10.3934/jimo.2018037
[18]

Yan Gu, Nobuo Yamashita. Alternating direction method of multipliers with variable metric indefinite proximal terms for convex optimization. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 487-510. doi: 10.3934/naco.2020047
[19]

Russell E. Warren, Stanley J. Osher. Hyperspectral unmixing by the alternating direction method of multipliers. Inverse Problems and Imaging, 2015, 9 (3) : 917-933. doi: 10.3934/ipi.2015.9.917
[20]

Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy