Speaker:  Professor Geoff Gordon, Associate Research Professor, Dept. of Machine Learning, Carnegie Mellon University

Title: 

Galerkin Methods for Monotone Linear Complementarity Problems

Abstract:
Linear complementarity problems are one way to encode the first-order optimality conditions for inequality-constrained optimization or saddle-point problems.  So, LCPs arise in a wide variety of areas, including machine learning, planning, game theory, and physical simulation.  In all of these areas, to handle large-scale LCP instances, we need fast approximate solution methods.  One promising idea is Galerkin approximation, in which we search for the best answer within the span of a given set of basis functions.  For equality-constrained problems, Galerkin methods have had a long history of practical and theoretical successes.  Unfortunately, the most straightforward way to apply Galerkin approximation to LCPs leads to difficulties in practice, including worse approximation errors than might be expected based on the ability of the basis to represent the desired solution.  So, in this talk, I'll present a new Galerkin method for LCPs that attempts to address the above difficulties.

Bio:

Dr. Gordon is an Associate Research Professor in the Department of Machine Learning at Carnegie Mellon University, and co-director of the Department's Ph. D. program. He works on multi-robot systems, statistical machine learning, game theory, and planning in probabilistic, adversarial, and general-sum domains.  His previous appointments include Visiting Professor at the Stanford Computer Science Department and Principal Scientist at Burning Glass Technologies in San Diego.  Dr.  Gordon received his B.A. in Computer Science from Cornell University in 1991, and his Ph.D. in Computer Science from Carnegie Mellon University in 1999.