Current students

Title: Efficient First-Order Methods for Linear Programming and Semidefinite Programming 

Abstract:

We will be discussing the paper (bearing the same title) of James Reneger.  We present a simple transformation of any linear program or semidefinite program into an equivalent convex optimization problem whose only constraints are linear equations. The objective function is defined on the whole space, making virtually all subgradient methods be immediately applicable.

Title: Orientations, Pseudoforests, Flows, and the Densest Subgraph
 

Abstract:

Given an undirected graph, consider the problem of finding an orientation such that the max-imum indegree is minimized. The Gabow-Westermann algorithm can solve it by exploiting the matroid structure of pseudoforests.

Title: Sum-of-Squares Proofs in Optimization

Abstract:

The old concept of sum-of-squares found its way into optimization and even machine learning. I will talk about this quickly evolving research area known as convex algebraic geometry.

Title: Nash-Williams

Abstract:

Crispin Nash-Williams was one of the founding professors of C&O. The talk will cover a small sample of his mathematical work, and also his association with C&O.

Title: Alternating Direction Method of Multipliers for the SDP Relaxation of the Quadratic Assignment Problem

Abstract:

The semidefinite programming (SDP) relaxation has proven to be extremely strong for many hard discrete optimization problems. This is in particular true for the quadratic assignment problem (QAP), arguably one of the hardest NP-hard discrete optimization problems.

Title: Ramsey theory for biased graphs

Abstract:

We discuss the unavoidable subgraphs of biased graphs whose underlying graph is a clique.

Title: Recent Advances in Frank-Wolfe Optimization

Abstract:

The Frank-Wolfe (FW) optimization algorithm has lately re-gained popularity thanks in particular to its ability to nicely handle the structured constraints appearing in machine learning and signal processing applications. However, its convergence rate is known to be slow (sublinear) when the solution lies at the boundary.

Title: Convex drawings of complete graphs:  topology meets geometry

Abstract:

A drawing D of the complete graph K(n) is the sphere is characterized by, for each isomorph J of K(5), D[J] is homeomorphic to one of the three rectilinear drawings of K(5).  Every drawing of K(n) in the plane with all edges straight-line segments is obviously convex.  Thus, convex drawings generalize planar point sets that are in general position. 

Title: Constructing cospectral graphs with a different switching

Abstract:

Many years ago, Brendan McKay and I introduced a construction of pairs of cospectral graphs, sometimes known as local switching. In the same paper we introduced a second switching technique which produces, as special cases, the smallest pair of cospectral graphs and the smallest pair of connected cospectral graphs.

Title: Proximal alternating linearized minimization for nonconvex and nonsmooth problems

Abstract:

We will be discussing the paper (having the same title) by Jerome Bolte, Shoham Sabach and Marc Teboulle.  We introduce a proximal alternating linearized minimization (PALM) algorithm for solving a broad class of nonconvex and nonsmooth minimization problems.