• Previous Article
    Equilibrium and optimal balking strategies for low-priority customers in the M/G/1 queue with two classes of customers and preemptive priority
  • JIMO Home
  • This Issue
  • Next Article
    On the M-eigenvalue estimation of fourth-order partially symmetric tensors
doi: 10.3934/jimo.2019061

Inverse quadratic programming problem with $ l_1 $ norm measure

1. 

School of Mathematical Sciences, Dalian University of Technology, Dalian 116024, China

2. 

College of Science, Liaoning Technical University, Fuxin 123000, China

* Corresponding author: Lidan Li

Received  October 2018 Revised  January 2019 Published  May 2019

Fund Project: The third author is supported by the National Natural Science Foundation of China under project grant No.11571059 and No.11731013

We consider an inverse quadratic programming (QP) problem in which the parameters in the objective function of a given QP problem are adjusted as little as possible so that a known feasible solution becomes the optimal one. We formulate this problem as a minimization problem involving $l_1$ vector norm with a positive semidefinite cone constraint. By utilizing convex optimization theory, we rewrite its first order optimality condition as a generalized equation. Under extremely simple assumptions, we prove that any element of the generalized Jacobian of the equation at its solution is nonsingular. Based on this, we construct an inexact Newton method with Armijo line search to solve the equation and demonstrate its global convergence. Finally, we report the numerical results illustrating effectiveness of the Newton methods.

Citation: Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, doi: 10.3934/jimo.2019061
References:
[1]

R. K. Ahuja and J. B. Orlin, Inverse optimization, Oper. Res., 49 (2001), 771-783. doi: 10.1287/opre.49.5.771.10607.

[2]

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

[3]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4612-1394-9.

[4]

R. E. BurkardY. Lin and J. Zhang, Weight reduction problems with certain bottleneck objectives, European J. Oper. Res., 153 (2004), 191-199. doi: 10.1016/S0377-2217(02)00713-0.

[5]

D. Burton and Ph. L. Toint, On an instance of the inverse shortest paths problem, Math. Program., 53 (1992), 45-61. doi: 10.1007/BF01585693.

[6]

M. C. CaiX. G. Yang and J. Zhang, The complexity analysis of the inverse center location problem, J. Glob. Optim., 15 (1999), 213-218. doi: 10.1023/A:1008360312607.

[7]

F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, 1983.

[8]

F. Facchinei, A. Fischer and C. Kanzow, Inexact newton methods for semismooth equations with applications to variational inequality problems, in Nonlinear Optimization And Applications (eds. G. F and D. G), Plenum press, New York, (1996), 125–139. doi: 10.1007/978-1-4899-0289-4_9.

[9]

C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results, J. Combin. Optim., 8 (2004), 329-361. doi: 10.1023/B:JOCO.0000038914.26975.9b.

[10]

G. Iyengar and W. Kang, Inverse conic programming with applications, Oper. Res. Lett., 33 (2005), 319-330. doi: 10.1016/j.orl.2004.04.007.

[11]

Y. JiangX. XiaoL. Zhang and J. Zhang, A perturbation approach for a type of inverse linear programming problems, Int. J. Comput. Math., 88 (2011), 508-516. doi: 10.1080/00207160903513003.

[12]

F. MengD. Sun and G. Zhao, Semismoothness of solutions to generalized equations and the moreau-yosida regularization, Math. Program., 104 (2005), 561-581. doi: 10.1007/s10107-005-0629-9.

[13]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, New York, 1998.

[14]

P. Sonneveld, Cgs, a fast lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10 (1989), 36-52. doi: 10.1137/0910004.

[15]

D. Sun, A Short Summer School Course on Modern Optimization Theory: Optimality Conditions and Perturbation Analysis, Part I, Part II, Part III, Technical report, National University of Singapore, Singapore, 2006.

[16]

D. Sun, The strong second order sufficient condition and constraint nondegenracy in nonlinear semidefinite programming and their implications, Math. Oper. Res, 31 (2006), 761-776. doi: 10.1287/moor.1060.0195.

[17]

