October 28, 2014, 4:00pm
Jonathan Hauenstein, Department of Applied and Computational Mathematics and Statistics, University of Notre Dame.
Optimization and Numerical Algebraic Geometry
Abstract: Classically, one can observe the combination of algebraic geometry and optimization in solving polynomial systems constructed from necessary condition of polynomial optimization problems. More recently, the connection between semidefinite programming and real algebraic geometry has been exploited. This talk will explore another use of optimization related to algebraic geometry, namely to construct homotopies in numerical algebraic geometry for solving polynomial systems. This idea has been used recently to solve a problem in real enumerative geometry. This talk will conclude with using algebraic geometry to solve sparse optimization problems arising from the concept of matrix rigidity. To incorporate a broad audience, all necessary concepts related to algebraic geometry and homotopies will be covered.
October 14, 2014, 4:00pm
Annie Raymond, Department of Mathematics, University of Washington.
A New Conjecture for Union-Closed Families
Abstract: The Frankl union-closed sets conjecture states that there exists an element present in at least half of the sets forming a union-closed family. We reformulate the conjecture as an optimization problem and present an integer program to model it. The computations done with this program lead to a new conjecture: we claim that the maximum number of sets in a non-empty union-closed family in which each element is present at most a times is independent of the number n of elements spanned by the sets if n is greater or equal to log_2(a)+1. We prove that this is true when n is greater or equal to a. We also discuss the impact that this new conjecture would have on the Frankl conjecture if it turns out to be true. This is joint work with Jonad Pulaj and Dirk Theis.
May 27, 2014, 4:00pm
Elina Robeva, Department of Mathematics, UC Berkeley.
Fixed Points of the EM Algorithm and Nonnegative Rank Boundaries
Abstract: Matrices of nonnegative rank $r$ represent mixtures of $r$ independent distributions for two random variables. Likelihood inference for this model leads to problems in real algebraic geometry that we address in this paper. We characterize the set of fixed points of Expectation Maximization, and we study the boundary of the space of matrices with nonnegative rank at most $3$. Both of these correspond to algebraic varieties with many irreducible components.
May 23, 2014, 3:30pm
Michael Joswig, Institute of Mathematics, TU Berlin.
Long and Winding Central Paths
Abstract: We disprove a continuous analog of the Hirsch conjecture proposed by Deza, Terlaky and Zinchenko, by constructing a family of linear programs with $3r+4$ inequalities in dimension $2r+2$ where the central path has a total curvature in $\Omega(2^r/r)$. Our method is to tropicalize the central path in linear programming. The tropical central path is the piecewise-linear limit of the central paths of parameterized families of classical linear programs viewed through logarithmic glasses. We show in particular that the tropical analogue of the analytic center is nothing but the tropical barycenter, that is, the maximum of a tropical polyhedron. It follows that unlike in the classical case, the tropical central path may lie on the boundary of the tropicalization of the feasible set, and may even coincide with a path of the tropical simplex method. Finally, our counter-example is obtained as a deformation of a family of tropical linear programs introduced by Bezem, Nieuwenhuis and Rodr\‘iguez-Carbonell.
This is joint work with Xavier Allamigeon, Pascal Benchimol and St\‘ephane Gaubert.
May 13, 2014, 4:00pm
Noah Simon, Department of Biostatistics, University of Washington.
Flexible Sparse Modeling
Abstract: Our ability to collect data has exploded over recent years. Across science and business, we now collect thousands to millions of measurements on each person. It is often of interest to use these measurements to predict some response (eg. likelihood of getting a disease, or probability of clicking a link). Methods for this problem must balance 3 objectives: they must be predictive, they must be computationally tractable, and, in many applications, they must be interpretable. Many machine learning methods are highly successful at the first two, but are black boxes. In contrast, the Lasso (l1 penalized regression) is interpretable and computationally tractable, but assumes linearity which limits its predictive accuracy.
In this talk we will discuss a class of sparse additive models induced by combining sparsity and structural penalties. These are more flexible than the standard linear penalized model, but maintain its interpretability and computational tractability. We will show when these penalties can and cannot be combined to induce the desired structure and sparsity. We will give an efficient algorithm for fitting a wide class of these models. And we will show that some of these models have desirable theoretical properties.
This is joint work with Ashley Petersen and Daniela Witten (UW).