On the convergence of inexact projection primal first order methods for convex minimization
Event details
| Date | 03.03.2017 |
| Hour | 10:15 › 11:15 |
| Speaker | Ion Necoara, University Politehnica Bucharest, Romania |
| Location | |
| Category | Conferences - Seminars |
It is well-known that primal first order algorithms achieve sublinear (linear) convergence for smooth convex (smooth strongly convex) constrained minimization. However, these methods encounter numerical difficulties when the primal feasible set is complicated, since they require exact projection onto this set. Algorithmic alternatives to convex problems with complicated feasible set are the dual first order methods. Dual methods are able to handle easily complicated constraints, but they have difficulties in convergence when the norm of the optimal Lagrange multiplier is large, since this norm appears linearly in the convergence estimates of these methods. Moreover, they have typically sublinear convergence rate in an average primal sequence, even when the primal problem has smooth and strongly convex objective function.
Motivated by these issues, in this talk we analyze the convergence of primal first order methods with inexact projections for solving constrained convex problems with smooth and then strongly convex objective function. In particular, we consider the inexact variants of Projected Gradient and Projected Fast Gradient methods, where instead of computing an exact projection onto the complicated primal feasible set, an approximate projection, not necessarily feasible, is used. We show that we can still achieve similar convergence rates for these inexact projection first order algorithms with those given in the exact projection settings, provided that the approximate projection is sufficiently accurate. Our convergence analysis allows to derive explicitly the accuracy of the inexact projection and the number of iterations we need to perform in order to obtain an approximate solution for our convex problem.
Bio : Ion Necoara received the MSc degree in optimization and statistics from University of Bucharest, Romania in 2002 and the PhD degree in applied sciences (cum laude) from Delft University of Technology, The Netherlands in 2006. For the period 2007-2009, he completed a postdoctoral fellowship at the Katholieke Universiteit Leuven, Belgium. Currently, he is a full professor at the Department of Automatic Control and Systems Engineering, University Politehnica Bucharest, Romania. His research interests cover various topics in developing new optimization algorithms with a focus on structure exploiting and applying optimization techniques for developing new advanced controller design algorithms for complex systems.
Motivated by these issues, in this talk we analyze the convergence of primal first order methods with inexact projections for solving constrained convex problems with smooth and then strongly convex objective function. In particular, we consider the inexact variants of Projected Gradient and Projected Fast Gradient methods, where instead of computing an exact projection onto the complicated primal feasible set, an approximate projection, not necessarily feasible, is used. We show that we can still achieve similar convergence rates for these inexact projection first order algorithms with those given in the exact projection settings, provided that the approximate projection is sufficiently accurate. Our convergence analysis allows to derive explicitly the accuracy of the inexact projection and the number of iterations we need to perform in order to obtain an approximate solution for our convex problem.
Bio : Ion Necoara received the MSc degree in optimization and statistics from University of Bucharest, Romania in 2002 and the PhD degree in applied sciences (cum laude) from Delft University of Technology, The Netherlands in 2006. For the period 2007-2009, he completed a postdoctoral fellowship at the Katholieke Universiteit Leuven, Belgium. Currently, he is a full professor at the Department of Automatic Control and Systems Engineering, University Politehnica Bucharest, Romania. His research interests cover various topics in developing new optimization algorithms with a focus on structure exploiting and applying optimization techniques for developing new advanced controller design algorithms for complex systems.
Practical information
- General public
- Free