arxiv 1901.02746v4

# Primal–dual proximal splitting and generalized conjugation in non-smooth
non-convex optimization

Christian Clason Faculty of Mathematics, University Duisburg-Essen, 45117
Essen, Germany (, 0000-0002-9948-8426<EMAIL_ADDRESS>Stanislav
Mazurenko Loschmidt Laboratories, Masaryk University, Brno, Czechia;
_previously_ Department of Mathematical Sciences, University of Liverpool,
United Kingdom (, 0000-0003-3659-4819<EMAIL_ADDRESS>Tuomo Valkonen
ModeMat, Escuela Politécnica Nacional, Quito, Ecuador _and_ Department of
Mathematics and Statistics, University of Helsinki, Finland; _previously_
Department of Mathematical Sciences, University of Liverpool, United Kingdom
(, 0000-0001-6683-3572<EMAIL_ADDRESS>
(2020-03-19)

###### Abstract

We demonstrate that difficult non-convex non-smooth optimization problems,
such as Nash equilibrium problems and anisotropic as well as isotropic Potts
segmentation model, can be written in terms of generalized conjugates of
convex functionals. These, in turn, can be formulated as saddle-point problems
involving convex non-smooth functionals and a general smooth but non-bilinear
coupling term. We then show through detailed convergence analysis that a
conceptually straightforward extension of the primal–dual proximal splitting
method of Chambolle and Pock is applicable to the solution of such problems.
Under sufficient local strong convexity assumptions of the functionals – but
still with a non-bilinear coupling term – we even demonstrate local linear
convergence of the method. We illustrate these theoretical results numerically
on the aforementioned example problems.

##  1 Introduction

This work is concerned with the numerical solution of non-smooth non-convex
saddle-point problems of the form

(1) $\min\limits_{x\in X}\max\limits_{y\in Y}G(x)+K(x,y)-F^{*}(y),$

where $G:X\to\overline{\mathbb{R}}$ and $F^{*}:Y\to\overline{\mathbb{R}}$ are
(possibly non-smooth) proper, convex and lower semicontinuous functionals on
Hilbert spaces $X$ and $Y$, and $K:X\times Y\to\mathbb{R}$ is smooth but may
be non-convex-concave. Such problems arise in many areas of optimal control,
inverse problems, and imaging; we will treat two specific examples below. To
find a critical point for (1), we propose the _generalized primal–dual
proximal splitting_ (GPDPS) method:

######  Algorithm 1.1 (GPDPS).

Given a starting point $(x^{0},y^{0})$ and step lengths
$\tau_{i},\omega_{i},\sigma_{i}>0$, iterate:

$\displaystyle x^{i+1}$
$\displaystyle:=\mathrm{prox}_{\tau_{i}G}(x^{i}-\tau_{i}K_{x}(x^{i},y^{i})),$
$\displaystyle\widebar{x}^{i+1}$
$\displaystyle:=x^{i+1}+\omega_{i}(x^{i+1}-x^{i}),$ $\displaystyle y^{i+1}$
$\displaystyle:=\mathrm{prox}_{\sigma_{i+1}F^{*}}(y^{i}+\sigma_{i+1}K_{y}(\widebar{x}^{i+1},y^{i})),$

where $\mathrm{prox}_{\tau_{i}G}(v)=(I+\tau_{i}\partial G)^{-1}(v)$ is the
proximal mapping for $G$; and $K_{x},K_{y}$ are the partial Fréchet
derivatives of $K$ with respect to $x$ and $y$. A main result of this work is
that under suitable conditions on the step length parameters $\tau_{i}$,
$\sigma_{i}$, and $\omega_{i}$, this algorithm converges weakly to a critical
point of (1); see Theorem 6.1. Furthermore, if $\partial G$ and/or $\partial
F^{*}$ is strongly metrically subregular at the saddle point (in particular,
if $G$ and/or $F^{*}$ are strongly convex), we show optimal convergence rates
for the standard acceleration strategies; see Theorems 6.4 and 6.6.

In addition, we demonstrate in this work how through a suitable reformulation
this method can be applied to the following two non-trivial applications:

  1. (i)

_elliptic Nash equilibrium problems_ , where $K(x,y)$ is the so-called
_Nikaido–Isoda_ function encoding the Nash equilibrium [29, 25, 38]; see
Section 2.1 for details.

  2. (ii)

_(Huber-regularized) $\ell^{0}$-$TV$ denoising_ (also referred to as the
_Potts model_) [18, 33, 34], where $K(x,y)$ is used to express the non-convex
Potts functional as the _generalized $K$-conjugate_ of a convex indicator
function; see Section 2.2 for details.

In particular, the second example demonstrates how the proposed method can be
used to solve (some) non-convex non-smooth problems by reformulating in them
in terms of a convex but non-smooth functional and a smooth but non-convex
coupling term. (We stress, however, that we do not claim that this approach is
superior to state-of-the-art problem-specific approaches such as the ones
mentioned in the cited works for the specific problems; such an investigation
is left for the future.)

#### Related literature.

Our approach is obviously motivated by the well-known primal–dual proximal
splitting (PDPS) method of Chambolle and Pock [8] for convex optimization
problems of the form $\min_{x\in X}F(Ax)+G(x)$ for
$F:Y\to\overline{\mathbb{R}}$ proper, convex, and lower semicontinuous and
$A:X\to Y$ linear. The method is based on the equivalent reformulation as the
saddle-point problem

(2) $\min_{x\in X}\max_{y\in Y}G(x)+\langle Ax,y\rangle-F^{*}(y)$

where $F^{*}$ is the Fenchel conjugate of $F$. Several other alternative
techniques for such optimization problems have also been developed, e.g.,
using smoothing schemes [28] or a proximal alternating predictor corrector
[13]. This approach was extended to allow for nonlinear but Fréchet
differentiable $A$ in [35]. Later work [12, 10] applied this to non-convex
PDE-constrained optimization problems and derived accelerated variants.

In a broader context, generalized convex conjugation has been studied for many
decades with applications in economics, see, e.g., [26, 32, 15] and the
references therein. Algorithms for the solution of general saddle-point
problems $\min_{x}\max_{y}f(x,y)$ have been considered in several seminal
papers. In particular, a prox-type method was suggested in [27] for $C^{1,1}$
convex–concave functions yielding a $O(1/N)$ rate of convergence for an
ergodic version of the gap $\max_{y^{\prime}\in
Y}f(x,y^{\prime})-\min_{x^{\prime}\in X}f(x^{\prime},y)$. These results were
further extended to allow non-smooth functions in the Mirror Descent method
[22], demonstrating a $O(1/\sqrt{N})$ rate of convergence for the ergodic gap
although with a vanishing step size for large $N$. The authors also considered
an acceleration of the Mirror Proximal method for the case when the gradient
map of $f$ can be split into a Lipschitz-continuous part and a monotone
operator [23]. The latter was assumed “simple” in the sense that a solution to
a specific variational inequality could be found relatively efficiently. As a
result, the authors obtained an $O(1/N)$ rate of convergence with a
possibility for improvement to $O(1/N^{2})$ for a strongly concave $f$.
Finally, the reformulation of (1) with a bilinear $K$ as a monotone inclusion
problem was considered in [21]. Algorithms applicable to (1) with a genuinely
nonlinear $K$ have only started to appear in literature relatively recently.
An abstract convergence result was obtained for an inexact regularized
Gauss–Seidel method in [3]. In [20], the authors considered saddle-point
representable functions and arrived at a very similar structure to (1);
specifically, they reformulated this problem as a smooth linearly-constrained
saddle point problem by moving the non-smooth terms into the problem domain
and applied the Mirror Proximal algorithm mentioned earlier, with a smooth
cost function and the $O(1/N)$ convergence rate [27]. Following [21],
Kolossoski and Monteiro [24] developed a non-Euclidean hybrid proximal
extragradient for $G$ and $F^{*}$ Bregman distances, and $K$ general
convex–concave. The case of a general convex–concave $K$ in (1) (which
therefore becomes an overall convex–concave problem) has been recently studied
in [19]. Besides being restricted to convex–concave problems, their algorithm
differs from Algorithm 1.1 in applying the overrelaxation to
$K_{y}(x^{i+1},y^{i})$ instead of to $x^{i+1}$ in the third step. Finally,
problems for general sufficiently smooth $K(x,y)$ were considered in [5] in
conjunction with a variant of ADMM; however, no proofs of convergence were
given in the general case.

#### Organization.

To motivate our approach, we start with a more detailed description of the
above-mentioned example problems and their reformulation as a saddle-point
problem of the form (1) in the next Section 2. (This section can be skipped by
readers only interested in the convergence analysis for the general Algorithm
1.1.) The following Section 3 then collects basic notation and definitions as
well as the fundamental assumptions that will be used throughout the
following. We then study the convergence and convergence rates of Algorithm
1.1 in Sections 4, 5 and 6. More precisely, in Section 4 we derive a basic
convergence estimate using the “testing” framework introduced in [36, 37] for
the study of preconditioned proximal point methods. The results and
assumptions depend on the iterates staying in a local neighborhood of a
solution. In Section 5 we therefore derive conditions on the step length
parameters and initial iterate that ensure that the iterates do not escape
from a local neighborhood. Afterwards, we provide in Section 6 exact step
length rules for Algorithm 1.1 together with respective weak convergence or
convergence rate results: linear under sufficient strong convexity of $G$ and
$F^{*}$, and “accelerated” $O(1/N)$ or $O(1/N^{2})$ rates with somewhat lesser
assumptions. Finally, we illustrate the applicability and performance of the
proposed approach applied to our two example problems in Section 7. Appendices
A to C contain further technical results on the assumptions required for
convergence, in particular verifying them for the Huber-regularized
$\ell^{0}$-TV denoising example.

##  2 Applications

Before we begin our analysis of the convergence of Algorithm 1.1, we motivate
its generality by discussing two examples of practically relevant problems
that can be cast in the form (1) and which will be used to numerically
illustrate the behavior of the algorithm in Section 7. The idea in each case
is to write a _non-convex_ functional $F$ as the generalized $K$-conjugate of
a _convex_ functional $F^{*}$, i.e.,

$F(x)=\sup_{y\in Y}K(x,y)-F^{*}(y)$

for a suitable $K$ (depending on $F$).

###  2.1 Elliptic Nash equilibrium problems

Our first example is the reformulation of Nash equilibrium problems using the
Nikaido–Isoda function following [38]. Consider a non-cooperative game of
$n\in\mathbb{N}$ players, each of which has a strategy $x_{k}\in
X_{k}\subset\mathbb{R}$ and a payout function
$\phi_{k}:\mathbb{R}^{n}\to\mathbb{R}$. For convenience, we introduce the
vector $x\in\mathbb{R}^{n}$ of strategies and the notation

$(x_{-k}|z):=(x_{1},\dots,x_{k-1},z,x_{k+1},\dots x_{n})\qquad(1\leq k\leq n,\
z\in\mathbb{R})$

for the vector where player $k$ changes their strategy $x_{k}$ to $z$. We also
set $X:=X_{1}\times\dots\times X_{n}$. A vector $x^{*}\in X$ of strategies is
then a Nash equilibrium if

(3)
$\phi_{k}(x^{*})=\phi_{k}(x^{*}_{-k}|x^{*}_{k})=\min_{z\in\mathbb{R}}\phi_{k}(x^{*}_{-k}|z)\qquad(1\leq
k\leq n).$

We now introduce the Nikaido–Isoda function [29] (also called the Ky Fan
function [17])

$\Psi(x,y)=\sum_{k=1}^{n}\left(\phi_{k}(x_{-k}|x_{k})-\phi_{k}(x_{-k}|y_{k})\right)\qquad(x,y\in
X)$

as well as the optimum response function

(4) $V(x)=\max_{y\in X}\Psi(x,y)\qquad(x\in X).$

It follows from [38, Thm. 2.2] that $x^{*}\in X$ is a Nash equilibrium if and
only if it is a minimizer of $V$. Using the indicator function of the set
$X\subset\mathbb{R}^{n}$ defined by

$\delta_{X}(x)=\begin{cases}0&\text{if }x\in X,\\\ \infty&\text{if }x\notin
X,\end{cases}$

we see that the generally non-convex response function $V$ is the
$\Psi$-preconjugate of the convex functional $\delta_{X}$ and can characterize
a Nash equilibrium $x^{*}\in X$ as the solution to the saddle-point problem

$\min_{x\in\mathbb{R}^{n}}\max_{y\in\mathbb{R}^{n}}\delta_{X}(x)+\Psi(x,y)-\delta_{X}(y).$

We can therefore solve the Nash equilibrium problem (3) by applying Algorithm
1.1 to

$K(x,y)=\Psi(x,y),\qquad F^{*}=G=\delta_{X}.$

In Section 7.1, we illustrate this exemplarily for the two-player elliptic
Nash equilibrium problem from [6].

######  Remark 2.1.

If the set $X_{k}$ of feasible strategies for each player depends on the
strategies of the other players (i.e., $X_{k}=X_{k}(x_{-k})$), (3) becomes a
_generalized Nash equilibrium problem (GNEP)_ ; see the survey [16] and the
literature cited therein. If for all $k$

$X_{k}(x_{-k})=\\{x_{k}\in\mathbb{R}^{n}:(x_{-k}|x_{k})\in Z\\}\qquad(1\leq
k\leq n)$

for some closed and convex set $Z\subset\mathbb{R}^{n}$, the GNEP is called
_jointly convex_. In this case, minimization of (4) is no longer an equivalent
characterization but defines a _variational equilibria_ [31]; every
variational equilibrium is a generalized Nash equilibrium but not vice versa,
see, e.g., [16, Thm. 3.9]. Hence Algorithm 1.1 can also be applied to compute
(some if not all) solutions to jointly convex GNEPs.

###  2.2 Huber–Potts denoising

Our next example is concerned with (Huber-regularized) $\ell^{0}$-TV denoising
or segmentation, also referred to as _Potts model_. Let
$f\in\mathbb{R}^{N_{1}\times N_{2}}$, $N_{1},N_{2}\in\mathbb{N}$, be a given
noisy or to be segmented image. We then search for the denoised or segmented
image as the solution to

(5) $\min_{x\in\mathbb{R}^{N_{1}\times
N_{2}}}\frac{1}{2\alpha}\|x-f\|^{2}+\|D_{h}x\|_{p,0},$

for a regularization parameter $\alpha\geq 0$ (which we write in front of the
discrepancy term to simplify the computations), the discrete gradient
$D_{h}:\mathbb{R}^{N_{1}\times N_{2}}\to\mathbb{R}^{N_{1}\times N_{2}\times
2}$, and the vectorial $\ell^{0}$-seminorm

(6)
$\|z\|_{p,0}:=\sum_{i=1}^{N_{1}}\sum_{j=1}^{N_{2}}\left|\left(|z_{ij1}|_{0},|z_{ij2}|_{0}\right)\right|_{p},\qquad\text{where
}|t|_{0}=\begin{cases}0&\text{if }t=0,\\\ 1&\text{if }t\neq 0,\end{cases}$

and $|\cdot|_{p}$ for $p\in[1,\infty]$ is the usual $p$-norm on
$\mathbb{R}^{2}$; we will discuss the choice of $p$ in detail below. Clearly,
$\|\,\boldsymbol{\cdot}\,\|_{p,0}$ is a non-convex functional for any
$p\in[1,\infty]$. Let us briefly comment on the use of $\ell^{0}$-TV as a
regularizer in imaging. Intuitively, the functional in (6) applied to the
discrete gradient counts the number of jumps of the image value between
neighboring pixels; it can therefore be expected that minimizers are piecewise
constant, and that jumps are penalized even more strongly than by the (convex)
total variation model.

To motivate our approach, we first consider a simple scalar (lower
semicontinuous) step function, i.e., we consider for
$(0,\infty)\subset\mathbb{R}$ the corresponding _characteristic function_

(7) $\chi_{(0,\infty)}(t)=\begin{cases}0&\text{if }t\leq 0,\\\ 1&\text{if
}t>0.\end{cases}$

To write this non-convex function as the generalized preconjugate of a convex
function, let $\rho:\mathbb{R}\to\mathbb{R}$ satisfy $\rho(0)=0$, $\sup_{t\leq
0}\rho(t)=0$, and $\sup_{t>0}\rho(t)=1$. Then a simple case distinction shows
that

(8) $\chi_{(0,\infty)}(t)=\sup_{s\geq
0}~{}\rho(st)=\sup_{s\in\mathbb{R}}~{}\rho(st)-\delta_{[0,\infty)}(s).$

Setting $\kappa(s,t):=\rho(st)$, we thus obtain that $\chi_{(0,\infty)}$ is
the $\kappa$-preconjugate of the convex indicator function
$\delta_{[0,\infty)}$. One possible choice for $\rho$ is
$\rho=\chi_{(0,\infty)}$; however, we require $\rho$ to be smooth in order to
apply Algorithm 1.1. A better choice is therefore

(9) $\rho(t)=2t-t^{2},\qquad(t\in\mathbb{R}),$

see Fig. 2, which has the advantage that the supremum in (8) is always
attained at a finite $s\geq 0$. We will use this choice from now on.

Noting that $|t|_{0}=\chi_{\\{0\\}}(t)$, we can proceed similarly by case
distinction to write

$|t|_{0}=\sup_{s\in\mathbb{R}}~{}\rho(st)=\sup_{s\in\mathbb{R}}~{}\rho(st)-0,$

i.e., for $\kappa(s,t)=\rho(st)$ as above, $|\cdot|_{0}$ is the
$\kappa$-preconjugate of the zero function $f^{*}\equiv 0$. In practice, it
may be useful to add Huber regularization, i.e., replace $f^{*}$ by
$f_{\gamma}^{*}:=f^{*}+\frac{\gamma}{2}|\cdot|^{2}=\frac{\gamma}{2}|\cdot|^{2}$
for some $\gamma>0$. Using the fact that $f_{\gamma}^{*}$ and our choice (9)
are differentiable, an elementary calculus argument shows that the
corresponding preconjugate is

$|t|_{\gamma}:=\sup_{s\in\mathbb{R}}~{}\rho(st)-\frac{\gamma}{2}|s|^{2}=\frac{2t^{2}}{2t^{2}+\gamma},$

which is a still non-convex approximation of $|t|_{0}$, see Fig. 2.

$-1$$-0.5$$0$$0.5$$1$$1.5$$2$$2.5$$3$$-3$$-2.5$$-2$$-1.5$$-1$$-0.5$$0$$0.5$$1$
Figure 1: plot of $\rho$ from (9)

$-1$$-0.8$$-0.6$$-0.4$$-0.2$$0$$0.2$$0.4$$0.6$$0.8$$1$$-0.1$$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$1$$\gamma=10^{-1}$$\gamma=10^{-2}$$\gamma=10^{-3}$
Figure 2: plot of $|t|_{\gamma}$ for different values of $\gamma$

We now turn to the vectorial $\ell^{0}$ seminorm, where we distinguish between
$p\in[1,\infty]$.

#### The case $p=1$.

With this choice, (6) reduces to

$\|z\|_{1,0}=\sum_{i=1}^{N_{1}}\sum_{j=1}^{N_{2}}\sum_{k=1}^{2}|z_{ijk}|_{0},$

which is the most common choice for the Potts model found in the literature.
Here, the Potts functional $\|D_{h}x\|_{1,0}$ counts for each pixel $(i,j)$
the jumps across each edge of the pixel separately, i.e., the contribution of
each pixel is either $0$ (no jump), $1$ (jump in either horizontal or vertical
direction), or $2$ (jump in both directions). We thus refer (in a slight abuse
of terminology) to this case as the _anisotropic Potts model_.

Since this functional is completely separable, we can apply the above scalar
approach componentwise by taking

(10)
$\kappa_{1}(z,y)=\sum_{i=1}^{N_{1}}\sum_{j=1}^{N_{2}}\sum_{k=1}^{2}\rho(z_{ijk}y_{ijk})$

such that $F=\|\,\boldsymbol{\cdot}\,\|_{1,0}$ is the
$\kappa_{1}$-preconjugate of the zero function $F^{*}\equiv 0$.
Correspondingly, the Huber regularization of $F$ is given by

$F_{\gamma}(z)=\sum_{i=1}^{N_{1}}\sum_{j=1}^{N_{2}}\sum_{k=1}^{2}|z_{ijk}|_{\gamma}.$

#### The case $p=\infty$.

Now (6) reduces to

$\|z\|_{\infty,0}=\sum_{i=1}^{N_{1}}\sum_{j=1}^{N_{2}}\max\left\\{|z_{ij1}|_{0},|z_{ij2}|_{0}\right\\}.$

Here, each pixel contributes to the Potts functional only once, even if there
is a jump across both edges. Since a simple case distinction shows that
$\max\\{|a|_{0},|b|_{0}\\}=||(a,b)|_{p}|_{0}$ for any $a,b\in\mathbb{R}$ and
$p\in[1,\infty]$, this case is equivalent to

${|\kern-1.0pt\|}z{|\kern-1.0pt\|}_{0,p}:=\sum_{i=1}^{N_{1}}\sum_{j=1}^{N_{2}}\left||(z_{ij1},z_{ij2})|_{p}\right|_{0}$

for any $p\in[1,\infty]$, which leads to an alternate definition of the Potts
functional sometimes found in the literature. We refer to this case as the
_isotropic Potts model_.

This functional is only separable with respect to the pixel coordinates
$(i,j)$ but not with respect to $k$. We thus extend our preconjugation
approach to $\mathbb{R}^{2}$ by observing for $t\in\mathbb{R}^{2}$ that

$||t|_{2}|_{0}=\sup_{s\in\mathbb{R}}\rho(\langle
s,t\rangle)=\sup_{s\in\mathbb{R}}\rho(s_{1}t_{1}+s_{2}t_{2})$

since for $t=0$, $\rho(\langle s,t\rangle)=0$ for all $s\in\mathbb{R}^{2}$,
while for $t_{1}\neq 0$ or $t_{2}\neq 0$, the supremum will be attained at $1$
by the choice of $\rho$. Setting

(11)
$\kappa_{\infty}(z,y)=\sum_{i=1}^{N_{1}}\sum_{j=1}^{N_{2}}\rho\left(z_{ij1}y_{ij1}+z_{ij2}y_{ij2}\right)$

makes $F=\|\,\boldsymbol{\cdot}\,\|_{\infty,0}$ again the
$\kappa_{\infty}$-preconjugate of the zero function $F^{*}\equiv 0$. The
corresponding Huber regularization can be once more computed by elementary
calculus as

$F_{\gamma}(z)=\sum_{i=1}^{N_{1}}\sum_{j=1}^{N_{2}}\left||(z_{ij1},z_{ij2})|_{2}\right|_{\gamma}.$

#### The case $p\in(1,\infty)$.

In principle, one could proceed as for $p=\infty$ by constructing a function
$\rho_{p}:\mathbb{R}^{2}\times\mathbb{R}^{2}\to\mathbb{R}$ with

$\sup_{s\in\mathbb{R}^{2}}\rho_{p}(s,t)=\begin{cases}0&\text{if }t=0,\\\
1&\text{if }t\neq 0,t_{1}t_{2}=0,\\\ 2^{1/p}&\text{if }t\neq 0,t_{1}t_{2}\neq
0,\end{cases}$

and setting $\kappa_{p}(s,t)=\rho_{p}(s,t)$. However, since the corresponding
Potts functional only differs from the case $p=1$ by the relative contribution
of pixels with jumps in both directions and $2^{1/p}\to 1$ for $p\to\infty$,
we will only consider the extremal cases $p=1$ and $p=\infty$.

In all cases, we can apply Algorithm 1.1 to

$K(x,y)=\kappa_{p}(D_{h}x,y),\qquad G(x)=\frac{1}{2\alpha}\|x-f\|^{2},\qquad
F^{*}_{\gamma}(y)=\frac{\gamma}{2}\|y\|^{2}$

for $p\in[1,\infty]$ and $\gamma\geq 0$. We illustrate the application of
Algorithm 1.1 for $p\in\\{1,\infty\\}$ and $\gamma>0$ in Section 7.2.

######  Remark 2.2.

We can also apply this approach for $|t|^{q}$ with $q\in(0,1)$ using the same
$\rho$ as above, writing

$|t|^{q}=\sup_{s\in\mathbb{R}}\kappa(t,s)\quad\text{for}\quad\kappa(t,s):=|t|^{q}\rho(st),$

as $\rho(st)=0$ if $t=0$ and attains the maximal value $1$ otherwise. However,
$\kappa(t,s)$ is not $C^{2}$; we can achieve that by instead writing

$|t|^{q}=\sup_{s\in\mathbb{R}}\kappa(t,s)\quad\text{for}\quad\kappa(t,s):=|t|^{q}\rho(|st|^{2}).$

##  3 Notation and assumptions

We start the development of our proposed method by introducing the necessary
notation and overall assumptions. Throughout the rest of this paper, we write
$\mathcal{L}(X;Y)$ for the space of bounded linear operators between Hilbert
spaces $X$ and $Y$. In what follows, we let $x$ and $y$ denote elements of $X$
and $Y$, respectively, and denote by $u$ a pair $(x,y)\in X\times Y$. For
brevity, we will also use this notation for similar tuples, e.g.,
$u^{i}:=(x^{i},y^{i})$, without explicit introduction in each case.

For any Hilbert space, $I$ is the identity operator, $\langle
x,x^{\prime}\rangle$ is the inner product in the corresponding space, and
$\vmathbb{B}(x,r)$ is the closed unit ball of the radius $r$ at $x$. If
$H:X\rightrightarrows X$ is a set-valued map, we will frequently use the
concise notation

$\langle H(x),\widetilde{x}\rangle:=\\{\langle w,\widetilde{x}\rangle:w\in
H(x)\\}$

as well as, e.g.,

$0\leq\langle H(x),\widetilde{x}\rangle$

if the corresponding relation holds for _all_ $w\in H(x)$.

For self-adjoint $T,S\in\mathcal{L}(X;Y)$, the inequality $T\geq S$ means
$T-S$ is positive semidefinite. If $T\in\mathcal{L}(X;X)$ is self-adjoint, we
further set $\langle x,x^{\prime}\rangle_{T}:=\langle Tx,x^{\prime}\rangle$,
and $\|x\|_{T}:=\sqrt{\langle x,x\rangle_{T}}$ (which define an inner product
and a norm in $X$, respectively, if $T$ is in addition positive definite). In
this case, $T\geq S$ implies that $\|x\|_{T}\geq\|x\|_{S}$ for all $x\in X$.

We also recall that $K_{x}$ and $K_{y}$ denote the partial Fréchet derivatives
of a continuosly differentiable operator $K$ with respect to the given
variable.

Throughout this paper, we make the following fundamental assumptions on (1).

######  Assumption 3.0.

The functionals $G:X\to\overline{\mathbb{R}}$ and
$F^{*}:Y\to\overline{\mathbb{R}}$ are convex, proper, and lower
semicontinuous. Furthermore,

  1. (i)

there exist a constant $\gamma_{G}\in\mathbb{R}$ and a neighborhood
$\mathcal{X}_{G}$ of ${\widehat{x}}$ such that

(12) $\langle\partial
G(x)+K_{x}({\widehat{x}},{\widehat{y}}),x-{\widehat{x}}\rangle\geq\gamma_{G}\|x-{\widehat{x}}\|^{2}\qquad(x\in\mathcal{X}_{G});$

  2. (ii)

there exist a constant $\gamma_{F^{*}}\in\mathbb{R}$ and a neighborhood
$\mathcal{Y}_{F^{*}}$ of ${\widehat{y}}$ such that

(13) $\langle\partial
F^{*}(y)-K_{y}({\widehat{x}},{\widehat{y}}),y-{\widehat{y}}\rangle\geq\gamma_{F^{*}}\|y-{\widehat{y}}\|^{2}\qquad(y\in\mathcal{Y}_{F^{*}}).$

Let us comment on this assumption. First, since the subgradients $\partial G$
and $\partial F^{*}$ of convex, proper, and lower semicontinuous functionals
are maximally monotone operators [4, Theorem 20.25], Section 3 always holds
with $\gamma_{G}=\gamma_{F^{*}}=0$. This is already sufficient for showing
weak convergence of Algorithm 1.1; see Theorem 6.1. For strong convergence
with rates, however, we (as usual in nonlinear optimization) need a local
superlinear growth condition near the solution that requires taking
$\gamma_{G}$ and/or $\gamma_{F^{*}}$ strictly positive (unless we can
compensate by better properties of $K$ through Section 3 below); see Theorems
6.4 and 6.6. In this case, Section 3 (i), for example, coincides with _strong
metric subregularity_ of $\partial G$; see [1, 2]. This property holds (at
_any_ $\hat{x}$ and $\hat{w}\in\partial G(\hat{x})$) whenever $G$ is strongly
convex; however, it is a strictly weaker property since we only require it to
hold at a _specific_ $\hat{x}$ and
$\hat{w}=-K_{x}({\widehat{x}},{\widehat{y}})$ arising from the first-order
necessary optimality conditions (17) below. (For example, $\partial g$ for
$g(x)=|x|$ is strongly metrically subregular at $x=0$ for $w\in(-1,1)$ – but
not at $w\in\\{-1,1\\}$ – although $g$ is not strongly convex.)

######  Assumption 3.0.

The functional $K(x,y)\in C^{1}(X\times Y)$ and there exist
$\rho_{x},\rho_{y}>0$ such that for all

(14)
$u,u^{\prime}\in\mathcal{U}(\rho_{x},\rho_{y}):=(\vmathbb{B}({\widehat{x}},\rho_{x})\cap\mathcal{X}_{G})\times(\vmathbb{B}({\widehat{y}},\rho_{y})\cap\mathcal{Y}_{F^{*}}),$

the following properties hold:

  1. (i)

(second partial derivatives) The second partial derivatives $K_{xy}(u)$ and
$K_{yx}(u)$ exist and satisfy $K_{xy}(u)=[K_{yx}(u)]^{*}$.

  2. (ii)

(locally Lipschitz gradients) For some functions $L_{x}(y),L_{y}(x)\geq 0$ and
a constant $L_{yx}\geq 0$,

$\displaystyle\|K_{x}(x^{\prime},y)-K_{x}(x,y)\|$ $\displaystyle\leq
L_{x}(y)\|x^{\prime}-x\|,$ $\displaystyle\|K_{yx}(x^{\prime},y)-K_{yx}(x,y)\|$
$\displaystyle\leq L_{yx}\|x^{\prime}-x\|,$
$\displaystyle\|K_{y}(x,y^{\prime})-K_{y}(x,y)\|$ $\displaystyle\leq
L_{y}(x)\|y^{\prime}-y\|.$

  3. (iii)

(locally bounded gradient) There exists $R_{K}>0$ with
$\sup_{u\in\mathcal{U}(\rho_{x},\rho_{y})}\|K_{xy}(x,y)\|\leq R_{K}$.

  4. (iv)

(three-point condition) There exist $\theta_{x},\theta_{y}>0$,
$\lambda_{x},\lambda_{y}\geq 0$, $\xi_{x},\xi_{y}\in\mathbb{R}$ such that

(15a) $\displaystyle\begin{aligned} &\langle
K_{x}(x^{\prime},{\widehat{y}})-K_{x}({\widehat{x}},{\widehat{y}}),x-{\widehat{x}}\rangle+\xi_{x}\|x-{\widehat{x}}\|^{2}\\\
&\geq\theta_{x}\|K_{y}({\widehat{x}},y)-K_{y}(x,y)-K_{yx}(x,y)({\widehat{x}}-x)\|-\frac{\lambda_{x}}{2}\|x-x^{\prime}\|^{2},\end{aligned}$
(15b) $\displaystyle\begin{aligned} &\langle
K_{y}(x,y)-K_{y}(x,y^{\prime})+K_{y}({\widehat{x}},{\widehat{y}})-K_{y}({\widehat{x}},y),y-{\widehat{y}}\rangle+\xi_{y}\|y-{\widehat{y}}\|^{2}\\\
&\geq\theta_{y}\|K_{x}(x^{\prime},{\widehat{y}})-K_{x}(x^{\prime},y^{\prime})-K_{xy}(x^{\prime},y^{\prime})({\widehat{y}}-y^{\prime})\|-\frac{\lambda_{y}}{2}\|y-y^{\prime}\|^{2}.\end{aligned}$

We again elaborate on this assumption. Section 3 (i)–(iii) are standard in
nonlinear optimization of smooth functions. Apart from the estimates in
Section 3 (ii), we make use of the following inequality that is an immediate
consequence:

(16)
$\|K_{y}(x^{\prime},y)-K_{y}(x,y)-K_{yx}(x,y)(x^{\prime}-x)\|\leq\frac{L_{yx}}{2}\|x-x^{\prime}\|^{2}.$

The constants $\xi_{x}$ and $\xi_{y}$ in Section 3 (iv) can typically be taken
positive by exploiting the strong monotonicity factors $\gamma_{G}$ and
$\gamma_{F^{*}}$ of $\partial G$ and $\partial F^{*}$. Indeed, further on in
Theorem 4.1, we will require that
$\gamma_{G}-\widetilde{\gamma}_{G}\geq\xi_{x}$ and
$\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}}\geq\xi_{y}$, where
$\widetilde{\gamma}_{G}$ and $\widetilde{\gamma}_{F^{*}}$ will be acceleration
factors employed to update the step length parameters $\tau_{i}$,
$\omega_{i}$, and $\sigma_{i}$ in the algorithm.

In Appendix A we demonstrate that Section 3 (iv) is closely related to
standard second-order optimality conditions, i.e., a positive definite Hessian
at the solution ${\widehat{u}}$. In particular, if the primal problem for the
saddle-point functional is strongly convex and the dual problem is strongly
concave, the constants that ensure Section 3 (iv) can be found explicitly.
Nonetheless, Section 3 (iv) is more general than the simple strong convex-
concavity. Indeed, in Appendix C we verify Section 3 for $K$ arising from
combinations of a linear operator with a generalized conjugate representations
of the step function and the $\ell^{0}$ function from Section 2.2.

Since (LABEL:eq:k-nonlinear-ky) holds for any $\xi_{y},\lambda_{y}\geq 0$ when
$K(x,y)=\langle A(x),y\rangle$ for some $A\in C^{1}(X)$, the conditions (15)
reduce to the three-point condition for $A$ from [10] with the exponent $p=1$.
In the present work, such an exponent would correspond to exponents
$p_{x},p_{y}\in[1,2]$ over the norms with the factors $\theta_{y}$ and
$\theta_{y}$ that we consider in Appendix B (ivenumi). These can sometimes be
useful: The exponent $p=2$ was needed in [35, Appendix B] to show the three-
point condition for $A$ for a phase and amplitude reconstruction problem. For
the sake of readability, in the main part of the present work we focus on the
case $p_{x}=p_{y}=1$, i.e., Section 3 (iv), and discuss the changes needed for
$p_{x},p_{y}\in(1,2]$ in Appendix B.

##  4 An abstract convergence result

We want to find a critical point
${\widehat{u}}=({\widehat{x}},{\widehat{y}})\in X\times Y$ of the saddle point
functional $(x,y)\mapsto G(x)+K(x,y)-F^{*}(y)$, i.e., satisfying

(17) $0\in H({\widehat{u}})\quad\text{for}\quad H(u):=\begin{pmatrix}\partial
G(x)+K_{x}(x,y)\\\ \partial F^{*}(y)-K_{y}(x,y)\end{pmatrix}.$

Since $G$ and $F^{*}$ are proper, convex, and lower semicontinuous, and $K$ is
continuously differentiable, using the definition of the saddle-point, the
Fréchet derivative, and the convex subdifferential, an elementary limiting
argument as in, e.g., [9, Prop. 2.2] shows that the inclusion (17) is a first-
order necessary optimality condition for a saddle point. If $K(x,y)=\langle
Ax,y\rangle$ for $A\in\mathcal{L}(X;Y)$, (17) reduces to
$-A^{*}{\widehat{y}}\in\partial G({\widehat{x}})$ and
$A{\widehat{x}}\in\partial F^{*}({\widehat{y}})$, which coincides with the
well-known Fenchel–Rockafellar extremality conditions for (2); see [14, Remark
4.2].

To study Algorithm 1.1, we reformulate it in the preconditioned proximal point
and testing framework of [36]. Specifically, we write Algorithm 1.1 in
_implicit proximal point_ form as solving in each iteration for
$u^{i+1}=(x^{i+1},y^{i+1})\in X\times Y$ in

(IPP) $0\in W_{i+1}\widetilde{H}_{i+1}(u^{i+1})+M_{i+1}(u^{i+1}-u^{i}),$

where the linearization $\widetilde{H}_{i+1}$ of $H$, the linear
preconditioner $M_{i+1}$, and the step length operator $W_{i+1}$ are defined
as

(18) $\displaystyle\widetilde{H}_{i+1}(u)$
$\displaystyle:=\begin{pmatrix}\partial
G(x)+K_{x}(x^{i},y^{i})+K_{xy}(x^{i},y^{i})(y-y^{i})\\\ \partial
F^{*}(y)-K_{y}((1+\omega_{i})x-\omega_{i}x^{i},y^{i})-K_{yx}(x^{i},y^{i})(x-[(1+\omega_{i})x-\omega_{i}x^{i}])\end{pmatrix},$
(19) $\displaystyle M_{i+1}$
$\displaystyle:=\begin{pmatrix}I&-\tau_{i}K_{xy}(x^{i},y^{i})\\\
-\omega_{i}\sigma_{i+1}K_{yx}(x^{i},y^{i})&I\end{pmatrix},$ (20)
$\displaystyle W_{i+1}$ $\displaystyle:=\begin{pmatrix}\tau_{i}I&0\\\
0&\sigma_{i+1}I\end{pmatrix}.$

Inserting these definitions into (IPP) and rearranging, we can rewrite
inclusion (IPP) as

(21) $0\in\begin{pmatrix}\tau_{i}\partial
G(x^{i+1})+\tau_{i}K_{x}(x^{i},y^{i})+x^{i+1}-x^{i}\\\ \sigma_{i+1}\partial
F^{*}(y^{i+1})-\sigma_{i+1}K_{y}((1+\omega_{i})x^{i+1}-\omega_{i}x^{i},y^{i})+y^{i+1}-y^{i}\end{pmatrix}.$

Therefore, based on the definitions of the proximal point mapping
$\mathrm{prox}_{\tau G}(v)=(I+\tau\partial G)^{-1}(v)$ and of
$\widebar{x}^{i+1}=(1+\omega_{i})x^{i+1}-\omega_{i}x^{i}$, solving (IPP) for
$u^{i+1}$ is equivalent to performing one step of Algorithm 1.1. Since
proximal mappings of proper, convex and lower semicontinuous functionals are
well-defined, single-valued, and Lipschitz continuous [4, Proposition 12.15],
and $K$ is twice Fréchet differentiable on $X\times Y$, this also shows that
(IPP) always admits a unique solution $u^{i+1}$.

The next step is to “test” the inclusion (IPP) by application of
$\langle\,\boldsymbol{\cdot}\,,u^{i+1}-{\widehat{u}}\rangle_{Z_{i+1}}$ for the
testing operator

$Z_{i+1}:=\begin{pmatrix}\phi_{i}I&0\\\ 0&\psi_{i+1}I\end{pmatrix}.$

This testing operator and the respective primal and dual testing variables
$\phi_{i}$ and $\psi_{i+1}$ will be seen to encode convergence rates after
some rearrangements of the tested inclusions for $i=0,\ldots,N-1$.

We will base our convergence analysis on the following abstract estimate,
where $\|\,\boldsymbol{\cdot}\,\|_{Z_{N+1}M_{N+1}}^{2}$ forms a local metric
that measures the convergence of the iterates while $\Delta_{i+1}$ can
potentially be used to measure function value or gap converge. In particular,
we therefore want $\|u\|_{Z_{N+1}M_{N+1}}\to\infty$ as $N\to\infty$ with a
certain rate such that boundedness of
$\|u^{N}-{\widehat{u}}\|_{Z_{N+1}M_{N+1}}$ implies the convergence of
$u^{N}\to{\widehat{u}}$ at the reciprocal rate (see Theorems 6.4 and 6.6).

######  Theorem 4.1 ([36, Theorem 2.1]).

Suppose (IPP) is solvable, and denote the iterates by
$\\{u^{i}\\}_{i\in\mathbb{N}}$. If $Z_{i+1}M_{i+1}$ is self-adjoint and for
some ${\widehat{u}}\in U$ and
$\Delta_{i+1}=\Delta_{i+1}({\widehat{u}})\in\mathbb{R}$, for all $i\leq N-1$,

(22) $\displaystyle\begin{aligned} \langle
Z_{i+1}W_{i+1}\widetilde{H}_{i+1}(u^{i+1}),u^{i+1}-{\widehat{u}}\rangle+\Delta_{i+1}&\geq\frac{1}{2}\|u^{i+1}-{\widehat{u}}\|_{Z_{i+2}M_{i+2}-Z_{i+1}M_{i+1}}^{2}-\frac{1}{2}\|u^{i+1}-u^{i}\|_{Z_{i+1}M_{i+1}}^{2},\end{aligned}$
then (23)
$\displaystyle\frac{1}{2}\|u^{N}-{\widehat{u}}\|^{2}_{Z_{N+1}M_{N+1}}\leq\frac{1}{2}\|u^{0}-{\widehat{u}}\|^{2}_{Z_{1}M_{1}}+\sum_{i=0}^{N-1}\Delta_{i+1}.$

The next theorem specializes Theorem 4.1 to our specific setup, converting the
abstract condition (22) into several step length and testing parameter update
rules and bounds. Specifically, (24a) below couples the primal and dual step
lengths $\tau_{i}$ and $\sigma_{i}$ and the over-relaxation parameter
$\omega_{i}$ with the testing parameters. Condition (24b) determines
convergence rates by limiting how fast the testing parameters can grow. This
rate is limited through the available strong monotonicity or second-order
behavior ($\gamma_{G}-\xi_{x}$ and $\gamma_{F^{*}}-\xi_{y}$) through (24d) and
(24e) as well as additional step length bounds from (24c). We point out that
only the latter are specific to our non-convex setting; the remaining
conditions are present in the convex setting as well, see [36]. We will
further develop these rules and conditions in the next section to obtain
specific convergence results; an explicit example for a set of parameters
satisfying these rules and conditions will be provided for the $\ell^{0}$-TV
denoising in Sections 7.2 and C. Here and in the following, we use the
notation $\widebar{x}^{i+1}:=x^{i+1}+\omega_{i}(x^{i+1}-x^{i})$ from Algorithm
1.1 for brevity.

######  Theorem 4.2.

Suppose Sections 3 and 3 hold with the constants $\theta_{x},\theta_{y}>0$;
$\xi_{x},\xi_{y}\in\mathbb{R}$; $\lambda_{x},\lambda_{y}\geq 0$; $L_{yx}\geq
0$ and $R_{K}>0$. For all $i\in\mathbb{N}$, let
$\widebar{u}^{i+1}:=(\widebar{x}^{i+1},y^{i})$, and suppose
$u^{i},u^{i+1},{\widehat{u}},\widebar{u}^{i+1}\in\mathcal{U}(\rho_{x},\rho_{y})$
for some $\rho_{x},\rho_{y}\geq 0$. Assume for all $i\in\mathbb{N}$ that
$\overline{\omega}\geq\omega_{i}\geq\underline{\omega}>0$ and that for some
$0<\delta\leq\mu<1$; $\eta_{i}>0$; and
$\widetilde{\gamma}_{G},\widetilde{\gamma}_{F^{*}}\geq 0$,

(24a) $\displaystyle\omega_{i}$ $\displaystyle=\eta_{i}\eta_{i+1}^{-1},$
$\displaystyle\eta_{i}$ $\displaystyle=\psi_{i}\sigma_{i}=\phi_{i}\tau_{i},$
(24b) $\displaystyle\phi_{i+1}$
$\displaystyle=\phi_{i}(1+2\tau_{i}\widetilde{\gamma}_{G}),$
$\displaystyle\psi_{i+2}$
$\displaystyle=\psi_{i+1}(1+2\sigma_{i+1}\widetilde{\gamma}_{F^{*}}),$ (24c)
$\displaystyle 1$
$\displaystyle\geq\sigma_{i}\biggl{(}\frac{R_{K}^{2}\tau_{i}}{1-\mu}+\frac{\lambda_{y}}{\omega_{i}}\biggr{)},$
$\displaystyle\tau_{i}$
$\displaystyle\leq\frac{\delta}{\lambda_{x}+L_{yx}\left(\omega_{i}+2\right)\rho_{y}},$
(24d) $\displaystyle\gamma_{G}$
$\displaystyle\geq\widetilde{\gamma}_{G}+\xi_{x},$ $\displaystyle\theta_{y}$
$\displaystyle\geq\overline{\omega}\rho_{x},$ (24e)
$\displaystyle\gamma_{F^{*}}$
$\displaystyle\geq\widetilde{\gamma}_{F^{*}}+\xi_{y},$
$\displaystyle\theta_{x}$ $\displaystyle\geq\rho_{y}\underline{\omega}^{-1}.$

Then (22) is satisfied for any $\Delta_{i+1}\leq 0$.

######  Proof 4.3.

We split the proof into several steps.

#### Step 1 (estimation of $Z_{i+1}M_{i+1}$)

By (24a), $\phi_{i}\tau_{i}=\eta_{i}$ and
$\psi_{i+1}\sigma_{i+1}\omega_{i}=\eta_{i}$, so (19) yields

(25) $Z_{i+1}M_{i+1}=\begin{pmatrix}\phi_{i}I&-\eta_{i}K_{xy}(x^{i},y^{i})\\\
-\eta_{i}K_{yx}(x^{i},y^{i})&\psi_{i+1}I\end{pmatrix},$

which is clearly self-adjoint. Applying Cauchy’s and Young’s inequalities, we
further obtain for any $\delta>0$, $x\in X$, and $y\in Y$ that

$-2\langle
x,\eta_{i}K_{xy}(x^{i},y^{i})y\rangle\geq-(1-\delta)\phi_{i}\|x\|^{2}-(1-\delta)^{-1}\phi_{i}^{-1}\eta_{i}^{2}\|K_{xy}(x^{i},y^{i})y\|^{2},$

implying that

(26) $Z_{i+1}M_{i+1}\geq\hat{Q}_{i+1}:=\begin{pmatrix}\delta\phi_{i}I&0\\\
0&\psi_{i+1}I-\frac{\eta^{2}_{i}\phi_{i}^{-1}}{1-\delta}K_{yx}(x^{i},y^{i})K_{xy}(x^{i},y^{i})\end{pmatrix}.$

#### Step 2 (estimation of $Z_{i+1}M_{i+1}-Z_{i+2}M_{i+2}$)

Expanding $Z_{i+1}M_{i+1}-Z_{i+2}M_{i+2}$ according to (25) and then applying
(24b), we obtain

(27)
$\frac{1}{2}\|u^{i+1}-{\widehat{u}}\|_{Z_{i+1}M_{i+1}-Z_{i+2}M_{i+2}}^{2}=-\eta_{i}\widetilde{\gamma}_{G}\|x^{i+1}-{\widehat{x}}\|^{2}-\eta_{i+1}\widetilde{\gamma}_{F^{*}}\|y^{i+1}-{\widehat{y}}\|^{2}\\\
+\langle(\eta_{i+1}K_{xy}(x^{i+1},y^{i+1})-\eta_{i}K_{xy}(x^{i},y^{i}))(y^{i+1}-{\widehat{y}}),x^{i+1}-{\widehat{x}}\rangle.$

#### Step 3 (estimation of $\widetilde{H}_{i+1}(u^{i+1})$)

By (18) we have

$\widetilde{H}_{i+1}(u^{i+1})=\begin{pmatrix}\partial
G(x^{i+1})+K_{x}(x^{i},y^{i})+K_{xy}(x^{i},y^{i})(y^{i+1}-y^{i})\\\ \partial
F^{*}(y^{i+1})-K_{y}(\widebar{x}^{i+1},y^{i})-K_{yx}(x^{i},y^{i})(x^{i+1}-\widebar{x}^{i+1})\end{pmatrix}.$

Since $0\in H({\widehat{u}})$, we have
$-K_{x}({\widehat{x}},{\widehat{y}})\in\partial G({\widehat{x}})$ and
$K_{y}({\widehat{x}},{\widehat{y}})\in\partial F^{*}({\widehat{y}})$. Using
(21) multliplied by $Z_{i+1}$, Section 3, and (24a), we can thus estimate

(28)
$\displaystyle\langle\widetilde{H}_{i+1}(u^{i+1}),u^{i+1}-{\widehat{u}}\rangle_{W_{i+1}Z_{i+1}}$
$\displaystyle\geq\eta_{i}\gamma_{G}\|x^{i+1}-{\widehat{x}}\|^{2}+\eta_{i+1}\gamma_{F^{*}}\|y^{i+1}-{\widehat{y}}\|^{2}$
$\displaystyle+\eta_{i}\langle
K_{x}(x^{i},y^{i})-K_{x}({\widehat{x}},{\widehat{y}})+K_{xy}(x^{i},y^{i})(y^{i+1}-y^{i}),x^{i+1}-{\widehat{x}}\rangle$
$\displaystyle+\eta_{i+1}\langle
K_{y}({\widehat{x}},{\widehat{y}})-K_{y}(\widebar{x}^{i+1},y^{i})-K_{yx}(x^{i},y^{i})(x^{i+1}-\widebar{x}^{i+1}),y^{i+1}-{\widehat{y}}\rangle.$

Combining (28), (27), and (26), we arrive at

(29) $\displaystyle S_{i+1}$
$\displaystyle:=\frac{1}{2}\|u^{i+1}-u^{i}\|_{Z_{i+1}M_{i+1}}^{2}+\frac{1}{2}\|u^{i+1}-{\widehat{u}}\|_{Z_{i+1}M_{i+1}-Z_{i+2}M_{i+2}}^{2}+\langle\widetilde{H}_{i+1}(u^{i+1}),u^{i+1}-{\widehat{u}}\rangle_{W_{i+1}Z_{i+1}}$
$\displaystyle\geq\frac{1}{2}\|u^{i+1}-u^{i}\|_{\hat{Q}_{i+1}}^{2}+D$

for

$\displaystyle D$
$\displaystyle:=\eta_{i}(\gamma_{G}-\widetilde{\gamma}_{G})\|x^{i+1}-{\widehat{x}}\|^{2}+\eta_{i+1}(\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}})\|y^{i+1}-{\widehat{y}}\|^{2}$
$\displaystyle+\langle(\eta_{i+1}K_{xy}(x^{i+1},y^{i+1})-\eta_{i}K_{xy}(x^{i},y^{i}))(y^{i+1}-{\widehat{y}}),x^{i+1}-{\widehat{x}}\rangle$
$\displaystyle+\eta_{i}\langle
K_{x}(x^{i},y^{i})-K_{x}({\widehat{x}},{\widehat{y}})+K_{xy}(x^{i},y^{i})(y^{i+1}-y^{i}),x^{i+1}-{\widehat{x}}\rangle$
$\displaystyle+\eta_{i+1}\langle
K_{y}({\widehat{x}},{\widehat{y}})-K_{y}(\widebar{x}^{i+1},y^{i})-K_{yx}(x^{i},y^{i})(x^{i+1}-\widebar{x}^{i+1}),y^{i+1}-{\widehat{y}}\rangle.$

