zbMATH — the first resource for mathematics

Interior path following primal-dual algorithms. II: Convex quadratic programming. (English) Zbl 0676.90039
[For part I see ibid. A 44, No.1, 27-41 (1989; Zbl 0676.90038).]
Authors’ abstract: “We describe a primal-dual interior point algorithm for convex quadratic programming problems which requires a total of O(\(\sqrt{n}L)\) number of iterations, where L is the input size. Each iteration updates a penalty parameter and finds an approximate Newton direction associated with the Karush-Kuhn-Tucker system of equations which characterizes a solution of the logarithmic barrier function problem. The algorithm is based on the path following idea. The total number of arithmetic operations is shown to be of the order of \(O(n^ 3L).''\)
Reviewer: N.Deng

90C20 Quadratic programming
90C25 Convex programming
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
Full Text: DOI
[1] C.C. Gonzaga, ”An algorithm for solving linear programming problems in O(n 3 L) operations,” Memorandum Number UCB/ERL M87/10, Electronics Research Laboratory, University of California (Berkeley, CA, March, 1987).
[2] S. Kappor 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 (Berkeley, California, May 1986) pp. 147–159.
[3] N. Karmarkar, ”A new polynomial time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065 · doi:10.1007/BF02579150
[4] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complemtarity problems,”Mathematical Programming 44 (1989) 1–26, this issue. · Zbl 0676.90087 · doi:10.1007/BF01587074
[5] M.K. Kozlov, S.P. Tarasov and L.G. Khachiyan, ”Polynomial solvability of convex quadratic programming,”Doklady Akademiia Nauk SSSR 5 (1979) 1051–1053. [Translated in:Soviet Mathematics Doklady 20 (1979) 1108–1111.] · Zbl 0434.90071
[6] C.E. Lemke, ”On complementary pivot theory,” in: G.B. Dantzig and A.F. Vienott, eds.,Mathematics of the Decision Sciences, Part I (American Mathematical Society, Providence, RI, 1968) pp. 95–114. · Zbl 0208.45502
[7] N. Megiddo, ”Pathways to the optimal set in linear programming,” Research Report, IBM Almaden Research Center (San Jose, CA, 1986). · Zbl 0612.90082
[8] C.R. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, New Jersey, 1982). · Zbl 0503.90060
[9] P.M. Vaidya, ”An algorithm for linear programming which requires O(((m + n)n 2+(m + n) 1.5 n)L) arithmetic operations,” Preprint, AT&T Bell Laboratories (Murray Hill, NJ, 1987). · Zbl 0708.90047
[10] Y. Ye and E. Tse, ”A polynomial algorithm for convex quadratic programming,” Working Paper, Department of Engineering-Economic Systems, Stanford University (Stanford, CA, 1986).
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.