A linear programming reformulation of the standard quadratic optimization problem

DOI10.1007/s10898-006-9037-9zbMath1127.90051OpenAlexW2163155064WikidataQ56874369 ScholiaQ56874369MaRDI QIDQ868634

Etienne de Klerk, Dimitrii V. Pasechnik

Publication date: 6 March 2007

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

Full work available at URL: https://doi.org/10.1007/s10898-006-9037-9

zbMATH Keywords

Linear programmingPositive polynomialsStandard quadratic optimization

Mathematics Subject Classification ID

Quadratic programming (90C20) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

Separable relaxation for nonconvex quadratic integer programming: Integer diagonalization approach, Copositive optimization -- recent developments and applications, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, Completely positive and completely positive semidefinite tensor relaxations for polynomial optimization, Convex relaxations for nonconvex quadratically constrained quadratic programming: matrix cone decomposition and polyhedral approximation, New approximations for the cone of copositive matrices and its dual, 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 Complete Semidefinite Algorithm for Detecting Copositive Matrices and Tensors, On the computation of \(C^*\) certificates, Complete positivity and distance-avoiding sets

Cites Work

• Linear inequalities and quadratic forms
• Semidefinite representations for finite varieties
• Solving standard quadratic optimization problems via linear, semidefinite and copositive pro\-gramming
• A PTAS for the minimization of polynomials of fixed degree over the simplex
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• Approximation of the Stability Number of a Graph via Copositive Programming
• Regularity versus Degeneracy in Dynamics, Games, and Optimization: A Unified Approach to Different Aspects
• On the Equivalence of Algebraic Approaches to the Minimization of Forms on the Simplex
• Polynomial Programming: LP-Relaxations Also Converge
• Maxima for Graphs and a New Proof of a Theorem of Turán
• LMI Approximations for Cones of Positive Semidefinite Forms
• Improved Bounds for the Crossing Numbers of Km,n and Kn
• Semidefinite Programming vs. LP Relaxations for Polynomial Programming
• A new bound for Pólya's theorem with applications to polynomials positive on polyhedra.