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

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

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

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

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

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

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

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028
[8]

Yves Dumont, Frederic Chiroleu. Vector control for the Chikungunya disease. Mathematical Biosciences & Engineering, 2010, 7 (2) : 313-345. doi: 10.3934/mbe.2010.7.313
[9]

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

A. K. Misra, Anupama Sharma, Jia Li. A mathematical model for control of vector borne diseases through media campaigns. Discrete & Continuous Dynamical Systems - B, 2013, 18 (7) : 1909-1927. doi: 10.3934/dcdsb.2013.18.1909
[11]

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

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

Nikolaz Gourmelon. Generation of homoclinic tangencies by $C^1$-perturbations. Discrete & Continuous Dynamical Systems - A, 2010, 26 (1) : 1-42. doi: 10.3934/dcds.2010.26.1
[14]

Dugan Nina, Ademir Fernando Pazoto, Lionel Rosier. Controllability of a 1-D tank containing a fluid modeled by a Boussinesq system. Evolution Equations & Control Theory, 2013, 2 (2) : 379-402. doi: 10.3934/eect.2013.2.379
[15]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[16]

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

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

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021008
[19]

Reza Lotfi, Yahia Zare Mehrjerdi, Mir Saman Pishvaee, Ahmad Sadeghieh, Gerhard-Wilhelm Weber. A robust optimization model for sustainable and resilient closed-loop supply chain network design considering conditional value at risk. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 221-253. doi: 10.3934/naco.2020023
[20]

Teddy Pichard. A moment closure based on a projection on the boundary of the realizability domain: 1D case. Kinetic & Related Models, 2020, 13 (6) : 1243-1280. doi: 10.3934/krm.2020045

2019 Impact Factor: 1.366

Tools

Metrics

  • PDF downloads (77)
  • HTML views (527)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences