Quadratic programming is in NP
From MaRDI portal
Publication:2640441
DOI10.1016/0020-0190(90)90100-CzbMath0719.90052MaRDI QIDQ2640441
Publication date: 1990
Published in: Information Processing Letters (Search for Journal in Brave)
Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20)
Related Items (41)
On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming ⋮ Trading performance for stability in Markov decision processes ⋮ The complexity of approximating a nonlinear program ⋮ Robustness to rank reversal in pairwise comparison matrices based on uncertainty bounds ⋮ On the utility maximization of the discrepancy between a perceived and market implied risk neutral distribution ⋮ Folded concave penalized sparse linear regression: sparsity, statistical performance, and algorithmic theory for local solutions ⋮ Facets of a mixed-integer bilinear covering set with bounds on variables ⋮ A study of piecewise linear-quadratic programs ⋮ Random projections for quadratic programs ⋮ Foundations of probability-raising causality in Markov decision processes ⋮ Approximation of the quadratic set covering problem ⋮ An approximation algorithm for indefinite mixed integer quadratic programming ⋮ Invariants of SDP exactness in quadratic programming ⋮ New bounds for nonconvex quadratically constrained quadratic programming ⋮ How Do Exponential Size Solutions Arise in Semidefinite Programming? ⋮ The computability of LQR and LQG control ⋮ Abstract interpretation meets convex optimization ⋮ Abstract model repair for probabilistic systems ⋮ On the complexity of computing the handicap of a sufficient matrix ⋮ Eigenvalue-based algorithm and analysis for nonconvex QCQP with one constraint ⋮ Solving optimization problems on ranks and inertias of some constrained nonlinear matrix functions via an algebraic linearization method ⋮ The computational complexity of evolutionarily stable strategies ⋮ Quadratic programming with one negative eigenvalue is NP-hard ⋮ Analysis of copositive optimization based linear programming bounds on standard quadratic optimization ⋮ Canonical Duality Theory: Connections between Nonconvex Mechanics and Global Optimization ⋮ Mixed-integer quadratic programming is in NP ⋮ Issues in computing contact forces for non-penetrating rigid bodies ⋮ Approximation algorithms for indefinite quadratic programming ⋮ Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial ⋮ On the parallel approximability of a subclass of quadratic programming. ⋮ Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming ⋮ Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons ⋮ QPLIB: a library of quadratic programming instances ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ On approximation algorithms for concave mixed-integer quadratic programming ⋮ Complexity, exactness, and rationality in polynomial optimization ⋮ Hessian Barrier Algorithms for Linearly Constrained Optimization Problems ⋮ Characterizations of mixed binary convex quadratic representable sets ⋮ An Error Analysis for Polynomial Optimization over the Simplex Based on the Multivariate Hypergeometric Distribution ⋮ On the complexity of finding a local minimizer of a quadratic function over a polytope ⋮ Exact Augmented Lagrangian Duality for Mixed Integer Quadratic Programming
Cites Work
This page was built for publication: Quadratic programming is in NP
