Optimization Online


Strong formulations for quadratic optimization with M-matrices and semi-continuous variables

Alper Atamturk (atamturk***at***berkeley.edu)
Andres Gomez (agomez***at***pitt.edu)

Abstract: We study quadratic optimization with semi-continuous variables and an M-matrix, i.e., PSD with non-positive off-diagonal entries. This structure arises in image segmentation, portfolio optimization, as well as a substructure of general quadratic optimization problems. We prove, under mild assumptions, that the minimization problem is solvable in polynomial time by showing its equivalence to a submodular minimization problem. To strengthen the formulation, we decompose the quadratic function into a sum of simple quadratic functions with at most two semi-continuous variables and provide the convex-hull descriptions of these sets. We also describe strong conic quadratic valid inequalities. Preliminary computational experiments indicate that the proposed inequalities can substantially improve the strength of the continuous relaxations with respect to the standard perspective reformulation.

Keywords: quadratic optimization, submodularity, convex hull, conic quadratic cuts, perspective

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: BCOL Research Report 18.01, UC Berkeley

Download: [PDF]

Entry Submitted: 02/01/2018
Entry Accepted: 02/01/2018
Entry Last Modified: 02/01/2018

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