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
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
