zbMATH — the first resource for mathematics

On affine scaling algorithms for nonconvex quadratic programming. (English) Zbl 0767.90065
Summary: We investigate the use of interior algorithms, especially the affine- scaling algorithm, to solve nonconvex — indefinite or negative definite — quadratic programming (QP) problems. Although the nonconvex QP with a polytope constraint is a “hard” problem, we show that the problem with an ellipsoidal constraint is “easy”. When the “hard” QP is solved by successively solving the “easy” QP, the sequence of points monotonically converges to a feasible point satisfying both the first and the second order optimality conditions.

90C26 Nonconvex programming, global optimization
90C20 Quadratic programming
90C60 Abstract computational complexity for mathematical programming problems
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI
[1] M. Ben Daya and C.M. Shetty, ”Polynomial barrier function algorithms for convex quadratic programming,” Report J 88-5, School of ISE, Georgia Institute of Technology (Atlanta, GA, 1988). · Zbl 0641.90058
[2] L. Csanky, ”Fast parallel matrix inversion algorithms,”SIAM Journal on Computing 4 (1976) 618–623. · Zbl 0353.68063
[3] I.I. Dikin, ”Iterative solution of problems of linear and quadratic programming,”Soviet Mathematical Doklady 8 (1967) 674–675. · Zbl 0189.19504
[4] M.R. Garey and D.S. Johnson,Computers and Intractability, A Guide to the Theory of NP-completeness (Freeman, New York, 1968). · Zbl 0411.68039
[5] D.M. Gay, ”Computing optimal locally constrained steps,”SIAM Journal on Scientific and Statistical Computing 2 (1981) 186–197. · Zbl 0467.65027
[6] D. Goldfarb and S. Liu, ”An O(n 3 L) primal interior point algorithm for convex quadratic programming,”Mathematical Programming 49 (1990/91) 325–340. · Zbl 0717.90055
[7] S.M. Goldfeld, R.E. Quandt and H.F. Trotter, ”Maximization by quadratic hill climbing,”Econometrica 34 (1966) 541–551. · Zbl 0145.40901
[8] B. Kalantari and J.B. Rosen, ”Large scale concave quadratic minimization and extensions,” Ph.D. Thesis, Computer Science Department, University of Minnesota (Minneapolis, MN, 1984).
[9] S. Kapoor and P. Vaidya, ”Fast algorithms for Convex quadratic programming and multicommodity flows,”Proceedings of the 18th Annual ACM Symposium on Theory Computing (1986) 147–159.
[10] N. Karmarkar, ”A new polynomial-time algorithm for linear programming,”Combinatorica 4 (1984) 373–395. · Zbl 0557.90065
[11] M. Kojima, S. Mizuno and A. Yoshise, ”A polynomial-time algorithm for a class of linear complementarity problems,”Mathematical Programming 44 (1989) 1–26. · Zbl 0676.90087
[12] T.Y. Li and T. Sauer, ”Homotopy methods for generalized eigenvalue problems,”Linear Algebra Applications 91 (1987) 65–74. · Zbl 0621.65028
[13] S. Mehrotra and J. Sun, ”An algorithm for convex quadratic programming that requires O(n 3.5 L) arithmetic operations Mathematics of Operations Research 15 (1990) 342–363. · Zbl 0714.90075
[14] R.C. Monteiro and I. Alder, ”An O(n 3 L) primal–dual interior point algorithm for convex quadratic programming,”Mathematical Programming 44 (1989) 27–42. · Zbl 0676.90038
[15] J.J. MorĂ©, ”The Levenberg-Marquardt algorithm: implementation and theory,” in G.A. Watson:Numerical Analysis (Springer, New York, 1977).
[16] K.G. Murty,Linear and Combinatorial Programming (Krieger Publishing Company, Malabar, 1976). · Zbl 0334.90032
[17] 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
[18] V. Pan, ”Algebraic complexity of computing polynomial zeros,” manuscript, Computer Science Department, SUNY at Albany (Albany, NY, 1988).
[19] C.H. Papadimitriou and K. Steiglitz,Combinatorial Optimization: Algorithms and Complexity (Prentice-Hall, Englewood Cliffs, NY, 1982). · Zbl 0503.90060
[20] P.M. Pardalos and J.B. Rosen,Constrained Global Optimization: Algorithms and Applications, Lecture Notes in Computer Sciences 268 (Springer, Berlin, 1987). · Zbl 0638.90064
[21] J. Renegar, ”A polynomial-time algorithm based on Newton’s method for linear programming,”Mathematical Programming 40 (1988) 59–93. · Zbl 0654.90050
[22] J. Renegar, private communication (1989).
[23] G. Sonnevend, ”An ’analytic center’ for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming,”Proceedings 12th IFIP Conference on System Modeling and Optimization (Budapest, 1985).
[24] D.C. Sorensen, ”Newton’s method with a model trust region modification,” Report ANL-80-106, Argonne National Laboratory (Argonne, IL, 1980). · Zbl 0483.65039
[25] M.J. Todd and Y. Ye, ”A centered projective algorithm for linear programming,”Mathematics of Operations Research 15 (1990) 508–529. · Zbl 0722.90044
[26] R.J. Vanderbei, M.S. Meketon and B.A. Freedman, ”On a modification of Karmarkar’s linear programming algorithm,”Algorithmica 1 (1986) 395–407. · Zbl 0626.90056
[27] Y. Ye, ”Interior algorithms for linear, quadratic, and linearly constrained convex programming,” Ph.D. Thesis, Department of Engineering-Economic Systems, Stanford University (Stanford, CA, 1987).
[28] Y. Ye, ”An extension of Karmarkar’s algorithm and the trust region method for quadratic programming,” in: N. Megiddo, ed.,Progress in Mathematical Programming (Springer, New York, 1989). · Zbl 0678.90064
[29] 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
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.