Name
Abstract | ||
|---|---|---|
We approach linearly constrained convex optimization problems through their dual reformulation. Specifically, we derive a family of accelerated dual algorithms by adopting a variational perspective in which the dual function of the problem represents the scaled potential energy of a synthetic mechanical system, and the kinetic energy is defined by the Bregman divergence induced by the dual velocity flow. Through application of Hamilton's principle, we derive a continuous-time dynamical system which exponentially converges to the saddle point of the Lagrangian. Moreover, this dynamical system only admits a stable discretization through accelerated higher-order gradient methods, which precisely corresponds to accelerated dual mirror ascent. In particular, we obtain discrete-time convergence rate O (1/k(p)), where p - 1 is the truncation index of the Taylor expansion of the dual function. For practicality sake, we consider p = 2 and p = 3 only, respectively corresponding to dual Nesterov acceleration and a dual variant of Nesterov's cubic regularized Newton method. This analysis provides an explanation from whence dual acceleration comes as the discretization of the Euler-Lagrange dynamics associated with the constrained convex program. We demonstrate the performance of the aforementioned continuous-time framework with numerical simulations. |
Year | Venue | Field |
|---|---|---|
2017 | 2017 AMERICAN CONTROL CONFERENCE (ACC) | Discretization,Mathematical analysis,Convex function,Bregman divergence,Rate of convergence,Convex optimization,Mathematics,Convex analysis,Taylor series,Newton's method |
DocType | ISSN | Citations |
Conference | 0743-1619 | 1 |
PageRank | References | Authors |
0.36 | 15 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mahyar Fazlyab | 1 | 33 | 6.06 |
| Alec Koppel | 2 | 99 | 21.66 |
| Victor M. Preciado | 3 | 205 | 29.44 |
| Alejandro Ribeiro | 4 | 2817 | 221.08 |