Convex quadratic programming with one constraint and bounded variables.(English)Zbl 0633.90057
An iterative algorithm is proposed to solve a convex quadratic problem with one linear equality constraint and bounded variables. At each iteration of the algorithm a separable convex quadratic problem with the same constraint set is solved. Two possibilities in choosing the step- size are analyzed, i.e. an exact line search and a unit step-size. The first approach requires fewer iterations in general, but more computation at each one. Some numerical testing results are included. Besides other results they show that the second approach requires less execution time.
Reviewer: A.Zilinskas
Keywords:
projection;separable program;convex quadratic problem;linear equality constraint;bounded variables;exact line search;unit step-sizeCite
Full Text:DOI
References:
| [1] | D. Bertsekas, ”On the Goldstein-Levitin-Polyak gradient projection method,”IEEE Transaction on Automatic Control AC-21 (1976) 174–184. ·Zbl 0326.49025 ·doi:10.1109/TAC.1976.1101194 |
| [2] | P.G. Ciarlet,Introduction à l’analyse numérique matricielle et à l’optimisation (Masson, Paris, France, 1982). ·Zbl 0488.65001 |
| [3] | R.W. Cottle, ”Monotone solutions of the parametric linear complementarity problem,”Mathematical Programming 3 (1972) 210–224. ·Zbl 0246.90039 ·doi:10.1007/BF01584990 |
| [4] | J.P. Dussault, ”Solution numérique de modèles d’équilibre,” Thèse de doctorat, Université de Montréal (Montréal, Canada, 1982). |
| [5] | J.A. Ferland, B. Lemaire and P. Robert, ”Analytic solutions for non-linear programs with one or two equality constraints,” Publication #285, Département d’informatique et de recherche opérationnelle, Université de Montréal (Montréal, Canada, 1978). |
| [6] | A.A. Goldstein, ”Convex programming in Hilbert space”Bulletin American Mathematical Society 70 (1964) 709–710. ·Zbl 0142.17101 ·doi:10.1090/S0002-9904-1964-11178-2 |
| [7] | R. Helgason, J. Kennington and H. Lall, ”A polynomially bounded algorithm for a singly constrained quadratic program,”Mathematical Programming 18 (1980) 338–343. ·Zbl 0452.90054 ·doi:10.1007/BF01588328 |
| [8] | E.S. Levitin and B.T. Polyak, ”Constrained minimization problems,”USSR Computational Mathematics and Mathematical Physics 6 (1966) 1–50. ·Zbl 0161.07002 ·doi:10.1016/0041-5553(66)90114-5 |
| [9] | R.K. McCord, ”Minimization with one linear equality constraint and bounds on the variables,” Technical Report SOL 79-20, System Optimization Laboratory, Dept. Operations Research, Stanford University, (Stanford, CA, 1979). |
| [10] | J.S. Pang, ”A new and efficient algorithm for a class of portfolio selection problems,”Operations Research 28 (1980) 754–767. ·Zbl 0451.90011 ·doi:10.1287/opre.28.3.754 |
| [11] | R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton N.J., 1970). ·Zbl 0193.18401 |
| [12] | M.C. Trevisan, ”Résolution numérique de problèmes d’optimisation à une seule contrainte linéaire. Application au problème de Thomas-Fermi,” Thèse de 3ième cycle, Université des Sciences et Techniques du Languedoc (Montpellier, France, 1980). |
| [13] | P. Wolfe, ”Finding the nearest point in a polytope,”Mathematical Programming 11 (1976) 128–149. ·Zbl 0352.90046 ·doi:10.1007/BF01580381 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
