Loading Events

« All Events

  • This event has passed.

GRASP Seminar: Asu Ozdaglar, MIT, “Approximate Primal Solutions and Rate Analysis for Subgradient Methods”

September 7, 2007 @ 11:00 am - 12:00 pm

Abstract: Subgradient methods provide effective means to solve large-scale convex optimization problems within the Lagrangian duality framework. For networking applications, these methods have recently been used with great success in developing decentralized cross-layer resource allocation mechanisms. Despite widespread use of subgradient methods to solve (nondifferentiable) dual problems, there are limited results in the existing literature on the recovery of approximate primal solutions and the convergence rate analysis both in the primal and the dual space.

In this talk, we first present dual subgradient methods that use averaging schemes to generate approximate primal optimal solutions for general convex constrained optimization problems. We provide estimates on the convergence rate of the primal sequences in terms of the amount of feasibility violation and primal function values. The estimates are given per iteration, thus providing practical stopping criteria.

We then consider problems where the subgradient of the dual function cannot be computed efficiently, thus impeding the use of dual subgraident methods. For these problems, we introduce new primal-dual subgradient methods aimed at computing the saddle points of the Lagrangian function and provide convergence rate estimates for the constructed primal solutions.

Presenter

Asu Ozdaglar received the B.S. degree in electrical engineering from the Middle East Technical University, Ankara, Turkey, in 1996, and the S.M. and the Ph.D. degrees in electrical engineering and computer science from the Massachusetts Institute of Technology, Cambridge, in 1998 and 2003, respectively.

Since 2003, she has been a member of the faculty of the Electrical Engineering and Computer Science Department at the Massachusetts Institute of Technology, where she is currently the Class of 1943 Career Development Associate Professor. She is also a member of the Laboratory for Information and Decision Systems and the Operations Research Center. Her research interests include optimization theory, with emphasis on nonlinear programming and convex analysis, game theory, and distributed optimization methods. She is the co-author (with Dimitri P. Bertsekas and Angelia Nedic) of the book entitled “Convex Analysis and Optimization” (Athena Scientific, 2003). She is the recipient of the Graduate Student Council Teaching award and the NSF Career award.

Details

Date:
September 7, 2007
Time:
11:00 am - 12:00 pm
Event Category: