Skip to content Skip to navigation

CME 510: Linear Algebra and Optimization Seminar


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