Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

DOI10.1080/02331939008843615MaRDI QIDQ3200891zbMATH OpenOpenAlexFDO

Authors Panos M. Pardalos

Publication date 1990

Published in Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1080/02331939008843615

zbMATH Keywords

extreme pointsglobal optimizationindefinite quadratic problemsisolated local minimum areasproduct of two linear functions

Mathematics Subject Classification ID

Computational methods for problems pertaining to operations research and mathematical programming (90-08) Quadratic programming (90C20) Nonconvex programming, global optimization (90C26) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• On the complexity of quadratic programming with two quadratic constraints
• Active constraints, indefinite quadratic test problems, and complexity
• scientific article; zbMATH DE number 1139465
• Approximation algorithms for indefinite quadratic programming
• Some NP-complete problems in quadratic and nonlinear programming

Cites work

• A new polynomial-time algorithm for linear programming
• A note on a quadratic formulation for linear complementarity problems
• Checking local optimality in constrained quadratic programming is NP- hard
• Global minimization of indefinite quadratic problems
• Global Optimization Approach to the Linear Complementarity Problem
• Karmarkar's algorithm and the ellipsoid method
• On a class of quadratic programs
• The simplex method. A probabilistic analysis

Cited in

(36)

• A nonisolated optimal solution of general linear multiplicative programming problems
• Branch-and-reduce algorithm for convex programs with additional multiplicative constraints
• On a class of quadratic programs
• 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
• Algorithms for approximate linear regression design with application to a first order model with heteroscedasticity
• A global optimization approach for solving generalized nonlinear multiplicative programming problem
• 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
• Global optimization method for linear multiplicative programming
• On the complexity of quadratic programming with two quadratic constraints
• A simplicial branch and bound duality-bounds algorithm to linear multiplicative programming
• \(NP\)-hardness of linear multiplicative programming and related problems
• A polynomial-time algorithm for affine variational inequalities
• Polynomial-Time Algorithms for Linear and Convex Optimization on Jump Systems
• Minimizing the sum of a convex function and a specially structured nonconvex function
• Approximation algorithms for homogeneous polynomial optimization with quadratic constraints
• 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 polynomial-time recursive algorithm for some unconstrained quadratic optimization problems
• Active fault diagnosis for stochastic systems subject to non-convex input constraints
• A method based on parametric convex programming for solving convex multiplicative programming problem
• An adaptive optimization algorithm to solve a class of linear multiplicative problems
• Non-convex optimization problems with linear KKT subsystem
• 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

This page was built for publication: Polynomial time algorithms for some classes of constrained nonconvex quadratic problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3200891)