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

scientific article; zbMATH DE number 3677572 (Why is no real title available?)
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
Checking local optimality in constrained quadratic programming is NP- hard
Constrained global optimization: algorithms and applications
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)

A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation
Special cases of the quadratic assignment problem
Convex hull results on quadratic programs with non-intersecting constraints
Quadratic programming and combinatorial minimum weight product problems
Open questions in complexity theory for numerical optimization
A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity
A Global Optimization Approach for Multimarginal Optimal Transport Problems with Coulomb Cost
Extending the Scope of Robust Quadratic Optimization
A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs
On solving linear complementarity problems by DC programming and DCA
On zero duality gap in nonconvex quadratic programming problems
Improved branch and bound algorithm and an interpolation-based search algorithm for quadratic minimization with one negative eigenvalue
A new SOCP relaxation of nonconvex quadratic programming problems with a few negative eigenvalues
Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming
On probability-raising causality in Markov decision processes
Improved semidefinite bounding procedure for solving max-cut problems to optimality
Quadratic programming is in NP
Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems
Smoothed amplitude flow-based phase retrieval algorithm
Optimization of functions with rank-two variation over a box
Statistical Analysis of Random Objects Via Metric Measure Laplacians
Foundations of probability-raising causality in Markov decision processes
Distribution of Distances based Object Matching: Asymptotic Inference
Conic approximation to nonconvex quadratic programming with convex quadratic constraints
Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods
On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems
Multi-market portfolio optimization with conditional value at risk
Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
On the construction of converging hierarchies for polynomial optimization based on certificates of global positivity
Semidefinite programming for discrete optimization and matrix completion problems
Linear interval parametric approach to testing pseudoconvexity
Complexity, exactness, and rationality in polynomial optimization
Complexity, exactness, and rationality in polynomial optimization
Theoretical and computational results about optimality-based domain reductions
A new branch-and-bound approach to semi-supervised support vector machine
Computation of the output of a function with fuzzy inputs based on a low-rank tensor approximation
Derivative-free trust region optimization for robust well control under geological uncertainty
Approximation algorithms for indefinite quadratic programming
Bounds on the spectral sparsification of symmetric and off-diagonal nonnegative real matrices
Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization
DC decomposition based branch-and-bound algorithms for box-constrained quadratic programs
An approximation algorithm for indefinite mixed integer quadratic programming
How to calculate the barycenter of a weighted graph
Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs
The complexity of simple models -- a study of worst and typical hard cases for the standard quadratic optimization problem
Completely positive and copositive program modelling for quadratic optimization problems
Role of sparsity and structure in the optimization landscape of non-convex matrix sensing
A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs
Extensions of Dinkelbach's algorithm for solving nonlinear fractional programming problems
A canonical dual approach for solving linearly constrained quadratic programs
Duality for semi-definite and semi-infinite programming
Strongly polynomial algorithm for a production-transportation problem with concave production cost
On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs
The exact solution of multiparametric quadratically constrained quadratic programming problems
Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality
Solutions to quadratic minimization problems with box and integer constraints
An efficient global algorithm for a class of indefinite separable quadratic programs
On the complexity of finding a local minimizer of a quadratic function over a polytope
On the relaxation complexity of nonconvex quadratic global optimization
Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound
Exact worst-case performance of first-order methods for composite convex optimization
A new polynomially solvable class of quadratic optimization problems with box constraints
A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables
Adaptive global algorithm for solving box-constrained non-convex quadratic minimization problems
Global optimization for non-convex programs via convex proximal point method
A finite algorithm for solving general quadratic problems
Adaptive computable approximation to cones of nonnegative quadratic functions
An LPCC approach to nonconvex quadratic programs
On tail dependence matrices. The realization problem for parametric families
Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial
A new algorithm for concave quadratic programming
Optimization and analysis of the profitability of tariff structures with two-part tariffs
A parametric branch and bound approach to suboptimal explicit hybrid MPC
Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities
An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials
Linear decomposition approach for a class of nonconvex programming problems
On exact and inexact RLT and SDP-RLT relaxations of quadratic programs with box constraints
Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution
A solution method for combined semi-infinite and semi-definite programming
Energy-regenerative model predictive control
Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems
Strongly polynomial time algorithms for certain concave minimization problems on networks
A study of piecewise linear-quadratic programs
Canonical duality theory: connections between nonconvex mechanics and global optimization
Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming
A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming
A new algorithm for the general quadratic programming problems with box constraints
A new Lagrangian-Benders approach for a concave cost supply chain network design problem
scientific article; zbMATH DE number 7413562 (Why is no real title available?)
Nonconvex quadratically constrained quadratic programming: Best D.C. Decompositions and their SDP representations
On a solution method in indefinite quadratic programming under linear constraints
How Do Exponential Size Solutions Arise in Semidefinite Programming?
Hierarchy relaxations for robust equilibrium constrained polynomial problems and applications to electric vehicle charging scheduling
Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard
Trading performance for stability in Markov decision processes
Generic properties for semialgebraic programs
An extension of Yuan's lemma and its applications in optimization
A polariton graph simulator
Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques
Minimizing the sum of a convex function and a specially structured nonconvex function

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)