2011

Lifts of convex sets and cone factorizations

Gouveia, João, Parrilo, Pablo A., Thomas, Rekha

Understand

In this paper we address the basic geometric question of when a given convex set is the image under a linear map of an affine slice of a given closed convex cone.

Such a representation or 'lift' of the convex set is especially useful if the cone admits an efficient algorithm for linear optimization over its affine slices.
We show that the existence of a lift of a convex set to a cone is equivalent to the existence of a factorization of an operator associated to the set and its polar via elements in the cone and its dual.
This generalizes a theorem of Yannakakis that established a connection between polyhedral lifts of a polytope and nonnegative factorizations of its slack matrix.

Built on

Extreme copositive quadratic forms
V. J. D. Baston · 1969
Earlier work this paper cites.
Disjunctive programming
Egon Balas · 1977
Earlier work this paper cites.
Regularizing the abstract convex program
Jon Borwein and Henry Wolkowicz · 1981
Earlier work this paper cites.
A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems
Hanif D. Sherali and Warren P. Adams · 1990
Earlier work this paper cites.
Cones of matrices and set-functions and 0 0 - 1 1 optimization
László Lovász and Alexander Schrijver · 1991
Earlier work this paper cites.
Expressing combinatorial optimization problems by linear programs
Mihalis Yannakakis · 1991
Earlier work this paper cites.
On the computational complexity and geometry of the first-order theory of the reals. I. Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals
James Renegar · 1992
Earlier work this paper cites.
Nonnegative ranks, decompositions, and factorizations of nonnegative matrices
Joel E. Cohen and Uriel G. Rothblum · 1993
Earlier work this paper cites.

Similar

Interior point polynomial methods in convex programming
Y. E. Nesterov and A. Nemirovski · 1994
Cited alongside, same era.
Cones of matrices and successive convex relaxations of nonconvex sets
Masakazu Kojima and Levent Tunçel · 2000
Cited alongside, same era.
Lectures on modern convex optimization
A. Ben-Tal and A. Nemirovski · 2001
Cited alongside, same era.
On polyhedral approximations of the second-order cone
Aharon Ben-Tal and Arkadi Nemirovski · 2001
Cited alongside, same era.
Global optimization with polynomials and the problem of moments
Jean B. Lasserre · 2001
Cited alongside, same era.
A course in convexity
Alexander Barvinok · 2002
Cited alongside, same era.
Semidefinite programming relaxations for semialgebraic problems
Pablo A. Parrilo · 2003
Cited alongside, same era.
Subset algebra lift operators for 0-1 integer programming
Daniel Bienstock and Mark Zuckerberg · 2004
Cited alongside, same era.
Approximations of convex bodies by polytopes and by projections of spectrahedra
Original
A. Barvinok
Cited in the paper.
Combinatorial bounds on nonnegative rank and extended formulations
Original
Samuel Fiorini, Volker Kaibel, Kanstantsin Pashkovich, and Dirk O. Theis
Cited in the paper.
Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds
Original
Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf
Cited in the paper.
On the geometric interpretation of the nonnegative rank
Original
Nicolas Gillis and Francois Glineur
Cited in the paper.

Then

Hyperbolic programs, and their derivative relaxations
James Renegar · 2006
Later among the works it cites.
Positive polynomials and sums of squares
Murray Marshall · 2008
Later among the works it cites.
On the copositive representation of binary and continuous nonconvex quadratic programs
Samuel Burer · 2009
Later among the works it cites.
On the complexity of nonnegative matrix factorization
Stephen A. Vavasis · 2009
Later among the works it cites.
Theta bodies for polynomial ideals
João Gouveia, Pablo A. Parrilo, and Rekha R. Thomas · 2010
Later among the works it cites.
Symmetry matters for the sizes of extended formulations
Volker Kaibel, Kanstantsin Pashkovich, and Dirk O. Theis · 2010
Later among the works it cites.
On the connection of facially exposed, and nice cones
Gabor Pataki · 2011
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…