The claim of the theorem is established if we prove that $S_{i+1}\geq 0$.

#### Step 4 (estimation of $D$)

With

$\displaystyle\widetilde{D}_{x+y}$ $\displaystyle\begin{aligned}
&:=\langle(\eta_{i+1}K_{xy}(x^{i+1},y^{i+1})-\eta_{i}K_{xy}(x^{i},y^{i}))(y^{i+1}-{\widehat{y}}),x^{i+1}-{\widehat{x}}\rangle\\\
&+\eta_{i}\langle
K_{x}(x^{i},y^{i})-K_{x}({\widehat{x}},{\widehat{y}})+K_{xy}(x^{i},y^{i})(y^{i+1}-y^{i}),x^{i+1}-{\widehat{x}}\rangle\\\
&+\eta_{i+1}\langle
K_{y}({\widehat{x}},{\widehat{y}})-K_{y}(x^{i+1},y^{i}),y^{i+1}-{\widehat{y}}\rangle,\\\
\end{aligned}$ and $\displaystyle D_{\omega}$ $\displaystyle\begin{aligned}
&:=\langle
K_{y}(x^{i+1},y^{i})-K_{y}(\widebar{x}^{i+1},y^{i})+K_{yx}(x^{i+1},y^{i})(\widebar{x}^{i+1}-x^{i+1}),y^{i+1}-{\widehat{y}}\rangle\\\
&+\langle[K_{yx}(x^{i},y^{i})-K_{yx}(x^{i+1},y^{i})](\widebar{x}^{i+1}-x^{i+1}),y^{i+1}-{\widehat{y}}\rangle,\end{aligned}$

we can rewrite

$\displaystyle D$
$\displaystyle=\eta_{i}(\gamma_{G}-\widetilde{\gamma}_{G})\|x^{i+1}-{\widehat{x}}\|^{2}+\eta_{i+1}(\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}})\|y^{i+1}-{\widehat{y}}\|^{2}+\widetilde{D}_{x+y}+\eta_{i+1}D_{\omega}.$

We rearrange

$\displaystyle\widetilde{D}_{x+y}$ $\displaystyle=\eta_{i}\langle
K_{x}(x^{i},{\widehat{y}})-K_{x}({\widehat{x}},{\widehat{y}}),x^{i+1}-{\widehat{x}}\rangle$
$\displaystyle+\eta_{i+1}\langle
K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})+K_{yx}(x^{i+1},y^{i+1})(x^{i+1}-{\widehat{x}}),y^{i+1}-{\widehat{y}}\rangle$
$\displaystyle+\eta_{i+1}\langle
K_{y}({\widehat{x}},{\widehat{y}})-K_{y}({\widehat{x}},y^{i+1}),y^{i+1}-{\widehat{y}}\rangle$
$\displaystyle+\eta_{i+1}\langle
K_{y}(x^{i+1},y^{i+1})-K_{y}(x^{i+1},y^{i}),y^{i+1}-{\widehat{y}}\rangle$
$\displaystyle-\eta_{i}\langle
K_{x}(x^{i},{\widehat{y}})-K_{x}(x^{i},y^{i})-K_{xy}(x^{i},y^{i})({\widehat{y}}-y^{i}),x^{i+1}-{\widehat{x}}\rangle.$

Since $\eta_{i+1}=\eta_{i}\omega_{i}^{-1}$, setting

$\displaystyle D_{x}$
$\displaystyle:=\xi_{x}\|x^{i+1}-{\widehat{x}}\|^{2}+\langle
K_{x}(x^{i},{\widehat{y}})-K_{x}({\widehat{x}},{\widehat{y}}),x^{i+1}-{\widehat{x}}\rangle$
$\displaystyle+\langle
K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})({\widehat{x}}-x^{i+1}),y^{i+1}-{\widehat{y}}\rangle\omega_{i}^{-1},\quad\text{and}$
$\displaystyle D_{y}$
$\displaystyle:=\xi_{y}\|y^{i+1}-{\widehat{y}}\|^{2}+\langle
K_{y}({\widehat{x}},{\widehat{y}})-K_{y}({\widehat{x}},y^{i+1}),y^{i+1}-{\widehat{y}}\rangle$
$\displaystyle+\langle
K_{y}(x^{i+1},y^{i+1})-K_{y}(x^{i+1},y^{i}),y^{i+1}-{\widehat{y}}\rangle$
$\displaystyle-\omega_{i}\langle
K_{x}(x^{i},{\widehat{y}})-K_{x}(x^{i},y^{i})-K_{xy}(x^{i},y^{i})({\widehat{y}}-y^{i}),x^{i+1}-{\widehat{x}}\rangle,$

we can write

$D=\eta_{i}(\gamma_{G}-\widetilde{\gamma}_{G}-\xi_{y})\|x^{i+1}-{\widehat{x}}\|^{2}+\eta_{i+1}(\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}}+\xi_{x})\|y^{i+1}-{\widehat{y}}\|^{2}+\eta_{i}D_{x}+\eta_{i+1}D_{y}+\eta_{i+1}D_{\omega}.$

As for the estimate for $D_{\omega}$, using Section 3 (ii) and (16) we obtain

(30) $\displaystyle D_{\omega}$
$\displaystyle\geq-\frac{L_{yx}}{2}\|\widebar{x}^{i+1}-x^{i+1}\|^{2}\|y^{i+1}-{\widehat{y}}\|-L_{yx}\|x^{i+1}-x^{i}\|\|\widebar{x}^{i+1}-x^{i+1}\|\|y^{i+1}-{\widehat{y}}\|$
$\displaystyle\geq-\frac{L_{yx}\omega_{i}(\omega_{i}+2)\rho_{y}}{2}\|x^{i+1}-x^{i}\|^{2}$

using in the last inequality the expansion
$\widebar{x}^{i+1}:=x^{i+1}+\omega_{i}(x^{i+1}-x^{i})$ and the bound
$\|y^{i+1}-{\widehat{y}}\|\leq\rho_{y}$ that follows from the assumed
inclusion $u^{i+1}\in\mathcal{U}(\rho_{x},\rho_{y})$.

We now use Section 3 (iv) to further bound $D_{x}$ and $D_{y}$. From (15a), we
obtain

(31) $\displaystyle D_{x}$
$\displaystyle\geq\theta_{x}\|K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})({\widehat{x}}-x^{i+1})\|-\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2}$
$\displaystyle-\|y^{i+1}-{\widehat{y}}\|\|K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})({\widehat{x}}-x^{i+1})\|\omega_{i}^{-1}$
$\displaystyle\geq(\theta_{x}-\rho_{y}\underline{\omega}^{-1})\|K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})({\widehat{x}}-x^{i+1})\|-\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2}$
$\displaystyle\geq-\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2},$

using in the last two inequalities that
$u^{i+1}\in\mathcal{U}(\rho_{x},\rho_{y})$ for some $\rho_{x},\rho_{y}\geq 0$,
$\omega_{i}^{-1}\leq\underline{\omega}^{-1}$ and
$\theta_{x}\geq\rho_{y}\underline{\omega}^{-1}$ from (24e). Analogously, from
(LABEL:eq:k-nonlinear-ky) and Cauchy’s inequality,

(32) $\displaystyle D_{y}$
$\displaystyle\geq\theta_{y}\|K_{x}(x^{i},{\widehat{y}})-K_{x}(x^{i},y^{i})-K_{xy}(x^{i},y^{i})({\widehat{y}}-y^{i})\|-\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2}$
$\displaystyle-\omega_{i}\|x^{i+1}-{\widehat{x}}\|\|K_{x}(x^{i},{\widehat{y}})-K_{x}(x^{i},y^{i})-K_{xy}(x^{i},y^{i})({\widehat{y}}-y^{i})\|$
$\displaystyle\geq(\theta_{y}-\rho_{x}\overline{\omega})\|K_{x}(x^{i},{\widehat{y}})-K_{x}(x^{i},y^{i})-K_{xy}(x^{i},y^{i})({\widehat{y}}-y^{i})\|-\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2}$
$\displaystyle\geq-\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2},$

where in the last two inequalities we again used
$u^{i+1}\in\mathcal{U}(\rho_{x},\rho_{y})$, $\omega_{i}\leq\overline{\omega}$,
and $\theta_{y}\geq\overline{\omega}\rho_{x}$ from (24d). Therefore, combining
(30), (31), and (32), we obtain

(33) $\displaystyle D$
$\displaystyle=\eta_{i}D_{x}+\eta_{i+1}D_{y}+\eta_{i+1}D_{\omega}+\eta_{i}(\gamma_{G}-\widetilde{\gamma}_{G}-\xi_{x})\|x^{i+1}-{\widehat{x}}\|^{2}+\eta_{i+1}(\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}}-\xi_{y})\|y^{i+1}-{\widehat{y}}\|^{2}$
$\displaystyle\geq\eta_{i+1}(\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}}-\xi_{y})\|y^{i+1}-{\widehat{y}}\|^{2}-\eta_{i}\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2}$
$\displaystyle+\eta_{i}(\gamma_{G}-\widetilde{\gamma}_{G}-\xi_{x})\|x^{i+1}-{\widehat{x}}\|^{2}-\eta_{i+1}\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2}-\eta_{i}\frac{L_{yx}}{2}(\omega_{i}+2)\rho_{y}\|x^{i+1}-x^{i}\|^{2}$
$\displaystyle\geq-\eta_{i}\frac{\lambda_{x}+L_{yx}(\omega_{i}+2)\rho_{y}}{2}\|x^{i+1}-x^{i}\|^{2}-\eta_{i+1}\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2},$

where we have also used the first bounds of (24d) and (24e) in the final step.
Further using (24c) and $\eta_{i+1}=\eta_{i}\omega_{i}^{-1}$, we deduce that
$D\geq-\frac{1}{2}\|u^{i+1}-u^{i}\|_{\hat{Q}_{i+1}}^{2}$. Recalling (29), we
obtain $S_{i+1}\geq 0$, i.e., (22) holds with $\Delta_{i+1}\leq 0$ as claimed.

In the subsequent sections, we will also need the following corollary.

######  Corollary 4.4.

Suppose that Section 3 (iii) and the conditions (24) hold. Then

$(1-\mu)\psi_{i+1}\geq\eta_{i}^{2}\phi_{i}^{-1}R_{K}^{2}$

and

(34) $Z_{i+1}M_{i+1}\geq\begin{pmatrix}\delta\phi_{i}I&0\\\
0&(\mu-\delta)(1-\delta)^{-1}\psi_{i+1}I\end{pmatrix}.$

######  Proof 4.5.

Observe that due to (24),

$(1-\mu)\psi_{i+1}\geq(1-\mu)\psi_{i}=\frac{(1-\mu)\eta_{i}^{2}}{\sigma_{i}\tau_{i}\phi_{i}}\geq\eta_{i}^{2}\phi_{i}^{-1}R_{K}^{2}.$

This is our first claim. As for the second term, from Section 3 (iii) we have

$\frac{\eta^{2}_{i}\phi_{i}^{-1}}{1-\delta}K_{yx}(x^{i},y^{i})K_{xy}(x^{i},y^{i})\leq\frac{\eta^{2}_{i}\phi_{i}^{-1}}{1-\delta}R_{K}^{2}I\leq\frac{1-\mu}{1-\delta}\psi_{i+1}I.$

Inserting this bound into (26) in the proof of Theorem 4.2 establishes (34).

##  5 Local step length bounds

In the previous section, we derived step length conditions that we will
further develop in Section 6 to prove convergence and convergence rates.
However, we implicitly required that all the iterations
$\\{u^{i}\\}_{i\in\mathbb{N}}$ belong to $\mathcal{U}(\rho_{x},\rho_{y})$. In
this section, we derive additional step lengths restrictions to ensure that
this holds.

We start with a lemma that bounds the next iterate $u^{i+1}$ given bounds on
the current iterate $u^{i}$ and the step lengths for the current iteration.
Afterwards, we chain these estimates to only require bounds on the initial
iterates and the step lengths.

######  Lemma 5.1.

Fix $i\in\mathbb{N}$. Suppose Section 3, Section 3 (ii), and (iii) hold in
$\mathcal{U}(\rho_{x},\rho_{y})$, and that $u^{i+1}$ solves (IPP). For
simplicity, assume $\omega_{i}\leq 1$. Suppose
$r_{x,i},r_{y,i},\delta_{x},\delta_{y}>0$ and ${\widehat{u}}\in H^{-1}(0)$ are
such that
$\vmathbb{B}({\widehat{x}},r_{x,i}+\delta_{x})\times\vmathbb{B}({\widehat{y}},r_{y,i}+\delta_{y})\subseteq\mathcal{U}(\rho_{x},\rho_{y})$
and
$u^{i}\in\vmathbb{B}({\widehat{x}},r_{x,i})\times\vmathbb{B}({\widehat{y}},r_{y,i})$.
If

(35)
$\tau_{i}\leq\frac{\delta_{x}}{2R_{K}r_{y,i}+2L_{x}({\widehat{y}})r_{x,i}}\quad\text{and}\quad\sigma_{i+1}\leq\frac{\delta_{y}}{L_{y}({\widehat{x}})r_{y,i}+R_{K}(r_{x,i}+\delta_{x})},$

then
$u^{i+1}\in\vmathbb{B}({\widehat{x}},r_{x,i}+\delta_{x})\times\vmathbb{B}({\widehat{y}},r_{y,i}+\delta_{y})$
and $\|\widebar{x}^{i+1}-{\widehat{x}}\|\leq r_{x,i}+\delta_{x}$.

######  Proof 5.2.

We want to show that the step length conditions (35) are sufficient for

$\|x^{i+1}-{\widehat{x}}\|\leq
r_{x,i}+\delta_{x},\quad\|\widebar{x}^{i+1}-{\widehat{x}}\|\leq
r_{x,i}+\delta_{x},\quad\text{and}\quad\|y^{i+1}-{\widehat{y}}\|\leq
r_{y,i}+\delta_{y}.$

We do this by applying the testing argument on the primal and dual variables
separately. Multiplying (IPP) by $Z_{i+1}^{*}(u^{i+1}-{\widehat{u}})$ with
$\phi_{i}=1$ and $\psi_{i+1}=0$, we obtain

$0\in\tau_{i}\langle\partial
G(x^{i+1})+K_{x}(x^{i},y^{i}),x^{i+1}-{\widehat{x}}\rangle+\langle
x^{i+1}-x^{i},x^{i+1}-{\widehat{x}}\rangle.$

Using the three-point identity

(36) $\langle
x^{i+1}-x^{i},x^{i+1}-{\widehat{x}}\rangle=\frac{1}{2}\|x^{i+1}-x^{i}\|^{2}-\frac{1}{2}\|x^{i}-{\widehat{x}}\|^{2}+\frac{1}{2}\|x^{i+1}-{\widehat{x}}\|^{2},$

we obtain

$\|x^{i}-{\widehat{x}}\|^{2}\in 2\tau_{i}\langle\partial
G(x^{i+1})+K_{x}(x^{i},y^{i}),x^{i+1}-{\widehat{x}}\rangle+\|x^{i+1}-x^{i}\|^{2}+\|x^{i+1}-{\widehat{x}}\|^{2}.$

Using further $0\in\partial
G({\widehat{x}})+K_{x}({\widehat{x}},{\widehat{y}})$ and the monotonicity of
$\partial G$, we arrive at

$\|x^{i+1}-x^{i}\|^{2}+\|x^{i+1}-{\widehat{x}}\|^{2}+2\tau_{i}\langle
K_{x}(x^{i},y^{i})-K_{x}({\widehat{x}},{\widehat{y}}),x^{i+1}-{\widehat{x}}\rangle\leq\|x^{i}-{\widehat{x}}\|^{2}.$

With
$C_{x}:=\tau_{i}\|K_{x}(x^{i},y^{i})-K_{x}({\widehat{x}},{\widehat{y}})\|$,
this implies that

(37) $\|x^{i+1}-x^{i}\|^{2}+\|x^{i+1}-{\widehat{x}}\|^{2}\leq
2C_{x}\|x^{i+1}-{\widehat{x}}\|+\|x^{i}-{\widehat{x}}\|^{2}.$

After rearranging the terms and using
$\|x^{i+1}-{\widehat{x}}\|\leq\|x^{i+1}-x^{i}\|+\|x^{i}-{\widehat{x}}\|$, we
thus have

$(\|x^{i+1}-x^{i}\|-C_{x})^{2}+\|x^{i+1}-{\widehat{x}}\|^{2}\leq(\|x^{i}-{\widehat{x}}\|+C_{x})^{2},$

which leads to

(38) $\|x^{i+1}-{\widehat{x}}\|\leq\|x^{i}-{\widehat{x}}\|+C_{x}.$

To estimate the dual variable, we multiply (IPP) by
$Z_{i+1}^{*}(u^{i+1}-{\widehat{u}})$ with $\phi_{i}=0$ and $\psi_{i+1}=1$.
This gives

$0\in\sigma_{i+1}\langle\partial
F^{*}(y^{i+1})-K_{y}(\widebar{x}^{i+1},y^{i}),y^{i+1}-{\widehat{y}}\rangle+\langle
y^{i+1}-y^{i},y^{i+1}-{\widehat{y}}\rangle.$

Using $0\in\partial F^{*}({\widehat{y}})-K_{y}({\widehat{x}},{\widehat{y}})$
and following the steps leading to (38), we deduce

(39) $\|y^{i+1}-{\widehat{y}}\|\leq\|y^{i}-{\widehat{y}}\|+C_{y}$

with
$C_{y}:=\sigma_{i+1}\|K_{y}({\widehat{x}},{\widehat{y}})-K_{y}(\widebar{x}^{i+1},y^{i})\|$.

We now proceed to derive bounds on $C_{x}$ and $C_{y}$ with the goal of
bounding both (38) and (39) from above. Using Section 3 (ii), (iii), and the
mean value theorem applied to $K_{x}(x^{i},\cdot)$ and $K_{y}(\cdot,y^{i})$,

$\displaystyle C_{x}$
$\displaystyle\leq\tau_{i}(\|K_{x}(x^{i},y^{i})-K_{x}(x^{i},{\widehat{y}})\|+\|K_{x}(x^{i},{\widehat{y}})-K_{x}({\widehat{x}},{\widehat{y}})\|)$
$\displaystyle\leq\tau_{i}(R_{K}r_{y,i}+L_{x}({\widehat{y}})r_{x,i})=:R_{x},\quad\text{and}$
$\displaystyle C_{y}$
$\displaystyle\leq\sigma_{i+1}(\|K_{y}({\widehat{x}},{\widehat{y}})-K_{y}({\widehat{x}},y^{i})\|+\|K_{y}({\widehat{x}},y^{i})-K_{y}(\widebar{x}^{i+1},y^{i})\|$
$\displaystyle\leq\sigma_{i+1}(L_{y}({\widehat{x}})r_{y,i}+R_{K}(r_{x,i}+\delta_{x}))=:R_{y},$

the latter under the assumption that $\|\widebar{x}^{i+1}-{\widehat{x}}\|\leq
r_{x,i}+\delta_{x}$, which we now verify. First, by definition,

$\displaystyle\|\widebar{x}^{i+1}-{\widehat{x}}\|^{2}$
$\displaystyle=\|x^{i+1}-{\widehat{x}}+\omega_{i}(x^{i+1}-x^{i})\|^{2}$
$\displaystyle=\|x^{i+1}-{\widehat{x}}\|^{2}+\omega_{i}^{2}\|x^{i+1}-x^{i}\|^{2}+2\omega_{i}\langle
x^{i+1}-{\widehat{x}},x^{i+1}-x^{i}\rangle$
$\displaystyle=(1+\omega_{i})\|x^{i+1}-{\widehat{x}}\|^{2}+\omega_{i}(1+\omega_{i})\|x^{i+1}-x^{i}\|^{2}-\omega_{i}\|x^{i}-{\widehat{x}}\|^{2}$
$\displaystyle\leq(1+\omega_{i})(\|x^{i+1}-{\widehat{x}}\|^{2}+\|x^{i+1}-x^{i}\|^{2})-\omega_{i}\|x^{i}-{\widehat{x}}\|^{2}.$

Applying (37) and (38), we obtain

$\displaystyle\|\widebar{x}^{i+1}-{\widehat{x}}\|^{2}$
$\displaystyle\leq(1+\omega_{i})(2C_{x}\|x^{i+1}-{\widehat{x}}\|+\|x^{i}-{\widehat{x}}\|^{2})-\omega_{i}\|x^{i}-{\widehat{x}}\|^{2}$
$\displaystyle\leq
4C_{x}\|x^{i+1}-{\widehat{x}}\|+\|x^{i}-{\widehat{x}}\|^{2}\leq
4C_{x}(\|x^{i}-{\widehat{x}}\|+C_{x})+\|x^{i}-{\widehat{x}}\|^{2}\leq(2C_{x}+r_{x,i})^{2}.$

The bound (35) on $\tau_{i}$ implies that $C_{x}\leq R_{x}\leq\delta_{x}/2$
and hence that $\|\widebar{x}^{i+1}-{\widehat{x}}\|\leq r_{x,i}+\delta_{x}$.
From (38) we thus obtain $\|x^{i+1}-{\widehat{x}}\|\leq r_{x,i}+\delta_{x}$.
The bound (35) on $\sigma_{i}$ then implies that $C_{y}\leq
R_{y}\leq\delta_{y}$, which together with (39) completes the proof.

To chain the applications of Lemma 5.1 on each iteration $i\in\mathbb{N}$, we
introduce the following assumption, for which we recall the notations in
Section 3 as well as the definition of $\mathcal{U}(\rho_{x},\rho_{y})$ from
(14).

######  Assumption 5.2.

Suppose Section 3 holds near a solution ${\widehat{u}}\in H^{-1}(0)$. Given an
initial iterate $u^{0}\in X\times Y$, and initial step length parameters
$\tau_{0},\sigma_{1},\omega_{0}>0$ as well as $0<\delta\leq\mu<1$ (to satisfy
(24)), define the weighted distance

(40)
$r_{\max}:=\sqrt{2\delta^{-1}(\|x^{0}-{\widehat{x}}\|^{2}+\nu^{-1}\|y^{0}-{\widehat{y}}\|^{2})}\quad\text{with}\quad\nu:=\sigma_{1}\omega_{0}\tau_{0}^{-1}.$

We then assume that there exist $\delta_{x},\delta_{y}>0$ and $r_{y}\geq
r_{\max}\sqrt{\nu(1-\delta)\delta(\mu-\delta)^{-1}}$ such that

$\vmathbb{B}({\widehat{x}},r_{\max}+\delta_{x})\times\vmathbb{B}({\widehat{y}},r_{y}+\delta_{y})\subseteq\mathcal{U}(\rho_{x},\rho_{y})$

and that for all $i\in\mathbb{N}$ the step lengths $\tau_{i},\sigma_{i}>0$
satisfy

(41)
$\tau_{i}\leq\frac{\delta_{x}}{2R_{K}r_{y}+2L_{x}({\widehat{y}})r_{\max}}\quad\text{and}\quad\sigma_{i+1}\leq\frac{\delta_{y}}{L_{y}({\widehat{x}})r_{y}+R_{K}(r_{\max}+\delta_{x})}.$

######  Lemma 5.3.

For all $i\in\mathbb{N}$, suppose $u^{i+1}$ solves (IPP) and that all the
conditions of Theorem 4.2 are satisfied for some $\rho_{x},\rho_{y}>0$ and
$\widetilde{\gamma}_{G},\widetilde{\gamma}_{F^{*}}\geq 0$ except for the
requirement
$u^{i},u^{i+1},\widebar{u}^{i+1}\in\mathcal{U}(\rho_{x},\rho_{y})$. Then if
Section 5 holds,
$\\{u^{i}\\}_{i\in\mathbb{N}},\\{\widebar{u}^{i+1}\\}_{i\in\mathbb{N}}\subset\mathcal{U}(\rho_{x},\rho_{y})$.

######  Proof 5.4.

We define
$r_{x,i}:=\frac{1}{\sqrt{\delta\phi_{i}}}\|u^{0}-{\widehat{u}}\|_{Z_{1}M_{1}}$
and

$\mathcal{U}_{i}:=\bigl{\\{}(x,y)\in X\times
Y\,\bigm{|}\,\|x-{\widehat{x}}\|^{2}+{\textstyle\frac{\psi_{i+1}}{\phi_{i}}\frac{\mu-\delta}{(1-\delta)\delta}}\|y-{\widehat{y}}\|^{2}\leq
r_{x,i}^{2}\bigr{\\}}.$

Since the conditions (24) hold, we can apply Corollary 4.4 and the estimate
(34) on $Z_{i+1}M_{i+1}$ to deduce that

(42) $\\{u\in X\times
Y\mid\|u-{\widehat{u}}\|_{Z_{i+1}M_{i+1}}\leq\|u^{0}-{\widehat{u}}\|_{Z_{1}M_{1}}\\}\subset\mathcal{U}_{i}.$

From (24b), we also deduce that $\phi_{i+1}\geq\phi_{i}$ and hence that
$r_{x,i+1}\leq r_{x,i}$. Consequently, if $r_{x,0}\leq r_{\max}$, then

(43)
$\vmathbb{B}({\widehat{x}},r_{x,i}+\delta_{x})\times\vmathbb{B}({\widehat{y}},r_{y}+\delta_{y})\subseteq\vmathbb{B}({\widehat{x}},r_{\max}+\delta_{x})\times\vmathbb{B}({\widehat{y}},r_{y}+\delta_{y})\subseteq\mathcal{U}(\rho_{x},\rho_{y}),$

so it will suffice to show that
$u^{i}\in\vmathbb{B}({\widehat{x}},r_{x,i}+\delta_{x})\times\vmathbb{B}({\widehat{y}},r_{y}+\delta_{y})$
for each $i\in\mathbb{N}$ to prove the claim. We do this in two steps. In the
first step, we show that $r_{x,i}\leq r_{\max}$ and

(44)
$\mathcal{U}_{i}\subseteq\vmathbb{B}({\widehat{x}},r_{x,i})\times\vmathbb{B}({\widehat{y}},r_{y})\quad(i\in\mathbb{N}).$

In the second step, we show by induction that $u^{i}\in\mathcal{U}_{i}$ as
well as $\widebar{u}^{i+1}\in\mathcal{U}(\rho_{x},\rho_{y})$ for
$i\in\mathbb{N}$.

#### Step 1

We first prove (44). Since
$\mathcal{U}_{i}\subseteq\vmathbb{B}({\widehat{x}},r_{x,i})\times Y$, we only
have to show that $\mathcal{U}_{i}\subseteq
X\times\vmathbb{B}({\widehat{y}},r_{y})$. First, note that (24) and
$\widetilde{\gamma}_{G},\widetilde{\gamma}_{F^{*}}\geq 0$ imply
$\psi_{i+1}\geq\psi_{i}\geq\psi_{1}$ as well as
$\phi_{i+1}\geq\phi_{i}\geq\phi_{0}=\eta_{1}\omega_{0}\tau_{0}^{-1}=\nu\psi_{1}$
for $\nu$ defined in (40). We then obtain from the definition of $r_{x,i}$
substituting $Z_{1}M_{1}$ from (25) that

$r_{x,i}^{2}\delta\phi_{i}=\|u^{0}-{\widehat{u}}\|^{2}_{Z_{1}M_{1}}=\nu\psi_{1}\|x^{0}-{\widehat{x}}\|^{2}-2\eta_{0}\langle
x^{0}-{\widehat{x}},K_{xy}(x^{0},y^{0})(y^{0}-{\widehat{y}})\rangle+\psi_{1}\|y^{0}-{\widehat{y}}\|^{2}.$

Using Cauchy’s and Young’s inequalities, the fact that
$\phi_{i}\geq\nu\psi_{1}$, and the assumption that
$\|K_{xy}(x^{0},y^{0})\|\leq R_{K}$, we arrive at

$r_{x,i}^{2}\leq(2\nu\psi_{1}\|x^{0}-{\widehat{x}}\|^{2}+(\psi_{1}+\eta_{0}^{2}\phi_{0}^{-1}R_{K}^{2})\|y^{0}-{\widehat{y}}\|^{2})(\delta\nu\psi_{1})^{-1}.$

We obtain from Corollary 4.4 that
$\eta_{0}^{2}\phi_{0}^{-1}R_{K}^{2}\leq(1-\mu)\psi_{1}\leq\psi_{1}$ and hence
that $r_{x,i}^{2}\leq r_{\max}^{2}$. The assumption on $r_{y}$ then yields for
all $i\in\mathbb{N}$ that

(45) $r_{y}^{2}\geq
r_{\max}^{2}\frac{\phi_{0}}{\psi_{1}}\frac{(1-\delta)\delta}{\mu-\delta}\geq\frac{r_{x,0}^{2}\phi_{0}}{\psi_{i+1}}\frac{(1-\delta)\delta}{\mu-\delta}=\frac{r_{x,i}^{2}\phi_{i}}{\psi_{i+1}}\frac{(1-\delta)\delta}{\mu-\delta}.$

Thus (44) follows from the definition of $\mathcal{U}_{i}$.

#### Step 2

We next show by induction that $u^{i}\in\mathcal{U}_{i}$ and
$\widebar{u}^{i+1}\in\mathcal{U}(\rho_{x},\rho_{y})$ for all $i\in\mathbb{N}$.
Since (42) holds for $i=0$, we have that $u^{0}\in\mathcal{U}_{0}$. Moreover,
since in Step 1 we have $r_{x,0}\leq r_{\max}$, the bound (35) for $i=0$
follows from (41). This gives the induction basis.

Suppose now that $u^{N}\in\mathcal{U}_{N}$. By (44), we have that
$u^{N}\in\vmathbb{B}({\widehat{x}},r_{x,N})\times\vmathbb{B}({\widehat{y}},r_{y})$.
Since again the bound (35) for $i=N$ follows from (41) and the bound
$r_{x,N}\leq r_{\max}$ follows from Step 1, we can apply Lemma 5.1 to obtain

$u^{N+1}\in\vmathbb{B}({\widehat{x}},r_{x,N}+\delta_{x})\times\vmathbb{B}({\widehat{y}},r_{y}+\delta_{y})\quad\text{and}\quad\widebar{x}^{N+1}\in\vmathbb{B}({\widehat{x}},r_{x,N}+\delta_{x}).$

By (43), we have
$\vmathbb{B}({\widehat{x}},r_{x,N}+\delta_{x})\times\vmathbb{B}({\widehat{y}},r_{y}+\delta_{y})\subseteq\mathcal{U}(\rho_{x},\rho_{y})$
and thus $u^{N+1},\widebar{u}^{N+1}\in\mathcal{U}(\rho_{x},\rho_{y})$. Theorem
4.2 now implies that (23) is satisfied for $i\leq N$ with $\Delta_{N+1}\leq
0$, which together with (23) and (42) yields that
$u^{N+1}\in\mathcal{U}_{N+1}$. This completes the induction step and hence the
proof.

##  6 Convergence estimates

We are now ready to formulate the main convergence results of this paper based
on the estimates derived above. First, based on (24d) and (24e), strong
convexity may be required if $\xi_{x}$ and $\xi_{y}$ have to be positive for
Section 3 to be satisfied. Moreover, the neighborhood
$\mathcal{U}(\rho_{x},\rho_{y})$ has to be small enough, as determined by the
assumptions $\theta_{x}\geq\rho_{y}{\underline{\omega}}^{-1}$ and
$\theta_{y}\geq\overline{\omega}\rho_{x}$ in the next results. This affects
the admissible step lengths and how close we have to initialize $u^{0}$ via
Section 5. After the next three main convergence results, we show that Section
5 is satisfied if we initialize close enough to a root ${\widehat{u}}\in
H^{-1}(0)$. Hence, to apply the theorems in practice, we have to find
constants for which Sections 3 and 3 are satisfied, use these constants to
bound and compute the step lengths as described in the theorems, and
initialize close enough to ${\widehat{u}}$. In Appendix B we consider some
relaxation of Section 3 (iv), which in turn requires larger $\gamma_{G}$ and
$\gamma_{F^{*}}$ instead of $\theta_{x}\geq\rho_{y}\underline{\omega}^{-1}$
and $\theta_{y}\geq\overline{\omega}\rho_{x}$.

The following theorem provides conditions sufficient for weak convergence of
the sequence $\\{u^{i}\\}_{i\in\mathbb{N}}$ generated by Algorithm 1.1. Apart
from technical requirements of Theorem 4.2, we require additional weak-to-
strong continuity of the mapping $u\mapsto K_{yx}(u)x$. While its verification
depends on the particular choice of $K$, it is trivially satisfied in two
cases: (i) $X$ and $Y$ are finite-dimensional and $K_{yx}$ is continuous; or
(ii) the mapping $u\mapsto K_{yx}(u)x$ is linear and compact.

######  Theorem 6.1 (weak convergence: $\omega_{i}=1$).

Suppose Sections 3, 3 and 5 hold for some $R_{K}>0$; $L_{yx}\geq 0$;
$\lambda_{x},\lambda_{y},\theta_{x},\theta_{y}\geq 0$; and
$\xi_{x},\xi_{y}\in\mathbb{R}$ such that

(46a) $\displaystyle\xi_{x}$ $\displaystyle=\gamma_{G},$
$\displaystyle\theta_{y}$ $\displaystyle\geq 2\rho_{x},$ (46b)
$\displaystyle\xi_{y}$ $\displaystyle=\gamma_{F^{*}},$
$\displaystyle\theta_{x}$ $\displaystyle\geq 2\rho_{y}.$

For some $0<\delta<\mu<1$, choose

(47)
$\displaystyle\tau_{i}\equiv\tau<\frac{\delta}{\lambda_{x}+3L_{yx}\rho_{y}},\qquad\sigma_{i}\equiv\sigma\leq\biggl{(}\frac{R_{K}^{2}\tau}{1-\mu}+\lambda_{y}\biggr{)}^{-1},\quad\text{and}\quad\omega_{i}\equiv
1.$

Furthermore, suppose that

  1. (i)

$u^{i}\mathrel{\rightharpoonup}\widebar{u}$ implies that
$K_{yx}(u^{i})x\rightarrow K_{yx}(\widebar{u})x$ for all $x\in X$,

and either

  1. (iia)

the mapping $u\mapsto(K_{x}(u),K_{y}(u))$ is weak-to-strong continuous in
$\mathcal{U}(\rho_{x},\rho_{y})$; or

  2. (iib)

the mapping $u\mapsto(K_{x}(u),K_{y}(u))$ is weak-to-weak continuous, but
Section 3 (monotone $\partial G$ and $\partial F^{*}$) and Section 3 (iv)
(three-point condition on $K$) hold at _any_ weak limit
$\widebar{u}=(\widebar{x},\widebar{y})$ of $\\{u^{i}\\}_{i\in\mathbb{N}}$ for
the same choices of $\theta_{x}$ and $\theta_{y}$.

Then the sequence $\\{u^{i}\\}_{i\in\mathbb{N}}$ generated by Algorithm 1.1
converges weakly to some $\widebar{u}\in H^{-1}(0)$ (possibly different from
${\widehat{u}}$).

Since it is assumed that $\theta_{x}\geq 2\rho_{y}$, we can replace $\rho_{y}$
by $\theta_{x}/2$ in the bound on $\tau$ in (47) if the latter is more readily
available.

For constant $\tau$, $\sigma$, and $\omega=1$, we have to set
$\psi_{i}\equiv\psi$ and $\phi_{i}\equiv\phi$ to satisfy (24a). Consequently,
applying Corollary 4.4 to bound $Z_{i+1}M_{i+1}$ from below will not help to
prove Theorem 6.1. We instead will make use of the following enhanced version
of Opial’s lemma.

######  Lemma 6.2 ([10, Lemma A.2]).

Let $U$ be a Hilbert space, $\hat{U}\subset U$ (not necessarily closed or
convex), and $\\{u^{i}\\}_{i\in\mathbb{N}}\subset U$. Also let
$A_{i}\in\mathcal{L}(U;U)$ be self-adjoint and $A_{i}\geq\hat{\epsilon}^{2}I$
for some $\hat{\epsilon}\neq 0$ for all $i\in\mathbb{N}$. If the following
conditions hold, then $u^{i}\mathrel{\rightharpoonup}\widebar{u}$ in $U$ for
some $\widebar{u}\in\hat{U}$:

  1. (i)

The sequence $\\{\|u^{i}-\hat{u}\|_{A_{i}}\\}_{i\in\mathbb{N}}$ is
nonincreasing for _some_ $\hat{u}\in\hat{U}$.

  2. (ii)

All weak limit points of $\\{u^{i}\\}_{i\in\mathbb{N}}$ belong to $\hat{U}$.

  3. (iii)

There exists $C>0$ such that $\|A_{i}\|\leq C^{2}$ for all $i$, and for any
weakly convergent subsequence $\\{u_{i_{k}}\\}_{k\in\mathbb{N}}$ there exists
$A_{\infty}\in\mathcal{L}(U;U)$ such that $A_{i_{k}}u\to A_{\infty}u$ strongly
in $U$ for all $u\in U$.

######  Proof 6.3 (Proof of Theorem 6.1).

We first verify (24) so that we can apply Theorem 4.2 and Lemma 5.3. We set
$\psi_{N}\equiv 1$, $\phi_{N}\equiv\sigma\tau^{-1}$,
$\widetilde{\gamma}_{G}=\widetilde{\gamma}_{F^{*}}=0$ to satisfy (24a), (24b),
(24d) and (24e) for $\omega=\underline{\omega}=\overline{\omega}=1$ and
$\xi_{x}$, $\xi_{y}$, $\theta_{x}$, $\theta_{y}$ satisfying (46). With the
choice $\omega=1$, the bounds (47) thus ensure (24c).

Hence (24) holds, which together with Section 5 and $\psi_{1}=1$ enables us to
use Lemma 5.3 to obtain
$\\{u^{i}\\}_{i\in\mathbb{N}}\in\mathcal{U}(\rho_{x},\rho_{y})$ and
$\\{\widebar{x}^{i+1}\\}_{i\in\mathbb{N}}\in\vmathbb{B}({\widehat{x}},\rho_{x})$.
Therefore there exists at least one weak limit point of
$\\{u^{i}\\}_{i\in\mathbb{N}}$. Moreover, (25) yields self-adjointness of
$Z_{i+1}M_{i+1}$ and since the bounds (47) are strict, Theorem 4.2 holds with
$\Delta_{i+1}\leq-\hat{\delta}\sum_{i=0}^{N}\|u^{i+1}-u^{i}\|^{2}$ for some
$\hat{\delta}>0$.

We now verify the conditions of Lemma 6.2 with $\hat{U}=H^{-1}(0)$ and
$A_{i}=Z_{i+1}M_{i+1}$. Estimate (23) is valid for any starting iterate; thus
setting $N=1$ and taking $u^{i}$ instead of $u^{0}$, we obtain
$\|u^{i+1}-{\widehat{u}}\|^{2}_{Z_{i+2}M_{i+2}}\leq\|u^{i}-{\widehat{u}}\|^{2}_{Z_{i+1}M_{i+1}}+\Delta_{i+1}$
for any $\Delta_{i+1}\leq 0$ due to Theorem 4.2. This verifies (i). Moreover,
(iii) follows from the assumed constant step lengths, Section 3 (iii), and the
assumption that $K_{yx}(u^{i})x\rightarrow K_{yx}(\widebar{u})x$ for all $x\in
X$ if $u^{i}\mathrel{\rightharpoonup}\widebar{u}$.

Hence we only need to verify (ii), i.e., if a subsequence of
$\\{u^{i}\\}_{i\in\mathbb{N}}$ converges weakly to some $\widebar{u}$, then
$\widebar{u}\in H^{-1}(0)$. We note that $W_{i+1}\equiv W$, and (IPP) implies
that $v_{i+1}\in WA(u^{i+1})$ for

(48) $\displaystyle A(u^{i+1})$ $\displaystyle:=\begin{pmatrix}\partial
G(x^{i+1})-\gamma_{G}(x^{i+1}-\widebar{x})\\\ \partial
F^{*}(y^{i+1})-\gamma_{F^{*}}(y^{i+1}-\widebar{y})\end{pmatrix}\quad\text{and}$
(51) $\displaystyle v_{i+1}$
$\displaystyle:=\begin{multlined}W\begin{pmatrix}-K_{x}(x^{i+1},y^{i+1})-\gamma_{G}(x^{i+1}-\widebar{x})\\\
K_{y}(x^{i+1},y^{i+1})-\gamma_{F^{*}}(y^{i+1}-\widebar{y})\end{pmatrix}-M_{i+1}(u^{i+1}-u^{i})\\\
-W\begin{pmatrix}K_{x}(x^{i},y^{i})-K_{x}(x^{i+1},y^{i+1})+K_{xy}(x^{i},y^{i})(y^{i+1}-y^{i})\\\
K_{y}(x^{i+1},y^{i+1})-K_{y}(\widebar{x}^{i+1},y^{i})-K_{yx}(x^{i},y^{i})(x^{i+1}-\widebar{x}^{i+1})\end{pmatrix}.\end{multlined}W\begin{pmatrix}-K_{x}(x^{i+1},y^{i+1})-\gamma_{G}(x^{i+1}-\widebar{x})\\\
K_{y}(x^{i+1},y^{i+1})-\gamma_{F^{*}}(y^{i+1}-\widebar{y})\end{pmatrix}-M_{i+1}(u^{i+1}-u^{i})\\\
-W\begin{pmatrix}K_{x}(x^{i},y^{i})-K_{x}(x^{i+1},y^{i+1})+K_{xy}(x^{i},y^{i})(y^{i+1}-y^{i})\\\
K_{y}(x^{i+1},y^{i+1})-K_{y}(\widebar{x}^{i+1},y^{i})-K_{yx}(x^{i},y^{i})(x^{i+1}-\widebar{x}^{i+1})\end{pmatrix}.$

Therefore it suffices to show that if
$u^{i_{k}}\mathrel{\rightharpoonup}\widebar{u}=(\widebar{x},\widebar{y})$ for
a subsequence, then

$v_{i_{k}}\mathrel{\rightharpoonup}\widebar{v}:=W\begin{pmatrix}-K_{x}(\widebar{x},\widebar{y})\\\
K_{y}(\widebar{x},\widebar{y})\end{pmatrix}\qquad\text{and}\qquad\widebar{v}\in
WA(\widebar{u}),$

which by construction is equivalent to $\widebar{u}\in H^{-1}(0)$. Note that
$A$ is maximally monotone since it only involves subgradient mappings of
proper convex lower semicontinuous functions due to Section 3. Moreover,
further use of (23) shows that
$\sum_{i=0}^{\infty}\frac{\hat{\delta}}{2}\|u^{i+1}-u^{i}\|^{2}<\infty$ and
hence that $\|u^{i+1}-u^{i}\|\to 0$. The last two terms in (51) thus converge
strongly to zero. We therefore only have to consider the first term, for which
we make a case distinction.

  1. (a)

If assumption (iia) holds, we obtain that $v_{i_{k}}\to\widebar{v}$, and the
required inclusion $\widebar{v}\in A(\widebar{u})$ follows from the fact that
the graph of the maximally monotone operator $A$ is sequentially
weakly–strongly closed; see [4, Proposition 16.36].

  2. (b)

If assumption (iib) holds, then only
$v_{i_{k}}\mathrel{\rightharpoonup}\widebar{v}$. In this case, we can apply
the Brezis–Crandall–Pazy Lemma [4, Corollary 20.59 (iii)] to obtain the
required inclusion under the additional condition that
$\limsup_{k\to\infty}~{}\langle
u^{i_{k}}-\widebar{u},v_{i_{k}}-\widebar{v}\rangle\leq 0$. In our case,
recalling that the last two terms of (51) converge strongly to zero, we have
that

$\limsup_{k\to\infty}~{}\langle
u^{i_{k}}-\widebar{u},v_{i_{k}}-\widebar{v}\rangle\leq\limsup_{i\rightarrow\infty}~{}\langle
u_{i}-\widebar{u},v_{i}-\widebar{v}\rangle=\limsup_{i\rightarrow\infty}~{}q_{i}$

for

$q_{i}:=\langle
K_{x}(\widebar{x},\widebar{y})-K_{x}(x^{i+1},y^{i+1}),x^{i+1}-\widebar{x}\rangle+\langle
K_{y}(x^{i+1},y^{i+1})-K_{y}(\widebar{x},\widebar{y}),y^{i+1}-\widebar{y}\rangle\\\
-\gamma_{F^{*}}\|y^{i+1}-\widebar{y}\|^{2}-\gamma_{G}\|x^{i+1}-\widebar{x}\|^{2}.$

Defining

$\displaystyle d_{i}^{x}$ $\displaystyle:=\langle
K_{y}(x^{i+1},y^{i+1})-K_{y}(\widebar{x},y^{i+1})+K_{yx}(x^{i+1},y^{i+1})(\widebar{x}-x^{i+1}),y^{i+1}-\widebar{y}\rangle$
$\displaystyle-\langle
K_{x}(x^{i},\widebar{y})-K_{x}(\widebar{x},\widebar{y}),x^{i+1}-\widebar{x}\rangle-\gamma_{G}\|x^{i+1}-\widebar{x}\|^{2}\quad\text{and}$
$\displaystyle d_{i}^{y}$ $\displaystyle:=\langle
K_{x}(x^{i},\widebar{y})-K_{x}(x^{i},y^{i})-K_{xy}(x^{i},y^{i})(\widebar{y}-y^{i}),x^{i+1}-\widebar{x}\rangle$
$\displaystyle-\langle
K_{y}(x^{i+1},y^{i+1})-K_{y}(x^{i+1},y^{i})+K_{y}(\widebar{x},\widebar{y})-K_{y}(\widebar{x},y^{i+1}),y^{i+1}-\widebar{y}\rangle-\gamma_{F^{*}}\|y^{i+1}-\widebar{y}\|^{2},$

we rearrange and estimate

(52) $\displaystyle q_{i}$ $\displaystyle=d_{i}^{x}+d_{i}^{y}+\langle
K_{y}(x^{i+1},y^{i+1})-K_{y}(x^{i+1},y^{i}),y^{i+1}-\widebar{y}\rangle$
$\displaystyle+\langle(K_{xy}(x^{i+1},y^{i+1})-K_{xy}(x^{i},y^{i}))(y^{i}-\widebar{y}),x^{i+1}-\widebar{x}\rangle$
$\displaystyle+\langle
K_{x}(x^{i},y^{i})-K_{x}(x^{i+1},y^{i+1})+K_{xy}(x^{i+1},y^{i+1})(y^{i+1}-y^{i}),x^{i+1}-\widebar{x}\rangle$
$\displaystyle\leq d_{i}^{x}+d_{i}^{y}+O(\|u^{i+1}-u^{i}\|).$

Using $\xi_{x}=\gamma_{G}$, $\xi_{y}=\gamma_{F^{*}}$, (16), and both Section 3
and Section 3 (iv) at $\widebar{u}$, we estimate $q_{i}\leq
O(\|u^{i+1}-u^{i}\|)$ as

$\displaystyle d_{i}^{x}$
$\displaystyle\leq(\|y^{i+1}-\widebar{y}\|-\theta_{x})\|K_{y}(x^{i+1},y^{i+1})-K_{y}(\widebar{x},y^{i+1})+K_{yx}(x^{i+1},y^{i+1})(\widebar{x}-x^{i+1})\|\leq
0,$ $\displaystyle d_{i}^{y}$
$\displaystyle\leq(\|x^{i+1}-\widebar{x}\|-\theta_{y})\|K_{x}(x^{i},\widebar{y})-K_{x}(x^{i},y^{i})-K_{xy}(x^{i},y^{i})(\widebar{y}-y^{i})\|\leq
0.$

In the last bounds we used $\theta_{x}\geq 2\rho_{y}$, $\theta_{y}\geq
2\rho_{x}$, and $\|y^{i+1}-\widebar{y}\|\leq 2\rho_{y}$ because both
$\|y^{i+1}-{\widehat{y}}\|\leq\rho_{y}$ and
$\|{\widehat{y}}-\widebar{y}\|\leq\rho_{y}$; likewise,
$\|x^{i+1}-\widebar{x}\|\leq 2\rho_{x}$. Since $\|u^{i+1}-u^{i}\|\to 0$, we
obtain that $\limsup_{i\rightarrow\infty}~{}q_{i}\leq 0$. The
Brezis–Crandall–Pazy Lemma thus yields the desired inclusion $\widebar{v}\in
A(\widebar{u})$.

Hence in both cases, $\widebar{u}\in H^{-1}(0)$ and the condition (ii) of
Lemma 6.2 is satisfied. Applying Lemma 6.2, we obtain the claim.

We now provide convergence rates under additional assumptions of strong
convexity of $G$ and/or $F^{*}$, although we still allow non-convexity of the
overall problem through $K$. To be specific, we require that we can take the
acceleration or step length update factors $\widetilde{\gamma}_{G}>0$ and/or
$\widetilde{\gamma}_{F^{*}}>0$ in (24d) and (24e), respectively. Let us start
with $\widetilde{\gamma}_{G}>0$, which is the case, for instance, when $G$ is
strongly convex and (15a) holds with $\xi_{x}=0$. Since we obtain _a fortiori_
strong convergence from the rates, we do not require the additional
assumptions on $K$ introduced in Theorem 6.1; on the other hand, we only
obtain convergence of the primal iterates. Similar to the linear case of [10],
the step length choice follows directly from having to satisfy (24b) and the
desire to keep the right-hand side of the $\sigma$-rule (24c) constant.

######  Theorem 6.4 (convergence rates under acceleration: $\omega_{i}=1$).

Suppose Sections 3, 3 and 5 hold for some $R_{K}>0$; $L_{yx}\geq 0$;
$\lambda_{x},\lambda_{y},\theta_{x},\theta_{y}\geq 0$; and
$\xi_{x},\xi_{y}\in\mathbb{R}$ such that for some $\widetilde{\gamma}_{G}>0$,

(53a) $\displaystyle\xi_{x}$
$\displaystyle=\gamma_{G}-\widetilde{\gamma}_{G},$ $\displaystyle\theta_{y}$
$\displaystyle\geq\rho_{x},$ (53b) $\displaystyle\xi_{y}$
$\displaystyle=\gamma_{F^{*}},$ $\displaystyle\theta_{x}$
$\displaystyle\geq\rho_{y}.$

Choose

(54)
$\tau_{i+1}=\frac{\tau_{i}}{1+2\widetilde{\gamma}_{G}\tau_{i}},\quad\sigma_{i+1}\equiv\sigma,\quad\text{and}\quad\omega_{i}\equiv
1,$

satisfying for some $0<\delta\leq\mu<1$ the bounds

(55)
$0<\tau_{0}\leq\frac{\delta}{\lambda_{x}+3L_{yx}\rho_{y}}\quad\text{and}\quad
0<\sigma\tau_{0}\leq\frac{1-\mu}{R_{K}^{2}}.$

Then $\|x^{N}-{\widehat{x}}\|^{2}$ converges to zero at the rate $O(1/N)$.

######  Proof 6.5.

We again first verify (24) so that we can apply Theorem 4.2 and Lemma 5.3.
Setting $\psi_{i}\equiv 1$, $\eta_{i}\equiv\sigma$,
$\phi_{i}:=\sigma\tau_{i}^{-1}$, and $\widetilde{\gamma}_{F^{*}}=0$, (24a)
follows from the $\sigma$-rule of (54) and the choice of $\psi_{i}$,
$\eta_{i}$, and $\phi_{i}$. Using (54) and $\tau_{i}:=\sigma\phi_{i}^{-1}$, we
obtain $\phi_{i+1}=(1+2\widetilde{\gamma}_{G}\tau_{i})\phi_{i}$, and hence
(24b) follows. Since $\tau_{i}\leq\tau_{0}$ and $\lambda_{y}\geq 0$, (24c)
follows from (55) and $\omega_{i}=1$. Furthermore, (24d) and (24e) are
satisfied due to the assumed bounds (53) on $\xi_{x}$, $\xi_{y}$,
$\theta_{x}$, and $\theta_{y}$ taking
$\overline{\omega}=\underline{\omega}=1$.

We can thus apply Theorem 4.2 and Lemma 5.3 to arrive at (23) for
$\Delta_{i+1}=0$. We now estimate the convergence rate from (23) by bounding
$Z_{N+1}M_{N+1}$ from below. Using Corollary 4.4, we obtain
$\delta\phi_{N}\|x^{N}-{\widehat{x}}\|^{2}\leq\|u^{0}-{\widehat{u}}\|^{2}_{Z_{1}M_{1}}$.
Moreover,

$\phi_{N+1}=(1+2\widetilde{\gamma}_{G}\tau_{N})\phi_{N}=\phi_{N}+2\widetilde{\gamma}_{G}\sigma=\ldots=\phi_{1}+2N\widetilde{\gamma}_{G}\sigma,$

which yields the claim.

######  Theorem 6.6 (linear convergence: $\omega_{i}<1$).

Suppose Sections 3, 3 and 5 hold for some $R_{K}>0$; $L_{yx}\geq 0$;
$\lambda_{x},\lambda_{y}\geq 0$; and
$\widetilde{\gamma}_{G},\widetilde{\gamma}_{F^{*}}>0$ as well as

(56a) $\displaystyle\xi_{x}$
$\displaystyle=\gamma_{G}-\widetilde{\gamma}_{G},$ $\displaystyle\theta_{y}$
$\displaystyle\geq\omega\rho_{x},$ (56b) $\displaystyle\xi_{y}$
$\displaystyle=\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}},$
$\displaystyle\theta_{x}$ $\displaystyle\geq\rho_{y}\omega^{-1}$

with

(57)
$\tau_{i}\equiv\tau,\quad\sigma_{i}\equiv\sigma:=\tau\widetilde{\gamma}_{G}\widetilde{\gamma}_{F^{*}}^{-1},\quad\text{and}\quad\omega_{i}\equiv\omega:=(1+2\widetilde{\gamma}_{G}\tau)^{-1}.$

Assume for some $0<\delta\leq\mu<1$ the bound

(58)
$\tau\leq\min\Biggl{\\{}\frac{\delta}{\lambda_{x}+3L_{yx}\rho_{y}},\,\frac{2\widetilde{\gamma}_{F^{*}}\widetilde{\gamma}_{G}^{-1}}{\lambda_{y}+\sqrt{\lambda_{y}^{2}+4\widetilde{\gamma}_{F^{*}}\widetilde{\gamma}_{G}^{-1}(R_{K}^{2}(1-\mu)^{-1}+2\widetilde{\gamma}_{G}\lambda_{y})}}\Biggr{\\}}.$

Then $\|u^{N}-{\widehat{u}}\|^{2}$ converges to zero with the linear rate
$O(\omega^{N})$.

######  Proof 6.7.

We will use Theorem 4.2 and Lemma 5.3, for both of which we need to verify
(24) first. We set $\overline{\omega}:=\underline{\omega}:=\omega$,

$\displaystyle\psi_{N}$
$\displaystyle:=\omega(1+2\sigma\widetilde{\gamma}_{F^{*}})^{N}=\omega(1+2\widetilde{\gamma}_{G}\tau)^{N}=\omega^{1-N},\quad\text{and}$
$\displaystyle\phi_{N}$
$\displaystyle:=\omega\sigma\tau^{-1}(1+2\tau\widetilde{\gamma}_{G})^{N}=\omega^{1-N}\sigma\tau^{-1}.$

Then $\psi_{1}=1$ and $\psi_{N}\sigma=\phi_{N}\tau$, verifying (24a) and
(24b). We next observe that substituting
$\sigma_{i}=\tau\widetilde{\gamma}_{G}\widetilde{\gamma}_{F^{*}}^{-1}$, the
first bound of (24c) is tantamount to requiring

$\tau\bigl{(}\tau
R_{K}^{2}(1-\mu)^{-1}+\lambda_{y}\omega^{-1}\bigr{)}\leq\widetilde{\gamma}_{F^{*}}\widetilde{\gamma}_{G}^{-1}.$

Substituting $\omega=(1+2\widetilde{\gamma}_{G}\tau)^{-1}$, this in turn is
equivalent to

$\left(R_{K}^{2}(1-\mu)^{-1}+2\widetilde{\gamma}_{G}\lambda_{y}\right)\tau^{2}+\lambda_{y}\tau-\widetilde{\gamma}_{F^{*}}\widetilde{\gamma}_{G}^{-1}\leq
0,$

which after solving a quadratic inequality for $\tau$ yields the second bound
of (58). Since $\omega\leq 1$, the first bound of (58) gives the second bound
of (24c). Finally, (24d) and (24e) follow directly from (56) with
$\underline{\omega}=\overline{\omega}=\omega$.

Since Section 5 and (24) hold, we can apply Lemma 5.3 to obtain
$\\{u^{i}\\}_{i\in\mathbb{N}}\in\mathcal{U}(\rho_{x},\rho_{y})$ and
$\\{\widebar{x}^{i+1}\\}_{i\in\mathbb{N}}\in\vmathbb{B}({\widehat{x}},\rho_{x})$.
Moreover, (25) yields self-adjointness of $Z_{i+1}M_{i+1}$. Consequently, we
can apply Theorem 4.2 and Lemma 5.3 to arrive at (23) for any
$\Delta_{i+1}\leq 0$.

We now estimate the convergence rate from (23) by bounding $Z_{N+1}M_{N+1}$
from below. Using Corollary 4.4, we obtain that

(59)
$\frac{1}{\omega^{N}}\left(\delta\sigma\omega\tau^{-1}\|x^{N}-{\widehat{x}}\|^{2}+\frac{\mu-\delta}{1-\delta}\|y^{N}-{\widehat{y}}\|^{2}\right)\leq\|u^{0}-{\widehat{u}}\|^{2}_{Z_{1}M_{1}}.$

Since $\omega\in(0,1)$, this gives the claimed linear convergence rate through
the exponential growth of $1/\omega^{N}$.

######  Remark 6.8.

If $K(x,y)=\langle A(x),y\rangle$ for some $A\in C^{1}(X)$, then
$K_{x}(x,y)=[\nabla A(x)]^{*}y$ and $K_{y}(x,y)=A(x)$ with $L_{y}(x)=0$ and
$L_{yx}=L$ for $L$ a local Lipschitz factor of $\nabla A$. Furthermore,
Section 3, the step length bounds, and the update rules required in Theorem
6.1 or 6.6 reduce to the corresponding ones introduced in [10] for this case.
As for acceleration, Theorem 6.4 now gives a weaker convergence rate of
$O(1/N)$ compared to $O(1/N^{2})$ in [10, Theorem 4.3]. This is due to (24c)
requiring $\sigma_{i}$ to be bounded whenever $\lambda_{y}>0$, even when
$\tau_{i}$ goes to zero.

Before we conclude this section, we refine Section 5 by showing that its
implicit requirements do not add any additional step length bounds provided
the starting point is sufficiently close to ${\widehat{u}}$.

######  Proposition 6.9.

Under the assumptions of Theorem 6.1, 6.4, or 6.6, suppose that
$\rho_{x},\rho_{y}>0$. Then there exists $\varepsilon>0$ such that Section 5
holds whenever the initial iterate $u^{0}=(x^{0},y^{0})$ satisfies

(60)
$r_{\max}:=\sqrt{2\delta^{-1}(\|x^{0}-{\widehat{x}}\|^{2}+\nu^{-1}\|y^{0}-{\widehat{y}}\|^{2})}\leq\varepsilon\quad\text{with}\quad\nu:=\sigma_{1}\omega_{0}\tau_{0}^{-1}.$

######  Proof 6.10.

We take $\mu$, $\delta$, $\sigma_{i}$, $\tau_{i}$, and $\omega_{i}$ as they
are defined in the corresponding Theorem 6.1, 6.4, or 6.6, and
$L_{x}(\widehat{y})$, $L_{y}(\widehat{x}),R_{K}$ from Section 3. We need to
show that there exist $\delta_{x},\delta_{y}>0$ and $r_{y}\geq
r_{\max}\sqrt{\nu(1-\delta)\delta(\mu-\delta)^{-1}}$ such that (41) holds and

(61)
$\vmathbb{B}({\widehat{x}},r_{\max}+\delta_{x})\times\vmathbb{B}({\widehat{y}},r_{y}+\delta_{y})\subseteq\mathcal{U}(\rho_{x},\rho_{y}).$

Let $\varepsilon>0$ and set
$r_{y}:=\varepsilon\sqrt{\nu(1-\delta)\delta(\mu-\delta)^{-1}}$ as well as
$\delta_{x}:=\sqrt{\varepsilon}$ and $\delta_{y}:=\rho_{y}-r_{y}$. Observing
(60), we then see both that $\delta_{y}>0$ and that (61) holds for
$\varepsilon>0$ sufficiently small. Furthermore, (60) yields that
$r_{\max}\leq\varepsilon$ in Lemma 5.3. Let

$c_{\varepsilon}:=\min\left\\{\frac{\delta_{x}}{2R_{K}r_{y}+2L_{x}({\widehat{y}})r_{\max}},\frac{\delta_{y}}{L_{y}({\widehat{x}})r_{y}+R_{K}(r_{\max}+\delta_{x})}\right\\}.$

Since $r_{y},r_{\max}=O(\varepsilon)$, $\delta_{x}=\sqrt{\varepsilon}$, and
$\delta_{y}>\rho_{y}/2>0$ for $\varepsilon>0$ small enough, we see that
$c_{\varepsilon}\to\infty$ as $\varepsilon\to 0$. Comparing the definition of
$c_{\varepsilon}$ to (41), we therefore see that the latter holds for any
given $\tau_{0}>0$ and $\sigma_{i}\equiv\sigma>0$ by taking $\varepsilon>0$
sufficiently small. Since in Theorems 6.1, 6.4 and 6.6 we have
$\tau_{i}\leq\tau_{0}$, the inequalities (41) hold.

##  7 Numerical examples

Finally, we illustrate the applicability of the proposed approach for the
example applications described in Section 2. The Julia implementation used to
generate the following results is on Zenodo [11].

###  7.1 An elliptic Nash equilibrium problem

Our first example illustrates the reformulation from Section 2.1 for the two-
player elliptic Nash equilibrium problem from [6]. Here the action space of
each player is $L^{2}(\Omega)$ for a bounded domain
$\Omega\subset\mathbb{R}^{d}$ with boundary $\partial\Omega$. To avoid
confusion with the spatial variable, we will in this subsection denote the
primal variable with $u$ and the dual variable with $v$. The set of admissible
strategies is

$X_{k}=\left\\{w\in L^{2}(\Omega):w(x)\in[a,b]\text{ a.e.
}x\in\Omega\right\\}\qquad(k=1,2).$

For a set of strategies $u:=(u_{1},u_{2})\in X=X_{1}\times X_{2}$, the payout
function for each player is

$\phi_{k}(u_{1},u_{2})=\frac{1}{2}\|S(u_{1},u_{2})-z_{k}\|_{L^{2}(\Omega)}^{2}+\frac{\alpha_{k}}{2}\|B_{k}u_{k}\|_{L^{2}(\Omega)}^{2}\qquad(k=1,2),$

where $\alpha_{k}>0$, $z_{k}\in L^{2}(\Omega)$ are given target states,
$S:L^{2}(\Omega)^{2}\to L^{2}(\Omega)$ maps $u=(u_{1},u_{2})$ to the solution
$y$ to the elliptic boundary value problem

(62) $\left\\{\begin{aligned} -\Delta
y&=B_{1}u_{1}+B_{2}u_{2}+f\quad&&\text{on }\Omega,\\\ y&=0\quad&&\text{on
}\partial\Omega,\end{aligned}\right.$

$B_{k}:L^{2}(\Omega)\to L^{2}(\Omega)$ are control operators which are here
chosen as

$B_{k}w:=\begin{cases}w(x)&\text{if }x\in\omega_{k},\\\ 0&\text{if
}x\notin\omega_{k},\end{cases}$

for some control domains $\omega_{k}\subset\Omega$, and $f$ is a common source
term. Following Section 2.1, the corresponding Nash equilibrium problem (3)
can then be solved by applying Algorithm 1.1 to

$\displaystyle G$ $\displaystyle:L^{2}(\Omega)^{2}\to\overline{\mathbb{R}},$
$\displaystyle G(u_{1},u_{2})$ $\displaystyle=\delta_{X}(u_{1},u_{2}),$
$\displaystyle F^{*}$
$\displaystyle:L^{2}(\Omega)^{2}\to\overline{\mathbb{R}},$ $\displaystyle
F^{*}(v_{1},v_{2})$ $\displaystyle=\delta_{X}(v_{1},v_{2}),$ $\displaystyle K$
$\displaystyle:L^{2}(\Omega)^{2}\times L^{2}(\Omega)^{2}\to\mathbb{R},$
$\displaystyle K((u_{1},u_{2}),(v_{1},v_{2}))$
$\displaystyle=[\phi_{1}(u_{1},u_{2})-\phi_{1}(v_{1},u_{2})]$
$\displaystyle+[\phi_{2}(u_{1},u_{2})-\phi_{2}(u_{1},v_{2})]$

To implement the algorithm, we need explicit forms of the proximal mappings
for $G$ and $F^{*}$ and of the partial derivatives of $K$. Since
$G=F^{*}=\delta_{X}$ for $X=X_{1}\times X_{2}$, we have

$\mathrm{prox}_{\tau G}(w)=\mathrm{prox}_{\sigma
F^{*}}(w)=\mathrm{proj}_{X}(w)=\left(\mathrm{proj}_{X_{1}}(w_{1}),\mathrm{proj}_{X_{2}}(w_{2})\right)$

for the metric projections onto the convex sets $X_{k}$ given pointwise almost
everywhere by

$[\mathrm{proj}_{X_{k}}(w_{k})](x)=\begin{cases}b&\text{if }w_{k}(x)>b,\\\
w_{k}(x)&\text{if }w_{k}(x)\in[a,b],\\\ a&\text{if }w_{k}(x)<a.\end{cases}$

It remains to address the computation of $K_{u}(u,v)$ and $K_{v}(u,v)$. Using
adjoint calculus and the linearity of the adjoint equation, we have that

$K_{u}(u,v)=\begin{pmatrix}p_{1}(u,v)+\alpha_{1}u_{1}\\\
p_{2}(u,v)+\alpha_{2}u_{2}\end{pmatrix},\qquad
K_{v}(u,v)=\begin{pmatrix}q_{1}(u,v)-\alpha_{1}v_{1}\\\
q_{2}(u,v)-\alpha_{2}v_{2}\end{pmatrix},$

where $p_{1}(u,v)=:p_{1}$ and $p_{2}(u,v)=:p_{2}$ are the solutions to the
equations

$\displaystyle-\Delta p_{1}$
$\displaystyle=2S(u_{1},u_{2})-S(u_{1},v_{2})-z_{1},$ $\displaystyle-\Delta
p_{2}$ $\displaystyle=2S(u_{1},u_{2})-S(v_{1},u_{2})-z_{2},$ and
$q_{1}(u,v)=:q_{1}$ and $q_{2}(u,v)=:q_{2}$ are the solutions to the equations
$\displaystyle-\Delta q_{1}$ $\displaystyle=-S(v_{1},u_{2})+z_{1},$
$\displaystyle-\Delta q_{2}$ $\displaystyle=-S(u_{1},v_{2})+z_{2},$

all with homogeneous Dirichlet conditions. Hence, every iteration of Algorithm
1.1 requires nine solutions of a partial differential equation (recall that
$K_{v}$ is evaluated at $(\widebar{u}^{i+1},v^{i})$, while $K_{u}$ is
evaluated at $(u^{i},v^{i})$). Since $S$ and hence $K_{u}$ and $K_{v}$ are
affine in $u$ and $v$, the assumptions of Theorem 6.1 are satisfied for
sufficiently small step lengths. Since neither $F^{*}$ nor $G$ are strongly
convex, no acceleration is possible.

For our numerical tests we follow [6] and consider a finite-difference
discretization of (62) on $\Omega=(0,1)^{2}$ with $N$ nodes in each direction,

$\omega_{1}=(0,1)\times(0,1/2),\qquad\omega_{2}=(0,1)\times(1/2,1),$

as well as $a=-0.5$, $b=0.5$, and $\alpha_{i}=1$. Using the method of
manufactured solutions, $z_{1}$, $z_{2}$, and $f$ are chosen such that the
solution $u^{*}=(u_{1}^{*},u_{2}^{*})$ of the Nash equilibrium problem is
known a priori; see Fig. 3. By construction, the saddle point then satisfies
$v^{*}=u^{*}$ and hence $\Psi(u^{*},v^{*})=0$.

(a) $u_{1}^{*}$

(b) $u_{2}^{*}$

Figure 3: Constructed solution for elliptic NEP example ($N=128$) Table 1: Results for elliptic NEP example for different $N$ $i$ | $N=64$ | $N=128$ | $N=256$ | $N=512$ | $N=1024$
---|---|---|---|---|---
$1$ | $1.298\text{⋅}{10}^{-01}$ | $1.319\text{⋅}{10}^{-01}$ | $1.330\text{⋅}{10}^{-01}$ | $1.335\text{⋅}{10}^{-01}$ | $1.338\text{⋅}{10}^{-01}$
$2$ | $3.889\text{⋅}{10}^{-06}$ | $4.048\text{⋅}{10}^{-06}$ | $4.074\text{⋅}{10}^{-06}$ | $4.088\text{⋅}{10}^{-06}$ | $4.097\text{⋅}{10}^{-06}$
$3$ | $3.835\text{⋅}{10}^{-10}$ | $3.977\text{⋅}{10}^{-10}$ | $4.010\text{⋅}{10}^{-10}$ | $4.026\text{⋅}{10}^{-10}$ | $4.032\text{⋅}{10}^{-10}$
$4$ | $3.811\text{⋅}{10}^{-14}$ | $3.952\text{⋅}{10}^{-14}$ | $3.986\text{⋅}{10}^{-14}$ | $4.001\text{⋅}{10}^{-14}$ | $4.008\text{⋅}{10}^{-14}$
$5$ | $3.787\text{⋅}{10}^{-18}$ | $3.928\text{⋅}{10}^{-18}$ | $3.963\text{⋅}{10}^{-18}$ | $3.977\text{⋅}{10}^{-18}$ | $3.985\text{⋅}{10}^{-18}$

Since the Lipschitz constants for $K$ and its derivatives are not available,
we simply take the parameters in Algorithm 1.1 as
$\sigma_{i+1}\equiv\sigma=1.0$, $\tau_{i}\equiv\tau=0.99$, and $\omega=1.0$.
The results of the algorithm for different values of
$N\in\\{64,128,256,512,1024\\}$ are shown in Table 1, which reports the
distance of the primal-dual iterates $(u^{i},v^{i})$ to the exact solution. As
can be seen, the iteration converges in each case to machine precision within
$5$ iterations, and the convergence behavior is virtually identical. This
demonstrates the mesh independence expected from an algorithm for which
convergence can be shown in function spaces.

###  7.2 $\ell^{0}$-TV denoising

Our next example concerns the $\ell^{0}$-TV denoising or segmentation problem
from Section 2.2. Recall that we can solve the (Huber-regularized)
$\ell^{0}$-TV problem (5) by applying Algorithm 1.1 to

$\displaystyle G$ $\displaystyle:\mathbb{R}^{N_{1}\times N_{2}}\to\mathbb{R},$
$\displaystyle G(x)$ $\displaystyle=\frac{1}{2\alpha}\|x-f\|_{2}^{2},$
$\displaystyle F_{\gamma}^{*}$ $\displaystyle:\mathbb{R}^{N_{1}\times
N_{2}\times 2}\to\mathbb{R},$ $\displaystyle F_{\gamma}^{*}(y)$
$\displaystyle=\frac{\gamma}{2}\|y\|_{2}^{2},$ $\displaystyle K_{p}$
$\displaystyle:\mathbb{R}^{N_{1}\times N_{2}}\times\mathbb{R}^{N_{1}\times
N_{2}\times 2}\to\mathbb{R},$ $\displaystyle K_{p}(x,y)$
$\displaystyle=\kappa_{p}(D_{h}x,y),$

for $p\in\\{1,\infty\\}$ and $\gamma\geq 0$, where
$D_{h}:\mathbb{R}^{N_{1}\times N_{2}}\to\mathbb{R}^{N_{1}\times N_{2}\times
2}$ is the discrete gradient. We write $H_{\gamma}$ for $H$ defined in (17)
corresponding to $F^{*}=F_{\gamma}^{*}$. Since $G$ and $F_{\gamma}^{*}$ are
quadratic, a simple computation shows that

$\mathrm{prox}_{\tau
G}(x)=\frac{1}{1+\frac{\tau}{\alpha}}\left(x+\frac{\tau}{\alpha}f\right),\quad\text{and}\quad\mathrm{prox}_{\sigma
F_{\gamma}^{*}}(y)=\frac{1}{1+\gamma\sigma}y,$

where all operations are to be understood componentwise. For the derivatives
of $K_{p}$, we have by the chain rule

(63) $K_{x}(x,y)=D_{h}^{T}\kappa_{p,z}(D_{h}x,y),\qquad
K_{y}(x,y)=\kappa_{p,y}(D_{h}x,y),$

where $D_{h}^{T}$ is the discrete (negative) divergence. For the partial
derivatives of $\kappa_{p,z}(z,y)$ and $\kappa_{p,y}(z,y)$, we again
distinguish the cases $p=1$ and $p=\infty$:

For $p=1$, we have componentwise $\displaystyle[\kappa_{1,z}(z,y)]_{ijk}$
$\displaystyle=2(1-z_{ijk}y_{ijk})y_{ijk},$
$\displaystyle[\kappa_{1,y}(z,y)]_{ijk}$
$\displaystyle=2(1-z_{ijk}y_{ijk})z_{ijk}.$ For $p=\infty$, we have
componentwise $\displaystyle[\kappa_{\infty,z}(z,y)]_{ijk}$
$\displaystyle=2(1-z_{ij1}y_{ij1}-z_{ij2}y_{ij2})y_{ijk},$
$\displaystyle[\kappa_{\infty,y}(z,y)]_{ijk}$
$\displaystyle=2(1-z_{ij1}y_{ij1}-z_{ij2}y_{ij2})z_{ijk}.$

It remains to choose valid step sizes for Algorithm 1.1, for which the next
result gives useful estimates. We recall from [7] that a forward differences
discretization of the gradient operator satisfies
$\|D_{h}\|_{2}\leq\sqrt{8}/h$. Recalling (63) and the definitions of $G$ and
$F_{\gamma}^{*}$, a critical point $({\widehat{x}},{\widehat{y}})\in
H^{-1}_{\gamma}(0)$ satisfies

(64)
$0=\alpha^{-1}({\widehat{x}}-f)+D_{h}^{T}\kappa_{p,z}(D_{h}{\widehat{x}},{\widehat{y}})\quad\text{and}\quad\gamma{\widehat{y}}=\kappa_{p,y}(D_{h}{\widehat{x}},{\widehat{y}}).$

For brevity, we set

$\displaystyle\widehat{m}_{x}$
$\displaystyle:=\max_{ij}|[D_{h}{\widehat{x}}]_{\,\boldsymbol{\cdot}\,ij}|_{2}\quad\text{and}$
$\displaystyle\widehat{m}_{y}$
$\displaystyle:=\max_{ij}|{\widehat{y}}_{\,\boldsymbol{\cdot}\,ij}|_{2}$
$\displaystyle(p=\infty),$ $\displaystyle\widehat{m}_{x}$
$\displaystyle:=\max_{kij}|[D_{h}{\widehat{x}}]_{kij}|\quad\text{and}$
$\displaystyle\widehat{m}_{y}$
$\displaystyle:=\max_{kij}|{\widehat{y}}_{kij}|$ $\displaystyle(p=1).$

Using the results of Appendix C we verify the fundamental Section 3.

######  Corollary 7.1.

Let $K=K_{p}$ for either $p=1$ or $p=\infty$. Choose $L\geq\|D_{h}\|_{2}$ and
$R_{K}>2L$. Then Section 3 holds for some $\theta_{x},\theta_{y}>0$ and
$\rho_{x},\rho_{y}>0$ with

$\displaystyle L_{x}(y)$ $\displaystyle=2L^{2}\|y\|_{2}^{2},$ $\displaystyle
L_{y}(x)$ $\displaystyle=2L^{2}\|x\|_{2}^{2},\qquad$ $\displaystyle L_{yx}$
$\displaystyle=4L\sup\nolimits_{y\in\vmathbb{B}({\widehat{y}},\rho_{y})}\|y\|_{2},$

and the constants $\xi_{x},\xi_{y}>0$, $\lambda_{x},\lambda_{y}\geq 0$
satisfying

(65)
$\xi_{x}\lambda_{x}>2L^{2}(L^{-1}\lambda_{x}+\widehat{m}_{y}^{2})\widehat{m}_{y}^{2}\quad\text{and}\quad\lambda_{y}>\widehat{m}_{x}^{2}.$

######  Proof 7.2.

We consider only $p=\infty$ as the proof for $p=1$ is similar. Taking
$\widetilde{R}_{K}>2$, Lemma C.1 applied componentwise shows that the operator
$\kappa_{p}$ satisfies Section 3 for some
$\widetilde{\theta}_{z},\widetilde{\theta}_{y}>0$ and
$\widetilde{\rho}_{x},\widetilde{\rho}_{y}>0$ (depending on
$\widetilde{R}_{K}$) when we take

$\widetilde{L}_{z}(y)=2\|y\|_{2}^{2},\qquad\widetilde{L}_{y}(z)=2\|z\|_{2}^{2},\quad\text{and}\quad\widetilde{L}_{yz}=4\max_{y\in\vmathbb{B}({\widehat{y}},\widetilde{\rho}_{y})}\|y\|_{2}.$

Moreover, the constants $\widetilde{\xi}_{z},\widetilde{\xi}_{y}\in\mathbb{R}$
and $\widetilde{\lambda}_{z},\widetilde{\lambda}_{y}\geq 0$ need to satisfy
$\widetilde{\xi}_{z}\widetilde{\lambda}_{z}>\max_{ij}2(\lambda_{z}+\|{\widehat{y}}_{\,\boldsymbol{\cdot}\,ij}\|^{2})\|{\widehat{y}}_{\,\boldsymbol{\cdot}\,ij}\|^{2}$
as well as $\widetilde{\xi}_{y}>0$ and
$\widetilde{\lambda}_{y}>\max_{ij}\|{\widehat{z}}_{\,\boldsymbol{\cdot}\,ij}\|^{2}$
for ${\widehat{z}}=D_{h}{\widehat{x}}$.

By Lemma C.3 on compositions with a linear operator, we can now take

$\displaystyle R_{K}=\widetilde{R}_{K}L,$
$\displaystyle\rho_{x}=L^{-1}\widetilde{\rho}_{x},$
$\displaystyle\rho_{y}=\widetilde{\rho}_{y},$
$\displaystyle\xi_{x}=L\widetilde{\xi}_{z},$
$\displaystyle\xi_{y}=\widetilde{\xi}_{y},$
$\displaystyle\lambda_{x}=L\widetilde{\lambda}_{z},$
$\displaystyle\lambda_{y}=\widetilde{\lambda}_{y},$
$\displaystyle\theta_{x}=\widetilde{\theta}_{z},$
$\displaystyle\theta_{y}=\widetilde{\theta}_{y}L^{-1},$ $\displaystyle
L_{x}(y)=L^{2}\widetilde{L}_{z}(y),$ $\displaystyle
L_{y}(x)=\widetilde{L}_{y}(D_{h}x),$ $\displaystyle
L_{yx}=L^{2}\widetilde{L}_{yz}.$

These give the claim.

We now obtain from Theorem 6.6 the following estimate.

######  Corollary 7.3.

Suppose Section 3 holds. Choose $L\geq\|D_{h}\|_{2}$. For some
$\widetilde{\gamma}_{G}\in(0,\alpha^{-1})$ and
$\widetilde{\gamma}_{F^{*}}\in(0,\gamma)$, take
$\xi_{x}=\alpha^{-1}-\widetilde{\gamma}_{G}$ and
$\xi_{y}=\gamma-\widetilde{\gamma}_{F^{*}}$ as well as
$\lambda_{x},\lambda_{y}\geq 0$ such that (65) holds. For some
$0<\delta\leq\mu<1$, take
$\sigma=\tau\widetilde{\gamma}_{G}\widetilde{\gamma}_{F^{*}}^{-1}$ and
$\omega:=(1+2\widetilde{\gamma}_{G}\tau)^{-1}$ as well as

(66)
$\tau<\min\left\\{\frac{\delta}{\lambda_{x}},\frac{2\widetilde{\gamma}_{F^{*}}\widetilde{\gamma}_{G}^{-1}}{\lambda_{y}+\sqrt{\lambda_{y}^{2}+4\widetilde{\gamma}_{F^{*}}\widetilde{\gamma}_{G}^{-1}(4L^{2}(1-\mu)^{-1}+2\widetilde{\gamma}_{G}\lambda_{y})}}\right\\}.$

Then $\|u^{N}-{\widehat{u}}\|^{2}$ converges to zero with the linear rate
$O(\omega^{N})$ provided $u^{0}$ is close enough to ${\widehat{u}}$.

######  Proof 7.4.

The assumptions $\widetilde{\gamma}_{G}\in(0,\alpha^{-1})$ and
$\widetilde{\gamma}_{F^{*}}\in(0,\gamma)$ ensure $\xi_{x},\xi_{y}>0$. Since we
have assumed (65), Corollary 7.1 yields Section 3 for any $R_{K}>2L$ and some
$\theta_{x},\theta_{y}>0$. We next use Theorem 6.6, whose conditions we need
to verify. First, taking $\rho_{x},\rho_{y}>0$ ensures that
$\theta_{x}\geq\rho_{y}\omega^{-1}$ and $\theta_{y}\geq\omega\rho_{x}$.
Furthermore, the strict inequality in (66) implies (58) for sufficiently small
$\rho_{y}>0$. Finally, Proposition 6.9 ensures that we can satisfy Section 5
by taking $u^{0}$ sufficiently close to ${\widehat{u}}$. The rest of the
conditions we have assumed explicitly, so we can apply Theorem 6.6 to finish
the proof.

Recall that Section 3 is a second-order growth condition at the critical point
$({\widehat{x}},{\widehat{y}})$, which is a common assumption needed to show
convergence of algorithms for non-convex optimization problems. To calculate
the upper bounds on $\tau$ in (66), we need to find
$\lambda_{x},\lambda_{y}\geq 0$ satisfying (65). For this, in turn, we need to
estimate $\widehat{m}_{x}$ and $\widehat{m}_{y}$. To do this, note that the
critical point conditions (64) imply

(67)
${\widehat{y}}_{\,\boldsymbol{\cdot}\,ij}=\frac{2[D_{h}{\widehat{x}}]_{\,\boldsymbol{\cdot}\,ij}}{2|[D_{h}{\widehat{x}}]_{\,\boldsymbol{\cdot}\,ij}|_{2}^{2}+\gamma}\quad(p=\infty)\quad\text{and}\quad{\widehat{y}}_{kij}=\frac{2[D_{h}{\widehat{x}}]_{kij}}{2|[D_{h}{\widehat{x}}]_{kij}|^{2}+\gamma}\quad(p=1).$

Since $t\mapsto t/(t+\gamma)$ is increasing, we can estimate $\widehat{m}_{y}$
based on $\widehat{m}_{x}$. Since any solution of the Potts problem should be
piecewise constant with very few intensity quantization levels, we can
estimate $\widehat{m}_{x}$ as the expected maximal jump between neighboring
pixels. We take this as 100% of the dynamic range for safety. In practice, as
a practical choice of $\gamma>0$ will likely not satisfy
$\xi_{x}>2L\widehat{m}_{y}^{2}$, we use an over-approximation
$\widebar{\gamma}:=10\geq\gamma$ in (67). We remark that we thus cannot
guarantee convergence of Algorithm 1.1 for small $\gamma>0$; however, we
demonstrate below that these estimates can still lead to useful step sizes for
such cases. Similarly, we do not have an estimate for the unknown local
neighborhood of convergence; we compensate for this by taking small
$\delta=0.1$ in (66). As the results below demonstrate, with these parameters
we nevertheless observe convergence for the reasonable starting point
$u^{0}=(x^{0},y^{0})$ with $x^{0}=f$ and $y^{0}\equiv 0$.

We illustrate the performance of the algorithm and the effects of the choice
of $p$. As a test image, we choose “blobs” from the ImageJ framework [30] with
size $N_{1}\times N_{2}=256\times 254$, see Fig. 4(a). We set $\alpha=1$ and
$\gamma=10^{-3}$ (cf. Fig. 2) and use the accelerated step size rule from
Theorem 6.6. To do this, we need to satisfy (66) for the primal step length
$\tau$. We discretize the problem such that $h=1$ and hence $L=\sqrt{8}$.
Furthermore, we set $\widetilde{\gamma}_{F^{*}}=\gamma/100$ and
$\widetilde{\gamma}_{G}=\widetilde{\alpha}^{-1}$ for
$\widetilde{\alpha}=10\alpha$. The above estimates then lead to the step
length parameters

$p=1$:

$\tau=1.04085\cdot 10^{-3}$, $\sigma=1.04085$, $\omega=0.99480$;

$p=\infty$:

$\tau=5.51922\cdot 10^{-4}$, $\sigma=0.551922$, $\omega=0.99724$.

Since the exact solution $({\widehat{x}},{\widehat{y}})$ is not available
here, we instead use $x^{\max}:=x^{N_{\max}}$ for $N_{\max}=10^{6}$ and
similarly $y^{\max}$ as references for computing errors. The corresponding
reference images $x^{\max}$ obtained from Algorithm 1.1 after
$N_{\max}=10^{6}$ iterations are shown in Figs. 4(b) and 4(c) for $p=1$ and
$p=\infty$, respectively. While the evaluation of the formulation and the
algorithm in the context of image processing is outside of the scope of this
work, we briefly comment on the difference between $p=1$ and $p=\infty$. As
can be seen by comparing the two images, the results are very similar.
However, since diagonal jumps are penalized less for $p=\infty$, the isotropic
Huber–Potts model is better able to preserve small light blobs such as the one
indicated by the red circles. The edges of the blobs are also noticeably
smoother.

(a) original image $f$

(b) $x^{\max}$ for $p=1$

(c) $x^{\max}$ for $p=\infty$

Figure 4: $\ell^{0}$-TV denoising: original image $f$ and reference iterates
$x^{\max}$ for anisotropic ($p=1$) and isotropic ($p=\infty$) Huber–Potts
model

$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{3.6}$$10^{3.8}$$10^{4}$$10^{4.2}$$10^{4.4}$$10^{4.6}$$10^{4.8}$$p=1$$p=\infty$
(a) function values

$1\cdot 10^{4}$$1\cdot 10^{5}$$2\cdot 10^{5}$$3\cdot 10^{5}$$4\cdot
10^{5}$$5\cdot
10^{5}$$10^{-25}$$10^{-22}$$10^{-19}$$10^{-16}$$10^{-13}$$10^{-10}$$10^{-7}$$10^{-4}$$10^{-1}$$10^{2}$$10^{5}$$10^{8}$$p=1$$p=\infty$
(b) errors

Figure 5: $\ell^{0}$-TV denoising: convergence of function values
$F_{\gamma}(x^{N})+G(x^{N})$ and errors
$\|x^{N}-x^{\max}\|^{2}+\|y^{N}-y^{\max}\|^{2}$

The convergence behavior of the method for both choices of $p$ over
$N_{\max}/2=5\cdot 10^{5}$ iterations is given in Fig. 5. For the function
values, we observe in Fig. 5(a) the usual fast decrease in the beginning of
the iteration, after which the values stagnate. Nevertheless, the errors
continue to decrease down to machine precision at the predicted linear rate.
The convergence behavior for $p=1$ and $p=\infty$ is similar, although the
linear convergence for $p=\infty$ is with a significantly smaller constant. We
remark that visually, the iterates in both cases are indistinguishable from
the reference images already after $N=10^{4}$ iterations. This is consistent
with Fig. 5(b) since the total error is dominated by the dual component, which
acts as an edge indicator; small changes of the boundaries of the blobs during
the iteration will, even for small gray value changes, lead to large
differences in the dual variable.

##  8 Conclusion

Using generalized conjugation, some non-smooth non-convex optimization
problems can be transformed into saddle-point problems involving non-smooth
convex functionals and a smooth non-convex-concave coupling term. For such
problems, a generalized primal–dual proximal splitting method can be applied
that converges weakly under step length conditions if a local quadratic growth
condition is satisfied near a saddle-point. Under additional strong convexity
assumptions on the functionals (but not the coupling term and hence the
problem), convergence rates for accelerated algorithms can be shown. This
approach can be applied to elliptic Nash equilibrium problems and for the
anisotropic and isotropic Huber-regularized Potts models, as the numerical
examples illustrate. Future work is concerned with further evaluating and
comparing the performance of the proposed algorithm for these examples.

## Acknowledgments

In the first stages of the research T. Valkonen and S. Mazurenko were
supported by the EPSRC First Grant EP/P021298/1, “PARTIAL Analysis of
Relations in Tasks of Inversion for Algorithmic Leverage”. Later T. Valkonen
was supported by the Academy of Finland grants 314701 and 320022. C. Clason
was supported by the German Science Foundation (DFG) under grant Cl 487/2-1.
We thank the anonymous reviewers for insightful comments.

## A data statement for the EPSRC

The source codes for the numerical experiments are on Zenodo at [11].

##  Appendix A Reductions of the three-point condition

The following two propositions demonstrate that Section 3 (iv) is closely
related to standard second-order optimality conditions, i.e., that the Hessian
is positive definite at the solution ${\widehat{u}}$.

######  Proposition A.1.

Suppose Section 3 (ii) (locally Lipschitz gradients of $K$) holds in some
neighborhood $\mathcal{U}$ of ${\widehat{u}}$, and for some
$\xi_{x}\in\mathbb{R}$, $\gamma_{x}>0$,

(68) $\xi_{x}\|x-{\widehat{x}}\|^{2}+\langle
K_{x}(x,{\widehat{y}})-K_{x}({\widehat{x}},{\widehat{y}}),x-{\widehat{x}}\rangle\geq\gamma_{x}\|x-{\widehat{x}}\|^{2}\quad((x,y)\in\mathcal{U}).$

Then (15a) holds in $\mathcal{U}$ with
$\theta_{x}=2(\gamma_{x}-\alpha)L_{yx}^{-1}$, and
$\lambda_{x}=L_{x}({\widehat{y}})^{2}(2\alpha)^{-1}$ for any
$\alpha\in(0,\gamma_{x}]$.

######  Proof A.2.

An application of Cauchy’s and Young’s inequalities with any factor
$\alpha>0$, Section 3 (ii), and (68) yields the estimate

$\displaystyle\langle
K_{x}(x^{\prime},{\widehat{y}})-K_{x}({\widehat{x}},{\widehat{y}}),x-{\widehat{x}}\rangle+\xi_{x}\|x-{\widehat{x}}\|^{2}$
$\displaystyle=\langle
K_{x}(x,{\widehat{y}})-K_{x}({\widehat{x}},{\widehat{y}}),x-{\widehat{x}}\rangle+\xi_{x}\|x-{\widehat{x}}\|^{2}$
$\displaystyle\quad+\langle
K_{x}(x^{\prime},{\widehat{y}})-K_{x}(x,{\widehat{y}}),x-{\widehat{x}}\rangle$
$\displaystyle\geq(\gamma_{x}-\alpha)\|x-{\widehat{x}}\|^{2}-L_{x}({\widehat{y}})^{2}(4\alpha)^{-1}\|x^{\prime}-x\|^{2}.$

At the same time, using (16),

$\|K_{y}({\widehat{x}},y)-K_{y}(x,y)-K_{yx}(x,y)({\widehat{x}}-x)\|\leq\frac{L_{yx}}{2}\|x-{\widehat{x}}\|^{2}.$

Therefore (15a) holds if we take $\theta_{x}\leq
2(\gamma_{x}-\alpha)L_{yx}^{-1}$ and
$\lambda_{x}=L_{x}({\widehat{y}})^{2}(2\alpha)^{-1}$.

######  Proposition A.3.

Suppose Section 3 (ii) (locally Lipschitz gradients of $K$) holds in some
neighborhood $\mathcal{U}$ of ${\widehat{u}}$ with
$L_{y}(x)\leq\widebar{L}_{y}$, and that

$\|K_{xy}(x,y^{\prime})-K_{xy}(x,y)\|\leq
L_{xy}\|y^{\prime}-y\|\quad(u,u^{\prime}\in\mathcal{U})$

for some constant $L_{xy}\geq 0$. Assume, moreover, for some
$\xi_{y}\in\mathbb{R}$, $\gamma_{y}>0$ that

(69) $\xi_{y}\|y-{\widehat{y}}\|^{2}+\langle
K_{y}({\widehat{x}},{\widehat{y}})-K_{y}({\widehat{x}},y),y-{\widehat{y}}\rangle\geq\gamma_{y}\|y-{\widehat{y}}\|^{2}\quad((x,y)\in\mathcal{U}).$

Then (LABEL:eq:k-nonlinear-ky) holds in $\mathcal{U}$ with
$\theta_{y}=2(\gamma_{y}-\alpha_{1})(1+\alpha_{2})^{-1}L_{xy}^{-1}$, and
$\lambda_{y}=(\widebar{L}_{y}^{2}(2\alpha_{1})^{-1}+(1+\alpha_{2}^{-1})L_{xy}\theta_{y})$
for any $\alpha_{1}\in(0,\gamma_{y}]$, $\alpha_{2}>0$.

######  Proof A.4.

An application of Cauchy’s and Young’s inequalities with any factor
$\alpha>0$, Section 3 (ii), and (69) yields the estimate

$\langle
K_{y}(x,y)-K_{y}(x,y^{\prime})+K_{y}({\widehat{x}},{\widehat{y}})-K_{y}({\widehat{x}},y),y-{\widehat{y}}\rangle+\xi_{y}\|y-{\widehat{y}}\|^{2}\\\
\begin{aligned} &\geq\langle
K_{y}(x,y)-K_{y}(x,y^{\prime}),y-{\widehat{y}}\rangle+\gamma_{y}\|y-{\widehat{y}}\|^{2}\\\
&\geq(\gamma_{y}-\alpha_{1})\|y-{\widehat{y}}\|^{2}-\frac{L_{y}(x)^{2}}{4\alpha_{1}}\|y^{\prime}-y\|^{2}.\end{aligned}$

At the same time, using (16) and Young’s inequality for any $\alpha_{2}>0$,

$\displaystyle\|K_{x}(x^{\prime},{\widehat{y}})-K_{x}(x^{\prime},y^{\prime})-K_{xy}(x^{\prime},y^{\prime})({\widehat{y}}-y^{\prime})\|$
$\displaystyle\leq\frac{L_{xy}}{2}\|y^{\prime}-{\widehat{y}}\|^{2}$
$\displaystyle\leq\frac{L_{xy}}{2}(1+\alpha_{2})\|y-{\widehat{y}}\|^{2}+\frac{L_{xy}}{2}(1+\alpha_{2}^{-1})\|y^{\prime}-y\|^{2}.$

Therefore (LABEL:eq:k-nonlinear-ky) holds if we take $\theta_{y}\leq
2\frac{\gamma_{y}-\alpha_{1}}{(1+\alpha_{2})L_{xy}}$ and
$\lambda_{y}=\frac{\widebar{L}_{y}^{2}}{2\alpha_{1}}+(1+\alpha_{2}^{-1})L_{xy}\theta_{y}$.

##  Appendix B Relaxations of the three-point condition

In all the results of this paper, Section 3 (iv) can be generalized to the
following three-point condition similar to the one used in [10].

######  Assumption B.0.

The functional $K(x,y)\in C^{1}(X\times Y)$ and there exists a neighborhood

(70)
$\mathcal{U}(\rho_{x},\rho_{y}):=(\vmathbb{B}({\widehat{x}},\rho_{x})\cap\mathcal{X}_{G})\times(\vmathbb{B}({\widehat{y}},\rho_{y})\cap\mathcal{Y}_{F^{*}}),$

for some $\rho_{x},\rho_{y}>0$ such that for all
$u^{\prime},u\in\mathcal{U}(\rho_{x},\rho_{y})$, the following property holds:

  1. (ivenumi)

(three-point condition) There exist $\theta_{x},\theta_{y}>0$,
$\lambda_{x},\lambda_{y}\geq 0$, $\xi_{x},\xi_{y}\in\mathbb{R}$, and
$p_{x},p_{y}\in[1,2]$ such that

(71a) $\displaystyle\begin{aligned} &\langle
K_{x}(x^{\prime},{\widehat{y}})-K_{x}({\widehat{x}},{\widehat{y}}),x-{\widehat{x}}\rangle+\xi_{x}\|x-{\widehat{x}}\|^{2}\\\
&\geq\theta_{x}\|K_{y}({\widehat{x}},y)-K_{y}(x,y)-K_{yx}(x,y)({\widehat{x}}-x)\|^{p_{x}}-\frac{\lambda_{x}}{2}\|x-x^{\prime}\|^{2},\quad\text{and}\end{aligned}$
(71b) $\displaystyle\begin{aligned} &\langle
K_{y}(x,y)-K_{y}(x,y^{\prime})+K_{y}({\widehat{x}},{\widehat{y}})-K_{y}({\widehat{x}},y),y-{\widehat{y}}\rangle+\xi_{y}\|y-{\widehat{y}}\|^{2}\\\
&\geq\theta_{y}\|K_{x}(x^{\prime},{\widehat{y}})-K_{x}(x^{\prime},y^{\prime})-K_{xy}(x^{\prime},y^{\prime})({\widehat{y}}-y^{\prime})\|^{p_{y}}-\frac{\lambda_{y}}{2}\|y-y^{\prime}\|^{2}.\end{aligned}$

This assumption introduces $p_{x}$ and $p_{y}$ in $[1,2]$, while in Section 3
(iv) we had $p_{x}=p_{y}=1$. For instance, in [10, Appendix B] we verified
Appendix B with $p_{x}=2$ for the case $K(x,y)=\langle A(x),y\rangle$ for the
reconstruction of the phase and amplitude of a complex number. This relaxation
mainly affects the proof of Step 4 in Theorem 4.2, which now requires a few
intermediate derivations.

######  Corollary B.1.

The results of Theorem 4.2 continue to hold if Section 3 (iv) is replaced with
Appendix B (ivenumi) for some $p_{x},p_{y}\in[1,2]$, where in case
$p_{y}\in(1,2]$, (24d) is replaced by

(72a) $\displaystyle\gamma_{G}$
$\displaystyle\geq\widetilde{\gamma}_{G}+\xi_{x}+\frac{p_{y}-1}{(\theta_{y}p_{y}^{p_{y}}\rho_{x}^{p_{y}-2}\overline{\omega}^{-1})^{\frac{1}{p_{y}-1}}},$
and in case $p_{x}\in(1,2]$, (24e) is replaced by (72b)
$\displaystyle\gamma_{F^{*}}$
$\displaystyle\geq\widetilde{\gamma}_{F^{*}}+\xi_{y}+\frac{p_{x}-1}{(\underline{\omega}\theta_{x}p_{x}^{p_{x}}\rho_{y}^{p_{x}-2})^{\frac{1}{p_{x}-1}}}.$

######  Proof B.2.

The beginning of the proof follows the exact same steps as in the proof of
Theorem 4.2 up until (30). We now use Appendix B (ivenumi) to further bound
$D_{x}$ and $D_{y}$ similarly to (31) and (32). From (71a),

(73) $\displaystyle D_{x}$
$\displaystyle\geq\theta_{x}\|K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})({\widehat{x}}-x^{i+1})\|^{p_{x}}-\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2}$
$\displaystyle-\|y^{i+1}-{\widehat{y}}\|\|K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})({\widehat{x}}-x^{i+1})\|\omega_{i}^{-1}.$

The following generalized Young’s inequality for any positive $a,b,p$ and $q$
such that $q^{-1}+p^{-1}=1$ allows for our choice of varying $p_{x}\in[1,2]$:

(74)
$ab=\left(ab^{\frac{2-p}{p}}\right)b^{2\frac{p-1}{p}}\leq\frac{1}{p}\left(ab^{\frac{2-p}{p}}\right)^{p}+\frac{1}{q}b^{2\frac{p-1}{p}q}=\frac{1}{p}a^{p}b^{2-p}+\biggl{(}1-\frac{1}{p}\biggr{)}b^{2}.$

Applying this inequality with $p=p_{x}$,

$\displaystyle a$
$\displaystyle:=(\zeta_{x}p_{x})^{-1/2}\|K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})({\widehat{x}}-x^{i+1})\|,\quad\text{and}$
$\displaystyle b$
$\displaystyle:=(\zeta_{x}p_{x})^{1/2}\|y^{i+1}-{\widehat{y}}\|,$

for any $\zeta_{x}>0$ to the last term of (73), we arrive at the estimate

$\displaystyle D_{x}$
$\displaystyle\geq\theta_{x}\|K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})({\widehat{x}}-x^{i+1})\|^{p_{x}}-\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2}$
$\displaystyle-\frac{\|y^{i+1}-{\widehat{y}}\|^{2-p_{x}}}{p_{x}^{p_{x}}\omega_{i}\zeta_{x}^{p_{x}-1}}\|K_{y}({\widehat{x}},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})({\widehat{x}}-x^{i+1})\|^{p_{x}}$
$\displaystyle-\frac{p_{x}-1}{\omega_{i}}\zeta_{x}\|y^{i+1}-{\widehat{y}}\|^{2}.$

We now use $u^{i+1}\in\mathcal{U}(\rho_{x},\rho_{y})$ for some
$\rho_{x},\rho_{y}\geq 0$, and $\omega_{i}^{-1}\leq\underline{\omega}^{-1}$ to
obtain

(75)
$\theta_{x}-\|y^{i+1}-{\widehat{y}}\|^{2-p_{x}}(p_{x}^{p_{x}}\omega_{i}\zeta_{x}^{p_{x}-1})^{-1}\geq\theta_{x}-\rho_{y}^{2-p_{x}}(p_{x}^{p_{x}}\underline{\omega}\zeta_{x}^{p_{x}-1})^{-1}.$

If $p_{x}=1$, we use the assumed inequality
$\theta_{x}\geq\rho_{y}\underline{\omega}^{-1}$ from (24e) to show that the
right-hand side of (75) is non-negative for any $\zeta_{x}>0$. Otherwise we
take
$\zeta_{x}:=(\underline{\omega}\theta_{x}p_{x}^{p_{x}}\rho_{y}^{p_{x}-2})^{1/(1-p_{x})}$
to ensure the right-hand side of (75) is zero. In either case,
$\theta_{x}-\rho_{y}^{2-p_{x}}(p_{x}^{p_{x}}\underline{\omega}\zeta_{x}^{p_{x}-1})^{-1}\geq
0$ and hence

(76)
$D_{x}\geq-\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2}-(p_{x}-1)\omega^{-1}_{i}\zeta_{x}\|y^{i+1}-{\widehat{y}}\|^{2}.$

Analogously, from (LABEL:eq:k-nonlinear-ky-p2) and Cauchy’s inequality,

$\displaystyle D_{y}$
$\displaystyle\geq\theta_{y}\|K_{x}(x^{i},{\widehat{y}})-K_{x}(x^{i},y^{i})-K_{xy}(x^{i},y^{i})({\widehat{y}}-y^{i})\|^{p_{y}}-\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2}$
$\displaystyle-\omega_{i}\|x^{i+1}-{\widehat{x}}\|\|K_{x}(x^{i},{\widehat{y}})-K_{x}(x^{i},y^{i})-K_{xy}(x^{i},y^{i})({\widehat{y}}-y^{i})\|.$

This has a structure similar to (73) with $\omega_{i}$ now as a multiplier.
Hence, we apply a similar generalized Young’s inequality to the last term with
any $\zeta_{y}>0$. Noting that $\omega_{i}\leq\overline{\omega}$, we use the
following bound similar to (75):

$\theta_{y}-\|x^{i+1}-{\widehat{x}}\|^{2-p_{y}}\omega_{i}(p_{y}^{p_{y}}\zeta_{y}^{p_{y}-1})^{-1}\geq\theta_{y}-\rho_{x}^{2-p_{y}}\overline{\omega}(p_{y}^{p_{y}}\zeta_{y}^{p_{y}-1})^{-1}\geq
0.$

The last inequality holds for any $\zeta_{y}>0$ if $p_{y}=1$ due to the
assumed $\theta_{y}\geq\overline{\omega}\rho_{x}$ from (24d); otherwise, we
set
$\zeta_{y}:=(\theta_{y}p_{y}^{p_{y}}\rho_{x}^{p_{y}-2}\overline{\omega}^{-1})^{1/(1-p_{y})}$.
We then obtain that

(77)
$D_{y}\geq-\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2}-(p_{y}-1)\omega_{i}\zeta_{y}\|x^{i+1}-{\widehat{x}}\|^{2}.$

Combining (30), (76), and (77), we can thus bound

(78) $\displaystyle D$
$\displaystyle=\eta_{i}D_{x}+\eta_{i+1}D_{y}+\eta_{i+1}D_{\omega}+\eta_{i}(\gamma_{G}-\widetilde{\gamma}_{G}-\xi_{x})\|x^{i+1}-{\widehat{x}}\|^{2}$
$\displaystyle+\eta_{i+1}(\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}}-\xi_{y})\|y^{i+1}-{\widehat{y}}\|^{2}$
$\displaystyle\geq\eta_{i+1}(\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}}-\xi_{y}-(p_{x}-1)\zeta_{x})\|y^{i+1}-{\widehat{y}}\|^{2}-\eta_{i}\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2}$
$\displaystyle+\eta_{i}(\gamma_{G}-\widetilde{\gamma}_{G}-\xi_{x}-(p_{y}-1)\zeta_{y})\|x^{i+1}-{\widehat{x}}\|^{2}-\eta_{i+1}\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2}$
$\displaystyle-\eta_{i}\frac{L_{yx}}{2}(\omega_{i}+2)\rho_{y}\|x^{i+1}-x^{i}\|^{2}$
$\displaystyle\geq-\eta_{i}\frac{\lambda_{x}+L_{yx}(\omega_{i}+2)\rho_{y}}{2}\|x^{i+1}-x^{i}\|^{2}-\eta_{i+1}\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2},$

