Autumn 2016 Calendar

Oct 11 [TOPS]
Harishchandra Ramadas, Department of Mathematics, University of Washington
A Deterministic Algorithm for Discrepancy Minimization

Nov 1 [TOPS]
Reza Eghbali, Department of Electrical Engineering, University of Washington
Worst Case Competitive Analysis of Online Algorithms for Conic Optimization

Nov 7 [EE Lytle Lecture – Broad Audience]
David Donoho, Department of Statistics, Stanford University
See details here.

Nov 8 [EE Lytle Lecture – Colloquium]
David Donoho, Department of Statistics, Stanford University
See details here.

Nov 15 [TOPS]
Rainer SinnSchool of Mathematics, Georgia Institute of Technology
Positive semidefinite matrix completion and sums of squares

Nov 21 [TOPS – special date]
Jonathan Jedwab, Department of Mathematics, Simon Fraser University
How many mutually unbiased bases can exist in complex space of dimension d?

Nov 22 [TOPS]
Jonathan Jonker, Department of Mathematics, University of Washington
Singular Kalman Smoothing

Nov 29 [TOPS]
Yin-Tat Lee, Microsoft Research
Geodesic Walks

Dec 1 [CORE / CSE Theory Seminar]
David Shmoys, Department of Computer Science, Cornell University
Models and Algorithms for the Operation and Design of Bike-Sharing Systems

Dec 2 [Math Across Campus – Broad Audience]
David Shmoys, Department of Computer Science, Cornell University
See details here.

Future Talks

Jan 17 [TOPS]
Abe Engle, Department of Mathematics, University of Washington

Jan 24 [TOPS]
Amy Wiebe, Department of Mathematics, University of Washington

Jan 31 [CORE]
Jon Lee, Department of Industrial and Operations Engineering, University of Michigan

Feb 7 [TOPS]
Asen L. DontchevMathematical Reviews and University of Michigan
Strong Metric Subregularity

Apr 11 [CORE]
Liza Levina, Department of Statistics, University of Michigan

Asen Dontchev; Strong Metric Subregularity

Feb 7, 2017, 4pm
TBA
Asen Dontchev, Mathematical Reviews and University of Michigan

Abstract:  Although the property of strong metric sub regularity of set-valued mappings has been present in the literature under various names and with various (equivalent) definitions for more than two decades, it has attracted much less attention than its older “siblings”, the metric regularity and the strong metric regularity. In this talk I will try to show that the strong metric subregularity shares the main features of these two most popular regularity properties and is not less instrumental in applications. In particular, it obeys the inverse function theorem paradigm also for nonsmooth perturbations.

A sufficient condition  for strong metric subregularity is established in terms of surjectivity of the Fr\’echet coderivative will be presented, and it will be shown by a counterexample that subjectivity of the limiting coderivative is not a sufficient condition for this property, in general. Then various versions of Newton’s method for solving variational inequalities will be considered including  inexact and semismooth methods. A characterization of the strong metric subregularity of the KKT mapping will be demonstrated, as well as a radius theorem for the optimality mapping of a nonlinear programming problem. Finally, an error estimate is derived for a discrete approximation in optimal control under strong metric subregularity of the mapping involved in the Pontryagin principle.

David Shmoys; Models and Algorithms for the Operation and Design of Bike-Sharing Systems

CORE Series (Joint with CSE Theory Seminar)
**Thursday**, Dec 1, 2016
11:00AM-12:00PM in CSE 403
David Shmoys, Cornell University

TITLE: Models and Algorithms for the Operation and Design of Bike-Sharing Systems

ABSTRACT: New York launched the largest bike-sharing system in North America in May 2013. We have worked with Citibike, using analytics and optimization to change how they manage the system. Huge rush-hour usage imbalances the system; we answer both of the questions: where should bikes be at the start of a day and how can we mitigate the imbalances that develop? We will survey the analytics we have employed for the former question, where we developed an approach based on continuous-time Markov chains combined with integer programming models to compute daily stocking levels for the bikes, as well as methods employed for optimizing the capacity of the stations. For the question of mitigating the imbalances that result, we will describe both heuristic methods and approximation algorithms that guide both mid-rush hour and overnight rebalancing, as well as for the positioning of corrals, which have been one of the most effective means of creating adaptive capacity in the system.

This is joint work with Daniel Freund, Shane Henderson, Nanjing Jian, Ashkan Nourozi-Fard, Eoin O’Mahoney, and Alice Paul.

 

David B. Shmoys pic

BIO: David Shmoys is the Laibe/Acheson Professor at Cornell University in the School of Operations Research and Information Engineering, and also the Department of Computer Science at Cornell University, and is currently the Director of the School of Operations Research and Information Engineering. Shmoys’s research has focused on the design and analysis of efficient algorithms for discrete optimization problems, with applications including scheduling, inventory theory, computational biology, and most recently, on stochastic optimization models and algorithms in computational sustainability. His graduate-level text, The Design of Approximation Algorithms, co-authored with David Williamson, was awarded the 2013 INFORMS Lanchester Prize. He is an INFORMS Fellow, a Fellow of the ACM, a SIAM Fellow, and was an NSF Presidential Young Investigator; he has served on numerous editorial boards, and is currently Editor-in-Chief of Research in the Mathematical Sciences (for theoretical computer science) and an Associate Editor of Mathematics of Operations Research.

Save

Jonathan Jonker; Singular Kalman Smoothing

Nov 22, 2016, 4pm
SAV 131
Jonathan Jonker, Department of Mathematics, University of Washington

Abstract: The Kalman filter is a process of estimating unknown variables using a sequence of known measurements. It is widely used in fields such as navigation, tracking and economics.  While this is not classically an optimization problem, it has been shown that by using a maximum a posteriori estimate it can be reformulated to be a least squares minimization problem.  This reformulation assumes that certain covariance matrices are nonsingular; we show that this assumption may be dropped.  Once the optimization problem is derived, we discuss solution methods and provide numerical examples.

Joint work with Sasha Aravkin.

Rainer Sinn; Positive semidefinite matrix completion and sums of squares

Nov 15, 2016, 4pm
SAV 131
Rainer Sinn, School of Mathematics, Georgia Institute of Technology

Abstract: I will discuss the positive semidefinite matrix completion problem arising in combinatorial statistics and explain how we can use results in algebraic geometry (or combinatorial commutative algebra) to understand it better. The object linking the two different areas is the cone of sums of squares and its properties as a convex cone.

Jonathan Jedwab; How many mutually unbiased bases can exist in complex space of dimension d?

*Monday* Nov 21, 2016, 3:30pm.
LOW 117
Jonathan Jedwab, Department of Mathematics, Simon Fraser University

Abstract: A set of m mutually unbiased bases in C^d comprises md unit vectors in C^d, partitioned into m orthonormal bases for C^d such that the pairwise angle between all vectors from distinct bases is arccos(1/sqrt(d)). Schwinger noted in 1960 that no information can be obtained when a quantum system is prepared in a state belonging to one of the bases of such a set but is measured with respect to any other one of the bases. This property can be exploited in secure quantum key exchange, quantum state determination, quantum state reconstruction, and detection of quantum entanglement.

The central problem is to determine the largest number \mu(d) of mutually unbiased bases that can exist in C^d. It has been known for 40 years that \mu(d) <= d + 1, but a construction achieving the upper bound d + 1 is known only when d is a prime power. Despite considerable effort and a huge literature, there has been little progress in determining \mu(d) when d is not a prime power, with the notable exception of Weiner’s 2013 result that \mu(d) never equals d. Even the smallest non-prime-power case d = 6 remains baffling: all that is known is that \mu(6) ∈ {3, 4, 5, 7}.

I shall give an overview of the motivation and current state of knowledge for this problem, and describe some new insights involving combinatorial designs. No prior knowledge will be assumed.

This is joint work with Lily Yen of Capilano University.

Yin-Tat Lee; Geodesic Walks

Nov 29, 2016, 4pm
SAV 131
Yin-Tat Lee, Microsoft Research

Abstract: We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating uniform random points from polytopes, a problem that is even more general than linear programming. The walk is a discrete-time simulation of a stochastic differential equation (SDE) on the Riemannian manifold. The resulting sampling algorithm for polytopes mixes in O*(mn^{3/4}) steps for a polytope in R^n specified by m inequalities. This is the first walk that breaks the quadratic barrier for mixing in high dimension, improving on the previous best bound of O*(mn) by Kannan and Narayanan for the Dikin walk. We also show that each step of the geodesic walk (solving an ODE) can be implemented efficiently, thus improving the time complexity for sampling polytopes.

Harishchandra Ramadas; A Deterministic Algorithm for Discrepancy Minimization

Oct 11, 2016, 4pm
SAV 131
Harishchandra Ramadas, Department of Mathematics, University of Washington

Given a collection of n items and n subsets of this collection, we want to color each object either red or blue so that in every subset, the number of red items is close to the number of blue items. In 1985, Spencer showed that there exists a coloring so that the “discrepancy” of each subset — the difference between the number of red and blue items — is at most sqrt(n). We present a deterministic algorithm based on the multiplicative weights update method to find such a coloring in polynomial time.

Based on joint work with Avi Levy and Thomas Rothvoss. No background will be assumed.