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 (41)

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

This page was built for publication: New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability