ﻻ يوجد ملخص باللغة العربية
This paper presents a selected tour through the theory and applications of lifts of convex sets. A lift of a convex set is a higher-dimensional convex set that projects onto the original set. Many convex sets have lifts that are dramatically simpler to describe than the original set. Finding such simple lifts has significant algorithmic implications, particularly for optimization problems. We consider both the classical case of polyhedral lifts, described by linear inequalities, as well as spectrahedral lifts, defined by linear matrix inequalities, with a focus on recent developments related to spectrahedral lifts. Given a convex set, ideally we would either like to find a (low-complexity) polyhedral or spectrahedral lift, or find an obstruction proving that no such lift is possible. To this end, we explain the connection between the existence of lifts of a convex set and certain structured factorizations of its associated slack operator. Based on this characterization, we describe a uniform approach, via sums of squares, to the construction of spectrahedral lifts of convex sets and illustrate the method on several families of examples. Finally, we discuss two flavors of obstruction to the existence of lifts: one related to facial structure, and the other related to algebraic properties of the set in question. Rather than being exhaustive, our aim is to illustrate the richness of the area. We touch on a range of different topics related to the existence of lifts, and present many examples of lifts from different areas of mathematics and its applications.
Two new optimization techniques based on projections onto convex space (POCS) framework for solving convex and some non-convex optimization problems are presented. The dimension of the minimization problem is lifted by one and sets corresponding to t
The goal of this paper is to derive new classes of valid convex inequalities for quadratically constrained quadratic programs (QCQPs) through the technique of lifting. Our first main result shows that, for sets described by one bipartite bilinear con
We consider the problem of the semidefinite representation of a class of non-compact basic semialgebraic sets. We introduce the conditions of pointedness and closedness at infinity of a semialgebraic set and show that under these conditions our modif
The Frank-Wolfe method solves smooth constrained convex optimization problems at a generic sublinear rate of $mathcal{O}(1/T)$, and it (or its variants) enjoys accelerated convergence rates for two fundamental classes of constraints: polytopes and st
In this paper we generalize the factorization theorem of Gouveia, Parrilo and Thomas to a broader class of convex sets. Given a general convex set, we define a slack operator associated to the set and its polar according to whether the convex set is