Optimization Online


The convex hull of a quadratic constraint over a polytope

Asteroide Santana (asteroide.santana***at***gatech.edu)
Santanu Dey (santanu.dey***at***isye.gatech.edu )

Abstract: A quadratically constrained quadratic program (QCQP) is an optimization problem in which the objective function is a quadratic function and the feasible region is defined by quadratic constraints. Solving non-convex QCQP to global optimality is a well-known NP-hard problem and a traditional approach is to use convex relaxations and branch-and-bound algorithms. This paper makes a contribution in this direction by showing that the exact convex hull of a general quadratic equation intersected with any bounded polyhedron is second-order cone representable. We present a simple constructive proof of this result.

Keywords: quadratically constrained quadratic program; convex relaxation; second-order cone representable

Category 1: Global Optimization (Theory )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )


Download: [PDF]

Entry Submitted: 12/27/2018
Entry Accepted: 12/30/2018
Entry Last Modified: 01/02/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society