D. Sun and J. Sun, Semismooth matrix valued functions, Math. Oper. Res., 27 (2002), 150-169. doi: 10.1287/moor.27.1.150.342.

[18]

D. SunJ. Sun and L. Zhang, The rate of convergence of the augmented lagrangian method for nonlinear semidefinite proguamming, Math. Program., 114 (2008), 349-391. doi: 10.1007/s10107-007-0105-9.

[19]

X. XiaoL. Zhang and J. Zhang, A smoothing newton method for a type of inverse semi-definite quadratic programming problem, J. Comput. Appl. Math., 223 (2009), 485-498. doi: 10.1016/j.cam.2008.01.028.

[20]

E. H. Zarantonello, Projections on convex sets in hilbert space and spectral theory: I and II, in Contributions to Nonlinear Functional Analysis (ed. E. H. Zarantonello), Academic Press, New York, 1971, 237-341.

[21]

J. Zhang and Z. Liu, Calculating some inverse linear programming problems, J. Comput. Appl. Math., 72 (1996), 261-273. doi: 10.1016/0377-0427(95)00277-4.

[22]

J. Zhang and Z. Liu, A further study on inverse linear programming problems, J. Comput. Appl. Math., 106 (1999), 345-359. doi: 10.1016/S0377-0427(99)00080-1.

[23]

J. Zhang and Z. Ma, Solution structure of some inverse combinatorial optimization problems, J. Combin. Optim., 3 (1999), 127-139. doi: 10.1023/A:1009829525096.

[24]

J. Zhang and L. Zhang, An augmented lagrangian method for a class of inverse quadratic programming problems, Appl. Math. Optim., 61 (2010), 57-83. doi: 10.1007/s00245-009-9075-z.

show all references

References:
[1]

R. K. Ahuja and J. B. Orlin, Inverse optimization, Oper. Res., 49 (2001), 771-783. doi: 10.1287/opre.49.5.771.10607.

[2]

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

[3]

J. F. Bonnans and A. Shapiro, Perturbation Analysis of Optimization Problems, Springer-Verlag, New York, 2000. doi: 10.1007/978-1-4612-1394-9.

[4]

R. E. BurkardY. Lin and J. Zhang, Weight reduction problems with certain bottleneck objectives, European J. Oper. Res., 153 (2004), 191-199. doi: 10.1016/S0377-2217(02)00713-0.

[5]

D. Burton and Ph. L. Toint, On an instance of the inverse shortest paths problem, Math. Program., 53 (1992), 45-61. doi: 10.1007/BF01585693.

[6]

M. C. CaiX. G. Yang and J. Zhang, The complexity analysis of the inverse center location problem, J. Glob. Optim., 15 (1999), 213-218. doi: 10.1023/A:1008360312607.

[7]

F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley and Sons, New York, 1983.

[8]

F. Facchinei, A. Fischer and C. Kanzow, Inexact newton methods for semismooth equations with applications to variational inequality problems, in Nonlinear Optimization And Applications (eds. G. F and D. G), Plenum press, New York, (1996), 125–139. doi: 10.1007/978-1-4899-0289-4_9.

[9]

C. Heuberger, Inverse combinatorial optimization: A survey on problems, methods and results, J. Combin. Optim., 8 (2004), 329-361. doi: 10.1023/B:JOCO.0000038914.26975.9b.

[10]

G. Iyengar and W. Kang, Inverse conic programming with applications, Oper. Res. Lett., 33 (2005), 319-330. doi: 10.1016/j.orl.2004.04.007.

[11]

Y. JiangX. XiaoL. Zhang and J. Zhang, A perturbation approach for a type of inverse linear programming problems, Int. J. Comput. Math., 88 (2011), 508-516. doi: 10.1080/00207160903513003.

[12]

F. MengD. Sun and G. Zhao, Semismoothness of solutions to generalized equations and the moreau-yosida regularization, Math. Program., 104 (2005), 561-581. doi: 10.1007/s10107-005-0629-9.

[13]

R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, New York, 1998.

[14]

P. Sonneveld, Cgs, a fast lanczos-type solver for nonsymmetric linear systems, SIAM J. Sci. Stat. Comput., 10 (1989), 36-52. doi: 10.1137/0910004.