where in the final step, we have also used (72) and the selected $\zeta_{x}$
and $\zeta_{y}$ if $p_{x}>1$ or $p_{y}>1$ or both. Thus, we obtained exactly
the same lower bound as in (33). We then continue along the rest of the proof
of Theorem 4.2 to obtain the claim.

It is worth observing that when $p_{x}\in(1,2]$ or $p_{y}\in(1,2]$, the
inequalities (72) do not directly bound the respective $\rho_{y}$ or
$\rho_{x}$. Hence, we do not need to initalize the corresponding variable
locally, unlike when $p_{x}=1$ or $p_{y}=1$. On the other hand, sufficient
strong convexity is required from the corresponding $G$ and $F^{*}$.

We start with the lemma ensuring that the iterates stay in the initial
neighborhood of the saddle point.

######  Corollary B.3.

The results of Lemma 5.3 continue to hold if the corresponding conditions of
Theorem 4.2 are replaced with those in Corollary B.1.

######  Proof B.4.

The proof repeats that of Lemma 5.3, applying Corollary B.1 instead of Theorem
4.2 in Step 2.

We next extend the results of Section 6 to arbitrary choices of both
$p_{x}\in[1,2]$ and $p_{y}\in[1,2]$. This mainly consists of verifying (72a)
when $p_{y}\neq 1$ and (72b) when $p_{x}\neq 1$. Note that it is possible to
take $p_{x}=1$ and $p_{y}\neq 1$, or vice versa, as long as the corresponding
conditions are satisfied.

######  Corollary B.5.

The results of Theorem 6.1 continue to hold if Section 3 (iv) is replaced with
Appendix B (ivenumi) for some $p_{x},p_{y}\in[1,2]$, where in case
$p_{y}\in(1,2]$, (46a) is replaced with

(79a) $\displaystyle\xi_{x}$
$\displaystyle=\gamma_{G}-\frac{p_{y}-1}{(\theta_{y}p_{y}^{p_{y}}(2\rho_{x})^{p_{y}-2})^{\frac{1}{p_{y}-1}}},$
and in case $p_{x}\in(1,2]$, (46b) is replaced with (79b)
$\displaystyle\xi_{y}$
$\displaystyle=\gamma_{F^{*}}-\frac{p_{x}-1}{(\theta_{x}p_{x}^{p_{x}}(2\rho_{y})^{p_{x}-2})^{\frac{1}{p_{x}-1}}}.$

######  Proof B.6.

Since conditions (79) are sufficient for (72) with
$\overline{\omega}=\underline{\omega}=1$ to hold, we can repeat the proof of
Theorem 6.1 replacing the references to Theorem 4.2 by references to Corollary
B.1 up until (52). If $p_{x}>1$, we now obtain a lower bound on $d_{i}^{x}$ by
arguing as in (73)–(75) with ${\widehat{u}}$ replaced by $\widebar{u}$.
Specifically, using (16), Appendix B (ivenumi) at $\widebar{u}$, and the
generalized Young’s inequality (74), we obtain for any $\zeta_{x}>0$ that

$\displaystyle d_{i}^{x}$
$\displaystyle\leq-\theta_{x}\|K_{y}(\widebar{x},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})(\widebar{x}-x^{i+1})\|^{p_{x}}$
$\displaystyle+\|y^{i+1}-\widebar{y}\|\|K_{y}(\widebar{x},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})(\widebar{x}-x^{i+1})\|$
$\displaystyle+\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2}-\frac{p_{y}-1}{(\theta_{y}p_{y}^{p_{y}}(2\rho_{x})^{p_{y}-2})^{\frac{1}{p_{y}-1}}}\|x^{i+1}-\widebar{x}\|^{2}$
$\displaystyle\leq\left(\frac{\|y^{i+1}-\widebar{y}\|^{2-p_{x}}}{p_{x}^{p_{x}}\zeta_{x}^{p_{x}-1}}-\theta_{x}\right)\|K_{y}(\widebar{x},y^{i+1})-K_{y}(x^{i+1},y^{i+1})-K_{yx}(x^{i+1},y^{i+1})(\widebar{x}-x^{i+1})\|^{p_{x}}$
$\displaystyle+(p_{x}-1)\zeta_{x}\|y^{i+1}-\widebar{y}\|^{2}+\frac{\lambda_{x}}{2}\|x^{i+1}-x^{i}\|^{2}-\frac{p_{y}-1}{(\theta_{y}p_{y}^{p_{y}}(2\rho_{x})^{p_{y}-2})^{\frac{1}{p_{y}-1}}}\|x^{i+1}-\widebar{x}\|^{2}.$

Inserting
$\zeta_{x}=(\theta_{x}p_{x}^{p_{x}}(2\rho_{y})^{p_{x}-2})^{1/(1-p_{x})}$ and
$\|y^{i+1}-\widebar{y}\|\leq 2\rho_{y}$, we eliminate the first term on the
right-hand side. Likewise, if $p_{y}>1$, similar steps applied to $d_{i}^{y}$
result in

$d_{i}^{y}\leq(p_{y}-1)\zeta_{y}\|x^{i+1}-\widebar{x}\|^{2}+\frac{\lambda_{y}}{2}\|y^{i+1}-y^{i}\|^{2}-\frac{p_{x}-1}{(\theta_{x}p_{x}^{p_{x}}(2\rho_{y})^{p_{x}-2})^{\frac{1}{p_{x}-1}}}\|y^{i+1}-\widebar{y}\|^{2}$

for $\zeta_{y}=(\theta_{y}p_{y}^{p_{y}}(2\rho_{x})^{p_{y}-2})^{1/(p_{y}-1)}$.
Using $\|u^{i+1}-u^{i}\|\to 0$ and the selection of $\zeta_{x}$ and
$\zeta_{y}$, we then obtain the desired estimate
$\limsup_{i\rightarrow\infty}~{}q_{i}:=\limsup_{i\rightarrow\infty}~{}(d_{i}^{x}+d_{i}^{y}+O(\|u^{i+1}-u^{i}\|))\leq
0$.

######  Corollary B.7.

The results of Theorem 6.4 continue to hold if Section 3 (iv) is replaced with
Appendix B (ivenumi) for some $p_{x},p_{y}\in[1,2]$, where in case
$p_{y}\in(1,2]$, (53a) is replaced for some $\widetilde{\gamma}_{G}>0$ with

(80a) $\displaystyle\xi_{x}$
$\displaystyle=\gamma_{G}-\widetilde{\gamma}_{G}-\frac{p_{y}-1}{(\theta_{y}p_{y}^{p_{y}}(\rho_{x})^{p_{y}-2})^{\frac{1}{p_{y}-1}}},$
and in case $p_{x}\in(1,2]$, (53b) is replaced with (80b)
$\displaystyle\xi_{y}$
$\displaystyle=\gamma_{F^{*}}-\frac{p_{x}-1}{(\theta_{x}p_{x}^{p_{x}}(\rho_{y})^{p_{x}-2})^{\frac{1}{p_{x}-1}}}.$

######  Proof B.8.

Conditions (80) are sufficient for (72) with
$\overline{\omega}=\underline{\omega}=1$ to hold; therefore, we can repeat the
proof of Theorem 6.4 replacing the references to Theorem 4.2 by references to
Corollary B.1.

######  Corollary B.9.

The results of Theorem 6.6 continue to hold if Section 3 (iv) is replaced with
Appendix B (ivenumi) for some $p_{x},p_{y}\in[1,2]$, where in case
$p_{y}\in(1,2]$, (56a) is replaced for some $\widetilde{\gamma}_{G}>0$ with

(81a) $\displaystyle\xi_{x}$
$\displaystyle=\gamma_{G}-\widetilde{\gamma}_{G}-\frac{p_{y}-1}{(\theta_{y}p_{y}^{p_{y}}(\rho_{x})^{p_{y}-2}\omega^{-1})^{\frac{1}{p_{y}-1}}},$
and in case $p_{x}\in(1,2]$, (56b) is replaced for some
$\widetilde{\gamma}_{F^{*}}>0$ with (81b) $\displaystyle\xi_{y}$
$\displaystyle=\gamma_{F^{*}}-\widetilde{\gamma}_{F^{*}}-\frac{p_{x}-1}{(\omega\theta_{x}p_{x}^{p_{x}}(\rho_{y})^{p_{x}-2})^{\frac{1}{p_{x}-1}}}.$

######  Proof B.10.

Conditions (81) are sufficient for (72) with
$\overline{\omega}=\underline{\omega}=\omega$ to hold; therefore, we can
repeat the proof of Theorem 6.6 replacing the references to Theorem 4.2 by
references to Corollary B.1.

######  Corollary B.11.

The results of Proposition 6.9 continue to hold if the corresponding
conditions of Theorem 6.1, 6.4, or 6.6 are replaced with those in Corollary
B.5, B.7, or B.9.

######  Proof B.12.

The proof repeats that of Proposition 6.9.

##  Appendix C Verification of conditions for step function presentation and
Potts model

Throughout this section, we set $\rho(t):=2t-t^{2}$ and
$\kappa(x,y):=\rho(\langle x,y\rangle)$ for $x,y\in\mathbb{R}^{m}$. Then
$\rho^{\prime}(t)=2(1-t)$ so that

(82a) $\displaystyle\kappa_{x}(x,y)$ $\displaystyle=2y(1-\langle y,x\rangle)$
and $\displaystyle\kappa_{xy}(x,y)$ $\displaystyle=2(I-\langle y,x\rangle
I-y\otimes x),$ (82b) $\displaystyle\kappa_{y}(x,y)$
$\displaystyle=2x(1-\langle x,y\rangle)$ and $\displaystyle\kappa_{yx}(x,y)$
$\displaystyle=2(I-\langle x,y\rangle I-x\otimes y),$

where $a\otimes b\in\mathbb{R}^{n\times n}$ is the tensor product between two
vectors $a$ and $b$, producing a matrix of all the combinations of products
between the entries.

The following lemma verifies Section 3 for $K=\kappa$.

######  Lemma C.1.

Let $R_{K}>2$, and suppose ${\widehat{x}},{\widehat{y}}\in\mathbb{R}^{m}$ for
$m\geq 1$ with

(83) $0\leq\langle{\widehat{x}},{\widehat{y}}\rangle
I+{\widehat{x}}\otimes{\widehat{y}}\leq 2I.$

Then the function $K=\kappa$ defined above satisfies Section 3 for some
$\theta_{x},\theta_{y}>0$ and some $\rho_{x},\rho_{y}>0$ dependent on $R_{K}$
with

$\displaystyle L_{x}(y)$ $\displaystyle=2|y|_{2}^{2},$ $\displaystyle
L_{y}(x)$ $\displaystyle=2|x|_{2}^{2},$ $\displaystyle L_{yx}$
$\displaystyle=4(|{\widehat{y}}|_{2}+\rho_{y}),$

as well as the constants $\xi_{x},\xi_{y}\in\mathbb{R}$,
$\lambda_{x},\lambda_{y}\geq 0$ satisfying
$\lambda_{x}\xi_{x}>2(\lambda_{x}+|{\widehat{y}}|_{2}^{2})|{\widehat{y}}|_{2}^{2}$,
$\xi_{y}>0$, and $\lambda_{y}>|{\widehat{x}}|_{2}^{2}$.

######  Proof C.2.

First, Section 3 (i) holds everywhere since $K\in C^{\infty}(\mathbb{R}^{m})$.
To verify Section 3 (ii), we observe using (82) that

(84a) $\displaystyle\kappa_{x}(x^{\prime},y)-\kappa_{x}(x,y)$
$\displaystyle=2(y\otimes y)(x-x^{\prime}),$ (84b)
$\displaystyle\kappa_{xy}(x,y^{\prime})-\kappa_{xy}(x,y)$
$\displaystyle=2\langle y-y^{\prime},x\rangle I+2(y-y^{\prime})\otimes x,$
(84c) $\displaystyle\kappa_{y}(x,y^{\prime})-\kappa_{y}(x,y)$
$\displaystyle=2(x\otimes x)(y-y^{\prime}),$ (84d)
$\displaystyle\kappa_{yx}(x^{\prime},y)-\kappa_{yx}(x,y)$
$\displaystyle=2\langle x-x^{\prime},y\rangle I+2(x-x^{\prime})\otimes y.$

Hence $L_{x}$, $L_{y}$, and $L_{yx}$ are as claimed.

To verify Section 3 (iii), we first of all observe using (83) that

$|\kappa_{xy}({\widehat{x}},{\widehat{y}})|_{2}=2|I-\langle{\widehat{y}},{\widehat{x}}\rangle
I-{\widehat{y}}\otimes{\widehat{x}}|_{2}\leq 2.$

Therefore
$\sup_{(x,y)\in\vmathbb{B}({\widehat{x}},\rho_{x})\times\vmathbb{B}({\widehat{y}},\rho_{y})}|\kappa_{xy}(x,y)|_{2}\leq
R_{K}$ for some $\rho_{x},\rho_{y}>0$ dependent on $R_{K}>2$.

Finally, to verify Section 3 (iv), we start with (15a), i.e.,

$\langle\kappa_{x}(x^{\prime},{\widehat{y}})-\kappa_{x}({\widehat{x}},{\widehat{y}}),x-{\widehat{x}}\rangle+\xi_{x}|x-{\widehat{x}}|_{2}^{2}\geq\theta_{x}|\kappa_{y}({\widehat{x}},y)-\kappa_{y}(x,y)-\kappa_{yx}(x,y)({\widehat{x}}-x)|_{2}-\frac{\lambda_{x}}{2}|x-x^{\prime}|_{2}^{2}.$

Expanding the equation using (82), (84), and

$\displaystyle\kappa_{y}({\widehat{x}},y)$
$\displaystyle-\kappa_{y}(x,y)-\kappa_{yx}(x,y)({\widehat{x}}-x)$
$\displaystyle=2{\widehat{x}}(1-\langle{\widehat{x}},y\rangle)-2x(1-\langle
x,y\rangle)-2(I-\langle x,y\rangle I-x\otimes y)({\widehat{x}}-x)$
$\displaystyle=2[\langle x,y\rangle
x-\langle{\widehat{x}},y\rangle{\widehat{x}}+(\langle x,y\rangle I+x\otimes
y)({\widehat{x}}-x)]$ $\displaystyle=2[\langle
x-{\widehat{x}},y\rangle{\widehat{x}}+(x\otimes y)({\widehat{x}}-x)]$
$\displaystyle=-2(({\widehat{x}}-x)\otimes y)({\widehat{x}}-x),$

we require that

(85)
$2\langle{\widehat{x}}-x^{\prime},x-{\widehat{x}}\rangle_{{\widehat{y}}\otimes{\widehat{y}}}+\xi_{x}|x-{\widehat{x}}|_{2}^{2}\geq
2\theta_{x}|y|_{2}|x-{\widehat{x}}|_{2}^{2}-\frac{\lambda_{x}}{2}|x-x^{\prime}|_{2}^{2}.$

Taking any $\alpha>0$, this will hold by Cauchy’s and Young’s inequalities if
$\xi_{x}\geq(2+\alpha)|{\widehat{y}}|_{2}^{2}+2\theta_{x}|y|_{2}$ and
$\lambda_{x}/2\geq\alpha^{-1}|{\widehat{y}}|_{2}^{2}$. If
$|{\widehat{y}}|_{2}=0$, clearly these hold for some $\alpha,\theta_{x}>0$.
Otherwise, solving $\alpha$ from the latter as an equality, i.e., taking
$\alpha=2\lambda^{-1}_{x}|{\widehat{y}}|_{2}^{2}$, the former holds if
$\xi_{x}\geq
2(1+\lambda^{-1}_{x}|{\widehat{y}}|_{2}^{2})|{\widehat{y}}|_{2}^{2}+2\theta_{x}|y|_{2}$.
If
$\lambda_{x}\xi_{x}>2(\lambda_{x}+|{\widehat{y}}|_{2}^{2})|{\widehat{y}}|_{2}^{2}$,
this holds for some $\theta_{x},\rho_{x},\rho_{y}>0$ in a neighborhood
$\vmathbb{B}({\widehat{x}},\rho_{x})\times\vmathbb{B}({\widehat{y}},\rho_{y})$
of (${\widehat{x}},{\widehat{y}})$.

It remains to verify (LABEL:eq:k-nonlinear-ky), i.e.,

$\langle\kappa_{y}(x,y)-\kappa_{y}(x,y^{\prime})+\kappa_{y}({\widehat{x}},{\widehat{y}})-\kappa_{y}({\widehat{x}},y),y-{\widehat{y}}\rangle+\xi_{y}|y-{\widehat{y}}|_{2}^{2}\\\
\geq\theta_{y}|\kappa_{x}(x^{\prime},{\widehat{y}})-\kappa_{x}(x^{\prime},y^{\prime})-\kappa_{xy}(x^{\prime},y^{\prime})({\widehat{y}}-y^{\prime})|_{2}-\frac{\lambda_{y}}{2}|y-y^{\prime}|_{2}^{2}.$

Again, using (82) and (84) we expand this as

$2\langle y^{\prime}-y,y-{\widehat{y}}\rangle_{x\otimes
x}+2|y-{\widehat{y}}|_{{\widehat{x}}\otimes{\widehat{x}}}^{2}+\xi_{y}|y-{\widehat{y}}|_{2}^{2}\geq
2\theta_{y}|x^{\prime}|_{2}|y^{\prime}-{\widehat{y}}|_{2}^{2}-\frac{\lambda_{y}}{2}|y-y^{\prime}|_{2}^{2}.$

Rearranging the $\theta_{y}$-term, we see that this holds if

$2\langle y^{\prime}-y,y-{\widehat{y}}\rangle_{x\otimes
x-2\theta_{y}|x^{\prime}|_{2}I}+2|y-{\widehat{y}}|^{2}_{{\widehat{x}}\otimes{\widehat{x}}}+(\xi_{y}-2\theta_{y})|x^{\prime}|_{2}|y-{\widehat{y}}|_{2}^{2}\geq\left(2\theta_{y}|x^{\prime}|_{2}-\frac{\lambda_{y}}{2}\right)|y^{\prime}-y|_{2}^{2}.$

Rearranging and estimating the first term as

$\displaystyle 2\langle y^{\prime}-y,y-{\widehat{y}}\rangle_{x\otimes
x-2\theta_{y}|x^{\prime}|_{2}I}$ $\displaystyle=2\langle
y^{\prime}-y,x\rangle\langle
y-{\widehat{y}},x\rangle-4\theta_{y}|x^{\prime}|_{2}\langle
y^{\prime}-y,y-{\widehat{y}}\rangle$
$\displaystyle\geq-2|y-{\widehat{y}}|^{2}_{x\otimes
x}-\frac{1}{2}|y^{\prime}-y|^{2}_{x\otimes
x}-4\theta_{y}|x^{\prime}|_{2}|y^{\prime}-y|_{2}^{2}-\theta_{y}|x^{\prime}|_{2}|y-{\widehat{y}}|_{2}^{2}$

and then using Young’s inequality on both parts, we obtain the condition

$2\left(|y-{\widehat{y}}|^{2}_{{\widehat{x}}\otimes{\widehat{x}}}-|y-{\widehat{y}}|^{2}_{x\otimes
x}\right)+(\xi_{y}-3\theta_{y})|x^{\prime}|_{2}|y-{\widehat{y}}|_{2}^{2}\geq\left(\frac{1}{2}|x|_{2}^{2}+6\theta_{y}|x^{\prime}|_{2}-\frac{\lambda_{y}}{2}\right)|y^{\prime}-y|_{2}^{2}.$

If $\xi_{y}>0$ and $\lambda_{y}>|{\widehat{x}}|_{2}^{2}$, this holds for some
$\theta_{y},\rho_{y},\rho_{x}>0$ in
$\vmathbb{B}({\widehat{x}},\rho_{x})\times\vmathbb{B}({\widehat{y}},\rho_{y})$.

We comment on the condition (83) on the primal–dual solutions pair
${\widehat{x}},{\widehat{y}}\in\mathbb{R}$. First, for $m=1$, this condition
reduces to ${\widehat{x}}{\widehat{y}}\in[0,1]$. This is necessarily satisfied
in the case of the step function (where $f^{*}=\delta_{[0,\infty)}$) and in
the case of the $\ell^{0}$ function (where $f^{*}=0$) as in both cases,
${\widehat{x}}{\widehat{y}}\in\\{0,1\\}$ by the dual optimality condition
$\kappa_{y}({\widehat{x}},{\widehat{y}})\in\partial f^{*}({\widehat{y}})$.
Furthermore, if we take
$f^{*}_{\gamma}=\frac{\gamma}{2}|\,\boldsymbol{\cdot}\,|_{2}^{2}$ for some
$\gamma\geq 0$, then for any $m\geq 1$ the dual optimality condition reads
$2{\widehat{x}}(1-\langle{\widehat{x}},{\widehat{y}}\rangle)=\gamma{\widehat{y}}$,
i.e, ${\widehat{y}}=2{\widehat{x}}(\gamma+2|{\widehat{x}}|_{2}^{2})^{-1}$, for
which (83) is easily verified.

The following lemma shows that Section 3 remains valid if we include a linear
operator in the primal component.

######  Lemma C.3.

Let $K(x,y)=\widetilde{K}(Ax,y)$ for some $A\in\mathcal{L}(X;Z)$ and
$\widetilde{K}\in C^{1}(Z\times Y)$ on Hilbert spaces $X,Y,Z$. Suppose
$\widetilde{K}$ satisfies Section 3 at
$({\widehat{z}},{\widehat{y}}):=(A{\widehat{x}},{\widehat{y}})$. Mark the
corresponding constants with a tilde: $\widetilde{L}_{z}$,
$\widetilde{R}_{K}$, and so on. Then $K$ satisfies Section 3 with
$R_{K}:=\widetilde{R}_{K}\|A\|$; $\xi_{x}=\|A\|\widetilde{\xi}_{z}$,
$\xi_{y}=\widetilde{\xi}_{y}$; $\lambda_{x}=\|A\|\widetilde{\lambda}_{z}$,
$\lambda_{y}=\widetilde{\lambda}_{y}$; $\theta_{x}=\widetilde{\theta}_{z}$,
$\theta_{y}=\widetilde{\theta}_{y}\|A\|^{-1}$;
$\rho_{x}=\|A\|^{-1}\widetilde{\rho}_{x}$, and $\rho_{y}=\widetilde{\rho}_{y}$
as well as

(86) $\displaystyle L_{x}(y)$ $\displaystyle=\|A\|^{2}\widetilde{L}_{z}(y),$
$\displaystyle L_{y}(x)$ $\displaystyle=\widetilde{L}_{y}(Ax),$ $\displaystyle