Checking local optimality in constrained quadratic programming is NP- hard
From MaRDI portal
Publication:1102861
DOI10.1016/0167-6377(88)90049-1zbMath0644.90067OpenAlexW2039526985MaRDI QIDQ1102861
Panos M. Pardalos, Georg Schnitger
Publication date: 1988
Published in: Operations Research Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0167-6377(88)90049-1
Related Items (61)
A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation ⋮ A finite concave minimization algorithm using branch and bound and neighbor generation ⋮ Descent approaches for quadratic bilevel programming ⋮ Solution to nonconvex quadratic programming with both inequality and box constraints ⋮ Continuous quadratic programming formulations of optimization problems on graphs ⋮ Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs ⋮ Polynomial time algorithms for some classes of constrained nonconvex quadratic problems ⋮ Global optimality conditions for fixed charge quadratic programs ⋮ On the complexity of approximating a KKT point of quadratic programming ⋮ A branch-and-reduce approach to global optimization ⋮ Global optimization over a box via canonical dual function ⋮ Convex Maximization via Adjustable Robust Optimization ⋮ A General Regularized Continuous Formulation for the Maximum Clique Problem ⋮ A Newton-CG Based Barrier Method for Finding a Second-Order Stationary Point of Nonconvex Conic Optimization with Complexity Guarantees ⋮ A new bound-and-reduce approach of nonconvex quadratic programming problems ⋮ A quadratic simplex algorithm for primal optimization over zero-one polytopes ⋮ Closing the Gap between Necessary and Sufficient Conditions for Local Nonglobal Minimizer of Trust Region Subproblem ⋮ Active constraints, indefinite quadratic test problems, and complexity ⋮ Solving optimization problems on ranks and inertias of some constrained nonlinear matrix functions via an algebraic linearization method ⋮ On second order conditions for equality constrained extremum problems ⋮ Quadratic programming with one negative eigenvalue is NP-hard ⋮ A sufficient conditions for global quadratic optimization ⋮ An optimality criterion for global quadratic optimization ⋮ New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation ⋮ Multilevel (Hierarchical) Optimization: Complexity Issues, Optimality Conditions, Algorithms ⋮ Complexity of uniqueness and local search in quadratic 0-1 programming ⋮ Optimality conditions for maximizing a function over a polyhedron ⋮ Open questions in complexity theory for numerical optimization ⋮ Algorithms for the single-source uncapacitated minimum concave-cost network flow problem ⋮ Globally tight bounds for almost differentiable functions over polytopes with application to tolerance analysis. ⋮ 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 ⋮ Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard ⋮ Piecewise convex maximization problems: Piece adding technique ⋮ Solving a combined cutting-stock and lot-sizing problem with a column generating procedure ⋮ Solving the canonical dual of box- and integer-constrained nonconvex quadratic programs via a deterministic direct search algorithm ⋮ A dynamic convexized method for nonconvex mixed integer nonlinear programming ⋮ Maximization of generalized convex functionals in locally convex spaces. ⋮ Exact solution approach for a class of nonlinear bilevel knapsack problems ⋮ Invex optimization revisited ⋮ On the solution of concave knapsack problems ⋮ Minimum concave-cost network flow problems: Applications, complexity, and algorithms ⋮ Solutions to quadratic minimization problems with box and integer constraints ⋮ Advantages of simplicial partitioning for Lipschitz optimization problems with linear constraints ⋮ A logarithmic descent direction algorithm for the quadratic knapsack problem ⋮ Generalized \(\gamma\)-valid cut procedure for concave minimization ⋮ Second-order sufficient optimality conditions for local and global nonlinear programming ⋮ Block pivoting and shortcut strategies for detecting copositivity ⋮ On the complexity of finding a local minimizer of a quadratic function over a polytope ⋮ 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 ⋮ Parallel computing in nonconvex programming ⋮ Interior-point algorithms for global optimization ⋮ A new technique for generating quadratic programming test problems ⋮ A finite algorithm for solving general quadratic problems ⋮ Algorithms for the solution of quadratic knapsack problems ⋮ Global optimization algorithms for linearly constrained indefinite quadratic problems ⋮ Role of copositivity in optimality criteria for nonconvex optimization problems ⋮ Objective function features providing barriers to rapid global optimization ⋮ A dynamic inventory model with supplier selection in a serial supply chain structure ⋮ Methods for convex and general quadratic programming
Cites Work
This page was built for publication: Checking local optimality in constrained quadratic programming is NP- hard