[15]

D. Sun, A Short Summer School Course on Modern Optimization Theory: Optimality Conditions and Perturbation Analysis, Part I, Part II, Part III, Technical report, National University of Singapore, Singapore, 2006.

[16]

D. Sun, The strong second order sufficient condition and constraint nondegenracy in nonlinear semidefinite programming and their implications, Math. Oper. Res, 31 (2006), 761-776. doi: 10.1287/moor.1060.0195.

[17]

D. Sun and J. Sun, Semismooth matrix valued functions, Math. Oper. Res., 27 (2002), 150-169. doi: 10.1287/moor.27.1.150.342.

[18]

D. SunJ. Sun and L. Zhang, The rate of convergence of the augmented lagrangian method for nonlinear semidefinite proguamming, Math. Program., 114 (2008), 349-391. doi: 10.1007/s10107-007-0105-9.

[19]

X. XiaoL. Zhang and J. Zhang, A smoothing newton method for a type of inverse semi-definite quadratic programming problem, J. Comput. Appl. Math., 223 (2009), 485-498. doi: 10.1016/j.cam.2008.01.028.

[20]

E. H. Zarantonello, Projections on convex sets in hilbert space and spectral theory: I and II, in Contributions to Nonlinear Functional Analysis (ed. E. H. Zarantonello), Academic Press, New York, 1971, 237-341.

[21]

J. Zhang and Z. Liu, Calculating some inverse linear programming problems, J. Comput. Appl. Math., 72 (1996), 261-273. doi: 10.1016/0377-0427(95)00277-4.

[22]

J. Zhang and Z. Liu, A further study on inverse linear programming problems, J. Comput. Appl. Math., 106 (1999), 345-359. doi: 10.1016/S0377-0427(99)00080-1.

[23]

J. Zhang and Z. Ma, Solution structure of some inverse combinatorial optimization problems, J. Combin. Optim., 3 (1999), 127-139. doi: 10.1023/A:1009829525096.

[24]

J. Zhang and L. Zhang, An augmented lagrangian method for a class of inverse quadratic programming problems, Appl. Math. Optim., 61 (2010), 57-83. doi: 10.1007/s00245-009-9075-z.

Table 1.  Numerical results of Problem (5)
n p iter I-norm-F T-norm-F time(s)
50 10 4 9.8e+003 9.9e-012 0.06
100 10 4 7.5e+004 2.8e-007 0.19
100 20 8 6.6e+004 1.0e-009 0.38
100 50 8 1.9e+005 8.6e-007 0.39
500 50 12 9.3e+006 1.1e-013 52.77
500 100 17 8.2e+006 4.0e-010 79.76
1000 100 25 7.7e+007 9.2e-009 916.90
1000 500 30 3.8e+007 6.0e-008 1191.39
2000 500 34 4.7e+008 3.5e-011 9300.16
n p iter I-norm-F T-norm-F time(s)
50 10 4 9.8e+003 9.9e-012 0.06
100 10 4 7.5e+004 2.8e-007 0.19
100 20 8 6.6e+004 1.0e-009 0.38
100 50 8 1.9e+005 8.6e-007 0.39
500 50 12 9.3e+006 1.1e-013 52.77
500 100 17 8.2e+006 4.0e-010 79.76
1000 100 25 7.7e+007 9.2e-009 916.90
1000 500 30 3.8e+007 6.0e-008 1191.39
2000 500 34 4.7e+008 3.5e-011 9300.16
[1]

Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487

[2]

Yong Xia, Yu-Jun Gong, Sheng-Nan Han. A new semidefinite relaxation for $L_{1}$-constrained quadratic optimization and extensions. Numerical Algebra, Control & Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185

[3]

Feishe Chen, Lixin Shen, Yuesheng Xu, Xueying Zeng. The Moreau envelope approach for the L1/TV image denoising model. Inverse Problems & Imaging, 2014, 8 (1) : 53-77. doi: 10.3934/ipi.2014.8.53

[4]

