**WINTER 2018 SCHEDULE**

**CME 510 is held on Thursdays at 4:30-5:30 PM in Y2E2-101.**

**April 5: Michael Saunders, MS&E and ICME, Stanford University**

Title: Algorithm NCL for constrained optimization

Abstract: Standard optimization solvers have difficulty if too many constraints are essentially active at a solution. For example, problems of the form min f(x) st c(x) >= 0 (m constraints and n variables) may have more than n constraints active at a solution. Such problems arise in the modeling of tax policy (with perhaps millions of constraints and thousands of variables).

Algorithm NCL solves a sequence of about 10 subproblems with regularized constraints c(x) + r >= 0 and an augmented Lagrangian objective f(x) - y'r + 1/2 rho r'r that drives the extra variables r to zero. Interior methods are able to warm start each subproblem. Assuming second derivatives are available, NCL expands the use of interior methods for large-scale optimization.

Joint work with Ding Ma, Kenneth Judd, and Dominique Orban.

**April 12: Qiaochu Yuan, UC Berkeley**

Title: A tour of the Lanczos algorithm and its convergence guarantees through the decades

Abstract: We review the Lanczos algorithm and the development of its variants (block Lanczos, randomized block Lanczos) from the 1950s until the present day. We focus on theoretical convergence results for each of these algorithms that provide bounds on the approximation accuracy. We conclude by presenting new results that provide a convergence bound for randomized block Lanczos with arbitrary block sizes.

**April 19: Esmond Ng, LBNL**

Title: Revisiting an elimination game

Abstract: We consider a game on an undirected graph, in which vertices and edges are eliminated. When a vertex is eliminated, the incident edges are removed, but new edges are added to the graph according to a prescribed rule. The added edges will eventually be removed, and the graph will be empty at the end of the game. We are interested in the total number of new edges that the game sees throughout the elimination.

The order in which the vertices are eliminated affects the number of added edges. Thus, we are interested in finding an elimination order that minimizes a function that depends on the number of added edges.

We provide an overview of the elimination game and revisit several strategies. The game is relevant to the problem of computing LU factors of a sparse matrix.

**April 26: Austin Benson, Cornell University**

Title: Simplicial closure and higher-order link prediction

Abstract: Networks are a fundamental abstraction of complex systems throughout the sciences and are typically represented by a graph consisting of nodes and edges. However, many systems have important higher-order interactions, where groups of nodes interact simultaneously, and such higher-order relations are not captured by a graph containing only pairwise connections. While there are certainly mathematical formalisms for expressing higher-order interactions (such as hypergraphs and simplicial complexes), we lack a systematic way to evaluate higher-order network models. Here, we evaluate higher-order network models through a new prediction problem for the temporal evolution of higher-order structure, which we call "higher-order link prediction". The central idea of this task is to predict which new sets of node will interact in the future given the history of the system. We develop a number of algorithms for higher-order link prediction and use them to predict group interactions in systems from biomedicine, social media, human collaboration, and communications. These algorithms use several large-scale sparse matrix computations that bring a number of scalability challenges.

**May 3: Tim Harton, University of Auckland**

**May 10: Osni Marques, LBNL**

**May 17: Zhaojun Bai, UC Davis**

**May 24: TBA**

**May 31: Yuekai Sun**