New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability

DOI10.1007/s10107-007-0138-0zbMath1171.90007OpenAlexW1971027118MaRDI QIDQ930342

Marco Locatelli, Immanuel M. Bomze, Fabio Tardella

Publication date: 30 June 2008

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-007-0138-0

zbMATH Keywords

semidefinite programmingnonconvex programmingbounds on optimal objective function valueLovasz's \(\theta\)-functionquadratic programmig

Mathematics Subject Classification ID

Semidefinite programming (90C22) Nonconvex programming, global optimization (90C26) Quadratic programming (90C20)

Related Items

Cutting planes for semidefinite relaxations based on triangle-free subgraphs, New Analysis on Sparse Solutions to Random Standard Quadratic Optimization Problems and Extensions, The difference between \(5\times 5\) doubly nonnegative and completely positive matrices, Tightening a copositive relaxation for standard quadratic optimization problems, Copositivity cuts for improving SDP bounds on the clique number, Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem, A new method for mean-variance portfolio optimization with cardinality constraints, Sparse solutions to random standard quadratic optimization problems, On solving a non-convex quadratic programming problem involving resistance distances in graphs, Strong duality and KKT conditions in nonconvex optimization with a single equality constraint and geometric constraint, Copositivity and constrained fractional quadratic problems, Complex portfolio selection via convex mixed‐integer quadratic programming: a survey, Convex Envelopes of Some Quadratic Functions over the n-Dimensional Unit Simplex, Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems, Performance comparison of two recently proposed copositivity tests, Nonparametric density estimation with nonuniform B-spline bases, Separating doubly nonnegative and completely positive matrices, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, An improved algorithm to test copositivity, Copositivity detection by difference-of-convex decomposition and \(\omega \)-subdivision, Factorization and cutting planes for completely positive matrices by copositive projection, Complexity and nonlinear semidefinite programming reformulation of \(\ell_1\)-constrained nonconvex quadratic optimization, Computing the value of the convex envelope of quadratic forms over polytopes through a semidefinite program, New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability, On sparsity of the solution to a random quadratic optimization problem, Solving Quadratic Programming by Cutting Planes, Improved SDP bounds for minimizing quadratic functions over the \(\ell^{1}\)-ball, Global solutions of nonconvex standard quadratic programs via mixed integer linear programming reformulations, Extensions of the standard quadratic optimization problem: strong duality, optimality, hidden convexity and S-lemma, A new branch-and-bound algorithm for standard quadratic programming problems, 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, Visualizing data as objects by DC (difference of convex) optimization, A clique algorithm for standard quadratic programming, Separable standard quadratic optimization problems, A new algorithm for concave quadratic programming, Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons, Local linear convergence of the alternating direction method of multipliers for nonconvex separable optimization problems, Metastability in stochastic replicator dynamics, Gap, cosum and product properties of the θ′ bound on the clique number, Two-stage stochastic standard quadratic optimization

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Branch-and-bound approaches to standard quadratic optimization problems
• A class of problems where dual bounds beat underestimation bounds
• New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability
• Properties of Euclidean and non-Euclidean distance matrices
• On standard quadratic optimization problems
• A new semidefinite programming bound for indefinite quadratic forms over a simplex
• Convex extensions and envelopes of lower semi-continuous functions
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• Undominated d.c. decompositions of quadratic functions and applications to branch-and-bound approaches
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• D.C. versus copositive bounds for standard QP
• On the equivalence between some discrete and continuous optimization problems
• Global Optimization with Polynomials and the Problem of Moments
• Approximation of the Stability Number of a Graph via Copositive Programming
• Connections between continuous and combinatorial optimization problems through an extension of the fundamental theorem of Linear Programming
• A comparison of the Delsarte and Lovász bounds
• Continuous Characterizations of the Maximum Clique Problem
• Maxima for Graphs and a New Proof of a Theorem of Turán
• Computing the Stability Number of a Graph Via Linear and Semidefinite Programming
• Lagrange Multipliers and Nonconvex Programs
• Convex Analysis
• On copositive programming and standard quadratic optimization problems