×

Approximation algorithms for indefinite quadratic programming. (English) Zbl 0845.90095

The author considers the nonconvex quadratic programming problem: \[ \text{Minimize}\quad \textstyle{{1\over 2}} (x^{\mathbb T} Hx)+ h^{\mathbb T} x\quad\text{subject to } Wx\geq b. \] An algorithm for finding an \(\varepsilon\)-approximation solution of this problem is suggested. The algorithm is polynomial in \(1/\varepsilon\) for fixed \(t\), where \(t\) is the number of negative eigenvalues of the quadratic term. The algorithm is exponential in \(t\) for fixed \(\varepsilon\). The results are applied to a special case of the quadratic knapsack problem. It is shown that there exists an approximation algorithm for this problem which is polynomial in \(t\).

MSC:

90C20 Quadratic programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
90C26 Nonconvex programming, global optimization
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.E. Bellman,Dynamic Programming (Princeton University Press, Princeton, NJ, 1957).
[2] P. Brucker, ”An O(n) algorithm for quadratic knapsack problems,”Operations Research Letters 3 (1984) 163–166. · Zbl 0544.90086 · doi:10.1016/0167-6377(84)90010-5
[3] R.W. Cottle, S.G. Duvall and K. Zikan, ”A Lagrangean relaxation algorithm for the constrained matrix problem,”Naval Research Logistics Quarterly 33 (1986) 55–76. · Zbl 0598.90070 · doi:10.1002/nav.3800330106
[4] R.M. Freund, R. Roundy, and M.J. Todd, ”Identifying the set of always active constraints in a system of linear inequalities by a single linear program,” Working Paper 1674-85, Sloan School of Management, MIT (Cambridge, MA, 1985).
[5] P.E. Gill, W. Murray and M.H. Wright,Practical Optimization (Academic Press, London, 1981).
[6] G.H. Golub and C.F. Van Loan,Matrix Computations (Johns Hopkins University Press, Baltimore, MD, 1989, 2nd ed.). · Zbl 0733.65016
[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] J. Hershberger, ”Finding the upper envelope ofn line segments in O(n logn) time,”Information Processing Letters 33 (1989) 169–174. · Zbl 0689.68058 · doi:10.1016/0020-0190(89)90136-1
[9] S. Kapoor and P.M. Vaidya, ”Fast algorithms for convex quadratic programming and multicommodity flows,” in:Proceedings of the 18th Annual ACM Symposium on Theory of Computing (ACM Press, New York, 1986) pp. 147–159.
[10] M.K. Kozlov, S.P. Tarasov and L.G. Hačijan, ”Polynomial solvability of convex quadratic programming,”Doklad Akademii Nauk SSSR 248 (1979) 1049–1051. [Translated in:Soviet Mathematics Doklady 20 (1979) 1108–1111.]
[11] L. Lovász,An Algorithmic Theory of Numbers, Graphs and Convexity (SIAM, Philadelphia, PA, 1986). · Zbl 0606.68039
[12] J.J. Moré and S.A. Vavasis, ”On the solution of concave knapsack problems,”Mathematical Programming 49 (1991) 397–411. · Zbl 0723.90059 · doi:10.1007/BF01588800
[13] K.G. Murty and S.N. Kabadi, ”Some NP-complete problems in quadratic and nonlinear programming,”Mathematical Programming 39 (1987) 117–129. · Zbl 0637.90078 · doi:10.1007/BF02592948
[14] A.S. Nemirovsky and D.B. Yudin,Problem Complexity and Method Efficiency in Optimization (Wiley, Chichester, 1983). [Translated by E.R. Dawson fromSlozhnost’ Zadach i Effektivnost’ Metodov Optimizatsii (1979).]
[15] C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization:Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NJ, 1982). · Zbl 0503.90060
[16] P.M. Pardalos and J.B. Rosen,Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Science No. 268 (Springer, Berlin, 1987). · Zbl 0638.90064
[17] P.M. Pardalos and S.A. Vavasis, ”Quadratic programming with one negative eigenvalue is NP-hard,”Journal of Global Optimization 1 (1990) 15–22. · Zbl 0755.90065 · doi:10.1007/BF00120662
[18] S. Sahni, ”Computationally related problems,”SIAM Journal on Computing 3 (1974) 262–279. · Zbl 0292.68020 · doi:10.1137/0203021
[19] P.M. Vaidya, ”Speeding-up linear programming using fast matrix multiplication (extended abstract),”Proceedings of the 30th Symposium on Foundations of Computer Science (ACM Press, New York, 1989) pp. 332–337.
[20] S.A. Vavasis, ”Quadratic programming is in NP,”Information Processing Letters 36 (1990) 73–77. · Zbl 0719.90052 · doi:10.1016/0020-0190(90)90100-C
[21] S.A. Vavasis, ”Approximation algorithms for indefinite quadratic programming,” Technical Report 91-1228, Department of Computer Science, Cornell University (Ithaca, NY, 1991). · Zbl 0845.90095
[22] S.A. Vavasis, ”On approximation algorithms for concave quadratic programming,” in: C.A. Floudas and P.M. Pardalos, eds.,Recent Advances in Global Optimization (Princeton University Press, Princeton, NJ, 1992a) pp. 3–18.
[23] S.A. Vavasis, ”Local minima for indefinite quadratic knapsack problems,”Mathematical Programming 54 (1992b) 127–153. · Zbl 0751.90058 · doi:10.1007/BF01586048
[24] Y. Ye and E. Tse, ”An extension of Karmarkar’s projective algorithm for convex quadratic programming,”Mathematical Programming 44 (1989) 157–179. · Zbl 0674.90077 · doi:10.1007/BF01587086
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.