Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
From MaRDI portal
Publication:3200891
DOI10.1080/02331939008843615zbMath0714.90082MaRDI QIDQ3200891
Publication date: 1990
Published in: Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/02331939008843615
global optimization; extreme points; indefinite quadratic problems; product of two linear functions; isolated local minimum areas
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
An outer approximation method for minimizing the product of several convex functions on a convex set, An algorithm for solving convex programs with an additional convex- concave constraint, A FPTAS for a class of linear multiplicative problems, An outcome-space finite algorithm for solving linear multiplicative programming, A nonisolated optimal solution of general linear multiplicative programming problems, Branch-and-reduce algorithm for convex programs with additional multiplicative constraints, Quadratic programming with one negative eigenvalue is NP-hard, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, A finite algorithm for solving general quadratic problems, Global minimization of a generalized convex multiplicative function, Bilinear separation of two sets in \(n\)-space, Strongly polynomial time algorithms for certain concave minimization problems on networks, Using copositivity for global optimality criteria in concave quadratic programming problems, Convex programs with an additional constraint on the product of several convex functions, Outcome-space cutting-plane algorithm for linear multiplicative programming, Efficient algorithms for solving certain nonconvex programs dealing with the product of two affine fractional functions, On the use of optimization models for portfolio selection: A review and some computational results, A branch-and-reduce approach to global optimization, A simplicial branch and bound duality-bounds algorithm to linear multiplicative programming, \(NP\)-hardness of linear multiplicative programming and related problems, Minimizing the sum of a convex function and a specially structured nonconvex function
Cites Work
- A new polynomial-time algorithm for linear programming
- On a class of quadratic programs
- The simplex method. A probabilistic analysis
- A note on a quadratic formulation for linear complementarity problems
- Global minimization of indefinite quadratic problems
- Karmarkar's algorithm and the ellipsoid method
- Checking local optimality in constrained quadratic programming is NP- hard
- Global Optimization Approach to the Linear Complementarity Problem
