Quadratic programming with one negative eigenvalue is NP-hard

From MaRDI portal

Publication:1177910

Jump to:navigation, search

DOI10.1007/BF00120662zbMath0755.90065WikidataQ56070241 ScholiaQ56070241MaRDI QIDQ1177910

Panos M. Pardalos, Stephen A. Vavasis

Publication date: 26 June 1992

Published in: Journal of Global Optimization (Search for Journal in Brave)

zbMATH Keywords

global optimization NP-hard concave quadratic function

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Quadratic programming (90C20)

Related Items

A new branch-and-cut algorithm for non-convex quadratic programming via alternative direction method and semidefinite relaxation, Topographic Mapping of Large Dissimilarity Data Sets, Derivative-free trust region optimization for robust well control under geological uncertainty, Theoretical and computational results about optimality-based domain reductions, Role of sparsity and structure in the optimization landscape of non-convex matrix sensing, Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound, Bilinear modeling solution approach for fixed charge network flow problems, An efficient global algorithm for a class of indefinite separable quadratic programs, Regularized robust optimization: the optimal portfolio execution case, On finding and enumerating maximal and maximum \( k\)-partite cliques in \( k\)-partite graphs, A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming, Optimality conditions and optimization methods for quartic polynomial optimization, On Approximation Algorithms for Concave Mixed-Integer Quadratic Programming, A reformulation-convexification approach for solving nonconvex quadratic programming problems, Trading performance for stability in Markov decision processes, Necessary and sufficient condition for local minima of a class of nonconvex quadratic programs, Energy-regenerative model predictive control, A strongly polynomial algorithm for a concave production-transportation problem with a fixed number of nonlinear variables, An extension of Yuan's lemma and its applications in optimization, An FPTAS for optimizing a class of low-rank functions over a polytope, An approximation bound analysis for Lasserre's relaxation in multivariate polynomial optimization, Exact computable representation of some second-order cone constrained quadratic programming problems, Special cases of the quadratic assignment problem, Completely positive reformulations of polynomial optimization problems with linear constraints, Multi-market portfolio optimization with conditional value at risk, A computational study on QP problems with general linear constraints, On tail dependence matrices. The realization problem for parametric families, On solving linear complementarity problems by DC programming and DCA, An FPTAS for minimizing the product of two non-negative linear cost functions, Enhancing the normalized multiparametric disaggregation technique for mixed-integer quadratic programming, Indefinite multi-constrained separable quadratic optimization: large-scale efficient solution, A study of piecewise linear-quadratic programs, An SR1/BFGS SQP algorithm for nonconvex nonlinear programs with block-diagonal Hessian matrix, An exact algorithm for graph partitioning, On zero duality gap in nonconvex quadratic programming problems, A new branch-and-bound approach to semi-supervised support vector machine, Global optimization for non-convex programs via convex proximal point method, An LPCC approach to nonconvex quadratic programs, A canonical dual approach for solving linearly constrained quadratic programs, Improved semidefinite bounding procedure for solving max-cut problems to optimality, Second order optimality conditions and reformulations for nonconvex quadratically constrained quadratic programming problems, Nonconvex quadratically constrained quadratic programming: Best D.C. Decompositions and their SDP representations, Solving optimization problems on ranks and inertias of some constrained nonlinear matrix functions via an algebraic linearization method, A parametric branch and bound approach to suboptimal explicit hybrid MPC, Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods, Smoothed amplitude flow-based phase retrieval algorithm, A convex relaxation bound for subgraph isomorphism, New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation, On topology optimization and canonical duality method, Nonlinear optimization problem of interdependent investment projects portfolio, Satisfactory fault tolerant control with soft-constraint for discrete time-varying systems: numerical recursive approach, A low-dimensional SDP relaxation based spatial branch and bound method for nonconvex quadratic programs, An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints, Canonical Duality Theory: Connections between Nonconvex Mechanics and Global Optimization, Approximation algorithms for indefinite quadratic programming, Open questions in complexity theory for numerical optimization, Linear decomposition approach for a class of nonconvex programming problems, A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, A nonconvex quadratic optimization approach to the maximum edge weight clique problem, Parametric simplex algorithms for a class of NP-complete problems whose average number of steps is polynomial, Minimizing the sum of a convex function and a specially structured nonconvex function, Strongly polynomial algorithm for a production-transportation problem with concave production cost, Two-stage robust LP with ellipsoidal right-hand side uncertainty is NP-hard, A solution algorithm for non-convex mixed integer optimization problems with only few continuous variables, Relaxing the optimality conditions of box QP, Globally solving nonconvex quadratic programming problems via completely positive programming, Semidefinite programming for discrete optimization and matrix completion problems, A new algorithm for concave quadratic programming, Optimization of functions with rank-two variation over a box, Computation of the output of a function with fuzzy inputs based on a low-rank tensor approximation, Optimization and analysis of the profitability of tariff structures with two-part tariffs, Conic approximation to nonconvex quadratic programming with convex quadratic constraints, The exact solution of multiparametric quadratically constrained quadratic programming problems, Linear interval parametric approach to testing pseudoconvexity, Quadratic programming and combinatorial minimum weight product problems, Second order cone constrained convex relaxations for nonconvex quadratically constrained quadratic programming, Solutions to quadratic minimization problems with box and integer constraints, Successive Lagrangian relaxation algorithm for nonconvex quadratic optimization, DC decomposition based branch-and-bound algorithms for box-constrained quadratic programs, Range assignment of base-stations maximizing coverage area without interference, On approximation algorithms for concave mixed-integer quadratic programming, Computing mixed strategies equilibria in presence of switching costs by the solution of nonconvex QP problems, Minimizing rational functions by exact Jacobian SDP relaxation applicable to finite singularities, A new polynomially solvable class of quadratic optimization problems with box constraints, Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy, On semi-infinite systems of convex polynomial inequalities and polynomial optimization problems, Complexity results for some global optimization problems, A Coordinate Ascent Method for Solving Semidefinite Relaxations of Non-convex Quadratic Integer Programs, Adaptive global algorithm for solving box-constrained non-convex quadratic minimization problems, Solutions and optimality criteria for nonconvex constrained global optimization problems with connections between canonical and Lagrangian duality, \(NP\)-hardness of linear multiplicative programming and related problems, On the complexity of finding a local minimizer of a quadratic function over a polytope, Compact mixed-integer programming formulations in quadratic optimization, Extensions of Dinkelbach's algorithm for solving nonlinear fractional programming problems, A new technique for generating quadratic programming test problems, A finite algorithm for solving general quadratic problems, Strongly polynomial time algorithms for certain concave minimization problems on networks, A new SOCP relaxation of nonconvex quadratic programming problems with a few negative eigenvalues, The clique problem for graphs with a few eigenvalues of the same sign, Methods for convex and general quadratic programming, LP relaxations for a class of linear semi-infinite programming problems, A new Lagrangian-Benders approach for a concave cost supply chain network design problem, Bounds on the spectral sparsification of symmetric and off-diagonal nonnegative real matrices, A solution method for combined semi-infinite and semi-definite programming, A New Global Optimization Scheme for Quadratic Programs with Low-Rank Nonconvexity, Extending the Scope of Robust Quadratic Optimization, Minimax Problems with Coupled Linear Constraints: Computational Complexity and Duality, A Global Optimization Approach for Multimarginal Optimal Transport Problems with Coulomb Cost, Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems, Guaranteed Error Bounds on Approximate Model Abstractions Through Reachability Analysis, Formal lumping of polynomial differential equations through approximate equivalences, Optimization under uncertainty and risk: quadratic and copositive approaches, On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Convex hull results on quadratic programs with non-intersecting constraints, On probability-raising causality in Markov decision processes, The ultrametric Gromov-Wasserstein distance, Foundations of probability-raising causality in Markov decision processes, Distribution of Distances based Object Matching: Asymptotic Inference, An approximation algorithm for indefinite mixed integer quadratic programming, Statistical Analysis of Random Objects Via Metric Measure Laplacians, An SDP method for fractional semi-infinite programming problems with SOS-convex polynomials, On a solution method in indefinite quadratic programming under linear constraints, How Do Exponential Size Solutions Arise in Semidefinite Programming?, Generic Properties for Semialgebraic Programs, A polariton graph simulator, Globally Solving Nonconvex Quadratic Programs via Linear Integer Programming Techniques, Completely positive and copositive program modelling for quadratic optimization problems, Adaptive computable approximation to cones of nonnegative quadratic functions, A new algorithm for the general quadratic programming problems with box constraints, Complexity, exactness, and rationality in polynomial optimization, Complexity, exactness, and rationality in polynomial optimization, The Complexity of Simple Models—A Study of Worst and Typical Hard Cases for the Standard Quadratic Optimization Problem, How to Calculate the Barycenter of a Weighted Graph, Duality for semi-definite and semi-infinite programming, Unnamed Item, Exact Worst-Case Performance of First-Order Methods for Composite Convex Optimization

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:1177910&oldid=12023494"