- Marina
Meila (The University of Washington)
Optimization for Ordered Data
This talk is concerned with summarizing -- by means of statistical
models -- of data that expresses preferences. This data is typically a
set of rankings of n items by a panel of experts; the simplest summary
is the "consensus ranking", or the "centroid" of the set of rankings.
I will describe how combinatorics, optimization and statistics come
together in this endeavor. At the center of the results is the "code"
of a permutation. This natural mathematical way to represent a
permutation is key both to fast computing and to better understanding
the models we create. Yet, estimating the models from data leads to
combinatorial optimization problems which are often NP-hard. The talk
will introduce a class of algorithms to attack these problems, that
are exact but intractable in the worst case, and will demonstrate that
they are effective on real-world examples.
Joint work with Alnur Ali, Raman Arora, Le Bao, Jeff Bilmes, Harr
Chen, Bhushan Mandhani, Chris Meek, Brendan Murphy, Kapil Phadnis,
Arthur Patterson.
- Mehran
Mesbahi (University of Washington)
Dynamics and control over graphs:
an eclectic set of problems and their applications
I will present an overview of a recent research direction in systems and control theory that is motivated by distributed and
networked dynamic systems. Along the way, I will discuss an eclectic set of problems and results with a common thread:
agreement problem, formation control, performance metrics for networked systems, network controllability and observability,
and connections with optimization and learning on networks.
- Dominique
Orban (GERAD and Ecole Polytechnique de Montreal)
Fast Local Convergence of Interior-Point Methods in the Absence of Strict Complementarity
We show that when strict complementarity fails to hold at a local solution, appropriate scaling of the primal-dual Lagrange multiplier estimates restores superlinear convergence in interior-point methods for nonlinear optimization. The scaling relies on indicator sets which we prove to be asymptotically \textit{exact}, i.e., to precisely identify strongly active, weakly active and inactive constraints. Our results show that the precise rate of convergence is sub-sesquilinear, i.e., can be anywhere between 1 and 3/2 and is determined by the rate of decrease of the barrier parameter. In the special case where all constraints are weakly active, the convergence rate is sub-quadratic.
This is joint work with Z. Coulibaly and N. I. M. Gould.
- Ting Kei
Pong
(University of British Columbia)
Gauge Optimization and Duality
Gauge optimization seeks the element of a convex set that is minimal with respect to a gauge function. It can be used to model a large class of useful problems, including conic optimization, and various problems that arise in machine learning and signal processing. In this talk, we explore the gauge duality framework proposed by Freund, and discuss a particular form of the problem that exposes some useful properties of this framework.
This is joint work with Michael Friedlander and Macedo Ives.
- Thomas
Rothvoss (University of Washington)
The matching polytope has exponential extension complexity
A popular method in combinatorial optimization is to express polytopes P, which may potentially
have exponentially many facets, as solutions of linear programs that use few extra variables to
reduce the number of constraints down to a polynomial. After two decades of standstill, recent
years have brought amazing progress in showing lower bounds for the so called extension complexity.
However, the central question in this field remained wide open: can the perfect matching polytope
be written as an LP with polynomially many constraints?
We answer this question negatively. In fact, the extension complexity of the perfect matching
polytope in a complete n-node graph is 2^Omega(n).
- Johannes
Royset (The Naval Postgraduate School)
Foundations and Applications of Epi-Splines
Approximation theory for functions deals with finding best approximations of a function when information about the function is limited, say only to its values at some points, but also includes some knowledge of its global properties such as smoothness level. This gives rise to the theory of splines and its manifold implementations. In an evolving range of applications, however, the function is only defined implicitly by a rather complex system with many side conditions. In this presentation, we consider such rich function identification problems that lead to constrained infinite-dimensional optimization problems and rely on a new class of approximating functions, epi-splines, to build approximate solutions. We present a broad framework for identifying a function that according to some criterion best represents a given data set and satisfies constraints derived from the data as well as external information. The framework allows any constraints, for example related to shape restrictions, enables studies of information growth such as from a larger sample, and facilitates the usually unavoidable approximations needed to make a procedure computationally tractable. The central components of the framework are epi-splines, which are piecewise polynomial functions that are structurally related to standard splines. However, they are more flexible than splines and arise more broadly. We present the theoretical foundations of the framework as well as illustrative examples.
- Martin
Skutella (Technical Institute of Berlin)
An improved additive approximation for the ring loading problem
The ring loading problem refers to the unsplittable multicommodity flow problem on undirected ring networks. We prove that any split routing solution to the ring loading problem can be turned into an unsplittable solution while increasing the flow value on any edge of the ring by no more than 1.4 times the maximum demand value d_max. This improves upon a classical result of Schrijver, Seymour, and Winkler (1998) who obtained a slightly larger bound of 1.5 times d_max.
![[Math logo]](pictures/mathlogo1.gif)
