November 13, 2014, 4:00pm
Henry Wolkowicz, Department of Mathematics, University of Waterloo.
Taking Advantage of Degeneracy in Cone Optimization: with Applications to Sensor Network Localization
Abstract: The elegant theoretical results for strong duality and strict complementarity for linear programming, LP, lie behind the success of current algorithms. However, the theory and preprocessing techniques that are successful for LP can fail for cone programming over nonpolyhedral cones.
Surprisingly, many important applications of semidefinite programming, SDP, that arise from relaxations of hard combinatorial problems are degenerate. (Slater’s constraint qualification fails.) This includes relaxations for problems such as the: Quadratic Assignment; Graph Partitioning; Set Covering and partitioning; and sensor network localization and molecular conformation. Rather than being a disadvantage, we show that this degeneracy can be exploited. In particular, several huge instances of SDP completion problems can be solved quickly and to extremely high accuracy. In particular, we illustrate this on the sensor network localization problem.
December 2, 2014, 4:00pm
Peter Bürgisser, Institute for Mathematics, TU Berlin.
Condition of Convex Optimization and Spherical Intrinsic Volumes
Abstract: The analysis of the stability and efficiency of algorithms for convex optimization naturally leads to the study of condition numbers. The Grassmann condition, which is a geometric version of Renegar’s condition, is especially suited for a probabilistic analysis. Such analysis can be performed by relying on techniques from spherical convex geometry and differential geometry. Along this way, we obtain an average analysis of the Grassmann condition number that holds for any regular convex cone. A closer look prompts the investigation of the spherical counterparts of intrinsic volumes — a notion thoroughly studied for euclidean spaces, but much less so for spheres, so that many fascinating questions remain.
Joint work with Dennis Amelunxen.
Bio: Peter Bürgisser has been a professor of Mathematics at the Technical University of Berlin since 2013. Prior to that he was a professor of Mathematics at the University of Paderborn. His research interests are algebraic complexity theory, symbolic and numeric computation, and more recently, the probabilistic analysis of numerical algorithms. Bürgisser was an invited speaker at the International Congress of Mathematicians in Hyderabad in 2010 and plenary speaker at Foundations of Computational Mathematics 2008 in Hong Kong. He is an associate editor of Computational Complexity, and an editor of the journal Foundations of Computational Mathematics. He served as a workshop co-organizer for the Foundations of Computational Mathematics conferences (2005, 2008, 2011), for the Special Year on Applications of Algebraic Geometry (IMA 2006/2007), and for the Oberwolfach workshops on Complexity Theory (2009, 2012). His research interests lie in algebraic complexity theory: both the design of efficient algorithms for algebraic problems, and the quest for lower bounds.
November 18, 2014, 4:00pm
Daniela Witten, Departments of Biostatistics and Statistics, UW.
Flexible Graphical Modeling
Abstract: In recent years, there has been considerable interest in estimating conditional dependence relationships among random variables in the high-dimensional setting, in which the number of variables far exceeds the number of available observations. Most prior work has assumed that the variables are multivariate Gaussian, or that the conditional means of the variables are linear. Unfortunately, if these assumptions are violated, then the resulting estimates can be inaccurate.
I will present two recent lines of work on learning the conditional dependence graph of a set of random variables in the non-Gaussian setting. First, I will present a semi-parametric method that allows the conditional means of the features to take on an arbitrary additive form. Next, I will present an approach for learning a graph in which the distribution of each node, conditioned on the others, may have a different parametric form. Each approach is formulated as the solution to a convex optimization problem corresponding to a penalized log likelihood.
This is joint work with Ali Shojaie, Shizhe Chen, and Arend Voorman.
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.