Mathematics Seminar: "Efficient Representations of Polytopes and Convex Sets"
4:10 pm; Neill 5W
Specific representation of a convex set can make a huge difference in the efficiency of optimization algorithms. As an illustrating example, one needs 2^n linear inequalities to represent the ell-1 ball in R^n. However, by introducing n ``additional" variables (lifting), one can describe the ell-1 ball as a projection of a polytope using only 2*n+1 linear inequalities, a huge difference in complexity compare to the previous representation. Given a convex set, how can one recognize whether there exists a more efficient "lifted representation"? I will describe two such results, one applies to polytopes, where the existence of lifted representation is related to the nonnegative matrix factorization (NMF) of a matrix called the "slack matrix". The second result is a recent generalization that applies to general convex sets. Finally, if time allows, I will describe a constructive approach to derive efficient lifted representations of polytopes with symmetry using reflections.