×

zbMATH — the first resource for mathematics

Towards a strongly polynomial algorithm for strictly convex quadratic programs: An extension of Tardos’ algorithm. (English) Zbl 0694.90075
E. Tardos [Oper. Res. 34, 250-256 (1986; Zbl 0626.90053)] was the first to present a polynomial algorithm for solving LP problems in which the number of arithmetic steps depends only on the size of the numbers in the constraint matrix and is independent of the size of the numbers in the right hand sides and the cost coefficients.
This paper extends Tardos’ results to convex quadratic programming problems of the form \[ (P)\quad Max\{c^ Tx-(1/2)x^ TDx:\quad Ax\leq b,\quad x\geq 0\} \] with D being a positive definite matrix. A polynomially bounded algorithm for solving (P) where the number of arithmetic steps is independent of c and b, but depends on the size of the entries of the matrices A and D is developed. The algorithm finds optimal primal and dual solutions to (P), if they exist, by solving a sequence of simple quadratic programming problems using the polynomial algorithm and by checking feasibility of linear system in time independent of the right hand sides.
Reviewer: J.Ramik

MSC:
90C20 Quadratic programming
90C25 Convex programming
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI
References:
[1] A. Bachem and B. Korte, ”An algorithm for quadratic optimization over transportation polytopes,”Zeitschrift für Angewandte Mathematik und Mechanik 58 (1978) 459–461. · Zbl 0396.90102
[2] R.W. Cottle, ”Symmetric dual quadratic programs,”Quarterly of Applied Mathematics 21 (1963) 237–243. · Zbl 0127.36802
[3] J.L. Debiesse and G. Matignon, ”Comparison of different methods for the calculation of traffic matrices,”Annales des Télécommunications 35 (1980) 91–102. · Zbl 0426.90030
[4] W.S. Dorn, ”Duality in quadratic programming,”Quarterly of Applied Mathematics 18 (1960) 155–162. · Zbl 0101.37003
[5] B.C. Eaves, ”On quadratic programming,”Management Science 17 (11) (1971) 698–711. · Zbl 0242.90040
[6] J. Edmonds, ”System of distinct representatives and linear algebra,”Journal of Research of the National Bureau of Standards, Section B 71 (1967) 241–245. · Zbl 0178.03002
[7] M. Grötschel, L. Lovàsz and A. Schrijver,Geometric Algorithms and Combinatorial Optimization (Springer, Berlin, 1988). · Zbl 0634.05001
[8] M. Held, P. Wolfe and H. Crowder, ”Validation of subgradient optimization,”Mathematical Programming 6 (1974) 62–88. · Zbl 0284.90057
[9] 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
[10] J. Kennington and M. Shalaby, ”An effective subgradient procedure for minimal cost multicommodity flow problems,”Management Science 23 (1977) 994–1004. · Zbl 0366.90118
[11] M.K. Kozlov, S.P. Tarasov and L.G. Khachiyan, ”Polynomial solvability of convex quadratic programming,”Soviet Mathmatics Doklady 20 (1979) 1108–1111. · Zbl 0434.90071
[12] M. Minoux, ”A polynomial algorithm for minimum quadratic cost flow problems,”European Journal of Operational Research 18 (1984) 377–387. · Zbl 0555.90039
[13] Eva Tardos, ”A strongly polynomial algorithm to solve combinatorial linear programs,”Operations Research 34 (2) (1986) 250–256. · Zbl 0626.90053
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.