-
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
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 |
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.
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. 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. |
[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. |
[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. 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. |
[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. |
[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. |
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] |
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
Other articles
by authors
[Back to Top]