Spring 2016 Calendar

May 17
Gwen Spencer, Department of Mathematics and Statistics, Smith College

April 19
Amin Jalali, Department of Electrical Engineering, University of Washington

May 10,
Behcet Acikmese, Department of Aeronautics & Astronautics, University of Washington

May 31
Nina Balcan, Carnegie Mellon University

Winter 2016 Calendar

January 12
James Davis, University of Illinois at Urbana-Champaign
Customer Choice Models and Assortment Optimization

January 19
João Gouveia, Departament of Mathematics, University of Coimbra
Positive semidefinite rank and representations of polytopes

February 9
Jane Ye, Department of Mathematics and Statistics
University of Victoria

On solving bilevel programming problems

February 16
Dima Drusvyatskiy, Departament of Mathematics, University of Wahington

March 8 [core]
Katya Scheinberg, Lehigh University

Fall 2015 Calendar

October 13 [CORE]
Michael Overton, Courant Institute of Mathematical Sciences, New York University
Non­smooth, Non­con­vex Opti­miza­tion: Algo­rithms and Examples

October 20
Sasha Aravkin, Department of Applied Mathematics, University of Washington
An Interior Point Approach for Data Science

October 27
Damek Davis, Department of Mathematics, University of California, Los Angeles
A Three-Operator Splitting Scheme and its Optimization Applications

November 10
James Saunderson, Department of Electrical Engineering, University of Washington
Semidefinite descriptions of regular polygons (and beyond)

November 24 [CORE]
Pedro Domingos, Department of Computer Science and Engineering, University of Washington
Nonsmooth, Nonconvex Optimization: Algorithms and Examples

December 8
Victor Falgas-Ravry, Department of Mathematics, Vanderbilt University
Finding large full subgraphs

Jane Ye; On solving bilevel programming problems

Feb 9, 2016, 4pm
SIG 226
Jane Ye,, University of Victoria, Canada.

Abstract:A bilevel program is a sequence of two optimization problems where the constraint region of the upper level problem is determined implicitly by the solution set to the lower level problem. In this talk we report some recent progresses on solving bilevel programming problems. In the case where all functions are polynomials, we propose a numerical method for globally solving the polynomial bilevel program. For the simple bilevel program where the lower level constraints are independent of the upper level variables we propose a numerical method for finding a stationary point.

James Davis; Customer Choice Models and Assortment Optimization

Tuesday, January 12, 2016, 4:00 pm
SIG 226

James Davis , University of Illinois at Urbana-Champaign .
Customer Choice Models and Assortment Optimization

Abstract: In this talk we will focus on the assortment optimization problem. In this problem there is a set of products, each of which gives some fixed revenue when it is purchased by a customer. There is also a set of customers who’s purchasing behavior is influenced by what products they view. Our objective is to select some subset of products to display to customers in order to maximize expected revenue. The key component in this problem is customer purchasing behavior which we describe with a customer choice model. We will introduce a variety of customer choice models, each of which presents unique challenges. Under one of these models, the multinomial logit model, we will solve variants of the assortment optimization problem.

João Gouveia; Positive semidefinite rank and representations of polytopes

Tuesday, January 19, 2016, 4:00 pm
SIG 226

João Gouveia, University of Coimbra .

Let M be a p-by-q matrix with nonnegative entries. The positive semidefinite rank (psd rank) of M is the smallest integer k for which there exist positive semidefinite matrices A_i,B_j of size k×k such that M_{ij}=trace(A_i,B_j). The psd rank was recently introduced, and has has many appealing interpretations, capturing some geometrical aspects of the power and limitations of semidefinite programming. In this talk, we will briefly cover basic properties and open questions on this quantity, and proceed to use some of this results to provide a complete characterization of polytopes in R^4 that can be represented as economically as possible by means of a semidefinite program.

Victor Falgas-Ravry; Finding large full subgraphs

Tuesday, December 8, 2015, 4:00 pm
GUG 204

Victor Falgas-Ravry, University of Washington .
Finding large full subgraphs

Abstract: A graph is a pair G=(V,E), where V is a set of vertices and E is a set of pairs from V forming the edges of G. Suppose G is a graph on n vertices in which a proportion p of all possible edges are present, for some fixed p: 0 \leq p \leq 1. We call a subgraph H of G on m vertices \emph{full} if every vertex in H is connected by an edge to at least p(m-1) other vertices in H. In other words, a subgraph H is full if its minimum degree is at least the expected average degree for an m-vertex subgraph. If we think of the graph G as representing a network, then its full subgraphs correspond to `cliquey’ communities within that network.

In this talk I shall consider the question of how large a full subgraph I can be guaranteed to find. Improving on earlier work of Erd\H{o}s, \L uczak and Spencer, I shall give a simple algorithm for finding full subgraphs of order at least n^{2/3}, and show that this order is best possible for infinitely many values of p.

Joint work with Klas Markstr\”om and Jacques Verstra\”ete.