American Institute of Mathematical Sciences

Advanced
  • Previous Article
    Minimizing total completion time in a two-machine no-wait flowshop with uncertain and bounded setup times
  • JIMO Home
  • This Issue
  • Next Article
    Performance evaluation and Nash equilibrium of a cloud architecture with a sleeping mechanism and an enrollment service
September  2020, 16(5): 2425-2437. doi: 10.3934/jimo.2019061

Inverse quadratic programming problem with $ l_1 $ norm measure

Lidan Li 1,2,, , Hongwei Zhang 1, and  Liwei Zhang 1,

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  September 2020 Early access  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.

Keywords: Inverse optimization, quadratic programming, inexact Newton method, l1 vector norm.
Mathematics Subject Classification: Primary: 90C20; Secondary: 90C25.
Citation: Lidan Li, Hongwei Zhang, Liwei Zhang. Inverse quadratic programming problem with $ l_1 $ norm measure. Journal of Industrial & Management Optimization, 2020, 16 (5) : 2425-2437. 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.  Google Scholar

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

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

[4]

R. E. Burkard, Y. 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.  Google Scholar

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

[6]

M. C. Cai, X. 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.  Google Scholar

[7]

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

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

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

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

[11]

Y. Jiang, X. Xiao, L. 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.  Google Scholar

[12]

F. Meng, D. 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.  Google Scholar

[13]

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

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

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

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

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

[18]

D. Sun, J. 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.  Google Scholar

[19]

X. Xiao, L. 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.  Google Scholar

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

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

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

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

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

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.  Google Scholar

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

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

[4]

R. E. Burkard, Y. 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.  Google Scholar

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

[6]

M. C. Cai, X. 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.  Google Scholar

[7]

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

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

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

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

[11]

Y. Jiang, X. Xiao, L. 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.  Google Scholar

[12]

F. Meng, D. 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.  Google Scholar

[13]

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

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

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

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

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

[18]

D. Sun, J. 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.  Google Scholar

[19]

X. Xiao, L. 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.  Google Scholar

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

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

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

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

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

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
Table Options

Download as excel

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]

Ahmad Mousavi, Zheming Gao, Lanshan Han, Alvin Lim. Quadratic surface support vector machine with L1 norm regularization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021046
[2]

Duo Wang, Zheng-Fen Jin, Youlin Shang. A penalty decomposition method for nuclear norm minimization with l1 norm fidelity term. Evolution Equations & Control Theory, 2019, 8 (4) : 695-708. doi: 10.3934/eect.2019034
[3]

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
[4]

Songqiang Qiu, Zhongwen Chen. An adaptively regularized sequential quadratic programming method for equality constrained optimization. Journal of Industrial & Management Optimization, 2020, 16 (6) : 2675-2701. doi: 10.3934/jimo.2019075
[5]

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
[6]

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

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
[8]

Hong-Yi Miao, Li Wang. Preconditioned inexact Newton-like method for large nonsymmetric eigenvalue problems. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 677-685. doi: 10.3934/naco.2021012
[9]

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
[10]

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
[11]

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
[12]

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

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
[14]

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
[15]

Hui Gao, Jian Lv, Xiaoliang Wang, Liping Pang. An alternating linearization bundle method for a class of nonconvex optimization problem with inexact information. Journal of Industrial & Management Optimization, 2021, 17 (2) : 805-825. doi: 10.3934/jimo.2019135
[16]

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
[17]

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
[18]

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
[19]

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
[20]

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

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (195)
  • HTML views (668)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy