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)

Scheduling for a processor sharing system with linear slowdown
A Lanczos Method for Large-Scale Extreme Lorentz Eigenvalue Problems
Data science applications to string theory
A completely positive representation of \(0\)-\(1\) linear programs with joint probabilistic constraints
Active constraints, indefinite quadratic test problems, and complexity
Signomial and polynomial optimization via relative entropy and partial dualization
Algorithms for determining the copositivity of a given symmetric matrix
A simplex algorithm for rational cp-factorization
Minimum wave speeds in monostable reaction-diffusion equations: sharp bounds by polynomial optimization
Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
Open questions in complexity theory for numerical optimization
On the accuracy of uniform polyhedral approximations of the copositive cone
Global convergence of a second-order augmented Lagrangian method under an error bound condition
scientific article; zbMATH DE number 7625188 (Why is no real title available?)
Applications of completions of operator matrices to some properties of operator products on Hilbert spaces
Augmented Lagrangians with constrained subproblems and convergence to second-order stationary points
Deciding uniqueness in norm maximazation
Optimality conditions for linear copositive programming problems with isolated immobile indices
A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
An efficient PGM-based algorithm with backtracking strategy for solving quadratic optimization problems with spherical constraint
On the facet defining inequalities of the mixed-integer bilinear covering set
Solution to nonconvex quadratic programming with both inequality and box constraints
Testing copositivity via mixed-integer linear programming
Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology
A game-theoretic perspective of deep neural networks
Uniqueness in quadratic and hyperbolic \(0-1\) programming problems
Lifting for simplicity: concise descriptions of convex sets
The bounds of feasible space on constrained nonconvex quadratic programming
Extensions of Gauss quadrature via linear programming
Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision
Distributionally Robust Chance Constrained Geometric Optimization
Complexity of a class of nonlinear combinatorial problems related to their linear counterparts
The complexity of gradient descent: CLS = PPAD pls
Bounding extrema over global attractors using polynomial optimisation
Some applications of polynomial optimization in operations research and real-time decision making
A generalized complex power iteration-based algorithm for quartic-quadratic optimization problems over a spherical constraint and its applications
Linear slices of hyperbolic polynomials and positivity of symmetric polynomial functions
Two methods for the maximization of homogeneous polynomials over the simplex
First-order methods almost always avoid strict saddle points
Solving the canonical dual of box- and integer-constrained nonconvex quadratic programs via a deterministic direct search algorithm
Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme
Global minimization of polynomial integral functionals
Conic approximation to quadratic optimization with linear complementarity constraints
Canonical dual least square method for solving general nonlinear systems of quadratic equations
Quadratic programming is in NP
Two-timescale gradient descent ascent algorithms for nonconvex minimax optimization
PGP for portfolio optimization: application to ESG index family
An effective iterated tabu search for the maximum bisection problem
Exploiting partial correlations in distributionally robust optimization
Globally solving extended trust region subproblems with two intersecting cuts
Checking local optimality in constrained quadratic programming is NP- hard
First-Order Methods for Nonconvex Quadratic Minimization
A deterministic annealing algorithm for approximating a solution of the min-bisection problem
Quadratic-programming criteria for copositive matrices
Polyhedral approximations of the semidefinite cone and their application
Unbounded convex sets for non-convex mixed-integer quadratic programming
Tensors in computations
Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems
A complete semidefinite algorithm for detecting copositive matrices and tensors
Bounding averages rigorously using semidefinite programming: mean moments of the Lorenz system
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
Optimizing a polyhedral-semidefinite relaxation of completely positive programs
On standard quadratic programs with exact and inexact doubly nonnegative relaxations
An improved algorithm to test copositivity
A convex polynomial that is not sos-convex
Local saddle points for unconstrained polynomial optimization
The extreme rays of the \(5 \times 5\) copositive cone
scientific article; zbMATH DE number 7307468 (Why is no real title available?)
On the computational complexity of membership problems for the completely positive cone and its dual
Toward unified analysis and controller synthesis for a class of hybrid systems
On the weak second-order optimality condition for nonlinear semidefinite and second-order cone programming
Convex computation of maximal Lyapunov exponents
Detecting all evolutionarily stable strategies
Effect of depth and width on local minima in deep learning
A game-theoretic analysis of deep neural networks
Copositivity detection of tensors: theory and algorithm
A guide to conic optimisation and its applications
Conic relaxations for semi-supervised support vector machines
Relative robust portfolio optimization with benchmark regret
Convex Relaxations of Integral Variational Problems: Pointwise Dual Relaxation and Sum-of-Squares Optimization
A geometric approach of gradient descent algorithms in linear neural networks
Optimality and stability of symmetric evolutionary games with applications in genetic selection
The problems of non-convex quadratic programming related to phased antenna arrays optimization
The Lorenz system as a gradient-like system
Narrowing the difficulty gap for the Celis-Dennis-Tapia problem
A hybrid branch-and-bound and evolutionary approach for allocating strings of applications to heterogeneous distributed computing systems
Stochastic robustness metric and its use for static resource allocations
Approximation algorithms for indefinite quadratic programming
Copositivity and complete positivity. Abstracts from the workshop held October 29 -- Novermber 4, 2017
Extremal copositive matrices with zero supports of cardinality n-2
Stochastic nonlinear resource allocation problem
CP graphs and SPN graphs
A semidefinite relaxation algorithm for checking completely positive separable matrices
Sharp restricted isometry bounds for the inexistence of spurious local minima in nonconvex matrix recovery
Alternative SDP and SOCP approximations for polynomial optimization
Extended trust-region problems with one or two balls: exact copositive and Lagrangian relaxations
An approximation algorithm for indefinite mixed integer quadratic programming
Distributionally robust mixed integer linear programs: persistency models with applications
Machine learning of time series using time-delay embedding and precision annealing

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)