Shuang Chen, Li-Ping Pang, Dan Li. An inexact semismooth Newton method for variational inequality with symmetric cone constraints. Journal of Industrial & Management Optimization, 2015, 11 (3) : 733-746. doi: 10.3934/jimo.2015.11.733

[5]

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems & Imaging, 2013, 7 (3) : 907-926. doi: 10.3934/ipi.2013.7.907

[6]

Linghua Chen, Espen R. Jakobsen. L1 semigroup generation for Fokker-Planck operators associated to general Lévy driven SDEs. Discrete & Continuous Dynamical Systems - A, 2018, 38 (11) : 5735-5763. doi: 10.3934/dcds.2018250

[7]

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

[8]

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

[9]

Dan Li, Li-Ping Pang, Fang-Fang Guo, Zun-Quan Xia. An alternating linearization method with inexact data for bilevel nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2014, 10 (3) : 859-869. doi: 10.3934/jimo.2014.10.859

[10]

Saeed Ketabchi, Hossein Moosaei, M. Parandegan, Hamidreza Navidi. Computing minimum norm solution of linear systems of equations by the generalized Newton method. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 113-119. doi: 10.3934/naco.2017008

[11]

Z.Y. Wu, H.W.J. Lee, F.S. Bai, L.S. Zhang. Quadratic smoothing approximation to $l_1$ exact penalty function in global optimization. Journal of Industrial & Management Optimization, 2005, 1 (4) : 533-547. doi: 10.3934/jimo.2005.1.533

[12]

Boshi Tian, Xiaoqi Yang, Kaiwen Meng. An interior-point $l_{\frac{1}{2}}$-penalty method for inequality constrained nonlinear optimization. Journal of Industrial & Management Optimization, 2016, 12 (3) : 949-973. doi: 10.3934/jimo.2016.12.949

[13]

Pia Heins, Michael Moeller, Martin Burger. Locally sparse reconstruction using the $l^{1,\infty}$-norm. Inverse Problems & Imaging, 2015, 9 (4) : 1093-1137. doi: 10.3934/ipi.2015.9.1093

[14]

P. R. Zingano. Asymptotic behavior of the $L^1$ norm of solutions to nonlinear parabolic equations. Communications on Pure & Applied Analysis, 2004, 3 (1) : 151-159. doi: 10.3934/cpaa.2004.3.151

[15]

Ben Green, Terence Tao, Tamar Ziegler. An inverse theorem for the Gowers $U^{s+1}[N]$-norm. Electronic Research Announcements, 2011, 18: 69-90. doi: 10.3934/era.2011.18.69

[16]

Donglei Du, Tianping Shuai. Errata to:''Optimal preemptive online scheduling to minimize $l_{p}$ norm on two processors''[Journal of Industrial and Management Optimization, 1(3) (2005), 345-351.]. Journal of Industrial & Management Optimization, 2008, 4 (2) : 339-341. doi: 10.3934/jimo.2008.4.339

[17]

Radu Ioan Boţ, Anca Grad, Gert Wanka. Sequential characterization of solutions in convex composite programming and applications to vector optimization. Journal of Industrial & Management Optimization, 2008, 4 (4) : 767-782. doi: 10.3934/jimo.2008.4.767

[18]

Paul B. Hermanns, Nguyen Van Thoai. Global optimization algorithm for solving bilevel programming problems with quadratic lower levels. Journal of Industrial & Management Optimization, 2010, 6 (1) : 177-196. doi: 10.3934/jimo.2010.6.177

[19]

Shu-Cherng Fang, David Y. Gao, Ruey-Lin Sheu, Soon-Yi Wu. Canonical dual approach to solving 0-1 quadratic programming problems. Journal of Industrial & Management Optimization, 2008, 4 (1) : 125-142. doi: 10.3934/jimo.2008.4.125

[20]

Yanqin Bai, Chuanhao Guo. Doubly nonnegative relaxation method for solving multiple objective quadratic programming problems. Journal of Industrial & Management Optimization, 2014, 10 (2) : 543-556. doi: 10.3934/jimo.2014.10.543

2017 Impact Factor: 0.994

Metrics

  • PDF downloads (6)
  • HTML views (42)
  • Cited by (0)

Other articles
by authors

[Back to Top]