Checking local optimality in constrained quadratic programming is NP- hard

Recommendations

On the complexity of local search in unconstrained quadratic binary optimization
scientific article; zbMATH DE number 861333
On the complexity of finding a local minimizer of a quadratic function over a polytope
On the quality of local search for the quadratic assignment problem
Complexity of uniqueness and local search in quadratic 0-1 programming
Local minimizer of a nonconvex quadratic programming problem
Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs
On the number of local maxima in quadratic 0-1 programs
Local search in a quadratic-linear bilevel programming problem
On local non-global minimizers of quadratic optimization problem with a single quadratic constraint

Cites work

Constrained global optimization: algorithms and applications
scientific article; zbMATH DE number 3566230 (Why is no real title available?)
scientific article; zbMATH DE number 3639144 (Why is no real title available?)
Second Order Conditions for Constrained Minima
Some NP-complete problems in quadratic and nonlinear programming
The complexity of analog computation

Cited in

(70)

Quadratic programming with one negative eigenvalue is NP-hard
An optimality criterion for global quadratic optimization
Complexity of uniqueness and local search in quadratic 0-1 programming
Algorithms for the single-source uncapacitated minimum concave-cost network flow problem
On the complexity of finding stationary points of nonconvex quadratic programs
Parallel computing in nonconvex programming
A new technique for generating quadratic programming test problems
A finite algorithm for solving general quadratic problems
Role of copositivity in optimality criteria for nonconvex optimization problems
A finite concave minimization algorithm using branch and bound and neighbor generation
Descent approaches for quadratic bilevel programming
On the complexity of approximating a KKT point of quadratic programming
Global optimality conditions for fixed charge quadratic programs
New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation
Generalized \(\gamma\)-valid cut procedure for concave minimization
An unconstrained optimization problem is NP-hard given an oracle representation of its objective function: a technical note
Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs
A branch-and-reduce approach to global optimization
Exact solution approach for a class of nonlinear bilevel knapsack problems
On the complexity of finding a local minimizer of a quadratic function over a polytope
On the complexity of testing attainment of the optimal value in nonlinear optimization
Optimality conditions for maximizing a function over a polyhedron
Invex optimization revisited
On the solution of concave knapsack problems
Minimum concave-cost network flow problems: Applications, complexity, and algorithms
A logarithmic descent direction algorithm for the quadratic knapsack problem
A dynamic inventory model with supplier selection in a serial supply chain structure
Methods for convex and general quadratic programming
On second order conditions for equality constrained extremum problems
Globally tight bounds for almost differentiable functions over polytopes with application to tolerance analysis.
Solving a combined cutting-stock and lot-sizing problem with a column generating procedure
Second-order sufficient optimality conditions for local and global nonlinear programming
Block pivoting and shortcut strategies for detecting copositivity
A new rectangle branch-and-reduce approach for solving nonconvex quadratic programming problems
A new class of improved convex underestimators for twice continuously differentiable constrained NLPs
Continuous quadratic programming formulations of optimization problems on graphs
Polynomial time algorithms for some classes of constrained nonconvex quadratic problems
Multilevel (Hierarchical) Optimization: Complexity Issues, Optimality Conditions, Algorithms
Some NP-complete problems in quadratic and nonlinear programming
Solving the canonical dual of box- and integer-constrained nonconvex quadratic programs via a deterministic direct search algorithm
Convex Maximization via Adjustable Robust Optimization
A general regularized continuous formulation for the maximum clique problem
Closing the gap between necessary and sufficient conditions for local nonglobal minimizer of trust region subproblem
A sufficient conditions for global quadratic optimization
Piecewise convex maximization problems: Piece adding technique
A dynamic convexized method for nonconvex mixed integer nonlinear programming
On convergence of the simplicial branch-and-bound algorithm based on \(\omega\)-subdivisions
Finiteness result for the simplicial branch-and-bound algorithm based on \(\omega\)-subdivisions
Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints
Global optimization over a box via canonical dual function
A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees
A quadratic simplex algorithm for primal optimization over zero-one polytopes
Solving optimization problems on ranks and inertias of some constrained nonlinear matrix functions via an algebraic linearization method
A new global optimization algorithm for mixed-integer quadratically constrained quadratic fractional programming problem
Open questions in complexity theory for numerical optimization
The complexity of computing KKT solutions of quadratic programs
Leveraging GPU batching for scalable nonlinear programming through massive Lagrangian decomposition
Computing local minimizers in polynomial optimization under genericity conditions
Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard
An optimization setup of the decarbonization problem in the transportation sector
Maximization of generalized convex functionals in locally convex spaces.
Interior-point algorithms for global optimization
Algorithms for the solution of quadratic knapsack problems
Global optimization algorithms for linearly constrained indefinite quadratic problems
Objective function features providing barriers to rapid global optimization
A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation
Solution to nonconvex quadratic programming with both inequality and box constraints
A new bound-and-reduce approach of nonconvex quadratic programming problems
Active constraints, indefinite quadratic test problems, and complexity
Solutions to quadratic minimization problems with box and integer constraints

This page was built for publication: Checking local optimality in constrained quadratic programming is NP- hard

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