Some NP-complete problems in quadratic and nonlinear programming

Recommendations

Checking local optimality in constrained quadratic programming is NP- hard
On the complexity of finding stationary points of nonconvex quadratic programs
Quadratic programming with one negative eigenvalue is NP-hard
On the complexity of quadratic programming in real number models of computation
Quadratic programming is in NP

Cites work

scientific article; zbMATH DE number 4089320 (Why is no real title available?)
scientific article; zbMATH DE number 3523317 (Why is no real title available?)
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
scientific article; zbMATH DE number 3307153 (Why is no real title available?)
Simplicial and Continuation Methods for Approximating Fixed Points and Solutions to Systems of Equations
The computation of fixed points and applications

Cited in

(only showing first 100 items - show all)

Copositive Lyapunov functions for switched systems over cones
Approachability in repeated games: Computational aspects and a Stackelberg variant
Efficient heuristics for inventory placement in acyclic networks
On the computation of \(C^*\) certificates
Checking local optimality in constrained quadratic programming is NP- hard
Local optimization on graphs
On computational complexity of invalidating structured uncertainty models
Quadratic programming with one negative eigenvalue is NP-hard
An analytical approach to global optimization
Local minima for indefinite quadratic knapsack problems
An optimality criterion for global quadratic optimization
On affine scaling algorithms for nonconvex quadratic programming
On the complexity of finding stationary points of nonconvex quadratic programs
A new technique for generating quadratic programming test problems
A finite algorithm for solving general quadratic problems
Using copositivity for global optimality criteria in concave quadratic programming problems
Detecting all evolutionarily stable strategies
Role of copositivity in optimality criteria for nonconvex optimization problems
Complexity of a class of nonlinear combinatorial problems related to their linear counterparts
A branch bound method for subset sum problem
Complexity issues in robust stability of linear delay-differential systems
Minimum distance to the complement of a convex set: Duality result
On the complexity of approximating a KKT point of quadratic programming
An objective general index for multivariate ordered data
Investigations in topology. 9. Work collection
Conditionally definite matrices
Bitopologies on products and ratios
An effective iterated tabu search for the maximum bisection problem
Constrained optimization with integer and continuous variables using inexact restoration and projected gradients
LP-based tractable subcones of the semidefinite plus nonnegative cone
Nested nonnegative cone analysis
Distributionally robust chance constrained problem under interval distribution information
Copositivity detection of tensors: theory and algorithm
UTA-poly and UTA-splines: additive value functions with polynomial marginals
A fresh CP look at mixed-binary QPs: new formulations and relaxations
Improved approximation results on standard quartic polynomial optimization
Open weak CAD and its applications
Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017
A robust unscented transformation for uncertain moments
Bounding averages rigorously using semidefinite programming: mean moments of the Lorenz system
Optimization over structured subsets of positive semidefinite matrices via column generation
Equivalences and differences in conic relaxations of combinatorial quadratic optimization problems
A new conic approach to semisupervised support vector machines
On approximation algorithms for concave mixed-integer quadratic programming
Note on combinatorial optimization with max-linear objective functions
The impact of accelerating tools on the interval subdivision algorithm for global optimization
Quadratic-programming criteria for copositive matrices
A continuous approach to nonlinear integer programming
Some aspects of studying an optimization or decision problem in different computational models
Criteria for copositive matrices using simplices and barycentric coordinates
A branch-and-bound algorithm for bound constrained optimization problems without derivatives
Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs
A branch-and-reduce approach to global optimization
NP-hardness of deciding convexity of quartic polynomials and related problems
An exact algorithm for graph partitioning
Separation and relaxation for cones of quadratic forms
Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
Algebra -- 9. Translated from the Russian
On the conditions for the finite termination of ADMM and its applications to SOS polynomials feasibility problems
Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches
A simplex algorithm for rational cp-factorization
The extreme rays of the \(6\times 6\) copositive cone
A proximal DC approach for quadratic assignment problem
Polyhedral approximations of the semidefinite cone and their application
Maximizing perturbation radii for robust convex quadratically constrained quadratic programs
Discriminant analysis of distributional data via fractional programming
Partially distributed outer approximation
Stability of the linear complementarity problem properties under interval uncertainty
A modified simplex partition algorithm to test copositivity
Fast incremental expectation maximization for finite-sum optimization: nonasymptotic convergence
Newton polytopes and relative entropy optimization
An alternative perspective on copositive and convex relaxations of nonconvex quadratic programs
Complexity aspects of local minima and related notions
An adaptive high order method for finding third-order critical points of nonconvex optimization
On the geometric analysis of a quartic-quadratic optimization problem under a spherical constraint
On the complexity of finding a local minimizer of a quadratic function over a polytope
Feedback control design using sum of squares optimisation
A game-theoretic perspective of deep neural networks
An efficient PGM-based algorithm with backtracking strategy for solving quadratic optimization problems with spherical constraint
Local saddle points for unconstrained polynomial optimization
On standard quadratic programs with exact and inexact doubly nonnegative relaxations
An active-set algorithm for norm constrained quadratic problems
A game-theoretic analysis of deep neural networks
On monotonicity and search strategies in face-based copositivity detection algorithms
Simulated annealing for convex optimization: rigorous complexity analysis and practical perspectives
On the exactness of sum-of-squares approximations for the cone of \(5 \times 5\) copositive matrices
Immobile indices and CQ-free optimality criteria for linear copositive programming problems
A survey of hidden convex optimization
Data science applications to string theory
On the complexity of detecting convexity over a box
A study of piecewise linear-quadratic programs
Hermitian completely positive matrices
Lower bounds for finding stationary points I
On the complexity of testing attainment of the optimal value in nonlinear optimization
On the facet defining inequalities of the mixed-integer bilinear covering set
Testing copositivity via mixed-integer linear programming
Exploiting partial correlations in distributionally robust optimization
Globally solving extended trust region subproblems with two intersecting cuts
Two methods for the maximization of homogeneous polynomials over the simplex
Optimality conditions for maximizing a function over a polyhedron

This page was built for publication: Some NP-complete problems in quadratic and nonlinear programming

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