\section{Convergence Analysis}
\label{sec:convergence}

If we utilize the DR envelope as the merit function in Algorithm~\ref{algo1}, and use condition~\eqref{eq:DRECondition} to determine acceptance for an accelerated iterate, then it can be shown that Algorithm~\ref{algo1} converges to a stationary point to the optimization problem. In the following, we will discuss the conditions for such convergence.
Unless stated otherwise, we assume that all the functions are lower semicontinuous and proper.
In contrast to Section~\ref{sec:algorithm}, we will write $\in$ instead of $=$ for the evaluation of proximal mappings and minimization subproblems, to indicate that our results are still applicable when these operators are multi-valued.
We first introduce some definitions:

\begin{defn}
A point $\bf{s}^*$ is said to be a fixed point of the mapping $\mathcal{G}$ if $\bf{s}^*\in\mathcal{G}(\bf{s}^*)$.
\end{defn}

\begin{defn}
A point $\bf{u}^*$ is said to be a stationary point of~\eqref{eq:DRProblem} if
$$ 0\in \partial \varphi_1(\bf{u}^*)+\partial\varphi_2(\bf{u}^*).  $$
\end{defn}

\begin{defn}
A function $F$ is said to be level-bounded if the set $\{\bf x:F(\bf x)\leq \alpha\}$ is bounded for any $\alpha\in\mathbb{R}$. 
\end{defn}

Our first convergence result requires the following assumptions:
\begin{description}
\item[(B.1)] The constants $\nu_1,\nu_2$ in condition~\eqref{eq:DRECondition} satisfy $\nu_1>0,\nu_2\geq 0$.
\item[(B.2)] $\varphi_1+\varphi_2$ is level-bounded.
\item[(B.3)] The constant $\gamma = 1/\beta$ satisfies $\gamma<\min\{\frac{1}{2\max\{-\sigma,0\}},\frac{1}{L}\}$, where $L$ and $\sigma$ are defined in Assumption~(A.1).
\item[(B.4)] The function $\overline{g}(\mathbf{z}) := g(\mathbf{z}) + \frac{\beta}{2}\|\bf B \mathbf{z}+\bf c-\bf s\|^2$ is level-bounded and bounded from below for any given $\bf s$.
\end{description}
Our first convergence result is then given as follows:
\begin{thm}
\label{thm2-9}
Suppose Assumptions (A.1)--(A.3) and (B.1)--(B.3) hold. Let $\{(\bf{s}_k,\bf{u}_k,\bf{v}_k)\}$ be the sequence generated by Algorithm~\ref{algo1} using Eq.~\eqref{eq:DRECondition} as the acceptance condition. Then
\begin{itemize}
\item[(a)] $\{\dre(\bf{s}_k)\}$ is monotonically decreasing and $\|\bf{v}_k-\bf{u}_k\|\rightarrow 0$.
\item[(b)] The sequence $(\bf s_k,\bf u_k,\bf v_k)$ is bounded. If any subsequence $\{\bf s_{k_i}\}$ converges to a point $\bf{s}^*$,  then $\bf{s}^*$ is a fixed point of $\mathcal{G}$ and $\bf{u}^*=\prox{\gamma\varphi_1}(\bf{s}^*)$ is a stationary point of~\eqref{eq:DRProblem}. Moreover, such a convergent subsequence must exist.
\item[(c)] Suppose Assumption (B.4) is also satisfied. For any convergent subsequence $\{\bf s_{k_i}\}$ in (b),  let $\{\bf z_{k_i}\}$ be the corresponding subsequence generated by Algorithm~\ref{algo1}, i.e., 
\[\bf z_{k_i} \in \argmin_{\mathbf{z}} \Big( g(\bf z)+\frac{1}{2\gamma}\left\|\bf B\bf z+\bf c - (2 \mathbf{u}(\mathbf{s}_{k_i}) - \bf s_{k_i}) \right\|^2 \Big).\] Then $\{\bf z_{k_i}\}$ is bounded. Let $\bf{z}^*$ be a cluster point of $\{\bf z_{k_i}\}$, and define
\begin{equation*}
\bf{x}^*\in\argmin\limits_{\bf x}f(\bf x)+\frac{\beta}{2}\|\bf A\bf x-\bf{s}^*\|^2, \qquad  
\bf{y}^*=\bf{u}^*-\bf{s}^*. 
\end{equation*}
Then $(\bf{x}^*,\bf{y}^*,\bf{z}^*)$ is a stationary point of~\eqref{eq:SeparableADMMProblem}.
\end{itemize}
\end{thm}
A proof is given in Appendix~\ref{app-C}. 
\begin{remark}
Given a fixed point $\bf{s}^*$ of $\mathcal{G}$, we can also compute a stationary point~\eqref{eq:SeparableADMMProblem} without the assumptions used in Theorem~\ref{thm2-9}. The reader is referred to Appendix~\ref{app-E} for further discussion.
\end{remark}
 
Theorem~\ref{thm2-9} shows the subsequence convergence of $\{(\mathbf{s}_k, \mathbf{u}_k, \mathbf{v}_k)\}$ to a value corresponding to a stationary point. 
Next, we consider the global convergence of the whole sequence. 
We define $$\Dg(\bf s,\bf u,\bf v)=\varphi_1(\bf u)+\varphi_2(\bf v)+\frac{1}{\gamma}\langle \bf s-\bf u,\bf v-\bf u \rangle+\frac{1}{2\gamma}\|\bf v-\bf u\|^2.$$
Our global convergence results rely on the following assumptions:
\begin{description}
\item[(C.1)] The constants $\nu_1,\nu_2$ used in condition~\eqref{eq:DRECondition} are positive.
\item[(C.2)] Function $\Dg$ is sub-analytic.
\end{description}
The definition of a sub-analytic function can be found in~\cite{Xu2013}.
Then we can show the following:
\begin{thm}
\label{thm4-4}
Suppose assumptions (A.1)--(A.3), (B.1)--(B.3) and (C.1)--(C.2) hold. Let $\{(\bf{s}_k,\bf{u}_k,\bf{v}_k)\}$ be the sequence generated by Algorithm~\ref{algo1} using Eq.~\eqref{eq:DRECondition} as the acceptance condition. Then $\{(\bf{s}_k,\bf{u}_k,\bf{v}_k)\}$ converges to $(\bf{s}^*,\bf{u}^*,\bf{v}^*)$, where $\bf{s}^*$ is a fixed-point of $\mathcal{G}$, and $\bf{v}^*=\bf{u}^*=\prox{\gamma\varphi_1}(\bf{s}^*)$.
\end{thm}
A proof is given in Appendix~\ref{app-F}.
\begin{remark}
\label{remark4-5}
A sufficient condition for Assumption (C.2) is that $f$ and $g$ are both semi-algebraic functions. In this case, $\varphi_1$ and $\varphi_2$ will both be semi-algebraic~\cite{themelis2020douglas}, thus $\Dg$ is also semi-algebraic. Since a semi-algebraic function is also sub-analytic~\cite{Xu2013}, $\Dg$ will be a sub-analytic function. 
As noted in~\cite{zhang2019accelerating}, a large variety of functions used in computer graphics are semi-algebraic. Interested readers are referred to~\cite{zhang2019accelerating} and~\cite{li2015global} for further discussion.  
\end{remark}
\begin{remark}
\label{remark4-6}
If the functions $f$ and $g$ satisfy some further conditions, it can be shown that the convergence rate of $(\bf{s}_k,\bf{u}_k,\bf{v}_k)$ is r-linear. The discussion relies on the KL property~\cite{AttBolSva13} and is rather technical, so we leave it to Appendix~\ref{app-F}. 
\end{remark}
\begin{remark}
Assumption (A.1) requires the function  $f$ in~\eqref{eq:SeparableADMMProblem} to be globally Lipschitz differentiable. When $f$ is only locally Lipschitz differentiable, it is still possible to prove the convergence of Algorithm~\ref{algo1}. One such example is given in Appendix~\eqref{appx:PhysicalSimulation}.  
\end{remark}


\subsection{Assumptions on $f$ and $g$}
Assumptions (A.1), (A.2) and (B.2) impose conditions on the functions $\varphi_1$ and $\varphi_{2}$ in~\eqref{eq:DRProblem}. As there is no closed-form expression for $\varphi_1$ and $\varphi_2$ in general, these conditions can be difficult to verify. For practical purposes, we provide some conditions on the functions $f$ and $g$ that can ensure Assumptions (A.1), (A.2) and (B.2). These conditions are based on the results in \cite[Section 5.4]{themelis2020douglas}.
\begin{proposition}
\label{prop4-7}
	Suppose the problem~\eqref{eq:SeparableADMMProblem} and the ADMM sub-problems in~\eqref{eq:SeparableADMMX} and \eqref{eq:SeparableADMMZ} have a solution. 
	Then the following conditions are sufficient for Assumptions (A.1), (A.2) and (B.2):
	\begin{description}
		\item[(D.1)] $f$ and $g$ are proper and lower semicontinuous.
		\item[(D.2)] One of the functions $f$ and $g$ is level-bounded, and the other is bounded from below.
		\item[(D.3)] $\bf A$ is surjective.
		\item[(D.4)] $f$ satisfies one of the following conditions:
		\begin{enumerate}
			\item $f$ is Lipschitz differentiable, and $\argmin_{\bf x}\{f(\bf x)\mid\bf A\bf x=\bf s\}$ is single-valued and Lipschitz continuous;
			\item $f$ is Lipschitz differentiable and convex;
			\item $f$ is differentiable, and $\|\nabla f(\bf x)-\nabla f(\bf y)\|\leq L\|\bf A(\bf x-\bf y)\|^2$ for any $\mathbf{x},\mathbf{y}$ if $\nabla f(\bf x)$ and $\nabla f(\bf y)$ are in the range of $\bf A^T$.
		\end{enumerate}
		\item[(D.5)]The function $\mathcal{Z}(\mathbf{s}) := \argmin_{\mathbf{z}} \left\{g(\mathbf{z}) \mid \mathbf{B} \mathbf{z} + \mathbf{c} = \mathbf{s}\right\}$ is locally bounded on the set $\mathcal{S} = \{\mathbf{B}\mathbf{z} + \mathbf{c} \mid g(\mathbf{z}) < +\infty\}$, i.e., for any $\mathbf{s} \in \mathcal{S}$ there exists a neighborhood $O$ such that $\mathcal{Z}$ is bounded on $O$. 
	\end{description}
\end{proposition}
A proof is given in Appendix~\ref{app-G}.
{"config": "arxiv", "file": "2006.14539/convergence.tex"}