Session: Continuous and Discrete Optimization
Chair: Marcia Fampa
Cluster: Interplay Between Continuous and Discrete Optimization
Talk 1: Stochastic Iterative Methods for Linear Problems with Adversarial Corruption
Speaker: Jamie Haddock
Abstract: Stochastic iterative methods, like stochastic gradient descent or the randomized Kaczmarz method, have gained popularity in recent times due to their amenability to large-scale data and distributed computing environments. This talk will focus on variants of the randomized Kaczmarz methods developed for problems with significant or adversarial corruption present in the problem-defining data. This type of corruption arises frequently in applications like medical imaging, sensor networks, error correction, and classification of mislabeled data. We will focus on recent results for linear feasibility problems and tensor regression problems.
Talk 2: Volume formulae for the convex hull of the graph of a $n$-monomial in some special cases
Speaker: Emily Speakman
Abstract: The spatial branch-and-bound algorithmic framework, used for solving non-convex mixed-integer nonlinear optimization problems, relies on obtaining quality convex approximations of the non-convex substructures in a problem formulation. A common example is a simple monomial, $y=x_1x_2, \dots, x_n$, defined over the box $[a_1, b_1] \times [a_2, b_2] \times \dots \times [a_n, b_n] \subseteq \R^n$. There are many choices of convex set that could be used to approximate this solution set, with the (polyhedral) convex hull giving the “tightest” or best possible outer approximation. By computing the volume of the convex hull, we obtain a measure that can be used to evaluate other convex outer approximations in comparison. In previous work, we have obtained a formula for the volume of the convex hull of the graph of a trilinear monomial (i.e., $n=3$) in terms of the $6 = 2n$ box parameters. Here, we seek to extend our work to the case of general $n$ by making additional assumptions on the box domain. In particular, we assume that only $k$ variables have a non-zero lower bound. In this work, we consider $k=1,2,3$, and conjecture the volume of the convex hull in each case. Moreover, we provide a proof for the case $k=1$.
Talk 3: New hierarchies for disjoint bilinear programs
Speaker: Mohit Tawarmalani
Abstract: Disjoint bilinear programs are mathematical optimization problems involving minimization of a bilinear function over a Cartesian product of polytope. In this paper, we iteratively obtain, in closed-form, rational functions that are barycentric coordinates of successively tighter outer-approximations of a polytope. This procedure converges in m steps, where m is the number of constraints describing the polytope. Using this procedure, we construct a finite hierarchy of relaxations that in m steps describes the convex hull of bilinear functions over the feasible region providing a linear reformulation for disjoint bilinear programming.
