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 computational study on QP problems with general linear constraints
Range assignment of base-stations maximizing coverage area without interference
Regularized robust optimization: the optimal portfolio execution case
Globally solving nonconvex quadratic programming problems via completely positive programming
On approximation algorithms for concave mixed-integer quadratic programming
Completely positive reformulations of polynomial optimization problems with linear constraints
LP relaxations for a class of linear semi-infinite programming problems
A reformulation-convexification approach for solving nonconvex quadratic programming problems
Compact mixed-integer programming formulations in quadratic optimization
Topographic mapping of large dissimilarity data sets
A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations
A new technique for generating quadratic programming test problems
Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy
\(NP\)-hardness of linear multiplicative programming and related problems
Minimax Problems with Coupled Linear Constraints: Computational Complexity and Duality
Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems
Complexity results for some global optimization problems
Homotopy trust-region method for phase-field approximations in perimeter-regularized binary optimal control
Guaranteed Error Bounds on Approximate Model Abstractions Through Reachability Analysis
Optimization under uncertainty and risk: quadratic and copositive approaches
A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables
The ultrametric Gromov-Wasserstein distance
An exact algorithm for graph partitioning
Nonlinear optimization problem of interdependent investment projects portfolio
Satisfactory fault tolerant control with soft-constraint for discrete time-varying systems: numerical recursive approach
An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints
Bilinear modeling solution approach for fixed charge network flow problems
Relaxing the optimality conditions of box QP
Optimization models and approaches for strongly correlated electrons systems
A normal fan projection algorithm for low-rank optimization
Polyhedral properties of RLT relaxations of nonconvex quadratic programs and their implications on exact relaxations
An FPTAS for optimizing a class of low-rank functions over a polytope
Formal lumping of polynomial differential equations through approximate equivalences
An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix
Methods for convex and general quadratic programming
A convex relaxation bound for subgraph isomorphism
New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
An FPTAS for minimizing the product of two non-negative linear cost functions
Solving optimization problems on ranks and inertias of some constrained nonlinear matrix functions via an algebraic linearization method
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 topology optimization and canonical duality method
A nonconvex quadratic optimization approach to the maximum edge weight clique problem
The clique problem for graphs with a few eigenvalues of the same sign
Optimality conditions and optimization methods for quartic polynomial optimization
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
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

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)