We discuss some basic concepts and present a numerical procedure for finding the minimum-norm solution of convex quadratic programs (QPs) subject to linear equality and inequality constraints. Our approach is based on a theorem of alternatives and on a convenient characterization of the solution set of convex QPs. We show that this problem can be reduced to a simple constrained minimization problem with a once-differentiable convex objective function. We use finite termination of an appropriate Newton’s method to solve this problem. Numerical results show that the proposed method is efficient.
Keywords: Solution set of convex problems, minimum-norm solution of convex quadratic programs, Newton’s method, theorems of alternative
@article{RO_2021__55_1_247_0,
author = {Ketabchi, Saeed and Moosaei, Hossein and Hlad{\'\i}k, Milan},
title = {On the minimum-norm solution of convex quadratic programming},
journal = {RAIRO. Operations Research},
pages = {247--260},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {1},
doi = {10.1051/ro/2021011},
mrnumber = {4229197},
zbl = {1471.90106},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2021011/}
}
TY - JOUR AU - Ketabchi, Saeed AU - Moosaei, Hossein AU - Hladík, Milan TI - On the minimum-norm solution of convex quadratic programming JO - RAIRO. Operations Research PY - 2021 SP - 247 EP - 260 VL - 55 IS - 1 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2021011/ DO - 10.1051/ro/2021011 LA - en ID - RO_2021__55_1_247_0 ER -
%0 Journal Article %A Ketabchi, Saeed %A Moosaei, Hossein %A Hladík, Milan %T On the minimum-norm solution of convex quadratic programming %J RAIRO. Operations Research %D 2021 %P 247-260 %V 55 %N 1 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2021011/ %R 10.1051/ro/2021011 %G en %F RO_2021__55_1_247_0
Ketabchi, Saeed; Moosaei, Hossein; Hladík, Milan. On the minimum-norm solution of convex quadratic programming. RAIRO. Operations Research, Tome 55 (2021) no. 1, pp. 247-260. doi: 10.1051/ro/2021011
[1] , Minimization of functions having lipschitz continuous first partial derivatives. Pac. J. Math. 16 (1966) 1–3. | MR | Zbl | DOI
[2] , and , Nonlinear Programming: Theory and Algorithms. John Wiley & Sons, New York (2013). | Zbl | MR
[3] and , A first order method for finding minimal norm-like solutions of convex optimization problems. Math. Program. 147 (2014) 25–46. | MR | Zbl | DOI
[4] , , and , Unique minimum norm solution to redundant reaction forces in multibody systems. Mech. Mach. Theory 116 (2017) 310–325. | DOI
[5] and , Theorems of alternative and optimization, in Optimization and Applications, edited by et al. In Vol. 12422 of Lecture Note in Computer Science. Springer, Cham (2020) 86–96. | MR | Zbl | DOI
[6] and , New perspective on the theorems of alternative. In: High Performance Algorithms and Software for Nonlinear Optimization, edited by and . Vol. 82 of: Applied Optimization. Kluwer Academic Publishers Springer (2003) 227–241. | MR | Zbl | DOI
[7] , The Theory of Linear Economic Models. University of Chicago Press (1989). | MR
[8] and , On the convergence of a heuristic parameter choice rule for Tikhonov regularization. SIAM J. Sci. Comput. 40 (2018) A2694–A2719. | MR | Zbl | DOI
[9] and , Theorems of the alternative and their applications in numerical methods. Comput. Math. Math. Phys. 43 (2003) 338–358. | Zbl | MR
[10] and , Global Optimization Using Interval Analysis, 2nd edition. Marcel Dekker, New York (2004). | MR | Zbl
[11] , and , Generalized Hessian matrix and second-order optimality conditions for problems with data. Appl. Math. Optim. 11 (1984) 43–56. | MR | Zbl | DOI
[12] , , and , Applied Interval Analysis. Springer, London (2001). | MR | Zbl | DOI
[13] , and , On the minimum norm solution of linear programs. J. Optim. Theory App. 116 (2003) 333–345. | MR | Zbl | DOI
[14] and , On the solution set of convex problems and its numerical application. J. Comput. Appl. Math. 206 (2007) 288–292. | MR | Zbl | DOI
[15] and , Minimum norm solution to the absolute value equation in the convex case. J. Optim. Theory App. 154 (2012) 1080–1087. | MR | Zbl | DOI
[16] and , Convergence of heuristic parameter choice rules for convex Tikhonov regularization. SIAM J. Numer. Anal. 58 (2020) 1773–1800. | MR | Zbl | DOI
[17] , A simple characterization of solution sets of convex programs. Oper. Res. Lett. 7 (1988) 21–26. | MR | Zbl | DOI
[18] , A Finite newton method for classification. Optim. Methods Softw. 17 (2002) 913–929. | MR | Zbl | DOI
[19] , and , Minimum norm solution to the positive semidefinite linear complementarity problem. Optimization 63 (2014) 359–369. | MR | Zbl | DOI
[20] , On equivalent reformulations for absolute value equations. Comput. Optim. App. 44 (2009) 363–372. | MR | Zbl | DOI
[21] , Minimum norm solution to the linear complementarity problem. In: Functional Analysis, Optimization and Mathematical Economics, edited by et al. Oxford University Press, Oxford (1990) 208–216. | MR | Zbl | DOI
[22] and , Solutions of Ill-Posed Problems. Winston, Washington, DC (1977). | MR | Zbl
[23] , and , Numerical constraint satisfaction problems with non-isolated solutions. In: Global Optimization and Constraint Satisfaction, edited by , and . Springer, Berlin-Heidelberg (2003) 194–210. | Zbl | DOI
[24] and , A dual neural network solving quadratic programming problems. In: Vol. 1 of IJCNN’99. International Joint Conference on Neural Networks. Proceedings (Cat. No. 99CH36339). IEEE (1999) 588–593. | DOI
[25] , and , Schemes for finding minimum-norm solutions of variational inequalities. Nonlinear Anal.: Theory Methods App. 72 (2010) 3447–3456. | MR | Zbl | DOI
Cité par Sources :
