Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
From MaRDI portal
Publication:3200891
DOI10.1080/02331939008843615zbMath0714.90082OpenAlexW1978344132MaRDI QIDQ3200891
Publication date: 1990
Published in: Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1080/02331939008843615
global optimizationextreme pointsindefinite quadratic problemsproduct of two linear functionsisolated local minimum areas
Abstract computational complexity for mathematical programming problems (90C60) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20) Computational methods for problems pertaining to operations research and mathematical programming (90-08)
Related Items
Algorithms for approximate linear regression design with application to a first order model with heteroscedasticity, Convex programs with an additional constraint on the product of several convex functions, On the use of optimization models for portfolio selection: A review and some computational results, A simplicial branch and bound duality-bounds algorithm to linear multiplicative programming, A FPTAS for a class of linear multiplicative problems, An outcome-space finite algorithm for solving linear multiplicative programming, A branch-and-reduce approach to global optimization, Active fault diagnosis for linear stochastic systems subject to chance constraints, An efficient global algorithm for indefinite separable quadratic knapsack problems with box constraints, A global optimization approach for solving generalized nonlinear multiplicative programming problem, Quadratic programming with one negative eigenvalue is NP-hard, 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, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, Minimizing the sum of a convex function and a specially structured nonconvex function, Efficient algorithms for solving certain nonconvex programs dealing with the product of two affine fractional functions, A nonisolated optimal solution of general linear multiplicative programming problems, Branch-and-reduce algorithm for convex programs with additional multiplicative constraints, \(NP\)-hardness of linear multiplicative programming and related problems, Outcome-space cutting-plane algorithm for linear multiplicative programming, 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, Global optimization method for linear multiplicative programming
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