Category Archives: Fall 2012

Richard Robinson; An Introduction to Cone Ranks of Polytopes

November 27, 2012, 4:00pm
Richard Robinson, University of Washington

Abstract: An extended formulation of a polytope P is a set Q coupled with an affine map L such that P=L(Q). For some polytopes, such as the permutahedron, we can find an extended formulation where Q is much simpler than P. Recently, much work has been done seeking to answer when and how such formulations can be found. In this talk, I will begin by presenting the connection between linear extended formulations and nonnegative rank as introduced by Yannakakis (1991). Then, I will discuss how this idea extends to the more general setting of cone rank as introduced by Gouveia, Parrilo, and Thomas (2011). Recent results concerning the PSD rank of polytopes will also be discussed. No material beyond Math 514 will be assumed for this talk.

Ting Kei Pong; The Generalized Trust Region Subproblem

November 20, 2012, 4:00pm
Ting Kei Pong, Department of Combinatorics and Optimization, University of Waterloo.

Abstract: The interval bounded generalized trust region subproblem (GTRS) consists in minimizing a general quadratic objective subject to an upper and lower bounded general quadratic constraint. In this talk, we first look at optimality conditions and the relationship between the problem and its SDP relaxation. We classify this problem into easy case and hard case instances as for trust region subproblems (TRS), and demonstrate that the general problem is reducible to an equality constrained problem after identifying suitable generalized eigenvalues and possibly solving a sparse system. Finally, we extend the Rendl-Wolkowicz algorithm for TRS to solve the equality constrained problem, highlighting its connection with the problem of finding the minimum generalized eigenvalues of a parameterized matrix pencil. This is a joint work with Henry Wolkowicz.

Thomas Rothvoss; Some 0/1 polytopes need exponential size extended formulations

November 6, 2012, 4:00pm
Thomas Rothvoss, MIT.

Abstract: We prove that there are 0/1 polytopes P that do not admit a compact LP formulation. More precisely we show that for every n there is a sets X \subseteq {0,1}^n such that conv(X) must have extension complexity at least 2^{n/2 * (1-o(1))}. In other words, every polyhedron Q that can be linearly projected on conv(X) must have exponentially many facets. In fact, the same result also applies if conv(X) is restricted to be a matroid polytope. The paper is available under: http://arxiv.org/abs/1105.0036 .

Dmitriy Drusvyatskiy; Active sets, steepest descent, and smooth approximations of functions

October 23, 2012, 4:00pm
Dmitriy Drusvyatskiy, School of Operations Research and Information Engineering, Cornell University

Abstract: Three ideas — active sets, steepest descent, and smooth approximations of functions — permeate non-smooth optimization. I will give a fresh  perspective on these concepts, and illustrate how many results in these areas can be greatly strengthened in the semi-algebraic setting.

Amitabh Basu; Corner Polyhedra and Maximal Lattice-free Convex Sets: A Geometric Approach to Cutting Planes

October 16, 2012, 4:00pm
Amitabh Basu, Department of Mathematics, University of California, Davis

Abstract: I will present my work on techniques which have the potential to create the next methodological breakthrough in solving general discrete optimization problems. The talk will focus on my work in cutting plane theory for Mixed-Integer Linear Programming. I will present a framework which unifies previous methods in cutting planes and provides new, and potentially much stronger, cutting plane ideas. This line of work combines the insights behind Gomory’s Corner Polyhedron and Balas’ Intersection Cuts, using tools from convex analysis, polyhedral geometry and the geometry of numbers. This line of work has initiated intense research activity in the integer programming community. The ultimate hope is to achieve the next leap in improving Integer Programming algorithms.