On affine scaling algorithms for nonconvex quadratic programming

DOI10.1007/BF01580903zbMath0767.90065MaRDI QIDQ1196182

Yinyu Ye

Publication date: 17 December 1992

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

zbMATH Keywords

nonconvex quadratic programming; NP-hard; ellipsoidal constraint; interior algorithms; affine- scaling algorithm

Mathematics Subject Classification ID

90C60: Abstract computational complexity for mathematical programming problems

90C26: Nonconvex programming, global optimization

90C20: Quadratic programming

90-08: Computational methods for problems pertaining to operations research and mathematical programming

Related Items

A splitting method for quadratic programming problem, A new algorithm for the general quadratic programming problems with box constraints, A first-order interior-point method for linearly constrained smooth optimization, A null-space method for computing the search direction in the general inertia-controlling method for dense quadratic programming, An extension of interior point potential reduction algorithm to solve general lcps, Newton-KKT interior-point methods for indefinite quadratic programming, Global optimization by canonical dual function, Solution to an optimal control problem via canonical dual method, A study on concave optimization via canonical dual function, Duallity and sensitivity in nonconvex quadratic optimization over an ellipsoid, On piecewise quadratic Newton and trust region problems, A potential reduction approach to the frequency assignment problem, On the complexity of approximating a KKT point of quadratic programming, Trust region affine scaling algorithms for linearly constrained convex and concave programs, Penalty parameter for linearly constrained 0--1 quadratic programming, Convergence properties of Dikin's affine scaling algorithm for nonconvex quadratic minimization, Bounds and fast approximation algorithms for binary quadratic optimzation problems with application to MAX 2SAT, A convergence analysis for a convex version of Dikin's algorithm, Hidden convexity in some nonconvex quadratically constrained quadratic programming, Convexity of quadratic transformations and its use in control and optimization, Multi-standard quadratic optimization: Interior point methods and cone programming reformulation, An interior-point trust-region polynomial algorithm for convex quadratic minimization subject to general convex constraints

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A modification of Karmarkar's linear programming algorithm
• A new polynomial-time algorithm for linear programming
• Homotopy method for generalized eigenvalue problems \(Ax=\lambda Bx\)
• Constrained global optimization: algorithms and applications
• A polynomial-time algorithm, based on Newton's method, for linear programming
• An extension of Karmarkar's projective algorithm for convex quadratic programming
• Interior path following primal-dual algorithms. I: Linear programming
• A polynomial-time algorithm for a class of linear complementarity problems
• An \(O(n^ 3L)\) primal interior point algorithm for convex quadratic programming
• An Algorithm for Convex Quadratic Programming That Requires O(n^3.5L) Arithmetic Operations
• A Centered Projective Algorithm for Linear Programming
• Some NP-complete problems in quadratic and nonlinear programming
• Computing Optimal Locally Constrained Steps
• Newton’s Method with a Model Trust Region Modification
• Fast Parallel Matrix Inversion Algorithms
• Maximization by Quadratic Hill-Climbing