Quadratic programming with one negative eigenvalue is NP-hard

Recommendations

Some NP-complete problems in quadratic and nonlinear programming
On the complexity of finding stationary points of nonconvex quadratic programs
Checking local optimality in constrained quadratic programming is NP- hard
Quadratic programming is in NP
The clique problem for graphs with a few eigenvalues of the same sign

Cites work

Checking local optimality in constrained quadratic programming is NP- hard
Constrained global optimization: algorithms and applications
scientific article; zbMATH DE number 3677572 (Why is no real title available?)
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
Methods for Global Concave Minimization: A Bibliographic Survey
Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
Quadratic programming is in NP
Some NP-complete problems in quadratic and nonlinear programming

Cited in

(only showing first 100 items - show all)

Complexity results for some global optimization problems
Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality
Special cases of the quadratic assignment problem
Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
On the complexity of finding stationary points of nonconvex quadratic programs
Extensions of Dinkelbach's algorithm for solving nonlinear fractional programming problems
A new technique for generating quadratic programming test problems
A finite algorithm for solving general quadratic problems
Strongly polynomial time algorithms for certain concave minimization problems on networks
Optimality conditions and optimization methods for quartic polynomial optimization
Energy-regenerative model predictive control
An extension of Yuan's lemma and its applications in optimization
Completely positive reformulations of polynomial optimization problems with linear constraints
An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix
A new branch-and-bound approach to semi-supervised support vector machine
Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods
New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
A nonconvex quadratic optimization approach to the maximum edge weight clique problem
Globally solving nonconvex quadratic programming problems via completely positive programming
On approximation algorithms for concave mixed-integer quadratic programming
A reformulation-convexification approach for solving nonconvex quadratic programming problems
Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs
A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
An exact algorithm for graph partitioning
On topology optimization and canonical duality method
A new algorithm for concave quadratic programming
Computation of the output of a function with fuzzy inputs based on a low-rank tensor approximation
Conic approximation to nonconvex quadratic programming with convex quadratic constraints
The exact solution of multiparametric quadratically constrained quadratic programming problems
Linear interval parametric approach to testing pseudoconvexity
Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems
A new polynomially solvable class of quadratic optimization problems with box constraints
Adaptive global algorithm for solving box-constrained non-convex quadratic minimization problems
On the complexity of finding a local minimizer of a quadratic function over a polytope
Compact mixed-integer programming formulations in quadratic optimization
A new SOCP relaxation of nonconvex quadratic programming problems with a few negative eigenvalues
Derivative-free trust region optimization for robust well control under geological uncertainty
Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
On tail dependence matrices. The realization problem for parametric families
A study of piecewise linear-quadratic programs
Smoothed amplitude flow-based phase retrieval algorithm
A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs
A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables
Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming
Range assignment of base-stations maximizing coverage area without interference
Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy
On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems
The clique problem for graphs with a few eigenvalues of the same sign
Methods for convex and general quadratic programming
Regularized robust optimization: the optimal portfolio execution case
Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming
Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution
Improved semidefinite bounding procedure for solving max-cut problems to optimality
Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems
A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
\(NP\)-hardness of linear multiplicative programming and related problems
On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs
A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming
Quadratic programming is in NP
Multi-market portfolio optimization with conditional value at risk
A computational study on QP problems with general linear constraints
Global optimization for non-convex programs via convex proximal point method
A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs
Theoretical and computational results about optimality-based domain reductions
An efficient global algorithm for a class of indefinite separable quadratic programs
Topographic mapping of large dissimilarity data sets
On approximation algorithms for concave mixed-integer quadratic programming
Trading performance for stability in Markov decision processes
Canonical duality theory: connections between nonconvex mechanics and global optimization
Some NP-complete problems in quadratic and nonlinear programming
An FPTAS for optimizing a class of low-rank functions over a polytope
Minimizing the sum of a convex function and a specially structured nonconvex function
Strongly polynomial algorithm for a production-transportation problem with concave production cost
An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization
Exact computable representation of some second-order cone constrained quadratic programming problems
On solving linear complementarity problems by DC programming and DCA
On zero duality gap in nonconvex quadratic programming problems
An LPCC approach to nonconvex quadratic programs
A canonical dual approach for solving linearly constrained quadratic programs
Duality for semi-definite and semi-infinite programming
A parametric branch and bound approach to suboptimal explicit hybrid MPC
A solution method for combined semi-infinite and semi-definite programming
Bounds on the spectral sparsification of symmetric and off-diagonal nonnegative real matrices
Nonlinear optimization problem of interdependent investment projects portfolio
A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity
Extending the Scope of Robust Quadratic Optimization
Satisfactory fault tolerant control with soft-constraint for discrete time-varying systems: numerical recursive approach
On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity
An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints
Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques
Completely positive and copositive program modelling for quadratic optimization problems
scientific article; zbMATH DE number 7413562 (Why is no real title available?)
Adaptive computable approximation to cones of nonnegative quadratic functions
The complexity of simple models -- a study of worst and typical hard cases for the standard quadratic optimization problem
How to calculate the barycenter of a weighted graph
Linear decomposition approach for a class of nonconvex programming problems
Exact worst-case performance of first-order methods for composite convex optimization
LP relaxations for a class of linear semi-infinite programming problems
Generic properties for semialgebraic programs
Relaxing the optimality conditions of box QP

This page was built for publication: Quadratic programming with one negative eigenvalue is NP-hard

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