---
abstract: |
    Accelerated optimization algorithms can be generated using a double-integrator model for the search dynamics imbedded in an optimal control problem.\
address: 'Naval Postgraduate School, Monterey, CA 93943'
author:
- 'I. M. Ross'
title: An Optimal Control Theory for Accelerated Optimization
---

accelerated Newton’s method ,control Lyapunov function ,Lie derivative ,Nesterov’s accelerated gradient method ,Polyak’s heavy ball method ,Riemannian metric

Introduction
============

In [@rossJCAM-1], we proposed an optimal control theory for solving a constrained optimization problem, $$(N) \left\{\displaystyle\mathop\text{Minimize }_{{\boldsymbol x}_f \in C \subseteq {{\mathbb R}^{N_x}}}   E({\boldsymbol x}_f) \right.$$ where $C$ is a constraint set in ${{\mathbb R}^{N_x}},\ N_x \in \mathbb{N}^+$ and $E: {\boldsymbol x}_f \ni {{\mathbb R}^{N_x}} \to {\mathbb R}$ is an objective function. A key concept in this framework was to view an algorithmic map $${\boldsymbol x}_0, {\boldsymbol x}_1, \ldots, {\boldsymbol x}_k, {\boldsymbol x}_{k+1}, \ldots$$ in terms of a discretization of a controllable, continuous-time trajectory, $t \mapsto {\boldsymbol x}\in {{\mathbb R}^{N_x}} $, whose dynamics is given by the single integrator model, $$\label{eq:xdot=u}
\dot{\boldsymbol x}= {{\boldsymbol u}}$$ where $t \mapsto {{\boldsymbol u}}\in {{\mathbb R}^{N_x}}$ is a control trajectory that must be designed such that at some time $t = t_f$, ${\boldsymbol x}(t_f) = {\boldsymbol x}_f$ is a solution to the given optimization problem. Starting with this simple idea, it is possible to generate a wide variety of well-known algorithms such as Newton’s method and the steepest descent method. Because continuous versions of “momentum” optimization methods involve second derivaties[@polyak64; @su], we explore the ramifications of replacing by a double-integrator model, $$\label{eq:xddot=u}
\ddot{\boldsymbol x}= {{\boldsymbol u}}$$ In essence, we show that the application of the theory presented in [@rossJCAM-1] with replaced by generates accelerated optimization techniques.

Rewriting in state-space form, $$\label{eq:dint-statespace}
\dot{\boldsymbol x}= {{\boldsymbol v}}, \quad \dot{{\boldsymbol v}}= {{\boldsymbol u}}$$ it follows from that a momentum method is essentially adding “inertia” to the “inertia-less” control of the single-integrator model.

\[rem:CG=HB\] A conjugate gradient (CG) method may also be viewed as an accelerated optimization technique in the context of . This observation follows by considering a generic CG method,

\[eq:CG\] $$\begin{aligned}
{\boldsymbol x}_{k+1} &= {\boldsymbol x}_k + \alpha_k {{\boldsymbol v}}_k \label{eq:CG-xk}\\
{{\boldsymbol v}}_{k} &= -{{\boldsymbol g}}_{k} + \beta^{CG}_k {{\boldsymbol v}}_{k-1} \label{eq:CG-pk}\end{aligned}$$

where $\alpha_k \ge 0 $ is the step length, ${{\boldsymbol v}}_k$ is the search direction, ${{\boldsymbol g}}_k := {{\boldsymbol g}}({\boldsymbol x}_k)$ is the gradient of the objective function function, and $\beta^{CG}_k \ge 0$ is the CG update parameter. Rewriting as single equation, $$\label{eq:CG=HB}
{\boldsymbol x}_{k+1} = {\boldsymbol x}_k - \alpha_k {{\boldsymbol g}}_k + \beta_k ({\boldsymbol x}_k - {\boldsymbol x}_{k-1}), \quad \beta_k := \left(\frac{\alpha_k \beta^{CG}_k}{\alpha_{k-1}}\right)$$ it follows that may be viewed as a discretization of $$\label{eq:u=HB}
\ddot{\boldsymbol x}= {{\boldsymbol u}}, \quad {{\boldsymbol u}}= -\gamma_a {{\boldsymbol g}}({\boldsymbol x})  -\gamma_b {{\boldsymbol v}}, \quad \gamma_a \in {\mathbb R}^+, \gamma_b \in {\mathbb R}^+$$ The non-control-theoretic, ordinary-differential-equation (ODE) form of , $$\label{eq:polyak}
\ddot{\boldsymbol x}+ \gamma_a {{\boldsymbol g}}({\boldsymbol x}) + \gamma_b \dot{\boldsymbol x}= {{\bf 0}}$$ is Polyak’s equation[@polyak64]. In the theory proposed in this paper, the function $({\boldsymbol x}, {{\boldsymbol v}})\mapsto -\gamma_a\, {{\boldsymbol g}}({\boldsymbol x}) - \gamma_b\, {{\boldsymbol v}}$ turns out to be a specific “optimal” feedback controller ${{\boldsymbol u}}$ for the double integrator $\ddot{\boldsymbol x}= {{\boldsymbol u}}$.

Despite their mathematical equivalence, there is a sharp change in perspective between and . Formula suggests that the search variable is velocity. According to , the search variable is acceleration.

It will be apparent shortly that the objective of the proposed theory is not to take existing algorithms and interpret them as ODEs or control systems, rather, it is to use optimal control theory as a foundational concept for optimization and as a discovery tool for algorithms[@rossJCAM-1].

Background: Optimal Control Theory for Optimization
===================================================

Consider some optimal control problem $(M)$ whose cost functional is given by a “Mayer” cost function $E : {\boldsymbol x}_f \mapsto {\mathbb R}$, where, ${\boldsymbol x}_f = {\boldsymbol x}(t_f)$ is constrained to lie in a target set $C$. A transversality condition for Problem $(M)$ is given by, $$\label{eq:tvc-cone}
{{\mbox{\boldmath $\lambda$}}}_x(t_f) \in \nu_0\,\partial E({\boldsymbol x}_f) + N_C({\boldsymbol x}_f)$$ where, ${{\mbox{\boldmath $\lambda$}}}_x(t_f)$ is the final value of an adjoint arc $t \mapsto {{\mbox{\boldmath $\lambda$}}}_x$ associated with $t \mapsto {\boldsymbol x}$, $\nu_0 \ge 0$ is a cost multiplier and $N_C({\boldsymbol x}_f)$ is the limiting normal cone[@vinter] to the set $C$ at ${\boldsymbol x}_f$. If Problem $(M)$ is designed so that ${{\mbox{\boldmath $\lambda$}}}_x(t_f)$ vanishes, then the transversality condition reduces to the necessary condition for Problem $(N)$, $${{\bf 0}}\in \nu_0\,\partial E({\boldsymbol x}_f) + N_C({\boldsymbol x}_f)$$ In [@rossJCAM-1], we showed the existence of Problem $(M)$ by direct construction for the case when $C$ is given by functional constraints, $$C =  {\left\{{\boldsymbol x}\in {{\mathbb R}^{N_x}}:\ {{\boldsymbol e}}^L \le {{\boldsymbol e}}({\boldsymbol x}) \le {{\boldsymbol e}}^U \right\}}$$ where, ${{\boldsymbol e}}: {\boldsymbol x}\mapsto {{\mathbb R}^{N_e}}$ is a given function, and ${{\boldsymbol e}}^L$ and ${{\boldsymbol e}}^U$ are the specified lower and upper bounds on the values of ${{\boldsymbol e}}$. In this paper, we briefly review and revise the results obtained in [@rossJCAM-1] in the context . Furthermore, for the purposes of brevity and clarity, we limit the discussions to the unconstrained “static” optimization problem given by, $$(S) \left\{\displaystyle\mathop\text{Minimize }_{{\boldsymbol x}_f \in {{\mathbb R}^{N_x}}}   E({\boldsymbol x}_f) \right.$$ In following [@rossJCAM-1], we create a vector field by “sweeping” the function $E$ backwards in time according to, $$\label{eq:idea-1}
y(t) := E({\boldsymbol x}(t))$$ Differentiating with respect to time we get, $$\label{eq:cost-evolution}
\dot y = \left[\partial_{{\boldsymbol x}} E({\boldsymbol x})\right]^T \dot{\boldsymbol x}= \left[\partial_{{\boldsymbol x}} E({\boldsymbol x})\right]^T {{\boldsymbol v}}, \quad \dot{{\boldsymbol v}}:= {{\boldsymbol u}}$$ Collecting all relevant equations, we define the following candidate optimal control problem $(R)$ that purportedly solves the optimization problem $(S)$: $$\begin{aligned}
&(R) \left\{
\begin{array}{lrl}
\textsf{Minimize }  & J[y(\cdot), {\boldsymbol x}(\cdot), {{\boldsymbol v}}(\cdot), {{{{\boldsymbol u}}(\cdot)}}, t_f]
:=& y_f  \\
\textsf{Subject to} & \dot{\boldsymbol x}=& {{\boldsymbol v}}\\
&\dot{{\boldsymbol v}}= & {{\boldsymbol u}}\\
&\dot y=& \left[\partial_{{\boldsymbol x}} E({\boldsymbol x})\right]^T {{\boldsymbol v}}\\
&({\boldsymbol x}(t_0), t_0) =& ({\boldsymbol x}^0, t^0) \\
& y(t_0) = & E({\boldsymbol x}^0) \\
&{{\boldsymbol v}}(t_f) = & {{\bf 0}}\end{array} \right.& \label{eq:prob-R}\end{aligned}$$ where, ${\boldsymbol x}^0$ is an initial “guess” of the solution (to Problem $(S)$). The variables $t_f, {\boldsymbol x}(t_f)$ and ${{\boldsymbol v}}(t_0)$ are free.

The main difference between and the optimal control problem for unconstrained optimization considered in [@rossJCAM-1] is the acceleration equation $\dot{{\boldsymbol v}}= {{\boldsymbol u}}$ and its associated endpoint condition ${{\boldsymbol v}}(t_f) = {{\bf 0}}$.

\[lemma:normality\] Problem $(R)$ has no abnormal extremals.

The Pontryagin Hamiltonian[@ross-book] for this problem is given by, $$\label{eq:H-unc}
H({{\mbox{\boldmath $\lambda$}}}_x, {{\mbox{\boldmath $\lambda$}}}_v, \lambda_y, {\boldsymbol x}, {{\boldsymbol v}}, y, {{\boldsymbol u}}):= {{\mbox{\boldmath $\lambda$}}}_x^T{{\boldsymbol v}}+ {{\mbox{\boldmath $\lambda$}}}_v^T{{\boldsymbol u}}+ \lambda_y \left[\partial_{{\boldsymbol x}} E({\boldsymbol x})\right]^T {{\boldsymbol v}}$$ where, ${{\mbox{\boldmath $\lambda$}}}_{x}, {{\mbox{\boldmath $\lambda$}}}_v$ and $\lambda_y$ are costates that satisfy the adjoint equations,

$$\begin{aligned}
\dot{{\mbox{\boldmath $\lambda$}}}_{x} &=-\partial_{{\boldsymbol x}}H = -\lambda_y\,\partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, {{\boldsymbol v}}\label{eq:adj-x-unc}\\
\dot{{\mbox{\boldmath $\lambda$}}}_v & = -\partial_{{{\boldsymbol v}}}H = - {{\mbox{\boldmath $\lambda$}}}_x -\lambda_y\,\partial_{{\boldsymbol x}}E({\boldsymbol x})\label{eq:adj-v-unc}\\
\dot\lambda_y & =-\partial_y H = 0 \label{eq:adj-y-unc}\end{aligned}$$

The transversality conditions[@ross-book] for Problem $(R)$ are given by,

$$\begin{aligned}
{{\mbox{\boldmath $\lambda$}}}_x(t_f) &= {{\bf 0}}\label{eq:tvc-x}\\
{{\mbox{\boldmath $\lambda$}}}_v(t_0) & = {{\bf 0}}\label{eq:tvc-v}\\
{{\mbox{\boldmath $\lambda$}}}_y(t_f) & = \nu_0 \ge 0 \label{eq:tvc-y}\end{aligned}$$

where, $\nu_0$ is the cost multiplier. From and we have, $$\label{eq:lam-y-pre-tvc}
\lambda_y(t) = \nu_0$$ If $\nu_0 = 0$, then $\lambda_y(t) \equiv 0$. This implies, from and , that ${{\mbox{\boldmath $\lambda$}}}_x(t) \equiv {{\bf 0}}$. Similarly, ${{\mbox{\boldmath $\lambda$}}}_v(t) \equiv {{\bf 0}}$ from and . The vanishing of all multipliers violates the nontriviality condition. Hence $\nu_0 > 0$.

\[thm-singular\] All extremals of Problem $(R)$ are singular. Furthermore, the singular arc is of infinite order.

The Hamiltonian is linear in the control variable and the control space is unbounded; hence, if ${{\boldsymbol u}}$ is optimal, it must be singular. Furthermore, from the Hamiltonian minimization condition we have the first-order condition, $$\label{eq:hmc-order-1}
\partial_{{{\boldsymbol u}}} H = {{\mbox{\boldmath $\lambda$}}}_v(t) = {{\bf 0}}\qquad\forall t \in [t_0, t_f]$$ Differentiating with respect to time, we get, $$\label{eq:SA-deg-1}
\frac{d}{dt}\partial_{{{\boldsymbol u}}} H =\dot{{\mbox{\boldmath $\lambda$}}}_v(t) = - {{\mbox{\boldmath $\lambda$}}}_x -\nu_0\,\partial_{{\boldsymbol x}}E({\boldsymbol x})  = {{\bf 0}}$$ Equation does not generate an expression for the control function; hence, taking the second time derivative of $\partial_{{{\boldsymbol u}}}H$ we get, $$\begin{aligned}
\frac{d^2}{dt^2}\partial_{{{\boldsymbol u}}} H &= -\dot{{\mbox{\boldmath $\lambda$}}}_x - \nu_0\, \partial^2_{{\boldsymbol x}} E({\boldsymbol x})\,\dot{\boldsymbol x}\nonumber\\
        &=-\dot{{\mbox{\boldmath $\lambda$}}}_x - \nu_0\, \partial^2_{{\boldsymbol x}} E({\boldsymbol x})\,{{\boldsymbol v}}\nonumber \\
        &\equiv {{\bf 0}}\end{aligned}$$ where, the last equality follows from and Lemma \[lemma:normality\]. Hence, we have, $$\frac{d^k}{dt^k}\partial_{{{\boldsymbol u}}} H = {{\bf 0}}\quad\text{for\ } k = 0, 1 \ldots$$ and no $k$ yields an expression for ${{\boldsymbol u}}$.

\[thm:tmt\] The necessary condition for Problem $(S)$ is part of the transversality condition for Problem $(R)$.

From , we have $$\label{eq:lam-x-sol-generic}
{{\mbox{\boldmath $\lambda$}}}_x(t) = -\nu_0\, \partial_{{\boldsymbol x}} E({\boldsymbol x}(t))$$ From and Lemma 1, it follows that $\partial_{{\boldsymbol x}_f}E({\boldsymbol x}_f) = {{\bf 0}}$.

Minimum Principles for Accelerated Optimization
===============================================

From the results of the previous section, it follows that the primal-dual control dynamical system generated by Problem $(R)$ is given by,

\[eq:p-d-dynamics\] $$\begin{aligned}
\dot{\boldsymbol x}& = {{\boldsymbol v}}& \dot{{\mbox{\boldmath $\lambda$}}}_{x} & = -\lambda_y\,\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) \, {{\boldsymbol v}}\\
\dot{{\boldsymbol v}}& = {{\boldsymbol u}}& \dot{{\mbox{\boldmath $\lambda$}}}_v & =  -{{\mbox{\boldmath $\lambda$}}}_x - \lambda_y\, \partial_{{\boldsymbol x}} E({\boldsymbol x})\\
\dot y & = \big[\partial_{{\boldsymbol x}} E({\boldsymbol x})\big]^T {{\boldsymbol v}}& \dot\lambda_y & = 0\end{aligned}$$

The boundary conditions for are given by,

\[eq:BCs\] $$\begin{aligned}
{\boldsymbol x}(t^0) & = {\boldsymbol x}^0  & {{\boldsymbol v}}(t_f) & = {{\bf 0}}\\
y(t^0) &= E({\boldsymbol x}^0)    & {{\mbox{\boldmath $\lambda$}}}_x(t_f) & = {{\bf 0}}\\
{{\mbox{\boldmath $\lambda$}}}_v(t^0) & =  {{\bf 0}}& \lambda_y(t_f) &= \nu_0 > 0\end{aligned}$$

Because the optimal control is singular of infinite order, any control trajectory that satisfies and is optimal. Along a singular arc, ${{\mbox{\boldmath $\lambda$}}}_v(t) \equiv {{\bf 0}}$; hence, the auxiliary controllable dynamical system of interest[@rossJCAM-1] resulting from is given by, $$\label{eq:aux-dynamics}
(A) \left \{
\begin{aligned}
\dot{{\mbox{\boldmath $\lambda$}}}_{x} & = -\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) \, {{\boldsymbol v}}\\
\dot{{\boldsymbol v}}& = {{\boldsymbol u}}\end{aligned}
\right.$$ where, we have scaled the adjoint covector ${{\mbox{\boldmath $\lambda$}}}_x$ by $\nu_0 > 0$ (cf. Lemma \[lemma:normality\]). The target final-time condition for $(A)$ is given by, $$\label{eq:aux-target}
(T) \left \{
\begin{aligned}
{{\mbox{\boldmath $\lambda$}}}_x(t_f) & = {{\bf 0}}\\
{{\boldsymbol v}}(t_f) & = {{\bf 0}}\end{aligned}
\right.$$ That is, any singular control that satisfies and generates a candidate “optimal” continuous-time algorithm for Problem $(S)$.

The auxiliary controllable dynamical system is equivalent to the time-derivative of the swept-back gradient function.

Application of a Minimum Principle Presented in [@rossJCAM-1]
-------------------------------------------------------------

Let ${{\mbox{\boldmath $\beta$}}}$ be a control vector field defined according to, $${{\mbox{\boldmath $\beta$}}}({\boldsymbol x}, {{\boldsymbol v}}, {{\boldsymbol u}}) := \left[
                        \begin{array}{c}
                          -\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) \, {{\boldsymbol v}}\\
                           {{\boldsymbol u}}\\
                        \end{array}
                      \right]$$ Let $V:({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}) \mapsto {\mathbb R}$ be a control Lyapunov function for the $(A, T)$ pair. Let $\pounds_\beta V$ be the Lie derivative of $V$ along the vector field ${{\mbox{\boldmath $\beta$}}}$. Then, a sufficient condition for producing a globally convergent algorithm[@rossJCAM-1] is to design a singular control function such that $V$ is dissipative (when ${\boldsymbol x}\ne {\boldsymbol x}_f$), $$\label{eq:clf-theory-1}
\pounds_\beta V = \big[\partial V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T {{\mbox{\boldmath $\beta$}}}({\boldsymbol x}, {{\boldsymbol v}}, {{\boldsymbol u}}) < 0$$ In [@rossJCAM-1], it is proposed that this objective can be achieved via the Minimum Principle, $$\begin{aligned}
&(P) \left\{
\begin{array} {lll}
\displaystyle\mathop\textsf{Minimize }_{{{\boldsymbol u}}}  & \pounds_\beta V := \big[\partial V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T {{\mbox{\boldmath $\beta$}}}({\boldsymbol x}, {{\boldsymbol v}}, {{\boldsymbol u}}) \\
\textsf{Subject to} & {{\boldsymbol u}}\in  {\mathbb{U}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t)
\end{array} \right.& \label{prob:Min-P}\end{aligned}$$ where, ${\mathbb{U}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t)$ is an appropriate compact set that may vary with respect to the tuple $({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t)$. In an “unaccelerated” method, a solution to Problem ($P$) ensures the satisfaction of when ${\mathbb{U}}$ is chosen to metricize the control space[@rossJCAM-1]. Because of the presence of a drift vector field in the auxiliary dynamical system $(A)$, the Minimum Principle $(P)$ cannot guarantee $\pounds_\beta V < 0$; this follows by simply inspecting the expression for $\pounds_\beta V$, $$\pounds_\beta V =  -\big[\partial_{\boldsymbol\lambda_x}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) \, {{\boldsymbol v}}+ \big[\partial_{{{\boldsymbol v}}}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T {{\boldsymbol u}}$$ To ensure $\pounds_\beta V < 0$, we impose the following requirement on $V$, $$\label{eq:drift-condition}
\partial_{\boldsymbol\lambda_x}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) \, {{\boldsymbol v}}> 0 \quad\text{if }\quad \partial_{{{\boldsymbol v}}}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}) = {{\bf 0}}\ \text{and } ({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}) \ne {{\bf 0}}$$ Furthermore, we set ${{\boldsymbol u}}= {{\bf 0}}$ if $\partial_{{{\boldsymbol v}}} V = {{\bf 0}}$. All of these results — in their general form — are well-known in nonlinear feedback control theory[@sontag-book]; hence, they are, technically, not new. What is new is their application to static optimization.

An Alternative Minimum Principle
--------------------------------

We can formulate an alternative Minimum Principle that essentially exchanges the cost and constraint functions in . Let $\rho:({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, {\boldsymbol x}) \mapsto {\mathbb R}_+$ be an appropriate design function such that $-\rho$ specifies a rate of descent for $\dot V$. We propose to select a singular control ${{\boldsymbol u}}$ such that, $$\label{eq:clf-theory-strong}
\pounds_\beta V = \big[\partial V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T {{\mbox{\boldmath $\beta$}}}({\boldsymbol x}, {{\boldsymbol v}}, {{\boldsymbol u}}) \le -\rho({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, {\boldsymbol x})$$ That is, in contrast to , we seek a singular control that merely achieves a specified rate of descent given in terms of $\rho$. Let $D: ({{\boldsymbol u}}, {\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t) \mapsto {\mathbb R}$ be an appropriate objective function. Then, a singular control ${{\boldsymbol u}}$ that solves the optimization problem, $$\begin{aligned}
&(P^*) \left\{
\begin{array} {lll}
\displaystyle\mathop\textsf{Minimize }_{{{\boldsymbol u}}}  &D ({{\boldsymbol u}}, {\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t) \\
\textsf{Subject to} & \pounds_\beta V +\rho({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, {\boldsymbol x}) \le 0
\end{array} \right.& \label{prob:Min-P*}\end{aligned}$$ is a candidate (continuous-time) solution to the accelerated optimization problem.

Problem $(P^*)$ has been widely used in control theory for generating feedback controls[@sontag-book; @freeman-acc]. Note also that condition on $V$ specified by is implicit in .

LaSalle’s invariance principle[@sontag-book] may be used to relax the positive definite condition on $V$ and the negative definite condition on $\pounds_\beta V$.

Accelerated Optimization via Minimum Principles
===============================================

Following [@rossJCAM-1], we consider $$\label{eq:U-metric-trust}
{\mathbb{U}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t) := {\left\{{{\boldsymbol u}}:\  {{\boldsymbol u}}^T{{\boldsymbol W}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t){{\boldsymbol u}}\le \Delta({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t) \right\}}$$ where, $\Delta({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t) \ne 0$ is a positive real number and ${{\boldsymbol W}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t)$ is some appropriate positive definite matrix that metricizes the space ${\mathbb{U}}$. The quantities $\Delta$ and ${{\boldsymbol W}}$ may depend upon some or all of the variables ${\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}$ and $t$. Applying the Minimum Principle given by , it is straightforward to show that if $\partial_{{{\boldsymbol v}}}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}) \ne {{\bf 0}}$, then ${{\boldsymbol u}}$ is given explicitly by, $$\label{eq:u-fromMinP}
{{\boldsymbol u}}= -\sigma[@t]\, {{\boldsymbol W}}^{-1}[@t] \, \partial_{{{\boldsymbol v}}} V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}), \qquad \sigma[@t] > 0$$ where, $$\sigma^2[@t] := \frac{\Delta({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t)}{\big[\partial_{{{\boldsymbol v}}}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T {{\boldsymbol W}}^{-1}[@t]\big[\partial_{{{\boldsymbol v}}}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]}$$ and ${{\boldsymbol W}}[@t]:= {{\boldsymbol W}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t)$. That is, the $[@t]$ notation is simply a convenient shorthand for the various implicit and explicit time dependencies[@ross-book].

Switching to an application of Minimum Principle $(P^*)$ and using $$D ({{\boldsymbol u}}, {\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t) =\frac{1}{2} \left({{\boldsymbol u}}^T{{\boldsymbol W}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t){{\boldsymbol u}}\right)$$ we get, $$\label{eq:u-fromMinP*}
{{\boldsymbol u}}= -\sigma^*[@t]\, {{\boldsymbol W}}^{-1}[@t] \, \partial_{{{\boldsymbol v}}} V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}), \qquad \sigma^*[@t] > 0$$ where, $$\sigma^*[@t] := \frac{\rho({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, {\boldsymbol x})  -\big[\partial_{\boldsymbol\lambda_x}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) \, {{\boldsymbol v}}}{\big[\partial_{{{\boldsymbol v}}}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T {{\boldsymbol W}}^{-1}[@t]\big[\partial_{{{\boldsymbol v}}}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]}$$ In other words, both minimum principles ($P$ and $P^*$) generate the same functional form for ${{\boldsymbol u}}$ but with different interpretations for the control “multipliers” given by $\sigma$ and $\sigma^*$.

\[thm:u-fromMPs\] Suppose we choose a quadratic positive definite Lyapunov function, $$\label{eq:V-quad-pd}
V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}) =  (a/2){{\mbox{\boldmath $\lambda$}}}_x^T{{\mbox{\boldmath $\lambda$}}}_x + (b/2){{\boldsymbol v}}^T{{\boldsymbol v}}+ c{{\mbox{\boldmath $\lambda$}}}_x^T{{\boldsymbol v}}$$ where, $$a > 0, \quad b > 0, \quad c \ne 0, \quad ab - c^2 > 0$$ are constants. Let ${{\boldsymbol W}}[@t]:= {{\boldsymbol W}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}, t)$ be a family of positive definite matrices that metricize the space ${\mathbb{U}}$. If $\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) > 0$, then, the singular control resulting from either minimum principle ($P$ or $P^*$) is given by, $${{\boldsymbol u}}=  - {{\boldsymbol W}}^{-1}[@t]\big(\gamma_a\,\partial_{{\boldsymbol x}}E({\boldsymbol x}) + \gamma_b\, {{\boldsymbol v}}\big)$$ where, $\gamma_a \in {\mathbb R}^+$ and $\gamma_b \in {\mathbb R}^+$ are (variable) controller gains.

Applying we get, $$\partial_{{{\boldsymbol v}}}V = c{{\mbox{\boldmath $\lambda$}}}_x + b{{\boldsymbol v}}= {{\bf 0}}\Rightarrow {{\mbox{\boldmath $\lambda$}}}_x = -(b/c){{\boldsymbol v}}$$ Hence, $$\begin{aligned}
\partial_{\boldsymbol\lambda_x}V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}})\big]^T\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) \, {{\boldsymbol v}}& = [a{{\mbox{\boldmath $\lambda$}}}_x + c {{\boldsymbol v}}]^T \partial^2_{{\boldsymbol x}}E({\boldsymbol x}) \, {{\boldsymbol v}}\\
                &= \left(\frac{-ab + c^2}{c}\right){{\boldsymbol v}}^T \partial^2_{{\boldsymbol x}}E({\boldsymbol x}) \, {{\boldsymbol v}}\end{aligned}$$ Thus, for to hold, it follows that $c < 0$ if $\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) > 0$.

The control solution resulting from the Minimum Principle $P$ or $P^*$ can be written as, $$\label{eq:uFromQuadV}
{{\boldsymbol u}}= -\sigma_q[@t] {{\boldsymbol W}}^{-1}[@t]\big(c{{\mbox{\boldmath $\lambda$}}}_x + b {{\boldsymbol v}}\big)$$ where $\sigma_q$ is given by $\sigma$ or $\sigma^*$ depending upon the choice of $P$ or $P^*$ respectively. Substituting ${{\mbox{\boldmath $\lambda$}}}_x = -\partial_{{\boldsymbol x}} E({\boldsymbol x})$ in we get, $$\label{eq:uFamilyNo1}
{{\boldsymbol u}}= - {{\boldsymbol W}}^{-1}[@t]\big(\gamma_a\,\partial_{{\boldsymbol x}}E({\boldsymbol x}) + \gamma_b\, {{\boldsymbol v}}\big)$$ where,

\[eq:gamma-def\] $$\begin{aligned}
\gamma_a &:= -c\,\sigma_q[@t] \ge 0\\
\gamma_b &:= b\,\sigma_q[@t] \ge 0\end{aligned}$$

are the (variable) controller gains.

\[corr:accel-x3\] A family of continuous accelerated optimization methods, parameterized by ${{\boldsymbol W}}$, is given by the ODE, $$\label{eq:FamilyNo1-ode}
\ddot{\boldsymbol x}= - {{\boldsymbol W}}^{-1}[@t]\big(\gamma_a\,\partial_{{\boldsymbol x}}E({\boldsymbol x}) + \gamma_b\, \dot{\boldsymbol x}\big)$$ Equation generates:

1.  Polyak’s equation for the choice of a Euclidean metric (tensor) for ${{\boldsymbol W}}$ given by the identity matrix;

2.  a continuous accelerated Newton’s method for a Riemannian ${{\boldsymbol W}}$ given by the Hessian, $\partial^2_{{\boldsymbol x}} E({\boldsymbol x})$; and,

3.  a continuous accelerated quasi-Newton method for the choice of ${{\boldsymbol W}}$ given by ${{\boldsymbol B}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x)$, a positive definite approximation to the Hessian.

The three special cases of are given explicitly by:

1.  *Polyak’s equation:* $$\label{eq:HB-derive}
    \ddot{\boldsymbol x}= - \big(\gamma_a\,\partial_{{\boldsymbol x}}E({\boldsymbol x}) + \gamma_b\, \dot{\boldsymbol x}\big)$$

2.  *Continuous Accelerated Newton (${{\boldsymbol W}}({\boldsymbol x}) = \partial^2_{{\boldsymbol x}}E({\boldsymbol x})$):* $$\label{eq:CAN}
    \ddot{\boldsymbol x}= - \left[\partial^2_{{\boldsymbol x}}E({\boldsymbol x})\right]^{-1}\big(\gamma_a\,\partial_{{\boldsymbol x}}E({\boldsymbol x}) + \gamma_b\, \dot{\boldsymbol x}\big)$$

3.  *Continuous Accelerated Quasi-Newton (${{\boldsymbol W}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x) = {{\boldsymbol B}}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x)$)*: $$\ddot{\boldsymbol x}= - {{\boldsymbol B}}^{-1}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x)\big(\gamma_a\,\partial_{{\boldsymbol x}}E({\boldsymbol x}) + \gamma_b\, \dot{\boldsymbol x}\big)$$

From Remark \[rem:CG=HB\], it follows that may also be viewed as a derivation of the continuous version of a conjugate gradient method.

Rewriting as, $$\partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, \ddot{\boldsymbol x}+ \gamma_b\, \dot{\boldsymbol x}+ \gamma_a\,\partial_{{\boldsymbol x}}E({\boldsymbol x}) = {{\bf 0}}$$ it follows that a mechanical-system analogy for the continuous accelerated Newton’s method may be described in terms of a nonlinear mass-spring-damper system, where, the Hessian provides the variable inertia. Consequently, Polyak’s equation may be viewed as the case corresponding to the use of a constant inertia. Note also that $\gamma_a$ and $\gamma_b$ are not necessarily constants; see .

In view of Corollary \[corr:accel-x3\], and , we define a family of generalized versions of the accelerated gradient, Newton and quasi-Newton methods according to:

1.  *Generalized Accelerated Gradient:* $$\ddot{\boldsymbol x}= -\sigma_q[@t]\, \partial_{{{\boldsymbol v}}} V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}), \qquad \sigma_q[@t] > 0$$

2.  *Generalized Accelerated Newton:* $$\ddot{\boldsymbol x}= -\sigma_q[@t]\, \left[\partial^2_{{\boldsymbol x}}E({\boldsymbol x})\right]^{-1} \partial_{{{\boldsymbol v}}} V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}), \qquad \sigma_q[@t] > 0$$

3.  *Generalized Accelerated Quasi-Newton*: $$\ddot{\boldsymbol x}= -\sigma_q[@t]\, {{\boldsymbol B}}^{-1}({\boldsymbol x}, {{\mbox{\boldmath $\lambda$}}}_x)\, \partial_{{{\boldsymbol v}}} V({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}), \qquad \sigma_q[@t] > 0$$

Accelerated Optimization via Direct Construction
================================================

As noted in Section 3, any singular control that satisfies and generates a candidate “optimal” continuous-time algorithm for Problem $(S)$; hence, the Minimum Principles proposed in Section 3 are not necessary conditions. They are simply a convenient systematic procedure for generating continuous accelerated optimization methods. In fact, is a sufficient condition; that is, any singular control ${{\boldsymbol u}}$ that renders $\pounds_\beta V < 0$ generates a globally convergent algorithm. In the case of the quadratic Lyapunov function given by , we have, $$\label{eq:Vdot-quadV}
\pounds_\beta V = -[a{{\mbox{\boldmath $\lambda$}}}_x + c{{\boldsymbol v}}]^T \partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, {{\boldsymbol v}}+ [c {{\mbox{\boldmath $\lambda$}}}_x + b {{\boldsymbol v}}]^T {{\boldsymbol u}}$$ The optimal control resulting from either of the Minimum Principles does not directly incorporate the drift vector field for a generic metric tensor ${{\boldsymbol W}}$. Motivated by the intuition to design a control that directly incorporates the drift vector field, consider a feedback control strategy given by, $$\label{eq:uFamilyNo2}
{{\boldsymbol u}}= K_a\, {{\mbox{\boldmath $\lambda$}}}_x + K_b\, {{\boldsymbol v}}+ K_c \, \partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, {{\boldsymbol v}}$$ where $K_a, K_b$ and $K_c$ are all (variable) real numbers that must be chosen so that $\pounds_\beta V$ is negative. Substituting in we get, $$\begin{aligned}
\label{eq:Vdot-wu2}
\pounds_\beta V &= \big(-a + c K_c\big){{\mbox{\boldmath $\lambda$}}}_x^T \partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, {{\boldsymbol v}}+ \big(-c + b K_c\big) {{\boldsymbol v}}^T\partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, {{\boldsymbol v}}\nonumber\\
 &  + \big(c {{\mbox{\boldmath $\lambda$}}}_x + b {{\boldsymbol v}}\big)^T \big(K_a\, {{\mbox{\boldmath $\lambda$}}}_x + K_b\, {{\boldsymbol v}}\big)\end{aligned}$$

Suppose $\partial^2_{{\boldsymbol x}}E({\boldsymbol x}) > 0$. Let $c < 0$ in . If $$K_a > 0, \quad K_b < 0, \quad b K_a  = c K_b,    \quad \text{and}\quad K_c = a/c < 0$$ then, $\pounds_\beta V < 0$ for all $({{\mbox{\boldmath $\lambda$}}}_x, {{\boldsymbol v}}) \ne {{\bf 0}}$ and ${{\boldsymbol u}}$ given by .

Substituting $b K_a = c K_b$ in the third term of generates, $$\label{eq:term3-result}
\big(c {{\mbox{\boldmath $\lambda$}}}_x + b {{\boldsymbol v}}\big)^T \big(K_a\, {{\mbox{\boldmath $\lambda$}}}_x + K_b\, {{\boldsymbol v}}\big) =\frac{K_b}{b}\big(c {{\mbox{\boldmath $\lambda$}}}_x + b {{\boldsymbol v}}\big)^T\big(c {{\mbox{\boldmath $\lambda$}}}_x + b {{\boldsymbol v}}\big) \le 0$$ where, the inequality in follows from the assumption that $K_b < 0$.

With $K_c = a/c$, the first term of vanishes. The second term simplifies to, $$\big(-c + b K_c\big) {{\boldsymbol v}}^T\partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, {{\boldsymbol v}}= \left(\frac{-c^2 + ab}{c} \right){{\boldsymbol v}}^T\partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, {{\boldsymbol v}}$$ Because $ab - c^2 >0$ and $c <0$, it follows that the second term of is negative for a positive definite Hessian; hence, $\pounds_\beta V < 0$.

Let,

$$\begin{aligned}
K_a &:= \gamma_a, &\gamma_a > 0\\
K_b &:= -\gamma_b, & \gamma_b > 0 \\
K_c &:= - \gamma_c, & \gamma_c > 0\end{aligned}$$

then, the singular control law given by generates a family of (continuous) Nesterov-type accelerated gradient methods given by, $$\label{eq:Nesterov}
\ddot{\boldsymbol x}+ \gamma_a\, \partial_{{\boldsymbol x}} E({\boldsymbol x}) + \gamma_b\, \dot{\boldsymbol x}+ \gamma_c \, \partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, \dot{\boldsymbol x}= {{\bf 0}}$$

Equation follows from $\ddot{\boldsymbol x}= {{\boldsymbol u}}$, with ${{\boldsymbol u}}$ given by . The claim that the resulting ODE generates a family of Nesterov’s accelerated gradient method[@nesterov83] follows by considering a discretization of . To this end, consider first a discretization of the the last term on the left-hand-side of : $$\label{eq:term-3}
\gamma_c \, \partial^2_{{\boldsymbol x}}E({\boldsymbol x})\, \dot{\boldsymbol x}= \gamma_c \,\frac{d}{dt}\Big(\partial_{{\boldsymbol x}}E({\boldsymbol x})\Big) \longrightarrow \frac{\gamma_c}{h_k}\Big(\partial_{{\boldsymbol x}}E({\boldsymbol x}_k) - \partial_{{\boldsymbol x}}E({\boldsymbol x}_{k-1})\Big)$$ where, $h_k > 0$ is a discretization step. Next, consider the first three terms of . These are identical to Polyak’s equation (Cf. ); hence it follows from and that may be discretized as, $$\label{eq:Nesterov-derived}
{\boldsymbol x}_{k+1} = {\boldsymbol x}_k - \alpha_k \partial_{{\boldsymbol x}}E({\boldsymbol x}_k) + \beta_k ({\boldsymbol x}_k - {\boldsymbol x}_{k-1}) - \gamma_k \Big(\partial_{{\boldsymbol x}}E({\boldsymbol x}_k) - \partial_{{\boldsymbol x}}E({\boldsymbol x}_{k-1})\Big)$$ Nesterov’s method[@nesterov83] is given by,

$$\begin{aligned}
{\boldsymbol x}_k &= {{\boldsymbol y}}_k -\alpha_k\, \partial_{{{\boldsymbol y}}}E({{\boldsymbol y}}_k) \label{eq:step-1:nes}\\
{{\boldsymbol y}}_{k+1} & = {\boldsymbol x}_k + \beta_k ({\boldsymbol x}_k - {\boldsymbol x}_{k-1}) \label{eq:step-2:nes}\end{aligned}$$

Substituting in generates $$\label{eq:Nesterov-y}
{{\boldsymbol y}}_{k+1} = {{\boldsymbol y}}_k - \alpha_k \partial_{{{\boldsymbol y}}}E({{\boldsymbol y}}_k) + \beta_k ({{\boldsymbol y}}_k - {{\boldsymbol y}}_{k-1}) - \alpha_k\beta_k \Big(\partial_{{{\boldsymbol y}}}E({{\boldsymbol y}}_k) - \partial_{{{\boldsymbol y}}}E({{\boldsymbol y}}_{k-1})\Big)$$ which is the same as with $\gamma_k = \alpha_k\beta_k$.

Equation was introduced and studied by Alvarez et al[@alvarez2002] as a “dynamical inertial Newton” system. Shi et al [@shi:hi-res-Nes] generated this system as a “high-resolution” ODE that represents Nesterov’s method[@nesterov83] in continuous-time. Equation differs from by an additive “Hessian-driven damping” term[@alvarez2002] which has the effect of a “gradient correction”[@shi:hi-res-Nes] a vis-à-vis Polyak’s equation[@polyak64].

References {#references .unnumbered}
==========

[10]{}

I. M. Ross, An optimal control theory for nonlinear optimization, J. Comp. and Appl. Math., 354 (2019) 39–51. B. T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Computational Math. and Math. Phys., 4/5 (1964) 1–17 (Translated by H. F. Cleaves).

W. Su, S. Boyd, E. J. Candes, A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights, J. machine learning research, 17 (2016) 1–43.

R. B. Vinter, Optimal Control, Birkhäuser, Boston, MA, 2000

I. M. Ross, A Primer on Pontryagin’s Principle in Optimal Control, second ed., Collegiate Publishers, San Francisco, CA, 2015.

E. D. Sontag, Mathematical Control Theory: Deterministic Finite Dimensional Systems, second ed., Springer, New York, NY, 1998.

R. A. Freeman, P. V. Kokotović, Optimal nonlinear controllers for feedback linearizable systems, Proc. ACC, Seattle, WA, June 1995.

Yu. E. Nesterov, A method of solving a convex programming problem with convergence rate $\mathcal{O}(1/k^2)$, Soviet Math. Dokl., 27/2 (1983) 371–376 (Translated by A. Rosa).

F. Alvarez, H. Attouch, J. Bolte, P. Redont, A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Applications to optimization and mechanics. J. Math. Pures Appl. 81 (2002) 747–779.

B. Shi, S. S. Du, M. I. Jordan, and W. J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, arXiv preprint (2018) arXiv:1810.08907.
