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

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

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

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

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

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

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

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

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

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

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

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

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

[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
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 and Management Optimization, 2022, 18 (3) : 1835-1861. 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 and 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 and 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 and 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 and Optimization, 2015, 5 (2) : 185-195. doi: 10.3934/naco.2015.5.185
[6]

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

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

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

Braxton Osting, Jérôme Darbon, Stanley Osher. Statistical ranking using the $l^{1}$-norm on graphs. Inverse Problems and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and 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 and Management Optimization, 2008, 4 (2) : 339-341. doi: 10.3934/jimo.2008.4.339

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (278)
  • HTML views (744)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy