Homec4science
Diffusion Nonlinear (master) Browse

R7172/tex/Linear convergence/Linear convergence.tex
72a654b4d03fmaster

Last Change
Raw File

Linear convergence.tex
View Options

\documentclass[english]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{hyperref}
\hypersetup{
colorlinks=true,%
citecolor=black,%
filecolor=black,%
linkcolor=black,%
urlcolor=blue
}
\makeatletter
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass uspecific LaTeX commands.
\theoremstyle{plain}
\newtheorem{thm}{\protect\theoremname}
\theoremstyle{plain}
\newtheorem{lem}[thm]{\protect\lemmaname}
\theoremstyle{plain}
\newtheorem{corr}[thm]{\protect\corrolaryname}
%\theoremstyle{definition}
\theoremstyle{plain}
\newtheorem{defn}[thm]{\protect\definitionname}
\theoremstyle{plain}
\newtheorem{prop}[thm]{\protect\propositionname}
\theoremstyle{definition}
\newtheorem{example}[thm]{\protect\examplename}
\newtheorem*{remark}{Remark}
\theoremstyle{plain}
\newtheorem{conditions}[thm]{\protect\conditionsname}
\makeatother
\usepackage{babel}
\providecommand{\definitionname}{Definition}
\providecommand{\examplename}{Example}
\providecommand{\lemmaname}{Lemma}
\providecommand{\corrolaryname}{Corollary}
\providecommand{\propositionname}{Proposition}
\providecommand{\conditionsname}{Conditions}
\providecommand{\theoremname}{Theorem}
\usepackage{geometry}
\geometry{
a4paper,
left=20mm,
%lmargin = 0mm,
%inner = 0mm,
right = 20mm,
%rmargin = 0mm,
%outer = 0mm,
top=15mm,
%tmargin = 0mm,
bottom = 15mm,
%bmargin = 0mm,
}
\def \l{\left}
\def \r{\right}
\def \R{\mathbb{R}}
\def \E{\mathbb{E}}
\def \wt{\widetilde}
\def \D{\mathcal{D}}
\def \wh{\widehat}
\def \ol{\overline}
\def \m{(m)}
\def \t {\theta}
\def \b {\beta}
\def \a {\alpha}
\def \g{\gamma}
\def \n{\natural}
\def \L{\mathcal{L}}
\def \la{\lambda}
\def \s{\sigma}
\title{Linear Convergence of the Augmented Lagrangian Algorithm}
\begin{document}
\maketitle
\section{Setup}
Consider the program
\begin{align}
\begin{cases}
\min_u h(u)\\
A(u) = 0,
\label{eq:main}
\end{cases}
\end{align}
where $h:\R^d\rightarrow\R$ and $A:\R^d\rightarrow \R^m$ satisfy
\begin{align}
\|\nabla_u h(u) - \nabla_u h(u')\|_2 \le \lambda_h \|u-u'\|_2,
\qquad
\| D_uA(u) - D_uA(u') \| \le \lambda_A \|u-u'\|_2,
\label{eq:regular}
\end{align}
for every $u,u'\in \R^d$. Above, $\nabla_u h$ and $D_u A$ are the gradient and Jacobian of $h$ and $A$, respectively, and $\| \cdot\|$ returns the spectral norm of a matrix. Moreover, for $\rho\ge 0$, assume that
\begin{align}
\sup_{\|A(u)\|_2 \le \rho }\|A(u)-A(u')\|_2 \le \lambda'_A \|u-u'\|_2.
\end{align}
Program \eqref{eq:main} is equivalent to
\begin{align}
\min_u \max_y h(u) + \langle A(u), y \rangle,
\end{align}
and in turn equivalent to the program
\begin{align}
\min_u \max_y \mathcal{L}_\beta(u,y),
\qquad
\mathcal{L}_\beta(u,y) = h(u) + \langle A(u),y \rangle + \frac{\beta}{2}\|A(u)\|_2^2,
\label{eq:defn of aug}
\end{align}
for penalty weight $\beta>0$. Above, $\L_\beta$ is the corresponding augmented Lagrangian for Program \eqref{eq:main}. Motivated by the equivalent formulation above, we propose to solve Program \eqref{eq:main} with the following algorithm. For $\beta,\gamma>0$ and a positive sequence $\{\s_k\}_k$, consider the updates
\begin{align}
\begin{cases}
u_{k+1} = u_k - \gamma \nabla \L_\beta (u_k,y_k)\\
y_{k+1} = y_k + \sigma_k A(u_{k+1}).
\end{cases}
\label{eq:updates}
\end{align}
\begin{thm}\label{thm:main}
Consider Algorithm \ref{eq:updates} with the parameters
\begin{align}
\g \le \frac{1}{\la_\b},
\qquad
\qquad
\s_k = \s_0 \min\l( 1, \frac{1}{\|A(u_k)\|_2 k \log (k+1)} \r),
\label{eq:step bnds}
\end{align}
Suppose that the restricted strong isometry holds for $h$ along the trajectory of the algorithm, namely,
\begin{align}
h(u_k) - h(\wh{u}) \ge \langle u_k - \wh{u}, \nabla h(\wh{u}) \rangle + \frac{\mu_h}{2}\|u_k- \wh{u}\|_2^2 - \nu_h ,
\label{eq:h key 1 thm}
\end{align}
\begin{align}
h(u_k) - h(\wh{u}) \le
\langle u_k- \wh{u} , \nabla h(u_k) \rangle - \frac{\mu_h}{2}\|u_k- \wh{u}\|_2^2 + \nu_h,
\label{eq:h key 2 thm}
\end{align}
for every $k$, and with $\mu_h,\nu_h>0$. Let $\wh{u}$ be the unique solution of Program (\ref{eq:main}) and let $\wh{y}$ be a corresponding optimal dual variable in Program (\ref{eq:defn of aug}).
Then it holds that
\begin{align}
\|u_k - \wh{u}\|_2^2 \le \frac{2\kappa_\b^t}{\mu_b} (\L_\b(u_0,y_0)-\L_\b(\wh{u},\wh{y})) + \tau_\b,
\end{align}
\begin{align}
\|A(u_k)\|_2^2 \le \frac{\kappa_\b^t}{\b}(\L_\b(u_0,y_0)-\L_\b(\wh{u},\wh{y})) +\frac{\mu_\b \tau_\b}{2\b},
\end{align}
where
\begin{align}
\kappa_\b = \frac{ \mu_\b- \frac{\gamma \mu_\b^2}{4} + \frac{\g\mu_\b\nu_\b}{\tau_\b^2}}{\mu_\b- 2\s_0\lambda'_A},
\end{align}
\begin{align}
\tau_\b = \max\l( 2 \sqrt{\frac{\g\mu_\b\nu_\b}{\g\mu_\b^2 - 8\s_0\la_A'}}, \l( \frac{ \g\mu_\b^2 \nu_\b+ 8\la_A'}{4(\mu_\b-2\s\lambda'_A)(1-\kappa_\b)} +1 \r) \frac{2\nu_\b}{\mu_\b} \r),
\end{align}
Here,
\begin{align*}
\mu_\b = \min\l( \frac{\mu_h}{2}, \mu_h - \sqrt{m}\la_A - \b\la'_A\r),
\end{align*}
\begin{align*}
\nu_\b =\nu_h + \frac{\|\nabla_u h(\wh{u})\|_2^2}{\mu_h} + \frac{\|y_k\|_2^2}{2\b}.
\label{eq:defn of Deltak}
\end{align*}
\begin{equation}
\s_0 < \frac{\mu_\b}{2\la'_A},
\qquad
\|A(u_0)\|_2 \le \rho.
\end{equation}
\end{thm}
\section{Proof of Theorem \ref{thm:main}}
First, in Appendix \ref{lem:smoothness}, we control the smoothness of $\L_\beta$.
\begin{lem}\label{lem:smoothness}
For every $y\in \R^m$, it holds that
\begin{align}
\L_\b(u,y) \le \L_\b(u',y) + \langle \nabla_u\L_\b(u',y), u-u'\rangle + \frac{\la_\b}{2}\|u-u' \|_2^2
\label{eq:smoothness of lagrangian}
\end{align}
where
\begin{align}
\la_\b \le \la_h + \sqrt{d} \la_A(\|y\|_2+\beta \|A(u)\|_2) + \b \|D_u A(u)\|^2_F.
\end{align}
\end{lem}
Let $\widehat{u}\in \R^d$ be the unique solution of Program \eqref{eq:main} and let $\widehat{y}$ be a corresponding optimal dual variable in Program \eqref{eq:defn of aug}. The following result, proved in Appendix , ensures that $\L_\b$ is strongly convex along the trajectory of our algorithm.
\begin{lem}\label{lem:strong cvx}
For $\mu_h,\nu_h>0$ and every $k$, suppose that
\begin{align}
h(u_k) - h(\wh{u}) \ge \langle u_k - \wh{u}, \nabla h(\wh{u}) \rangle + \frac{\mu_h}{2}\|u_k- \wh{u}\|_2^2 - \nu_h ,
\label{eq:h key 1}
\end{align}
\begin{align}
h(u_k) - h(\wh{u}) \le
\langle u_k- \wh{u} , \nabla h(u_k) \rangle - \frac{\mu_h}{2}\|u_k- \wh{u}\|_2^2 + \nu_h.
\label{eq:h key 2}
\end{align}
Then, for every $k$, it holds that
\begin{align}
\Delta_k \ge \frac{\mu_\b \|u_k - \widehat{u}\|_2^2}{2} - \nu_\b.
\label{eq:key 1}
\end{align}
\begin{align}
\Delta_k \le \langle \nabla_u \L_\b(u_k,y_k) ,u_k-\wh{u}\rangle - \frac{\mu_\b \|u_k - \widehat{u}\|_2^2}{2} + \nu_\b,
\label{eq:key 2}
\end{align}
where
\begin{align*}
\Delta_k := \L_\beta (u_k,y_k) - \L_\beta (\widehat{u},\widehat{y}),
\end{align*}
\begin{align*}
\mu_\b = \min\l( \frac{\mu_h}{2}, \mu_h - \sqrt{m}\la_A - \b\la'_A\r),
\end{align*}
\begin{align}
\nu_\b =\nu_h + \frac{\|\nabla_u h(\wh{u})\|_2^2}{\mu_h} + \frac{\|y_k\|_2^2}{2\b}.
\label{eq:defn of Deltak}
\end{align}
\end{lem}
Note that
\begin{align}
& \L_\beta(u_{k+1},y_{k+1}) \nonumber\\
& = h(u_{k+1}) + \langle A(u_{k+1}), y_{k+1} \rangle + \frac{\beta}{2} \|A(u_{k+1})\|_2^2
\qquad \text{(see \eqref{eq:defn of aug})}
\nonumber\\
& = h(u_{k+1}) + \langle A(u_{k+1}), y_{k} \rangle + \l( \frac{\beta}{2}+ \sigma_k \r) \|A(u_{k+1})\|_2^2
\qquad \text{(see \eqref{eq:updates})}
\nonumber\\
& = \L_\beta (u_{k+1},y_k ) + \sigma_k \|A(u_{k+1})\|_2^2
\qquad \text{(see \eqref{eq:defn of aug})}
\nonumber\\
& \le \L_\beta(u_{k},y_k) + \langle u_{k+1}-u_k,\nabla_u \L_\beta(u_k,y_k) \rangle + \frac{\la_\b }{2}\|u_{k+1}-u_k\|_2^2 + \sigma_k \|A(u_{k+1})\|_2^2
\qquad \text{(see \eqref{eq:smoothness of lagrangian})}
\nonumber\\
& \le \L_\beta(u_{k},y_k) + \langle u_{k+1}-u_k,\nabla_u \L_\beta(u_k,y_k) \rangle + \frac{\|u_{k+1}-u_k\|_2^2}{2\gamma} + \sigma_k \|A(u_{k+1})\|_2^2
\qquad \text{(see \eqref{eq:step bnds})}
\label{eq:long chain 1}
\end{align}
By its definition in \eqref{eq:updates}, we have that
\begin{equation}
u_{k+1} = \arg\min_u \langle u-u_k,\nabla_u \L_\beta(u_k,y_k) \rangle + \frac{\|u-u_k\|_2^2}{2\gamma}.
\end{equation}
This allows us to write that
\begin{align}
\nonumber\\
& \L_\b(u_{k+1},y_{k+1}) \nonumber\\
& \le \L_\beta(u_{k},y_k) + \s_k \|A(u_{k+1})\|_2^2+
\begin{cases}
\min_{\alpha,u} \langle u-u_k,\nabla_u \L_\beta(u_k,y_k) \rangle + \frac{\|u-u_k\|_2^2}{2\gamma} \\
u= \alpha \widehat{u} +(1-\alpha) u_k\\
\alpha \in [0,1]
\end{cases}
\nonumber\\
& = \L_\beta(u_{k},y_k) + \s_k \|A(u_{k+1})\|_2^2 +
\min_{\alpha \in [0,1]} \alpha \langle \widehat{u}-u_k,\nabla_u \L_\beta(u_k,y_k) \rangle + \frac{\alpha^2 \|\widehat{u}-u_k\|^2_2}{2\gamma} \nonumber\\
& \le \L_\beta(u_{k},y_k) + \s_k \|A(u_{k+1})\|^2_2+
\min_{\alpha \in [0,1]} \alpha (\L_\beta (\widehat{u},\widehat{y}) - \L_\beta(u_k,y_k) + \nu_\b ) + \frac{\alpha^2\|\widehat{u} - u_k\|^2_2}{2\gamma}.
\qquad \text{(see \eqref{eq:key 2})}
\label{eq:chain}
\end{align}
The quadratic expression in $\alpha$ in the last line above is minimized at $\wh{\a}$ on $\R$, computed as
\begin{equation}
\wh{ \alpha} = \frac{\gamma (\L_\beta(u_k,y_k) - \L_\beta(\widehat{u},\widehat{y}) -\nu_\b) }{\|u_k - \widehat{u}\|_2^2}.
\label{eq:bnd on alpha}
\end{equation}
On the one hand, $\nabla_u \L_\b(\widehat{u},\widehat{y})=0$. Therefore, (\ref{eq:step bnds},\ref{eq:smoothness of lagrangian}) together imply that
\begin{align}
\wh{\a} \le \g \la_\b \le 1.
\label{eq:bnd alphastar 1}
\end{align}
On the other hand, (\ref{eq:key 1}) implies that
\begin{align}
\wh{\a} \ge \frac{\g\mu_\b}{2} - \frac{2\g\nu_\b}{\|u_k-u\|_2^2}.
\label{eq:bnd alphastar 2}
\end{align}
Based on these observations, let us assume that
\begin{align}
\|u_k-\wh{u}\|_2 \ge \tau_\b \ge 2\sqrt{\frac{\nu_\b}{\mu_\b}},
\label{eq:thresh 1}
\end{align}
for a threshold $\tau_\b$ to be set later so that $\a^*\in [0,1]$, by (\ref{eq:bnd alphastar 1},\ref{eq:bnd alphastar 2}).
With the choice of $\alpha=\wh{\alpha}$, we may simplify the last line of \eqref{eq:chain} as
\begin{align*}
& \L_\beta(u_{k+1},y_{k+1}) \nonumber\\
&\le \L_\beta(u_{k},y_k) + \s_k \|A(u_{k+1})\|^2_2+
\wh{\alpha} (\L_\beta (\widehat{u},\widehat{y}) - \L_\beta(u_k,y_k) + \nu_\b ) + \frac{\wh{\alpha}^2\|\widehat{u} - u_k\|^2_2}{2\gamma} \nonumber\\
& = \L_\beta(u_{k},y_k) + \s_k \|A(u_{k+1})\|^2_2
- \frac{\gamma ( \L_\beta(u_k,y_k) - \L_\beta(\wh{u},\wh{y} ) - \nu_\b )^2 }{2\|u_k-u^*\|^2}
\nonumber\\
& \le \L_\beta(u_{k},y_k) + \s_k \|A(u_{k+1})\|^2_2
-\g\l(\frac{ \mu_\b}{4}-\frac{\nu_\b}{\|u_k-\wh{u}\|_2^2} \r) | \L_\beta(u_k,y_k) - \L_\beta(\wh{u},\wh{y} ) - \nu_\b|
\qquad \text{(see \eqref{eq:key 1})} \nonumber\\
& \le \L_\beta(u_{k},y_k) + \s_k \|A(u_{k+1})\|^2_2
-\g\l(\frac{ \mu_\b}{4}-\frac{\nu_\b}{\tau_\b^2} \r) | \L_\beta(u_k,y_k) - \L_\beta(\wh{u},\wh{y} ) - \nu_\b| \nonumber\\
& \le \L_\beta(u_{k},y_k) + \s_k \|A(u_{k+1})\|^2_2
-\g\l(\frac{ \mu_\b}{4}-\frac{\nu_\b}{\tau_\b^2} \r) ( \L_\beta(u_k,y_k) - \L_\beta(\wh{u},\wh{y} ) - \nu_\b)
\qquad \text{(see \eqref{eq:thresh 1})}
\end{align*}
which, after rearranging and simplification, yields that
\begin{align}
\Delta_{k+1}& \le
\s_k \|A(u_{k+1})\|_2^2
+
\l( 1- \frac{\g\mu_\b}{4} + \frac{\g\nu_\b}{\tau_\b^2} \r)
\Delta_k + \frac{\g\mu_\b\nu_\b}{4}.
\qquad \text{(see \eqref{eq:defn of Deltak})}
\label{eq:linear pre}
\end{align}
To control $\|A(u_{k+1})\|_2$ above, we write that
\begin{align}
\s_k \|A(u_{k+1})\|^2 & \le \s_0 \|A(u_{k+1}) - A(\wh{u}) \|_2^2
\qquad \l(\text{\eqref{eq:step bnds} and } A(\wh{u})=0 \r)
\nonumber\\
& \le \s_0\lambda'_A \|u_{k+1}-\wh{u}\|_2^2
\qquad \text{(see (\ref{eq:regular}))}\nonumber\\
& \le \frac{2\s_0\lambda'_A }{\mu_\b } \l( \Delta_k + \nu_\b \r).
\qquad \text{(see \eqref{eq:key 1})}
\end{align}
Substituting the above bound back into \eqref{eq:linear pre}, we arrive at
\begin{align*}
\Delta_{k+1} \le
\kappa_\b \Delta_k
+ \frac{ \g\mu_\b^2 \nu_\b+ 8\la_A'}{4(\mu_\b-2\s_0\lambda'_A)} \nu_\b
,
\end{align*}
\begin{align}
\kappa_\b := \frac{ \mu_\b- \frac{\gamma \mu_\b^2}{4} + \frac{\g\mu_\b\nu_\b}{\tau_\b^2}}{\mu_\b- 2\s_0\lambda'_A}.
\label{eq:contraction}
\end{align}
Let us take
\begin{align}
\tau_\b
> 2 \sqrt{\frac{\g\mu_\b\nu_\b}{\g\mu_\b^2 - 8\s_0\la_A'}},
\qquad
\s_0 < \frac{\mu_\b}{2\la_A'},
\label{eq:contraction cnds}
\end{align}
so that $\kappa_\b \in [0,1)$. Then, by unfolding \eqref{eq:contraction}, we reach
\begin{align}
\Delta_k & \le \kappa_\b^t \Delta_0 + \frac{ \g\mu_\b^2 \nu_\b+ 8\la_A'}{4(\mu_\b-2\s_0\lambda'_A)} \frac{ \nu_\b}{1-\kappa_\b}.
\label{eq:geo decay lagrangian}
\end{align}
From combining (\ref{eq:key 1},\ref{eq:geo decay lagrangian}), it follows that
\begin{align}
\|u_k-\wh{u}\|_2^2 \le \frac{2\kappa_\b^t \Delta_0}{\mu_\b} + \l( \frac{ \g\mu_\b^2 \nu_\b+ 8\la_A'}{4(\mu_\b-2\s_0\lambda'_A)(1-\kappa_\b)} +1 \r) \frac{2\nu_\b}{\mu_\b}.
\label{eq:geo decay dist}
\end{align}
In light of \eqref{eq:geo decay dist}, we must take
\begin{align}
\tau_\b \ge \l( \frac{ \g\mu_\b^2 \nu_\b+ 8\la_A'}{4(\mu_\b-2\s\lambda'_A)(1-\kappa_\b)} +1 \r) \frac{2\nu_\b}{\mu_\b},
\label{eq:other cnd on tau}
\end{align}
which also simplifies \eqref{eq:geo decay dist} as
\begin{align}
\|u_k-\wh{u}\|_2^2 \le \frac{2\kappa_\b^t \Delta_0}{\mu_\b} + \tau_\b.
\end{align}
Moreover, by combining (\ref{eq:defn of aug},\ref{eq:geo decay lagrangian}), we can bound the feasibility gap as
\begin{align}
\|A(u_{k})\|_2^2 & = \|A(u_{k})\|_2^2- \|A(\wh{u})\|_2^2
\qquad \l( A(\wh{u})=0 \r)
\nonumber\\
& \le \frac{\Delta_k}{\beta}
\qquad \text{(see (\ref{eq:defn of aug},\ref{eq:defn of Deltak}))}
\nonumber\\
& \le
\frac{\kappa_\b^t\Delta_0}{\b} +
\frac{ \g\mu_\b^2 \nu_\b+ 8\la_A'}{4\b(\mu_\b-2\s_0\lambda'_A)} \frac{ \nu_\b}{1-\kappa_\b}
\qquad \text{(see \eqref{eq:geo decay lagrangian})} \nonumber\\
& \le
\frac{\kappa_\b^t\Delta_0}{\b} +
\l( \frac{ \g\mu_\b^2 \nu_\b+ 8\la_A'}{4(\mu_\b-2\s_0\lambda'_A)(1-\kappa_\b)} +1 \r)\frac{\nu_\b}{\beta} \nonumber\\
& \le
\frac{\kappa_\b^t\Delta_0}{\b} +
\frac{\mu_\b \tau_\b}{2\beta}.
\qquad \text{(see \eqref{eq:other cnd on tau})}
\end{align}
\appendix
\section{Proof of Lemma \ref{lem:smoothness}}
Note that
\begin{align}
\L_\b(u,y) = h(u)+ \sum_{i=1}^d y_i A_i(u) + \frac{\beta}{2}\sum_{i=1}^d |A_i(u)|^2,
\qquad \text{(see \eqref{eq:defn of aug})}
\end{align}
and, consequently,
\begin{align}
\nabla_u \L_\b(u,y) = \nabla_u h(u) + \sum_{i=1}^d y_i \nabla_u A_i(u) + \beta \sum_{i=1}^d A_i(u)\cdot \nabla_u A_i(u) ,
\end{align}
\begin{align}
\nabla_{uu} \L_{\b}(u,y) = \nabla_{uu} h(u) + \sum_{i=1}^d y_i \nabla_{uu} A_i(u) + \beta \sum_{i=1}^d A_i(u) \cdot \nabla_{uu}A_i(u)
+ \beta \sum_{i=1}^d \nabla_u A_i(u) \nabla_u A_i(u)^\top.
\end{align}
It follows that
\begin{align}
\la_\b & = \|\nabla_{uu} \L_\b(u,y)\| \nonumber\\
& \le \|\nabla_{uu}h(u)\| + \sum_{i=1}^d (|y_i|+\b|A_i(u)|) \cdot \|\nabla_{uu}A_i(u)\|
+ \b \sum_{i=1}^d \|\nabla_u A_i(u)\|^2_2 \nonumber\\
& \le \la_h + \sqrt{d} (\|y\|_2+\beta \|A(u)\|_2) \cdot \max_i \|\nabla_{uu}A_i(u)\| + \b \|D_u A(u)\|^2_F\nonumber\\
& \le \la_h + \sqrt{d} (\|y\|_2+\beta \|A(u)\|_2) \la_A + \b \|D_u A(u)\|^2_F,
\end{align}
which completes the proof of Lemma \ref{lem:smoothness}.
\section{Proof of Lemma \ref{lem:strong cvx} \label{sec:proof of strong cvx}}
We first control the growth of the dual sequence $\{y_k\}_k$. Note that
\begin{align}
\|y_k\|_2 & = \| y_0 + \sum_{i=1}^k \s_i A(u_i)\|_2
\qquad \text{(see \eqref{eq:updates})} \nonumber\\
& \le \|y_0\|_2+ \sum_{i=1}^k \s_i \|A(u_i)\|_2
\qquad \text{(triangle inequality)} \nonumber\\
& \le \|y_0\|_2+ \sum_{i=1}^k \frac{\s_0}{k\log (k+1)}
\qquad \text{(see \eqref{eq:step bnds})} \nonumber\\
& \le \|y_0\|_2+ c \s_0,
\label{eq:dual seq}
\end{align}
where
\begin{align}
c \ge \sum_{i=1}^\infty \frac{1}{k\log (k+1)}.
\end{align}
Having controlled the growth of the dual sequence above, we write that
\begin{align}
& \L_\b(u_k,y_k) - \L_\b(\wh{u},\wh{y}) \nonumber\\
&
= h(u_k) - h(\wh{u}) + \langle A(u_k),y_k\rangle + \frac{\b}{2}\|A(u_k)\|_2^2
\qquad \l( \text{\eqref{eq:defn of aug} and } A(\wh{u})=0 \r) \nonumber\\
& \ge h(u_k) - h(\wh{u}) - \langle u_k - \wh{u}, \nabla_u h(\wh{u}) \rangle + \langle u_k - \wh{u}, \nabla_u h(\wh{u}) \rangle + \langle A(u_k),y_k\rangle + \frac{\b}{2}\|A(u_k)\|_2^2 \nonumber\\
& \ge \frac{\mu_h}{2}\|u_k-\wh{u}\|_2^2 - \nu_h + \langle u_k - \wh{u}, \nabla_u h(\wh{u}) \rangle + \langle A(u_k),y_k\rangle + \frac{\b}{2}\|A(u_k)\|_2^2
\qquad \text{(see \eqref{eq:h key 1})}
\nonumber\\
& \ge \frac{\mu_h}{2}\|u_k-\wh{u}\|_2^2 - \nu_h - \frac{\mu_h}{4} \|u_k-\wh{u}\|_2^2 - \frac{\|\nabla_u h(\wh{u})\|_2^2}{\mu_h} - \frac{\b}{2}\|A(u_k)\|_2^2 - \frac{\|y_k\|_2^2}{2\b} + \frac{\b}{2}\|A(u_k)\|_2^2 \nonumber\\
& = \frac{\mu_h}{4}\|u_k-\wh{u}\|_2^2 - \nu_h - \frac{\|\nabla_u h(\wh{u})\|_2^2}{\mu_h} - \frac{\|y_k\|_2^2}{2\b} \nonumber\\
& \ge \frac{\mu_h}{4}\|u_k-\wh{u}\|_2^2 - \nu_h - \frac{\|\nabla_u h(\wh{u})\|_2^2}{\mu_h} - \frac{\|y_0\|_2^2+c\s_0^2}{\b},
\qquad \text{(see \eqref{eq:dual seq})}
\end{align}
which proves \eqref{eq:key 1}. To prove \eqref{eq:key 2}, we write that
\begin{align}
& \L_\b(\wh{u},\wh{y}) - \L_\b(u_k,y_k) - \langle \wh{u}-u_k , \nabla_u \L_\b(u_k,y_k) \rangle \nonumber\\
& = \l( h(\wh{u}) - h(u_k) - \langle \wh{u}-u_k, \nabla h(u_k) \rangle \r)
+ \l( \langle A(\wh{u}), y_k \rangle - \langle A(u_k), y_k \rangle - \langle \wh{u}-u_k, DA(u_k)^\top y_k\rangle \r) \nonumber\\
& \qquad + \b\l( \|A(\wh{u})\|_2^2- \|A(u_k)\|_2^2 - \langle \wh{u}-u_k, DA(u_k)^\top A(u_k) \rangle \r)
\qquad \text{(see \eqref{eq:defn of aug})} \nonumber\\
& \ge \frac{\mu_h}{2}\|u_k - \wh{u}\|_2^2 - \nu_h
- \frac{\sqrt{m}\lambda_A}{2}\|u_k- \wh{u}\|_2^2 - \frac{\b\la_A'}{2}\|u_k-\wh{u}\|_2^2
\qquad \text{(see (\ref{eq:smoothness of lagrangian},\ref{eq:h key 2}))}\nonumber\\
& = \frac{1}{2}\l(\mu_h - \sqrt{m}\la_A - \b\la'_A \r)\|u_k-\wh{u}\|_2^2 - \nu_h.
\end{align}
This completes the proof of Lemma \ref{lem:strong cvx}.
\end{document}
c4science · Help