remarkRemark hypothesisHypothesis claimClaim Full splitting algorithm for
structured fractional programsRadu Ioan Boţ, Guoyin Li, and Min Tao

# A full splitting algorithm for fractional programs with structured
numerators and denominators ††thanks: Submitted to the editors DATE. The
research of RIB has been partially supported by the Austrian Science Fund
(FWF), project number W1260-N35. The research of MT has been partially
supported by the Natural Science Foundation of China (No. 11971228), by the
Jiangsu University QingLan Project, and by the China Scholarship Council
(202006195015) and it has been conducted during her research visit at the
University of Vienna in 2023.

Radu Ioan Boţ Faculty of Mathematics, University of Vienna, A-1090 Vienna,
Austria<EMAIL_ADDRESS>Guoyin Li Department of Applied Mathematics,
University of New South Wales, Sydney 2052, Australia<EMAIL_ADDRESS>Min
Tao Department of Mathematics, National Key Laboratory for Novel Software
Technology, Nanjing University, Nanjing, 210093, Republic of China,
<EMAIL_ADDRESS>
###### Abstract

In this paper, we consider a class of nonconvex and nonsmooth fractional
programming problems, which involve the sum of a convex, possibly nonsmooth
function composed with a linear operator and a differentiable, possibly
nonconvex function in the numerator and a convex, possibly nonsmooth function
composed with a linear operator in the denominator. These problems have
applications in various fields, including CT reconstruction and sparse signal
recovery. We propose an adaptive full-splitting proximal subgradient algorithm
with an extrapolated step that addresses the challenge of evaluating the
composition in the numerator by decoupling the linear operator from the
nonsmooth component. We specifically evaluate the nonsmooth function using its
proximal operator, while the linear operator is assessed through forward
evaluations. Furthermore, the smooth component in the numerator is evaluated
through its gradient, the nonsmooth component in the denominator is managed
using its subgradient, and the linear operator in the denominator is also
assessed through forward evaluations. We demonstrate subsequential convergence
toward an approximate lifted stationary point and ensure global convergence
under the Kurdyka-Łojasiewicz property, all achieved without relying on any
full-row rank assumptions regarding the linear operators. We further explain
the reasoning behind aiming for an approximate lifted stationary point. This
is exemplified by constructing a scenario illustrating that the algorithm
could diverge when seeking exact solutions. Lastly, we present a practical
iteration of the algorithm incorporating a nonmonotone line search,
significantly enhancing its convergence performance. Our theoretical findings
are validated through simulations involving limited-angle CT reconstruction
and the robust sharp ratio minimization problem.

###### keywords:

structured fractional programs, full splitting algorithm, convergence
analysis, lifted stationary points, Kurdyka-Łojasiewicz property, nonmonotone
line search

90C26, 90C32, 49M27, 65K05

##  1 Introduction

In this paper, we consider the following class of nonsmooth and nonconvex
fractional programs:

(1) $\displaystyle\min_{\mathbf{x}\in{\cal
S}}F({\mathbf{x}}):=\frac{g(A{\mathbf{x}})+h({\mathbf{x}})}{f(K{\mathbf{x}})},$

where ${\cal S}$ is a nonempty convex and compact subset of
${\mathbb{R}}^{n}$,
$f:{\mathbb{R}}^{p}\rightarrow{\overline{\mathbb{R}}}:={\mathbb{R}}\cup\\{+\infty\\}$
and $g:{\mathbb{R}}^{s}\rightarrow{\overline{\mathbb{R}}}$ are proper, convex
and lower semicontinuous functions;
$A:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{s}$ and
$K:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{p}$ are linear operators;
$h:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}$ is a (possibly nonconvex)
differentiable function over an open set containing ${\cal S}$ and its
derivative $\nabla h$ is Lipschitz continuous over this open set with a
Lipschitz constant $L_{\nabla h}$. To ensure the model problem is well-
defined, we also assume for the denominator that $f(K{\mathbf{x}})>0$ for all
$\mathbf{x}\in{\cal S}$. For more detailed assumptions, we direct the reader
to our subsequent sections.

Problem (1) falls within the category of single ratio fractional programming
problems. However, it showcases a more intricate structure compared to, for
instance, the problems discussed in [7] and [9]. In the specific scenario
where the linear operators $A$ and $K$ are identity mappings (represented as
$I$), the model (1) simplifies to the problem addressed in [25].

The model (1) encompasses a variety of optimization problems stemming from
diverse domains. These include the limited-angle CT reconstruction problem
[23, 32], robust sharp ratio minimization [14], the first stage of the single-
period optimal portfolio selection problem involving a risk-free asset [27],
the recently introduced scale-invariant sparse signal reconstruction problem
[31, 25, 35], and their respective extensions. Subsequently, we offer a few
illustrative examples to demonstrate the nature of the model problem (1).

(a) The limited-angle CT reconstruction problem aims at reconstructing the
true image from limited-angle scanning measurements, with prescribed known
bounds. By representing an image as an $(n\times n)$ matrix, it can be
mathematically formulated as

(2) $\displaystyle\min_{{\mathbf{x}}\in{\cal
B}}\frac{\tau\|\nabla{\mathbf{x}}\|_{1}+\frac{1}{2}\|P{\mathbf{x}}-{\mathbf{f}}\|^{2}}{\|\nabla{\mathbf{x}}\|_{p}},$

where $1<p\leq+\infty$, $P$ is the projection operator, ${\mathbf{f}}$ the
given measurement data and $\tau>0$ a regularization parameter. The linear
operator ${\nabla}:{\mathbb{R}}^{n\times n}\mapsto{\mathbb{R}}^{n\times
n}\times{\mathbb{R}}^{n\times n}$ denotes the discrete gradient operator
defined as
${\nabla{\mathbf{v}}}=\left(\nabla_{\mathbf{x}}{\mathbf{v}},\nabla_{\mathbf{y}}{\mathbf{v}}\right),$
where ${\nabla}_{\mathbf{x}},{\nabla}_{\mathbf{y}}:{\mathbb{R}}^{n\times
n}\mapsto{\mathbb{R}}^{n\times n}$ are the forward horizontal and vertical
difference operators, respectively. Regarding the box constraint ${\cal
B}:=[{\mathbf{l}},{\mathbf{u}}]\subseteq\mathbb{R}^{n\times n}$, representing
the prescribed bounds for the true image to be reconstructed [32], we assume
that ${\cal B}\cap{\text{span}}({\bf E})=\emptyset$, where ${\bf E}$ is the
matrix with all entries equal to one. This condition is imposed to exclude
images where each pixel has a constant level, which does not correspond to
reality.

By identifying the matrix space $\mathbb{R}^{n\times n}$ as the Euclidean
space $\mathbb{R}^{n^{2}}$, problem (2) can be written as a special case of
(1) with $g({\mathbf{x}}):=\tau\|{\mathbf{x}}\|_{1}$,
$f({\mathbf{x}}):=\|{\mathbf{x}}\|_{p}$, $A=K=\nabla$,
$h({\mathbf{x}}):=\frac{1}{2}\|P{\mathbf{x}}-{\mathbf{f}}\|^{2}$, and ${\cal
S}:={\cal B}$. Here, $\|\cdot\|_{p}$ denotes the usual $\ell_{p}$-norm for
$1\leq p\leq\infty$, while for $p=2$ we will simply write $\|\cdot\|_{2}$ as
$\|\cdot\|$.

(b) Robust sharp ratio minimization problem. The robust sharp ratio
optimization problem under scenario data uncertainty, which arises in finance,
takes the form

(3) $\min_{{\mathbf{x}}\in\Delta}\frac{\max_{1\leq i\leq
m_{1}}\\{r_{i}-{\mathbf{a}}_{i}^{\top}{\mathbf{x}}\\}}{\max_{1\leq i\leq
m_{2}}{\mathbf{x}}^{\top}C_{i}{\mathbf{x}}},$

where
$\Delta=\\{{\mathbf{x}}\in\mathbb{R}^{n}\,|\,{\mathbf{e}}^{\top}{\mathbf{x}}=1,{\mathbf{x}}\geq
0\\}$ with ${\mathbf{e}}=(1,\ldots,1)\in\mathbb{R}^{n}$,
$({\mathbf{a}}_{i},r_{i})\in{\mathbb{R}}^{n}\times{\mathbb{R}}$,
$i=1,\ldots,m_{1}$, are such that
$r_{i}-{\mathbf{a}}_{i}^{\top}{\mathbf{x}}\geq 0$ for all
$\mathbf{x}\in\Delta$, and $C_{i}$, $i=1,\ldots,m_{2}$, are positive definite
matrices. We recall that the standard sharp ratio optimization problem without
data uncertainty reads as (for example, see [14])

(4)
$\displaystyle\max_{\mathbf{x}\in{\Delta}}\frac{{\mathbf{a}}^{\top}{\mathbf{x}}-{r}}{{\mathbf{x}}^{\top}C{\mathbf{x}}},$

where $C\in\operatorname{\mathbb{R}}^{n\times n}$ is a symmetric positive
definite matrix and $(\mathbf{a},r)\in\mathbb{R}^{n}\times\mathbb{R}$. Here,
without loss of generality, we assume that
${\mathbf{a}}^{\top}{\mathbf{x}}-{r}\geq 0$ for all $\mathbf{x}\in\Delta$.
Suppose that the data $(\mathbf{a},r)$ and $C$ are subject to scenario
uncertainty, that is,

$(\mathbf{a},r)\in\mathcal{U}_{1}=\\{(\mathbf{a}_{1},\overline{r}_{1}),\ldots,(\mathbf{a}_{m_{1}},\overline{r}_{m_{1}})\\}\mbox{
and }C\in\mathcal{U}_{2}=\\{C_{1},\ldots,C_{m_{2}}\\},$

where
$({\mathbf{a}}_{i},\overline{r}_{i})\in{\mathbb{R}}^{n}\times{\mathbb{R}}$,
$i=1,\ldots,m_{1}$, are such that
${\mathbf{a}}_{i}^{\top}{\mathbf{x}}-\overline{r}_{i}\geq 0$ for all
${\mathbf{x}}\in\Delta$ and $C_{i}$, $i=1,\ldots,m_{2}$, are positive definite
matrices. Then, the robust counterpart of the above sharp ratio optimization
problem is

$\displaystyle\max_{{\mathbf{x}}\in\Delta}\min_{\begin{subarray}{c}(a,r)\in\mathcal{U}_{1},\\\
C\in\mathcal{U}_{2}\end{subarray}}\frac{{\mathbf{a}}^{\top}{\mathbf{x}}-r}{{\mathbf{x}}^{\top}C{\mathbf{x}}}=\max_{{\mathbf{x}}\in\Delta}\frac{\min_{1\leq
i\leq
m_{1}}\\{{\mathbf{a}}_{i}^{\top}{\mathbf{x}}-\overline{r}_{i}\\}}{\max_{1\leq
i\leq m_{2}}{\mathbf{x}}^{\top}C_{i}{\mathbf{x}}},$

which can be further equivalently rewritten as
$\displaystyle\min_{{\mathbf{x}}\in\Delta}\frac{\max_{1\leq i\leq
m_{1}}\\{\overline{r}_{i}-{\mathbf{a}}_{i}^{\top}{\mathbf{x}}\\}}{\max_{1\leq
i\leq m_{2}}{\mathbf{x}}^{\top}C_{i}{\mathbf{x}}}$. By adding a positive
constant if necessary (without affecting the solutions), we then obtain the
formulation (3).

Direct verification shows that (3) is a special case of our model problem (1)
with $f({\mathbf{x}}_{\bf 1},\cdots,{\mathbf{x}}_{m_{2}}):=\max_{1\leq i\leq
m_{2}}\|{\mathbf{x}}_{i}\|^{2}_{2}$,
$K:\mathbf{x}\mapsto(C_{1}^{1/2}\mathbf{x},\cdots,C^{1/2}_{m_{2}}\mathbf{x})$,
$g(\mathbf{x}):=\|{\mathbf{r}}-{\mathbf{x}}\|_{\infty}$ with
${\mathbf{r}}:=(r_{1},\ldots,r_{m_{1}})$,
$A:\mathbf{x}\mapsto({\mathbf{a}}_{1}^{\top}\mathbf{x},{\mathbf{a}}_{2}^{\top}\mathbf{x},\cdots,{\mathbf{a}}_{m_{1}}^{\top}\mathbf{x})^{\top}$,
$h({\mathbf{x}})=0$ and ${\cal S}:=\Delta$.

The conventional approach to tackling single ratio fractional programming
problems commonly involves utilizing Dinkelbach’s method or its variants [17,
22]. The recent monograph [16] comprehensively explores Dinkelbach’s
algorithm, incorporating surrogation as a mechanism to overcome the inherent
nonconvexity of the resultant subproblems. However, solving the problem (1)
via Dinkelbach’s method (or its variants) might prove to be expensive and
challenging due to the presence of linear compositions both in numerator and
denominator.

For solving simple single ratio problems, where compositions of nonsmooth
functions with linear operators do not occur, various splitting algorithms
have been proposed in a series of recent works [7, 8, 9, 25]. These methods
share the feature that at every iterative step, instead of invoking an inner
loop aimed at solving the resulting Dinkelbach’s scalarization of the
fractional program, they execute only one iterative of a suitable splitting
algorithm and updates the sequence of function values.

Our objective is to devise an algorithm for solving (1) employing the full
splitting paradigm [13, 10, 19]. To tackle this challenge, we take inspiration
from recent works such as [13, 25], developing an adaptive full-splitting
proximal subgradient algorithm with an extrapolated step (Adaptive FSPS). In
this approach, the linear operator in the numerator is evaluated through
forward assessments. Using the technique of conjugate unfolding, it is
disentangled from the nonsmooth component, which is evaluated via its proximal
operator. Furthermore, the smooth component in the numerator is evaluated
through its gradient, the nonsmooth component in the denominator is managed
using its subgradient, and the linear operator in the denominator is also
assessed through forward evaluations.

The adaptive strategy, another notable feature of the algorithm, involves a
backtracking approach implemented to ensure the preservation of positivity in
the sequence of augmented function values. This property plays a crucial role
in the convergence analysis. We incorporate an extrapolated step to update the
primal sequence, differing from the inertial steps in [7, 8]. This step serves
to foster positivity in the sequence of augmented function values and enhance
the convergence performance of the algorithm. We prove subsequential
convergence toward an approximate lifted stationary point and ensure global
convergence under the Kurdyka-Lojasiewicz property. Unlike existing primal-
dual splitting approaches for nonconvex problems [11, 12, 21, 24, 28], the
global convergence of Adaptive FSPS is established without imposing full-row
rank assumptions on the involved linear operators. Furthermore, we elucidate
the rationale behind striving for an approximate lifted stationary point. To
illustrate this fact, we also construct a scenario demonstrating that a
natural adaptation of the algorithm in seeking exact stationary solutions
could easily diverge.

Additionally, we devise a practical version of the algorithm by integrating a
nonmonotone line search [32, 36] to enhance convergence. The motivation behind
developing the nonmonotone line search is to enable larger step sizes for the
relevant subproblem, facilitating aggressive progress supported by a recent
study [18].

The rest of this paper is structured as follows. Section 2 presents the
necessary preliminary notions and results, while Section 3 introduces the
stationarity notions used in this paper and explores their relationships. In
Section 4, we introduce Adaptive FSPS and discuss the benefits of integrating
the extrapolated step and adopting an adaptive version. Section 5 and Section
6 are dedicated to establishing subsequential and global convergence
properties of Adaptive FSPS under the Kurdyka-Łojasiewicz assumption,
respectively. Section 7 introduces a practical adaptation of Adaptive FSPS by
integrating nonmonotone line search, aiming to reduce dependence on unknown
parameters. Furthermore, we conduct numerical experiments demonstrating the
promising performance of this practical algorithm in two specific
applications. Lastly, Section 8 contains our conclusions.

##  2 Preliminaries and calculus rules

In this section, we will introduced some notions and preliminary results that
will be utilized throughout the paper. Finite-dimensional spaces within the
paper will be equipped with the Euclidean norm, denoted by $\|\cdot\|$, while
$\langle\cdot,\cdot\rangle$ will represent the Euclidean scalar product. Given
a set ${\cal C}\subseteq{\mathbb{R}}^{n}$, ${\text{ri}}({\cal C})$ and
${\text{int}}({\cal C})$ denote its relative interior and its interior,
respectively. The function $\iota_{\cal
C}:{\mathbb{R}}^{n}\rightarrow{\overline{\mathbb{R}}}:={\mathbb{R}}\cup\\{+\infty\\}$,
defined by $\iota_{\cal C}({\mathbf{x}})=0$, for ${\mathbf{x}}\in{\cal C}$,
and $\iota_{\cal C}({\mathbf{x}})=+\infty$, otherwise, denotes the indicator
function of the set ${\cal C}$.

For a function $f:{\mathbb{R}}^{n}\rightarrow{\overline{\mathbb{R}}}$, we
denote by
$\operatorname*{dom}f:=\\{{\mathbf{x}}\in{\mathbb{R}}^{n}:f({\mathbf{x}})<+\infty\\}$
its effective domain and say that it is proper if
$\operatorname*{dom}f\neq\emptyset$. For
$\overline{\mathbf{x}}\in\operatorname*{dom}f$, the set

${\hat{\partial}}f({\overline{\mathbf{x}}}):=\left\\{{\mathbf{v}}\in{\mathbb{R}}^{n}:{\liminf\limits_{\mathbf{x}\to{\overline{\mathbf{x}}}\;{\mathbf{x}}\neq{\overline{\mathbf{x}}}}}\frac{f(\mathbf{x})-f(\overline{\mathbf{x}})-\langle{\mathbf{v}},{\mathbf{x}}-{\overline{\mathbf{x}}}\rangle}{\|{\mathbf{x}}-\overline{\mathbf{x}}\|}\geq
0\right\\}$

is the so-called Fréchet subdifferential of $f$ at $\overline{\mathbf{x}}$.
The limiting subdifferential of $f$ at $\overline{\mathbf{x}}$ is defined as

$\partial
f({\overline{\mathbf{x}}}):=\left\\{{\mathbf{v}}\in\operatorname{\mathbb{R}}^{n}\\!:\\!\exists\;\\{{\mathbf{x}}^{k}\\}\rightarrow{\overline{\mathbf{x}}},\
f({\mathbf{x}}^{k})\rightarrow
f(\overline{\mathbf{x}}),\\{{\mathbf{v}}^{k}\\}\rightarrow{\mathbf{v}}\
\text{as}\ k\rightarrow+\infty,\
{\mathbf{v}}^{k}\in{\hat{\partial}}f({\mathbf{x}}^{k})\right\\}.$

If $f$ is proper, convex and lower semicontinuous function and
$\varepsilon\geq 0$, we denote by

(5)
$\partial_{\varepsilon}f(\overline{\mathbf{x}}):=\\{{\mathbf{v}}\in\operatorname{\mathbb{R}}^{n}:f({\mathbf{x}})\geq
f(\overline{\mathbf{x}})+{\mathbf{v}}^{\top}({\mathbf{x}}-\overline{\mathbf{x}})-\varepsilon\
\forall{\mathbf{x}}\in\operatorname{\mathbb{R}}^{n}\\}$

the $\varepsilon$-subdifferential of $f$ at $\overline{\mathbf{x}}$. It holds
${\mathbf{v}}\in\partial_{\varepsilon}f(\overline{\mathbf{x}})$ if and only if
$f^{*}({\mathbf{v}})+f(\overline{{\mathbf{x}}})-\langle{\mathbf{v}},\overline{\mathbf{x}}\rangle\leq\varepsilon$,
where $f^{*}:\operatorname{\mathbb{R}}^{n}\rightarrow{\overline{\mathbb{R}}}$,
$f^{*}({\mathbf{v}})=\sup_{{\mathbf{x}}\in\operatorname{\mathbb{R}}^{n}}\\{\langle{\mathbf{v}},{\mathbf{x}}\rangle-f({\mathbf{x}})\\}$,
denotes the (Fenchel) conjugate function of $f$. The convex subdifferential of
$f$ at $\overline{\mathbf{x}}$ is defined by $\partial
f(\overline{\mathbf{x}}):=\partial_{0}f(\overline{\mathbf{x}})$ and it
coincides in this case with the Fréchet and the limiting subdifferential. It
holds ${\mathbf{v}}\in\partial f(\overline{\mathbf{x}})$ if and only if
$f^{*}({\mathbf{v}})+f(\overline{{\mathbf{x}}})=\langle{\mathbf{v}},\overline{\mathbf{x}}\rangle$.
If ${\overline{\mathbf{x}}}\notin\operatorname*{dom}f$, we set
${\hat{\partial}}f({\overline{\mathbf{x}}})=\partial_{\varepsilon}f(\overline{\mathbf{x}})=\partial
f(\overline{\mathbf{x}})=\emptyset$. The domain of the convex subdifferential
is defined as $\operatorname*{dom}(\partial
f):=\\{{\mathbf{x}}\in\operatorname{\mathbb{R}}^{n}:\partial
f({\mathbf{x}})\neq\emptyset\\}$.

For a proper, convex lower semicontinuous function
$f:{\mathbb{R}}^{n}\rightarrow{\overline{\mathbb{R}}}$, its proximal operator
of modulus $\kappa>0$ is defined as ([30, Definition 1.22])

$\operatorname{Prox}_{f,\;\kappa}:\operatorname{\mathbb{R}}^{n}\rightarrow\operatorname{\mathbb{R}}^{n},\
\operatorname{Prox}_{f,\;\kappa}({\mathbf{x}})=\arg\min_{{\mathbf{y}}\in\operatorname{\mathbb{R}}^{n}}\Big{\\{}f({\mathbf{y}})+\frac{1}{2\kappa}\|{\mathbf{y}}-{\mathbf{x}}\|^{2}\Big{\\}}.$

It holds ${\mathbf{y}}=\operatorname{Prox}_{f,\;\kappa}({\mathbf{x}})$ if and
only if ${\mathbf{x}}\in{\mathbf{y}}+\kappa\partial f({\mathbf{y}})$.

A proper function $f:{\mathbb{R}}^{n}\rightarrow{\overline{\mathbb{R}}}$ is
called essentially strictly convex if it is strictly convex on every convex
subset of $\operatorname*{dom}(\partial f)$. A proper and convex function
$f:{\mathbb{R}}^{n}\rightarrow{\overline{\mathbb{R}}}$ is called essentially
smooth if it satisfies the following three conditions [29]: (a)
$\operatorname*{int}(\operatorname*{dom}f)$ is not empty; (b) $f$ is
differentiable on $\operatorname*{int}(\operatorname*{dom}f)$; (c) for every
sequence
$\\{{\mathbf{x}}^{k}\\}\subseteq\operatorname*{int}(\operatorname*{dom}f)$
which converges to a boundary point of $\operatorname*{dom}f$, it holds
$\mathop{\lim}\limits_{k\to+\infty}\|\nabla f({\mathbf{x}}_{k})\|=+\infty$.
For a proper, convex and lower semicontinuous function $f$, it is well known
that [29, Theorem 26.3] $f$ is essentially strictly convex if and only if its
conjugate $f^{*}$ is essentially smooth.

Given a linear operator $A:{\mathbb{R}}^{n}\rightarrow{\mathbb{R}}^{m}$, we
denote by $A^{*}:{\mathbb{R}}^{m}\rightarrow{\mathbb{R}}^{n}$ its adjoint
operator. The norm of the linear operator $A$ is given by
$\|A\|=\sup\\{\|A\mathbf{x}\|:\|\mathbf{x}\|=1\\}$. Next, we review the
Kurdyka-Łojasiewicz (KL) property [5] which has been widely use in the
convergence analysis of algorithms for nonconvex optimization [2, 3].

######  Definition 2.1.

A proper and lower semicontinuous function
$f:\mathbb{R}^{n}\rightarrow\overline{\operatorname{\mathbb{R}}}$ is said to
satisfy the Kurdyka-Łojasiewicz (KL) property at a point
${\hat{\mathbf{x}}}\in{\text{\rm dom}}(\partial f)$ if there exist a constant
$\mu\in(0,+\infty]$, an open neighborhood $U$ of ${\hat{\mathbf{x}}},$ and a
desingularization function $\phi:\;[0,\mu)\rightarrow[0,+\infty)$, which is
continuous and concave, and continuously differentiable on $(0,\mu)$ with
$\phi(0)=0$ and $\phi^{\prime}>0$ on $(0,\mu)$, such that for every
$\mathbf{x}\in U$ with
$f({\hat{\mathbf{x}}})<f(\mathbf{x})<f(\hat{\mathbf{x}})+\mu$ it holds

$\displaystyle\phi^{\prime}(f(\mathbf{x})-f(\hat{\mathbf{x}})){\text{\rm{dist}}}(\mathbf{0},\partial
f({\mathbf{x}}))\geq 1.$

The concept of calmness [30] will play an important role throughout this
paper.

######  Definition 2.2.

A proper function $f:{\mathbb{R}}^{n}\rightarrow{\overline{\mathbb{R}}}$ is
said to be calm at ${\mathbf{x}}\in{\text{\rm dom}}f$ if there exist
$\varepsilon>0$ and $\kappa>0$ such that
$|f({\mathbf{y}})-f({\mathbf{x}})|\leq\kappa\|{\mathbf{y}}-{\mathbf{x}}\|$ for
all ${\mathbf{y}}\in
B({\mathbf{x}},\varepsilon):=\\{{\mathbf{z}}\in\operatorname{\mathbb{R}}^{n}:\|{\mathbf{z}}-{\mathbf{x}}\|<\varepsilon\\}$.

The following lemma provides a formula for the Fréchet subdifferential of the
ratios of two functions.

######  Lemma 2.3.

Let $O\subseteq\operatorname{\mathbb{R}}^{n}$ be an open set, and
$f_{1}:O\rightarrow\overline{\mathbb{\operatorname{\mathbb{R}}}}$ and
$f_{2}:O\rightarrow\mathbb{\operatorname{\mathbb{R}}}$ be two functions which
are finite at ${\mathbf{x}}\in O$ with $f_{2}({\mathbf{x}})>0$. Suppose that
$f_{1}$ is continuous at ${\mathbf{x}}$ relative to ${\text{\rm dom}}f_{1}$,
that $f_{2}$ is calm at ${\mathbf{x}}$, and denote
$\alpha_{i}:=f_{i}({\mathbf{x}})$, $i=1,2$.

(i) Then

(6)
$\displaystyle{\hat{\partial}}\left(\frac{f_{1}}{f_{2}}\right)({{\mathbf{x}}})=\frac{{\hat{\partial}}(\alpha_{2}f_{1}-\alpha_{1}f_{2})({{\mathbf{x}}})}{f_{2}({{\mathbf{x}}})^{2}}.$

(ii) If, in addition, $f_{2}$ is convex and $\alpha_{1}\geq 0$, then

(7)
$\displaystyle{\hat{\partial}}\left(\frac{f_{1}}{f_{2}}\right)({{\mathbf{x}}})\subseteq\frac{{\hat{\partial}}(\alpha_{2}f_{1})({{\mathbf{x}}})-\alpha_{1}{\hat{\partial}}f_{2}({{\mathbf{x}}})}{f_{2}({{\mathbf{x}}})^{2}}.$

######  Proof 2.4.

(i) The proof is similar to [36, Proposition 2.2].

(ii) If $h_{2}$ is convex and $\alpha_{1}\geq 0$, then
${\hat{\partial}}(\alpha_{1}f_{2})({\mathbf{x}})\neq{\emptyset}$ thanks to
${\mathbf{x}}\in{\text{\rm int}}({\text{\rm dom}}f_{2})$. According to [26,
eq. (1.6)], this further leads to

$\displaystyle{\hat{\partial}}(\alpha_{2}f_{1}-\alpha_{1}f_{2})({{\mathbf{x}}})\subseteq{\hat{\partial}}(\alpha_{2}f_{1})({\mathbf{x}})-{\hat{\partial}}(\alpha_{1}f_{2})({{\mathbf{x}}})={\hat{\partial}}(\alpha_{2}f_{1})({\mathbf{x}})-\alpha_{1}{\hat{\partial}}f_{2}({{\mathbf{x}}}).$

Next, we present a simple lemma that will be useful in establishing
approximate stationarity for the accumulation points of the sequence generated
by the algorithm proposed in this paper.

######  Lemma 2.5.

Let $g:{{\mathbb{R}}^{n}}\rightarrow{\overline{\mathbb{R}}}$ be a proper,
convex and lower semicontinuous convex function, and
${\mathbf{w}}\in{\text{\rm int}}({\text{\rm dom}}g)$. Let $\varepsilon>0$ and
${\cal K}$ be a compact set such that
$B({\mathbf{w}},\varepsilon)\subseteq{\cal K}\subseteq{\text{\rm
int}}({\text{\rm dom}}g)$ and $g$ is Lipschitz continuous on $\cal K$ with
constant $\kappa>0$. Further, let
${{\mathbf{z}}}\in\operatorname{\mathbb{R}}^{n}$ be such that ${\text{\rm
dist}}({\mathbf{w}},\partial
g^{*}({{\mathbf{z}}})):=\inf\\{\|{\mathbf{w}}-{\bm{\eta}}\|:{\bm{\eta}}\in\partial
g^{*}({{\mathbf{z}}})\\}\leq\varepsilon$. Then, one has

(8)
$\displaystyle{{\mathbf{z}}}\in\partial_{\hat{\varepsilon}}g({\mathbf{w}}),$

where ${\hat{\varepsilon}}:=2\kappa\varepsilon$. Furthermore, if $g$ has full
domain and $g$ is differentiable with $L_{\nabla g}$-Lipschitz continuous
gradient ($L_{\nabla g}>0$), then (8) holds for
${\hat{\varepsilon}}:=\frac{L_{\nabla g}}{2}\varepsilon^{2}$.

######  Proof 2.6.

First, we prove that $\sup\\{\|{\bm{\xi}}\|:{\bm{\xi}}\in\partial
g({\mathbf{w}}+{\mathbf{u}}),\|{\mathbf{u}}\|\leq\varepsilon\\}\leq\kappa$.
Indeed, this follows since for all
$\mathbf{u}\in\operatorname{\mathbb{R}}^{n}$ with
$\|\mathbf{u}\|\leq\varepsilon$ and all ${\bm{\xi}}\in\partial
g({\mathbf{w}}+{\mathbf{u}})$ it holds $-{\bm{\xi}}^{\top}{\mathbf{u}}\leq
g({\mathbf{w}})-g({\mathbf{w}}+{\mathbf{u}})\leq\kappa\|\mathbf{u}\|$.

For $\overline{\bm{\eta}}:={\text{Proj}}_{\partial
g^{*}({{\mathbf{z}}})}({\mathbf{w}})$, the projection of $\mathbf{w}$ on
$\partial g^{*}({{\mathbf{z}}})$ (which exists and is unique), it holds
$\|\overline{\bm{\eta}}-{\mathbf{w}}\|\leq\varepsilon$. Therefore, for
$\overline{\mathbf{u}}:=\overline{\bm{\eta}}-{\mathbf{w}}$, we have
$\|\overline{\mathbf{u}}\|\leq\varepsilon$,
${\mathbf{w}}+\overline{\mathbf{u}}\in\partial g^{*}({\mathbf{z}})$ or,
equivalently, ${{\mathbf{z}}}\in\partial
g({\mathbf{w}}+\overline{\mathbf{u}}).$

We claim that

(9) $\displaystyle
g({\mathbf{w}})-g({\mathbf{w}}+\overline{\mathbf{u}})+\langle\overline{\mathbf{u}},{{\mathbf{z}}}\rangle\leq{\hat{\varepsilon}},$

where ${\hat{\varepsilon}}$ is defined in the statement of the lemma. Since
$\langle{\mathbf{w}}+\overline{\mathbf{u}},{{\mathbf{z}}}\rangle-g^{*}({\mathbf{z}})=g({\mathbf{w}}+\overline{\mathbf{u}})$,
thanks to the fact ${{\mathbf{z}}}\in\partial
g({\mathbf{w}}+\overline{\mathbf{u}})$, this is equivalent to
$g({\mathbf{w}})+g^{*}({{\mathbf{z}}})\leq{\hat{\varepsilon}}+\langle{\mathbf{w}},{{\mathbf{z}}}\rangle,$
which is nothing else than (8).

Now we will prove that (9) is true. In the general case, by direct
calculations, we have
$g({\mathbf{w}})-g({\mathbf{w}}+\overline{\mathbf{u}})+\langle\overline{\mathbf{u}},{{\mathbf{z}}}\rangle\leq\kappa\|\overline{\mathbf{u}}\|+\kappa\|\overline{\mathbf{u}}\|\leq
2\kappa\varepsilon={\hat{\varepsilon}}$.

If $\operatorname*{dom}g=\operatorname{\mathbb{R}}^{n}$, $g$ is differentiable
and $\nabla g$ is Lipschitz continuous with Lipschitz constant $L_{\nabla
g}>0$, then ${{\mathbf{z}}}=\nabla g({\mathbf{w}}+\overline{\mathbf{u}})$, and
so, by the usual Descent Lemma [6, Lemma 1],
$g({\mathbf{w}})-g({\mathbf{w}}+\overline{\mathbf{u}})+\langle\overline{\mathbf{u}},{{\mathbf{z}}}\rangle\leq\frac{L_{\nabla
g}}{2}\|{\overline{\mathbf{u}}}\|^{2}\leq\frac{L_{\nabla
g}}{2}\varepsilon^{2}.$

##  3 Basic assumptions and stationary points of fractional programs

In this section, we introduce the basic assumptions regarding (1) and present
two versions of stationary points for fractional programs, examining their
relationships.

######  Assumption 3.1.

Throughout this paper, we assume that
(a) ${\cal S}\subseteq{\mathbb{R}}^{n}$ is a nonempty convex and compact set;
(b) $g$ is a proper, convex and lower semicontinuous function;
(c) $h$ is differentiable with Lipschitz continuous gradient over an open set
containing the compact set ${\cal S}$ with a Lipschitz constant $L_{\nabla
h}$;
(d) $f$ is a proper, convex and lower semicontinuous function with
$K(\mathcal{S})\subseteq{\rm int}({\rm dom}f)$ and $f(K{\mathbf{x}})>0$ for
all ${\mathbf{x}}\in{\cal S}$;
(e) ${\cal S}\cap A^{-1}({\text{\rm dom}}g)\neq\emptyset$ and
$\alpha:=\inf_{\mathbf{x}\in{\cal
S}}\\{g(A{\mathbf{x}})+h({\mathbf{x}})\\}>0.$

######  Remark 3.2.

The assumption ${\cal S}\cap A^{-1}({\text{\rm dom}}g)\neq\emptyset$ is to
guarantee that the objective function $F$ is not identically $+\infty$. The
second condition in Assumption 3.1(e) might seem more restrictive than it is
at first glance. In fact, if $\inf_{{\mathbf{x}}\in{\cal
S}}F({\mathbf{x}})>-\infty$, we can equivalently reformulate the optimization
problem by augmenting the objective with a suitable positive constant. This
reformulation allows us to redefine the function $g$ and the linear operator
$A$ in a manner that satisfies the requirement $\alpha>0$.

######  Definition 3.3.

For the optimization problem (1), we say that
${\overline{\mathbf{x}}}\in{\mathbb{R}}^{n}$ is

  * (i)

a Fréchet stationary point if

$\displaystyle 0\in{\hat{\partial}}\left(\frac{g\circ A+h+\iota_{\cal
S}}{f\circ K}\right)({\overline{\mathbf{x}}});$

  * (ii)

a limiting lifted stationary point if

$\displaystyle 0\in\left(A^{*}\partial g(A{\overline{\mathbf{x}}})+\nabla
h(\overline{\mathbf{x}})+\partial\iota_{\cal
S}({\overline{\mathbf{x}}})\right)f(K\overline{\mathbf{x}})-(g(A\overline{\mathbf{x}})+h(\overline{\mathbf{x}}))K^{*}\partial
f(K{\overline{\mathbf{x}}}).$

From the definition, it is clear that any local minimizer
${\overline{\mathbf{x}}}\in{\mathbb{R}}^{n}$ of (1) is a Fréchet stationary
point. On the other hand, if ${\overline{\mathbf{x}}}\in{\mathbb{R}}^{n}$ is a
Fréchet stationary point of (1) such that
$K{\overline{\mathbf{x}}}\in{\text{\rm int}}({\text{\rm dom}}f)$, and either
$\overline{\mathbf{x}}\in{\rm ri}(\mathcal{S})\cap A^{-1}{\rm ri}({\rm dom}g)$
or $\mathcal{S}$ is polyhedral and $\overline{\mathbf{x}}\in\mathcal{S}\cap
A^{-1}{\rm ri}({\rm dom}g)$, then, according to Lemma 2.3,
${\overline{\mathbf{x}}}\in{\mathbb{R}}^{n}$ is also a limiting lifted
stationary point of (1).

The following examples (see [7, Example 3.1]) illustrates that a limiting
lifted stationary point may not necessarily be a Fréchet stationary point.

######  Example 3.4.

Consider the one-dimensional fractional optimization problem

$\min_{x\in[-1,1]}\frac{x^{2}+1}{|x|+1}.$

Then ${\cal S}=[-1,1]$, $g(x)=0$, $h(x)=x^{2}+1$ and $f({x})=|x|+1$, and
$A=K=I$. For $\overline{\mathbf{x}}=0$, we have

$\displaystyle\left(A^{*}\partial g(A{\overline{\mathbf{x}}})+\nabla
h(\overline{\mathbf{x}})+\partial\iota_{\cal
S}({\overline{\mathbf{x}}})\right)f(K\overline{\mathbf{x}})-(g(A\overline{\mathbf{x}})+h(\overline{\mathbf{x}}))K^{*}\partial
f(K{\overline{\mathbf{x}}})$ $\displaystyle=\ $
$\displaystyle(2{\overline{\mathbf{x}}}+\partial\iota_{[-1,1]}(\overline{\mathbf{x}}))\times(|\overline{\mathbf{x}}|+1)-({\overline{\mathbf{x}}}^{2}+1)\times\partial(|\cdot|+1)(\overline{\mathbf{x}})=[-1,1].$

Thus, $\overline{\mathbf{x}}$ is a limiting lifted stationary point.

On the other hand, using the assertion (i) of Lemma 2.3 for
$\alpha_{1}=\alpha_{2}=1$, we have

$\displaystyle{\hat{\partial}}\left(\frac{(({\cdot})^{2}+1)+\iota_{[-1,1]}({\cdot})}{|\cdot|+1}\right)(\overline{\mathbf{x}})={\hat{\partial}}(({\cdot})^{2}+\iota_{[-1,1]}(\cdot)-|\cdot|)(\overline{\mathbf{x}})=\hat{\partial}(-|\cdot|)(\overline{\mathbf{x}})=\emptyset,$

therefore, $\overline{\mathbf{x}}$ is not a Fréchet stationary point.

Next we introduce the notion of an approximate lifted stationary point for the
problem (1), which will play an important role in our analysis.

######  Definition 3.5.

Given $\epsilon_{1},\epsilon_{2}\geq 0$, we say that
${\overline{\mathbf{x}}}\in\operatorname{\mathbb{R}}^{n}$ is a limiting
$({\epsilon_{1},\epsilon_{2}})$-lifted stationary point of the problem (1) if
there exists ${{\overline{\Psi}}}\in\mathbb{R}$ with
$|{{\overline{\Psi}}}-(g(A\overline{\mathbf{x}})+h(\overline{\mathbf{x}}))|\leq\epsilon_{2}$
such that

$\displaystyle
0\in\left(A^{*}\partial_{\epsilon_{1}}g(A{\overline{\mathbf{x}}})+\nabla
h(\overline{\mathbf{x}})+\partial\iota_{\cal
S}({\overline{\mathbf{x}}})\right)f(K\overline{\mathbf{x}})-{\overline{\Psi}}\,K^{*}\partial
f(K{\overline{\mathbf{x}})}.$

If $\epsilon_{1}=\epsilon_{2}=0$, then this notion reduces to the one of a
limiting lifted stationary point.

##  4 Full-splitting adaptive algorithm

###  4.1 Conceptual algorithmic framework

We first propose a conceptual algorithmic framework for solving (1) which we
call full-splitting proximal subgradient algorithm with an extrapolated step
(FSPS).

Let $0<\beta<2$, the sequences of positive numbers $\\{\gamma_{k}\\}$ and
$\\{\delta_{k}\\}$, $\theta_{0}>0$ and a given starting point
$({\mathbf{x}}^{0},{\mathbf{z}}^{0},{\mathbf{u}}^{0})$. For all $k\geq 0$, we
consider the following update rule:

$\left\\{\begin{array}[]{rcl}{\mathbf{y}}^{k+1}&\in&\partial
f(K{\mathbf{x}}^{k})\\\ \mathbf{x}^{k+1}&=&{\text{Proj}}_{\cal
S}\left({\mathbf{u}}^{k}+\frac{\theta_{k}}{\delta_{k}}K^{*}{\mathbf{y}}^{k+1}-\frac{1}{\delta_{k}}\nabla
h({\mathbf{x}}^{k})-\frac{1}{\delta_{k}}A^{*}{\mathbf{z}}^{k}\right),\\\
{\mathbf{u}}^{k+1}&:=&(1-\beta){\mathbf{u}}^{k}+\beta{\mathbf{x}}^{k+1},\\\
{\mathbf{z}}^{k+1}&:=&\operatorname{Prox}_{g^{*},\;1/\gamma_{k}}\left(\frac{A{\mathbf{x}}^{k+1}}{\gamma_{k}}\right),\\\\[2.84544pt]
\theta_{k+1}&:=&\frac{{\rm\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1};\delta_{k},{\gamma_{k}})}{f(K{\mathbf{x}}^{k+1})},\end{array}\right.$

where

$\displaystyle{\Psi}({\mathbf{x}},{\mathbf{z}},{\mathbf{u}},\delta,\gamma)\\!:=\\!\langle{\mathbf{z}},A{\mathbf{x}}\rangle-g^{*}({\mathbf{z}})+h({\mathbf{x}})+\iota_{\cal
S}({\mathbf{x}})+\frac{\delta}{2}\|{\mathbf{x}}-{\mathbf{u}}\|^{2}\\!-\\!\frac{\gamma}{2}\|{\mathbf{z}}\|^{2}.$

######  Remark 4.1.

Assumption 3.1(d) ensures that $\partial f(K{\mathbf{x}})\neq\emptyset$ when
${\mathbf{x}}\in{\cal S}$. The primal sequence $\\{{\mathbf{u}}^{k}\\}$ is
updated with an extrapolation step. The extrapolation parameter
$\beta\in(0,2)$ could also be chosen as variable from iteration to iteration;
however, we fix it for simplicity. As we will see later in the adaptive
version, the positive sequences $\\{\gamma_{k}\\}$ and $\\{\delta_{k}\\}$ will
be chosen such that $0<\gamma_{k+1}\leq\gamma_{k}$ and, respectively,
$\delta_{k}:=2\nu+L_{\nabla h}+\frac{2\|A\|^{2}}{\gamma_{k}}$ for all $k\geq
0$, where $\nu>0.$

###  4.2 The benefit of $\beta$

In the following toy example we illustrate the potential accelerating effect
of using a large extrapolation parameter $\beta$.

######  Example 4.2.

Consider the problem (1) for ${\cal S}={[0,1]^{2}}$, $A=K=I$, and
$g,h,f:\mathbb{R}^{2}\rightarrow\mathbb{R}$ given by
$g({\mathbf{x}})=\tau\|{\mathbf{x}}\|_{1}$,
$h({\mathbf{x}})=\frac{1}{2}\|B{\mathbf{x}}-{\mathbf{b}}\|^{2}$ and
$f({\mathbf{x}})=\|{\mathbf{x}}\|$, respectively, where
$B=\left(\begin{array}[]{cc}0.7071&0.7071\\\ 0.7071&-0.7071\end{array}\right)$
is a discrete cosine transform matrix, ${\mathbf{x}}^{*}:=(1,0)^{\top}$ is the
true signal,
${\mathbf{b}}:=B{\mathbf{x}}^{*}=\left(\begin{array}[]{c}0.7071\\\
0.7071\end{array}\right),$ and $\tau=10^{-3}$. We tested FSPS for
$\gamma_{k}:=q^{k}$, with $q:=0.9999$, $\delta_{k}:=5+L_{\nabla
h}+\frac{2}{\gamma_{k}}$ for all $k\geq 0$, $\theta_{0}:=0.8053$, starting
point given by ${\mathbf{u}}^{0}={\mathbf{x}}^{0}:=(0.2,1)^{\top}$ and
${\mathbf{z}}^{0}:=(10^{-3},10^{-3})^{\top}$ and various choices for the
extrapolation parameter $\beta\in\\{0.2,0.6,1.0,1.4,1.8\\}$. As a stopping
criterion we considered ${\rm
RErr}(k):=\|{\mathbf{x}}^{k}-{\mathbf{x}}^{*}\|/\|{\mathbf{x}}^{*}\|<10^{-6}$.

Fig. 1 illustrates the trajectory of the relative error ${\rm RErr}(k)$ and
the primal sequence $\\{{\mathbf{x}}^{k}\\}$ generated by FSPS for different
choices of $\beta$. One can notice that as the value of $\beta$ increases, the
required number of iterations gradually decreases, indicating that a larger
value of $\beta$ might lead to a faster convergence speed.

|
---|---
Figure 1: The evolution of the relative error (left) and of the primal
sequence $\\{{\mathbf{x}}^{k}\\}$ (right).

###  4.3 Adaptive FSPS algorithm with extrapolation

In this subsection, we present an adaptive version of FSPS, called the
Adaptive FSPS algorithm, which determines the parameter sequences
$\\{\gamma_{k}\\}$ and $\\{\delta_{k}\\}$ in a self-adapting manner and
ensures the positivity of the sequence $\\{\theta_{k}\\}$.

######  Algorithm 4.3 (Adaptive FSPS algorithm).

Let $0<\beta<2$, $\nu>0$, $0<q<1$, $\delta_{0},\theta_{0}>0$, $\gamma_{0}=1$
and $\varepsilon>0$, and given a starting point
$({\mathbf{x}}^{0},{\mathbf{z}}^{0},{\mathbf{u}}^{0})$. For all $k\geq 0$,
consider the following update rule:

$\displaystyle\text{Choose}\ {\mathbf{y}}^{k+1}\in\partial
f(K{\mathbf{x}}^{k}).$ $\displaystyle\text{Update}\
{\mathbf{x}}^{k+1}:=\operatorname*{Proj}\nolimits_{\cal
S}\left({\mathbf{u}}^{k}+\frac{\theta_{k}}{\delta_{k}}K^{*}{\mathbf{y}}^{k+1}-\frac{1}{\delta_{k}}\nabla
h({\mathbf{x}}^{k})-\frac{1}{\delta_{k}}A^{*}{\mathbf{z}}^{k}\right).$
$\displaystyle\text{Update}\
{\mathbf{u}}^{k+1}:=(1-\beta){\mathbf{u}}^{k}+\beta{\mathbf{x}}^{k+1}.$
$\displaystyle\text{Set}\ \gamma_{k,0}:=\gamma_{k}.$ $\displaystyle\text{Find
the smallest}\ j_{{k}}\in\\{0,1,2,\ldots\\}\ \text{such that for}\
\gamma_{k,j_{k}}:=\gamma_{k,0}q^{j_{k}}\ \text{and}\ $
$\displaystyle{\mathbf{z}}^{k+1,j_{k}}:=\operatorname{Prox}_{g^{*},\;1/\gamma_{k,j_{k}}}\left(\frac{A{\mathbf{x}}^{k+1}}{\gamma_{k,j_{k}}}\right)$
$\displaystyle\text{it holds}\
\theta_{k+1}:=\frac{{\rm\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1,{j_{k}}},{\mathbf{u}}^{k+1},\delta_{k},\gamma_{k,j_{k}})}{f(K{\mathbf{x}}^{k+1})}>0.$
$\displaystyle\text{Update}\ \gamma_{k+1}:=\gamma_{k,j_{k}}.$
$\displaystyle\text{Update}\ \delta_{k+1}:=2\nu+L_{\nabla
h}+\frac{2\|A\|^{2}}{\gamma_{k+1}}.$ $\displaystyle\text{Update}\
{\mathbf{z}}^{k+1}:={\mathbf{z}}^{k+1,j_{k}}.$ $\displaystyle\text{If}\
\|{\mathbf{z}}^{k+1}\|>\min\left(\frac{\varepsilon}{\gamma_{k+1}},\sqrt{\frac{2\varepsilon}{\gamma_{k+1}}}\right),\
\text{then}$ $\displaystyle\;\;\;\;\text{Update}\
\gamma_{k+1}:=\gamma_{k+1}q.$ $\displaystyle\;\;\;\;\text{Update}\
\delta_{k+1}:=2\nu+L_{\nabla h}+\frac{2\|A\|^{2}}{\gamma_{k+1}}.$ End If

The following assumption ensures the well-posedness of the algorithm.

######  Assumption 4.4.

It holds that $A({\cal S})\subseteq\operatorname*{dom}(\partial g)$ and there
exists a constant $\ell>0$ such that ${\rm dist}(0,\partial
g(A\mathbf{x}))\leq\ell\mbox{ for all }\mathbf{x}\in{\cal S}.$

Note that this condition is automatically satisfied when the compact set
$A(\mathcal{S})$ is a subset of the interior of $\operatorname*{dom}g$.

######  Lemma 4.5 (Well-definedness of Algorithm 4.3).

Suppose Assumptions 3.1 and 4.4 hold. Then the following statements are true:

  * (i)

It holds $\|{\mathbf{z}}^{k+1}\|\leq\ell+1$ for all $k\geq 0$.

  * (ii)

The procedure of finding the smallest $j_{k}\in\\{0,1,2,\ldots\\}$ such that
$\theta_{k+1}>0$ is executed in every iteration of Algorithm 4.3 a finite
number of times, and so the algorithm is well-defined. Moreover,
$\gamma_{k+1}\leq\gamma_{k}$ for all $k\geq 0$.

  * (iii)

There exists a constant $\gamma>0$ and an index $K_{0}\geq 0$ such that
$\gamma_{k}=\gamma>0$, $\delta_{k}=\delta:=2\nu+L_{\nabla
h}+\frac{2\|A\|^{2}}{\gamma}$, and
$\|{\mathbf{z}}^{k+1}\|\leq\min\left(\frac{\varepsilon}{\gamma},\sqrt{\frac{2\varepsilon}{\gamma}}\right)$
for all $k\geq K_{0}$.

######  Proof 4.6.

(i) From the construction of the algorithm, we have that
$\mathbf{x}^{k}\in\mathcal{S}$ for all $k\geq 0$. So, by Assumption 4.4, for
all $k\geq 0$ there exists ${\tilde{\mathbf{z}}}^{k}\in\partial
g(A{\mathbf{x}}^{k+1})$ with $\|{\tilde{\mathbf{z}}}^{k}\|\leq\ell+1$.

Taking into account the definitions of ${\mathbf{z}}^{k+1,j_{k}}$ and the
proximal opeartor, for all $k\geq 0$, we have

$\displaystyle\ g^{*}({\mathbf{z}}^{k+1,j_{k}})-\langle
A{\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1,j_{k}}\rangle+\frac{\gamma_{k,j_{k}}}{2}\|{\mathbf{z}}^{k+1,j_{k}}\|^{2}$
(10) $\displaystyle\leq$ $\displaystyle\
g^{*}({\tilde{\mathbf{z}}^{k}})-\langle
A{\mathbf{x}}^{k+1},{\tilde{\mathbf{z}}^{k}}\rangle+\frac{\gamma_{k,j_{k}}}{2}\|{\tilde{\mathbf{z}}}^{k}\|^{2}=-g(A{\mathbf{x}}^{k+1})+\frac{\gamma_{k,j_{k}}}{2}\|{\tilde{\mathbf{z}}}^{k}\|^{2}$
$\displaystyle\leq$ $\displaystyle\ g^{*}({\mathbf{z}}^{k+1,j_{k}})-\langle
A{\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1,j_{k}}\rangle+\frac{\gamma_{k,j_{k}}}{2}\|{\tilde{\mathbf{z}}}^{k}\|^{2}.$

Since $\gamma_{k,j_{k}}>0$, it follows that

$\|{\mathbf{z}}^{k+1,j_{k}}\|^{2}\leq\|{\tilde{\mathbf{z}}}^{k}\|^{2}\leq(\ell+1)^{2},$

consequently, $\|{\mathbf{z}}^{k+1}\|\leq\ell+1$ for all $k\geq 0$.

(ii) Let $k\geq 0$ and $j_{k}\in\\{0,1,2,...\\}$. According to (4.6) and
Assumption 3.1(e), it holds

$\displaystyle\
{\rm\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1,{j_{k}}},{\mathbf{u}}^{k+1},\delta_{k},\gamma_{k,j_{k}})$
$\displaystyle=$ $\displaystyle\ \langle
A{\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1,j_{k}}\rangle-g^{*}({\mathbf{z}}^{k+1,j_{k}})+h({\mathbf{x}}^{k+1})+\frac{\delta_{k}}{2}\|{\mathbf{x}}^{k+1}-{\mathbf{u}}^{k+1}\|^{2}-\frac{\gamma_{k,j_{k}}}{2}\|{\mathbf{z}}^{k+1,j_{k}}\|^{2}$
$\displaystyle\geq$ $\displaystyle\
g(A{\mathbf{x}}^{k+1})+h({\mathbf{x}}^{k+1})+\frac{\delta_{k}}{2}\|{\mathbf{x}}^{k+1}-{\mathbf{u}}^{k+1}\|^{2}-\frac{\gamma_{k,j_{k}}}{2}\|{\tilde{\mathbf{z}}}^{k}\|^{2}\geq\alpha-\frac{\gamma_{k,j_{k}}}{2}\|{\tilde{\mathbf{z}}}^{k}\|^{2}.$

Since $\|{\tilde{\mathbf{z}}}^{k}\|\leq\ell+1$, it is evident that after
finitely many increases of $j_{k}$ with $1$ we obtain
$\frac{\gamma_{k,j_{k}}}{2}\|{\tilde{\mathbf{z}}}^{k}\|^{2}<\frac{\alpha}{2}$
and, therefore,
${\rm\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1,{j_{k}}},{\mathbf{u}}^{k+1},\delta_{k},\gamma_{k,j_{k}})>0$.
Consequently, Algorithm 4.3 is well-defined. Finally, from the formulation of
the algorithm we easily see that $\gamma_{k+1}\leq\gamma_{k}$ for all $k\geq
0$.

(iii) In order to prove the statement, it is sufficient to show that there
exist $\gamma>0$ and $K_{0}\geq 0$ such that $\gamma_{k}=\gamma>0$ for all
$k\geq K_{0}$. Assuming the contrary, there exists a strictly decreasing
subsequence $\\{\gamma_{k_{s}}\\}$ such that $\gamma_{k_{s}}\rightarrow 0$ as
$s\to+\infty$. As $\|{\mathbf{z}}^{k_{s}}\|\leq\ell+1$ for all $s\geq 0$,
there exists $s_{0}\geq 0$ such that inequality in the “If-End If” statement
is not verified for all $s\geq s_{0}$. Therefore, as $\\{\gamma_{k_{s}}\\}$ is
strictly decreasing, for all $s\geq s_{0}$ there exists
$\widehat{k}_{s}\in\mathbb{N}$ with $k_{s}\leq\widehat{k}_{s}\leq k_{s+1}$
such that $\theta_{\widehat{k}_{s}+1,0}\leq 0$. Using a similar argument as in
(ii), this implies that
$\gamma_{\widehat{k}_{s}}=\gamma_{\widehat{k}_{s},0}\geq\frac{2\alpha}{(\ell+1)^{2}}>0$
for all $s\geq s_{0}$. The monotonicity of the sequence $\\{\gamma_{k}\\}$
leads to $\gamma_{\widehat{k}_{s}}\to 0$ as $s\rightarrow+\infty$, and further
to a contradiction.

######  Remark 4.7.

In the illustrative examples for the model problem (1) provided in Section 1,
the the functions $f$ and $g$ have full domain; therefore Assumptions
3.1(a)-(d) are evidently fulfilled. For example (a), it also holds
$\alpha:=\inf_{x\in{\cal S}}g(A{\mathbf{x}})+h({\mathbf{x}})>0$ owing the
assumption ${\cal B}\cap{\text{span}}({\bf E})=\emptyset$. In example (b), we
have $\alpha:=\inf_{x\in{\cal S}}g(A{\mathbf{x}})+h({\mathbf{x}})\geq 0$; one
could then augment the objective with a positive constant as described in
Remark 3.2.

##  5 Convergence analysis of the Adaptive FSPS algorithm

In this section, we provide the convergence analysis for Algorithm 4.3. In
order to simplify the presentation, we denote

${\bm{W}}^{k}:=({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})\quad\forall
k\geq 0.$

###  5.1 Subsequential convergence

In this subsection, we first demonstrate that the iterative sequence generated
by the proposed algorithm is bounded. Additionally, we show that any cluster
point of the sequence is a limiting approximate stationary point of the
underlying fractional program.

######  Lemma 5.1.

Suppose Assumption 3.1 holds. Then, there exist two positive scalars $m$ and
$M$ such that $m<f(K{\mathbf{x}}^{k})\leq M$ for all $k\geq 0$.

######  Proof 5.2.

Firstly, $\sup_{{\mathbf{x}}\in\cal S}f(K{\mathbf{x}})<+\infty$ holds due to
[29, Theorem 10.4] and Assumption 3.1(d). Further, we have $\inf_{k\geq
0}f(K{\mathbf{x}}^{k})>0$. Supposing the contrary, there exists a subsequence
$\\{{\mathbf{x}}^{k_{j}}\\}$ such that
${\mathbf{x}}^{k_{j}}\to\hat{\mathbf{x}}\in S$ and
$f(K{\mathbf{x}}^{k_{j}})\to 0$ as $j\to+\infty$. Using the lower
semicontinuity of $f$, this yields $f(K\hat{\mathbf{x}})\leq 0$, which
contradicts Assumption 3.1(d).

As shown in Lemma 4.5, there exists $K_{0}\geq 0$ such that
$\gamma_{k}=\gamma$ and $\delta_{k}=\delta=2\nu+L_{\nabla
h}+\frac{2\|A\|^{2}}{\gamma}$ for all $k\geq K_{0}$. Algorithm 4.3 guarantees
$\theta_{k}>0$, therefore,
${\Psi}({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)>0$
for all $k\geq K_{0}+1$.

######  Theorem 5.3.

Suppose Assumption 3.1 and Assumption 4.4 hold. Let $\gamma>0$ and $K_{0}\geq
0$ satisfy $\gamma_{k}=\gamma>0$, $\delta_{k}=\delta:=2\nu+L_{\nabla
h}+\frac{2\|A\|^{2}}{\gamma}$, and
$\|{\mathbf{z}}^{k+1}\|\leq\min\left(\frac{\varepsilon}{\gamma},\sqrt{\frac{2\varepsilon}{\gamma}}\right)$
for all $k\geq K_{0}$, as indicated by Lemma 4.5 (iii). Let

$c_{1}:=\nu,\quad c_{2}:=\frac{\delta(2-\beta)}{2\beta},\quad
c_{3}:=\frac{\gamma}{2}.$

Then, for all $k\geq K_{0}+1$, the following statements are true:

  * (i)

$\displaystyle{\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)+\theta_{k}f(K{\mathbf{x}}^{k})-\theta_{k}\left(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})\right)$
$\displaystyle\leq\ $
$\displaystyle{\Psi}({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)-c_{1}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}-c_{2}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}-c_{3}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2};$

  * (ii)

$\displaystyle{\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)-\theta_{k}f(K{\mathbf{x}}^{k+1})$
$\displaystyle\leq$ $\displaystyle-
c_{1}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}-c_{2}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}-c_{3}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}.$

######  Proof 5.4.

Let $k\geq K_{0}+1$.

(i) According to the properties of the projection, we have

$\displaystyle\mathbf{x}^{k+1}=\arg\min_{{\mathbf{x}}\in\cal
S}\left[\langle{\mathbf{z}}^{k},A{\mathbf{x}}\rangle-\theta_{k}\langle
K{\mathbf{x}},{\mathbf{y}}^{k+1}\rangle+\langle\nabla
h({\mathbf{x}}^{k}),{\mathbf{x}}-{\mathbf{x}}^{k}\rangle+\frac{\delta}{2}\|{\mathbf{x}}-{\mathbf{u}}^{k}\|^{2}\right].$

The objective function of the above optimization problem is strongly convex
with modulus $\delta$, therefore,

$\displaystyle\
\langle{\mathbf{z}}^{k},A{\mathbf{x}}^{k+1}\rangle+\langle{\mathbf{x}}^{k+1}-{\mathbf{x}}^{k},\nabla
h({\mathbf{x}}^{k})\rangle-\theta_{k}\langle
K^{*}{\mathbf{y}}^{k+1},{\mathbf{x}}^{k+1}\rangle+\frac{\delta}{2}\|{\mathbf{x}}^{k+1}-{\mathbf{u}}^{k}\|^{2}$
$\displaystyle\leq$ $\displaystyle\
\langle{\mathbf{z}}^{k},A{\mathbf{x}}^{k}\rangle-\theta_{k}\langle
K^{*}{\mathbf{y}}^{k+1},{\mathbf{x}}^{k}\rangle+\frac{\delta}{2}\|{\mathbf{x}}^{k}-{\mathbf{u}}^{k}\|^{2}-\frac{\delta}{2}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}.$

By combining the above inequality with the fact that

$\langle{\mathbf{y}}^{k+1},K({\mathbf{x}}^{k}-{\mathbf{x}}^{k+1})\rangle=f(K{\mathbf{x}}^{k})-\left(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})\right),$

it yields

$\displaystyle\langle{\mathbf{z}}^{k},A{\mathbf{x}}^{k+1}\rangle+\langle{\mathbf{x}}^{k+1}-{\mathbf{x}}^{k},\nabla
h({\mathbf{x}}^{k})\rangle+\theta_{k}\left[f(K{\mathbf{x}}^{k})-(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1}))\right]$
(11)
$\displaystyle+\frac{\delta}{2}\|{\mathbf{x}}^{k+1}-{\mathbf{u}}^{k}\|^{2}\leq\langle{\mathbf{z}}^{k},A{\mathbf{x}}^{k}\rangle+\frac{\delta}{2}\|{\mathbf{x}}^{k}-{\mathbf{u}}^{k}\|^{2}-\frac{\delta}{2}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}.$

Since $\nabla h$ is Lipschitz continuous with constant $L_{\nabla h}$, it
holds that

(12) $\displaystyle
h({\mathbf{x}}^{k+1})-h({\mathbf{x}}^{k})\leq\langle{\mathbf{x}}^{k+1}-{\mathbf{x}}^{k},\nabla
h({\mathbf{x}}^{k})\rangle+\frac{L_{\nabla
h}}{2}\|{\mathbf{x}}^{k+1}-{\mathbf{x}}^{k}\|^{2}.$

By substituting (12) into (5.4), we obtain

$\displaystyle\langle{\mathbf{z}}^{k},A{\mathbf{x}}^{k+1}\rangle+h({\mathbf{x}}^{k+1})-h({\mathbf{x}}^{k})+\theta_{k}\left[f(K{\mathbf{x}}^{k})-(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1}))\right]$
$\displaystyle+\frac{\delta}{2}\|{\mathbf{x}}^{k+1}-{\mathbf{u}}^{k}\|^{2}\leq\langle{\mathbf{z}}^{k},A{\mathbf{x}}^{k}\rangle+\frac{\delta}{2}\|{\mathbf{x}}^{k}-{\mathbf{u}}^{k}\|^{2}-\frac{\delta-
L_{\nabla h}}{2}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}$

or, equivalently,

$\displaystyle\
\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)+\theta_{k}\left[f(K{\mathbf{x}}^{k})-(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1}))\right]$
(13) $\displaystyle\leq$ $\displaystyle\
\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)-\frac{\delta-
L_{\nabla h}}{2}\|{\mathbf{x}}^{k+1}-{\mathbf{x}}^{k}\|^{2}.$

According to the definition of the proximal operator, we have
$A{\mathbf{x}}^{k}-\gamma{\mathbf{z}}^{k}\in\partial g^{*}({\mathbf{z}}^{k}).$
Thus,
$-g^{*}({\mathbf{z}}^{k+1})\leq-g^{*}({\mathbf{z}}^{k})-\langle{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k},A{\mathbf{x}}^{k}-\gamma{\mathbf{z}}^{k}\rangle$,
which, in combination with the identity

$\displaystyle-\frac{\gamma}{2}\|{\mathbf{z}}^{k+1}\|^{2}=-\frac{\gamma}{2}\|{\mathbf{z}}^{k}\|^{2}-\gamma\langle{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k},{\mathbf{z}}^{k}\rangle-\frac{\gamma}{2}\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k}\|^{2},$

gives

$\displaystyle\
\langle{\mathbf{z}}^{k+1},A{\mathbf{x}}^{k+1}\rangle-g^{*}({\mathbf{z}}^{k+1})-\frac{\gamma}{2}\|{\mathbf{z}}^{k+1}\|^{2}$
$\displaystyle\leq$ $\displaystyle\
\langle{\mathbf{z}}^{k},A{\mathbf{x}}^{k+1}\rangle-g^{*}({\mathbf{z}}^{k})-\frac{\gamma}{2}\|{\mathbf{z}}^{k}\|^{2}+\langle{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k},A{\mathbf{x}}^{k+1}-A{\mathbf{x}}^{k}\rangle-\frac{\gamma}{2}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}$
(14) $\displaystyle\leq$ $\displaystyle\
\langle{\mathbf{z}}^{k},A{\mathbf{x}}^{k+1}\rangle-g^{*}({\mathbf{z}}^{k})-\frac{\gamma}{2}\|{\mathbf{z}}^{k}\|^{2}+\frac{\|A\|^{2}}{2\gamma}\|{\mathbf{x}}^{k+1}-{\mathbf{x}}^{k}\|^{2},$

where the last inequality follows by the Young’s inequality. Using
$A{\mathbf{x}}^{k+1}-\gamma{\mathbf{z}}^{k+1}\in\partial
g^{*}({\mathbf{z}}^{k+1})$ and
$A{\mathbf{x}}^{k}-\gamma{\mathbf{z}}^{k}\in\partial g^{*}({\mathbf{z}}^{k})$,
and the monotonicity of the subdifferential operator, it yields

$\gamma\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}\leq-\langle{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1},A({\mathbf{x}}^{k+1}-{\mathbf{x}}^{k})\rangle\leq\frac{\gamma}{2}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}+\frac{\|A\|^{2}}{2\gamma}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2},$

and further, in combination with (5.4),

$\displaystyle\
\langle{\mathbf{z}}^{k+1},A{\mathbf{x}}^{k+1}\rangle-g^{*}({\mathbf{z}}^{k+1})-\frac{\gamma}{2}\|{\mathbf{z}}^{k+1}\|^{2}$
$\displaystyle\leq$ $\displaystyle\
\langle{\mathbf{z}}^{k},A{\mathbf{x}}^{k+1}\rangle-g^{*}({\mathbf{z}}^{k})-\frac{\gamma}{2}\|{\mathbf{z}}^{k}\|^{2}+\frac{\|A\|^{2}}{\gamma}\|{\mathbf{x}}^{k+1}-{\mathbf{x}}^{k}\|^{2}-\frac{\gamma}{2}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}.$

In other words,

(15)
${\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k},\delta,\gamma)\leq{\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)+\frac{\|A\|^{2}}{\gamma}\|{\mathbf{x}}^{k+1}-{\mathbf{x}}^{k}\|^{2}-\frac{\gamma}{2}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}.$

Using the extrapolation step, we get

$\displaystyle\frac{\delta}{2}\|{\mathbf{u}}^{k+1}-{\mathbf{x}}^{k+1}\|^{2}=$
$\displaystyle\frac{\delta}{2}\|{\mathbf{u}}^{k}-\beta({\mathbf{u}}^{k}-{\mathbf{x}}^{k+1})-{\mathbf{x}}^{k+1}\|^{2}$
$\displaystyle=$
$\displaystyle\frac{\delta}{2}\|{\mathbf{u}}^{k}-{\mathbf{x}}^{k+1}\|^{2}-\frac{\delta(1-(1-\beta)^{2})}{2\beta^{2}}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2},$

which leads to

(16)
$\displaystyle{\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)\leq{\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k},\delta,\gamma)-\frac{\delta(2-\beta)}{2\beta}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}.$

Finally, by adding (5.4), (15) and (16), the assertion follows by using the
definition of $\delta$.

(ii) Follows from (i) by using that $f(K{\mathbf{x}}^{k+1})\geq\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})$,
$\theta_{k}>0$, and
$\theta_{k}f(K{\mathbf{x}}^{k})={\Psi}({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)$.

Let $\gamma$ and $\delta$ be the constants indicated in Lemma 4.5 (iii), and
the merit function $\Pi:{\mathbb{R}}^{n}\times{\text{\rm
dom}}g^{*}\times{\mathbb{R}^{n}}\rightarrow\overline{{\mathbb{\operatorname{\mathbb{R}}}}}$
defined by

$\displaystyle\Pi({\mathbf{x}},{\mathbf{z}},{\mathbf{u}})=\frac{{\Psi}({\mathbf{x}},{\mathbf{z}},{\mathbf{u}},\delta,\gamma)}{f(K{\mathbf{x}})}=\frac{\langle{\mathbf{z}},A{\mathbf{x}}\rangle-g^{*}({\mathbf{z}})+h({\mathbf{x}})+\iota_{\cal
S}({\mathbf{x}})+\frac{\delta}{2}\|{\mathbf{x}}-{\mathbf{u}}\|^{2}\\!-\\!\frac{\gamma}{2}\|{\mathbf{z}}\|^{2}}{f(K{\mathbf{x}})}.$

######  Theorem 5.5 (Subsequential convergence).

Suppose Assumption 3.1 and Assumption 4.4 hold. Let $\gamma>0$ and $K_{0}\geq
0$ satisfy $\gamma_{k}=\gamma>0$, $\delta_{k}=\delta:=2\nu+L_{\nabla
h}+\frac{2\|A\|^{2}}{\gamma}$, and
$\|{\mathbf{z}}^{k+1}\|\leq\min\left(\frac{\varepsilon}{\gamma},\sqrt{\frac{2\varepsilon}{\gamma}}\right)$
for all $k\geq K_{0}$, as indicated by Lemma 4.5 (iii). Let $\Omega$ be the
set of the accumulation points of the sequence $\\{{\bm{W}}^{k}\\}$. Then, the
following statements are true:

  * (i)

The sequence
$\left\\{\\!\theta_{k}\\!=\\!\frac{{\Psi}({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)}{f(K{\mathbf{x}}^{k})}=\Pi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})\right\\}$
is nonincreasing and there exists a scalar $\overline{\theta}\geq 0$ such that
$\lim_{k\to+\infty}\theta_{k}=\overline{\theta}$.

  * (ii)

The sequence $\\{{\bm{W}}^{k}\\}$ is bounded.

  * (iii)

For every
$(\overline{\mathbf{x}},{\overline{\mathbf{y}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}})\in\Omega$
it holds
${\rm\Pi}(\overline{\mathbf{x}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}})={\overline{\theta}}$.

  * (iva)

If $K_{\varepsilon}:=\\{{\mathbf{x}}\,|\,{\rm{dist}}({\mathbf{x}},A({\cal
S}))\leq\varepsilon\\}\subseteq{\rm int}({\rm dom}g)$, then $g$ is Lipschitz
continuous on the compact set $K_{\varepsilon}$ with some Lipschitz constant
$\kappa>0$. In this case, any accumulation point of the sequence
$\\{{\mathbf{x}}^{k}\\}$ is a limiting
$\left(2\kappa\varepsilon,(2\kappa+1)\varepsilon\right)$-lifted approximate
stationary point of (1).

  * (ivb)

If $g$ has full domain and is differentiable with $L_{\nabla g}$-Lipschitz
continuous gradient ($L_{\nabla g}>0$), then any accumulation point of the
sequence $\\{{\mathbf{x}}^{k}\\}$ is a limiting $\left(\frac{L_{\nabla
g}\varepsilon^{2}}{2},\frac{L_{\nabla
g}\varepsilon^{2}}{2}+\varepsilon\right)$-lifted approximate stationary point
of (1).

  * (v)

It holds

(17) $\displaystyle\lim_{k\to+\infty}\frac{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})}{f(K{\mathbf{x}}^{k})}=1.$

Furthermore, there exists an index $K_{1}\geq K_{0}+1$ such that

(18) $0<m\leq\langle
K{\mathbf{x}}^{k},{\mathbf{y}}^{k}\rangle-f^{*}({\mathbf{y}}^{k})\leq
f(K{\mathbf{x}}^{k})\leq M\quad\forall k\geq K_{1},$

where $m$ and $M$ are the bounds from Lemma 5.1.

######  Proof 5.6.

(i) It follows from Theorem 5.3 (ii) that for all $k\geq K_{0}+1$

$\displaystyle\theta_{k+1}\leq$ $\displaystyle\
\theta_{k}-\frac{1}{f(K{\mathbf{x}^{k+1}})}\left(c_{1}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}+c_{2}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}+c_{3}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}\right)$
(19) $\displaystyle\leq$ $\displaystyle\
\theta_{k}-\frac{1}{M}\left(c_{1}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}+c_{2}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}+c_{3}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}\right),$

where $M>0$ is the constant provided by Lemma 5.1. Thus,

(20) $\displaystyle\;\;\;\;\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|\rightarrow
0,\;\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|\rightarrow
0,\;\|{\mathbf{z}}^{k+1}-{\mathbf{z}}^{k}\|\rightarrow
0,\;\|{\mathbf{x}}^{k+1}-{\mathbf{u}}^{k}\|\rightarrow 0,$

as $k\to+\infty$ and the sequence $\\{\theta_{k}\\}$ is nonincreasing.
Therefore, ${\overline{\theta}}:=\lim_{k\to\infty}\theta_{k}\geq 0$ exists.

(ii) Since $\cal S$ is a compact set, the sequence $\\{{\mathbf{x}}^{k}\\}$ is
bounded by construction, which, according to (20), guarantees that
$\\{{\mathbf{u}}^{k}\\}$ is bounded. The sequence $\\{{\mathbf{y}}^{k}\\}$ is
bounded due to Assumption 3.1 (d), and the sequence $\\{{\mathbf{z}}^{k}\\}$
is bounded due to Assumption 4.4.

(iii) Let
$\overline{\bm{W}}=(\overline{\mathbf{x}},{\overline{\mathbf{y}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}})$
be an accumulation point of the sequence and $\\{{\bm{W}}^{k}\\}$ and
$\\{{\bm{W}}^{k_{j}}\\}$ be a subsequence such that
$\lim_{j\to+\infty}{\bm{W}}^{k_{j}}={\overline{\bm{W}}}.$

From

$\displaystyle\lim_{j\to+\infty}\frac{\Psi({\mathbf{x}}^{k_{j}},{\mathbf{z}}^{k_{j}},{\mathbf{u}}^{k_{j}},\delta,\gamma)}{f(K{\mathbf{x}}^{k_{j}})}=\lim_{j\to+\infty}\theta_{k_{j}}={\overline{\theta}}$

and
$\lim_{j\to+\infty}f(K{\mathbf{x}}^{k_{j}})=f(K{\overline{\mathbf{x}}})>0$,
which holds due to Assumption 3.1 (d), by noting that
$\\{K{\mathbf{x}}^{k_{j}}\\}\subseteq K(\mathcal{S})\subseteq{\rm int}({\rm
dom}f$) and $K(\mathcal{S})$ is closed, we have that the following limit
exists:

(21)
$\displaystyle\overline{\Psi}:=\lim_{j\to\infty}\Psi({\mathbf{x}}^{k_{j}},{\mathbf{z}}^{k_{j}},{\mathbf{u}}^{k_{j}},\delta,\gamma)\in\mathbb{R}.$

Next, we show that
$\overline{\Psi}=\Psi({\overline{\mathbf{x}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}},\delta,\gamma)$.
From (21), ${\mathbf{x}}^{k_{j}}\in\mathcal{S}$, $g^{*}$ is lower
semicontinuous and the definition of
${\Psi}(\cdot,\cdot,\cdot,\delta,\gamma)$, we have that
$\Psi({\overline{\mathbf{x}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}},\delta,\gamma)\geq\overline{\Psi}$.
Invoking the update scheme, for every $j\geq 0$ such that $k_{j}\geq K_{0}+1$
it holds

$g^{*}({\overline{\mathbf{z}}})-\langle\overline{\mathbf{z}},A{\mathbf{x}}^{k_{j}}\rangle+\frac{\gamma}{2}\|{\overline{\mathbf{z}}}\|^{2}\geq
g^{*}({\mathbf{z}}^{k_{j}})-\langle{\mathbf{z}}^{k_{j}},A{\mathbf{x}}^{k_{j}}\rangle+\frac{\gamma}{2}\|{\mathbf{z}}^{k_{j}}\|^{2}$

and, further,

$\displaystyle-g^{*}({\overline{\mathbf{z}}})+\langle\overline{\mathbf{z}},A{\mathbf{x}}^{k_{j}}\rangle-\frac{\gamma}{2}\|{\overline{\mathbf{z}}}\|^{2}+h({\mathbf{x}}^{k_{j}})\leq-g^{*}({\mathbf{z}}^{k_{j}})+\langle{\mathbf{z}}^{k_{j}},A{\mathbf{x}}^{k_{j}}\rangle-\frac{\gamma}{2}\|{\mathbf{z}}^{k_{j}}\|^{2}+h({\mathbf{x}}^{k_{j}}).$

We let $j\to+\infty$ and get

$\displaystyle-g^{*}({\overline{\mathbf{z}}})+\langle\overline{\mathbf{z}},A{\overline{\mathbf{x}}}\rangle-\frac{\gamma}{2}\|{\overline{\mathbf{z}}}\|^{2}+h({\overline{\mathbf{x}}})\leq\lim_{j\to+\infty}(-g^{*}({\mathbf{z}}^{k_{j}})+\langle{\mathbf{z}}^{k_{j}},A{\mathbf{x}}^{k_{j}}\rangle-\frac{\gamma}{2}\|{\mathbf{z}}^{k_{j}}\|^{2}+h({\mathbf{x}}^{k_{j}})),$

so,
$\Psi({\overline{\mathbf{x}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}},\delta,\gamma)\leq\overline{\Psi}$.
In conclusion,
$\Psi({\overline{\mathbf{x}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}},\delta,\gamma)=\overline{\Psi}$
and
$\Pi({\overline{\mathbf{x}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}})={\overline{\theta}}$.

(iva)-(ivb) Invoking the update rules for ${\mathbf{x}}^{k+1}$,
${\mathbf{y}}^{k+1}$, ${\mathbf{z}}^{k+1}$ and ${\mathbf{u}}^{k+1}$, for all
$k\geq K_{0}+1$ it yields

(26) $\displaystyle\left\\{\begin{array}[]{l}{\mathbf{y}}^{k+1}\in\partial
f(K{\mathbf{x}}^{k}),\\\\[2.84544pt] 0\in\partial\iota_{\cal
S}({\mathbf{x}}^{k+1})+A^{*}{\mathbf{z}}^{k}+\nabla
h({\mathbf{x}}^{k})-\theta_{k}K^{*}{\mathbf{y}}^{k+1}+\delta({\mathbf{x}}^{k+1}-{\mathbf{u}}^{k}),\\\\[2.84544pt]
A{\mathbf{x}}^{k+1}-\gamma{\mathbf{z}}^{k+1}\in\partial
g^{*}({\mathbf{z}}^{k+1}),\\\\[2.84544pt]
{\mathbf{u}}^{k+1}=(1-\beta){\mathbf{u}}^{k}+\beta{\mathbf{x}}^{k+1}.\end{array}\right.$

Let
$\overline{\bm{W}}=(\overline{\mathbf{x}},{\overline{\mathbf{y}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}})$
be an accumulation point of the sequence of $\\{{\bm{W}}^{k}\\}$, and let
$\\{{\bm{W}}^{k_{j}}=({\mathbf{x}}^{k_{j}},{{\mathbf{y}}}^{k_{j}},{{\mathbf{z}}}^{k_{j}},{{\mathbf{u}}}^{k_{j}})\\}$
be a subsequence converging to $\overline{\bm{W}}$ as $j\rightarrow+\infty$.
From (20), we see that
${\mathbf{x}}^{k_{j}-1}\rightarrow\overline{\mathbf{x}}$ and
${\mathbf{u}}^{k_{j}-1}\rightarrow\overline{\mathbf{u}}$ as
$j\rightarrow+\infty$ Then, letting $k=k_{j}-1$ and $j\rightarrow+\infty$ in
the above system and taking into account the fact that the graph of the convex
subdifferential is closed, we obtain

(31)
$\displaystyle\left\\{\begin{array}[]{l}{\overline{\mathbf{y}}}\in\partial
f(K{\overline{\mathbf{x}}}),\\\\[2.84544pt] {\bf 0}\in\partial\iota_{\cal
S}({\overline{\mathbf{x}}})+A^{*}{\overline{\mathbf{z}}}+\nabla
h({\overline{\mathbf{x}}})-{\overline{\theta}}K^{*}{\overline{\mathbf{y}}},\\\\[2.84544pt]
A{\overline{\mathbf{x}}}-\gamma{\overline{\mathbf{z}}}\in\partial
g^{*}(\overline{\mathbf{z}}),\\\\[2.84544pt]
{\overline{\mathbf{u}}}={\overline{\mathbf{x}}}.\end{array}\right.$

Since
$\|{\mathbf{z}}^{k+1}\|\leq\min\left(\frac{\varepsilon}{\gamma},\sqrt{\frac{2\varepsilon}{\gamma}}\right)$
for all $k\geq K_{0}$, it yields
$\|{\overline{\mathbf{z}}}\|\leq\min\left(\frac{\varepsilon}{\gamma},\sqrt{\frac{2\varepsilon}{\gamma}}\right)$
. The third inclusion relation in (31) guarantees that ${\text{dist}}(\partial
g^{*}({\overline{\mathbf{z}}}),A{\overline{\mathbf{x}}})\leq\varepsilon$.
Therefore, according to Lemma 2.5,
$\overline{\mathbf{z}}\in\partial_{2\kappa\epsilon}g(A\overline{\mathbf{x}})$,
which, combined with the first two inclusion relations in (31), leads to

$0\in\left(A^{*}\partial_{2\kappa\epsilon}g(A\overline{\mathbf{x}})+\nabla
h({\overline{\mathbf{x}}})+\partial\iota_{\cal
S}({\overline{\mathbf{x}}})\right)f(K{\overline{\mathbf{x}}})-{\overline{\Psi}}K^{*}\partial
f(K{\overline{\mathbf{x}}}).$

As seen in the proof of statement (iii), we have $\overline{\Psi}=\langle
A{\overline{\mathbf{x}}},{\overline{\mathbf{z}}}\rangle-g^{*}({\overline{\mathbf{z}}})+h({\overline{\mathbf{x}}})-\frac{\gamma}{2}\|{\overline{\mathbf{z}}}\|^{2},$
therefore

$\displaystyle|\overline{\Psi}-(g(A{\overline{\mathbf{x}}})+h({\overline{\mathbf{x}}}))|=$
$\displaystyle\
(g(A{\overline{\mathbf{x}}})+h({\overline{\mathbf{x}}}))-\left(\langle
A{\overline{\mathbf{x}}},{\overline{\mathbf{z}}}\rangle-g^{*}({\overline{\mathbf{z}}})+h({\overline{\mathbf{x}}})-\frac{\gamma}{2}\|{\overline{\mathbf{z}}}\|^{2}\right)$
$\displaystyle=$ $\displaystyle\
g(A{\overline{\mathbf{x}}})+g^{*}({\overline{\mathbf{z}}})-\langle
A{\overline{\mathbf{x}}},{\overline{\mathbf{z}}}\rangle+\frac{\gamma}{2}\|{\overline{\mathbf{z}}}\|^{2}\leq
2\kappa\epsilon+\varepsilon=(2\kappa+1)\varepsilon.$

Consequently, ${\overline{\mathbf{x}}}$ is a limiting
$(2\kappa\epsilon,(2\kappa+1)\varepsilon)$-lifted approximate stationary point
of (1). The statement in (ivb) follows from (iva) and the second statement of
Lemma 2.5.

(v) Invoking the first inclusion relation in (31) and Lemma 5.1, we obtain for
all $k\geq K_{0}+1$

$\displaystyle\frac{|f(K{\mathbf{x}}^{k})-\left(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})\right)|}{f(K{\mathbf{x}}^{k})}=$
$\displaystyle\
\frac{|\langle{\mathbf{y}}^{k+1},K({\mathbf{x}}^{k}-{\mathbf{x}}^{k+1})\rangle|}{f(K{\mathbf{x}}^{k})}$
$\displaystyle\leq$ $\displaystyle\
\frac{|\langle{\mathbf{y}}^{k+1},K({\mathbf{x}}^{k}-{\mathbf{x}}^{k+1})\rangle|}{m}.$

Using that ${\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\rightarrow 0$ as
$k\rightarrow+\infty$ and the boundedness of $\\{\mathbf{y}^{k}\\}$, we obtain

(32) $\displaystyle\lim_{k\to+\infty}\frac{|f(K{\mathbf{x}}^{k})-\left(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})\right)|}{f(K{\mathbf{x}}^{k})}=0.$

The second statement is a direct consequence of (32).

Let $m>0$ be the scalar introduced in Lemma 5.1, $\gamma$ and $\delta$ the
constants indicated in Lemma 4.5 (iii), and the following modified merit
function
$\Gamma:\\{({\mathbf{x}},{\mathbf{y}})\in{\mathbb{R}}^{n}\times\text{\rm{dom}}f^{*}:\langle
K{\mathbf{x}},{\mathbf{y}}\rangle-f^{*}({\mathbf{y}})>m/2\\}\times{\text{\rm
dom}}g^{*}\times{\mathbb{R}^{n}}\rightarrow\overline{{\mathbb{\operatorname{\mathbb{R}}}}}$
defined by

$\displaystyle\Gamma({\mathbf{x}},{\mathbf{y}},{\mathbf{z}},{\mathbf{u}})=$
$\displaystyle\
\frac{{\Psi}({\mathbf{x}},{\mathbf{z}},{\mathbf{u}},\delta,\gamma)}{\langle
K{\mathbf{x}},{\mathbf{y}}\rangle-f^{*}({\mathbf{y}})}$ $\displaystyle=$
$\displaystyle\
\frac{\langle{\mathbf{z}},A{\mathbf{x}}\rangle-g^{*}({\mathbf{z}})+h({\mathbf{x}})+\iota_{\cal
S}({\mathbf{x}})+\frac{\delta}{2}\|{\mathbf{x}}-{\mathbf{u}}\|^{2}\\!-\\!\frac{\gamma}{2}\|{\mathbf{z}}\|^{2}}{\langle
K{\mathbf{x}},{\mathbf{y}}\rangle-f^{*}({\mathbf{y}})}.$

In the following we show that values of $\Gamma$ along the sequence
$({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})$
converge to $\overline{\theta}$ as $k\rightarrow+\infty$ and that it takes
this value at every point of $\Omega$.

######  Theorem 5.7.

Suppose Assumption 3.1 and Assumption 4.4 hold. Let $\gamma>0$ and $K_{0}\geq
0$ satisfy $\gamma_{k}=\gamma>0$, $\delta_{k}=\delta:=2\nu+L_{\nabla
h}+\frac{2\|A\|^{2}}{\gamma}$, and
$\|{\mathbf{z}}^{k+1}\|\leq\min\left(\frac{\varepsilon}{\gamma},\sqrt{\frac{2\varepsilon}{\gamma}}\right)$
for all $k\geq K_{0}$, as indicated by Lemma 4.5 (iii), and $K_{1}\geq
K_{0}+1$ such that (18) holds, as indicated by Theorem 5.5 (v). Then, the
following statements are true:

  * (i)

There exists $c>0$ such that for all $k\geq K_{1}$

$\displaystyle\
\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1})$
(33) $\displaystyle\leq$ $\displaystyle\
\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})-c\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}-c\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}-c\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2};$

  * (ii)

$\lim_{k\to+\infty}\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})$
exists and it is equal to
${\overline{\theta}}=\lim_{k\rightarrow+\infty}\theta_{k}$;

  * (iii)

For every
$(\overline{\mathbf{x}},{\overline{\mathbf{y}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}})\in\Omega$
it holds
${\rm\Gamma}(\overline{\mathbf{x}},{\overline{\mathbf{y}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}})={\overline{\theta}}$

######  Proof 5.8.

(i) By using the fact of
$\theta_{k}f(K{\mathbf{x}}^{k})=\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)$,
from Theorem 5.3 (i) we obtain for all $k\geq K_{1}$

$\displaystyle{\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)\leq$
$\displaystyle\ \theta_{k}\left(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})\right)$
$\displaystyle\
-c_{1}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}-c_{2}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}-c_{3}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}.$

Since $0<m\leq\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})\leq M$
for all $k\geq K_{1}$, it yields

(34)
$\displaystyle\eta_{k+1}\leq\theta_{k}-\frac{c_{1}}{M}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}-\frac{c_{2}}{M}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}-\frac{c_{3}}{M}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2},$

where
$\eta_{k+1}:=\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1})=\frac{\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)}{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})}$.
Then one can choose $c:=\frac{1}{M}\min({c_{1}},{c_{2}},{c_{3}})$ and the
conclusion follow as $\theta_{k}\leq\eta_{k}$ for all $k\geq K_{1}$.

(ii) Since $\eta_{k}\geq\theta_{k}$ for all $k\geq K_{1}$, the sequence
$\\{\eta_{k}\\}_{k\geq K_{1}}$ is bounded from below. In addition, it is non-
increasing, which means that $\lim_{k\to+\infty}\eta_{k}$ exists and
$\lim_{k\to+\infty}\eta_{k}\geq\lim_{k\to+\infty}\theta_{k}=\overline{\theta}$.
On the other hand, invoking (34), it yields

$\displaystyle\lim\limits_{k\to+\infty}\eta_{k+1}\leq$ $\displaystyle\
\lim\limits_{k\to+\infty}(\theta_{k}-c\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}-c\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}-c\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2})$
$\displaystyle=$ $\displaystyle\
\lim\limits_{k\to\infty}\theta_{k}=\overline{\theta},$

which proves the statement.

(iii) For every
$(\overline{\mathbf{x}},{\overline{\mathbf{y}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}})\in\Omega$
it holds ${\overline{\mathbf{y}}}\in\partial f(K\overline{\mathbf{x}})$,
therefore

${\rm\Gamma}(\overline{\mathbf{x}},{\overline{\mathbf{y}}},{\overline{\mathbf{z}}},{\overline{\mathbf{u}}})=\frac{{\Psi}(\overline{\mathbf{x}},\overline{\mathbf{z}},\overline{\mathbf{u}},\delta,\gamma)}{{\langle
K\overline{\mathbf{x}},\overline{\mathbf{y}}\rangle-f^{*}(\overline{\mathbf{y}})}}=\frac{{\Psi}(\overline{\mathbf{x}},\overline{\mathbf{z}},\overline{\mathbf{u}},\delta,\gamma)}{f(K\overline{\mathbf{x}})}=\overline{\theta}.$

The conclusion follows.

##  6 Convergence of the full sequence

In this section we establish the convergence of the sequence generated by
Adaptive FSPS under suitable assumptions. To this end we will provide two
different settings in which we can bound the distance between the origin and
the limiting subdifferential of ${\rm\Gamma}$ and ${\rm\Pi}$, respectively, in
terms of the residual between two consecutive iterates. As we will see later,
the assumptions of these two settings either can be enforced without loss of
generality or can be automatically satisfied by many applications (such as the
motivation examples mentioned in the introduction).

The two settings are considered below under the assumptions of Theorem 5.7,
namely, by supposing that Assumption 3.1 and Assumption 4.4 hold and
$\gamma>0$ and $K_{0}\geq 0$ satisfy $\gamma_{k}=\gamma>0$,
$\delta_{k}=\delta:=2\nu+L_{\nabla h}+\frac{2\|A\|^{2}}{\gamma}$, and
$\|{\mathbf{z}}^{k+1}\|\leq\min\left(\frac{\varepsilon}{\gamma},\sqrt{\frac{2\varepsilon}{\gamma}}\right)$
for all $k\geq K_{0}$, as indicated by Lemma 4.5 (iii), and $K_{1}\geq
K_{0}+1$ is such that (18) holds, as indicated by Theorem 5.5 (v).

###  6.1 $f^{*}$ satisfies the calm condition over its effective domain and
$g$ is essentially strictly convex

The following characterization of the Fréchet subdifferential of the merit
function $\Gamma$ follows from Lemma 2.3 and the exact Fréchet subdifferential
formula for the sum of a function and a differentiable function.

######  Lemma 6.1.

Suppose Assumption 3.1 holds. Let $f^{*}$ satisfy the calm condition at
$\widehat{\mathbf{y}}\in{\text{\rm{dom}}}f^{*}$, $\widehat{\mathbf{x}}\in{\cal
S}$ be such that $\langle
K\widehat{\mathbf{x}},\widehat{\mathbf{y}}\rangle-f^{*}(\widehat{\mathbf{y}})>m/2$,
and $g^{*}$ be differentiable at ${\widehat{\mathbf{z}}}\in\text{\rm
int}({\text{\rm dom}}g^{*})$. Denote
$\alpha_{1}:=\Psi(\widehat{\mathbf{x}},\widehat{\mathbf{z}},\widehat{\mathbf{u}},\delta,\gamma)$
and $\alpha_{2}:=\langle
K{\widehat{\mathbf{x}}},\widehat{\mathbf{y}}\rangle-f^{*}(\widehat{\mathbf{y}})$,
and suppose that $\alpha_{1}>0$. Then, there exist open sets
$\mathcal{O}_{i}$, $i=1,2,3$, such that $\widehat{\mathbf{x}}\in{\cal
O}_{1}\subseteq\mathbb{R}^{n}$, $\widehat{\mathbf{y}}\in{\cal
O}_{2}\subseteq{\text{\rm dom}}f^{*}$ and $\widehat{\mathbf{z}}\in{\cal
O}_{3}\subseteq{\text{\rm dom}}g^{*}$ such that $\langle
K{\mathbf{x}},{\mathbf{y}}\rangle-f^{*}({\mathbf{y}})>m/2$ for all
$({\mathbf{x}},{\mathbf{y}})\in{\cal O}_{1}\times{\cal O}_{2}$, and

$\displaystyle{\hat{\partial}}\Gamma(\widehat{\mathbf{x}},\widehat{\mathbf{y}},\widehat{\mathbf{z}},\widehat{\mathbf{u}})\\!\\!=\\!\\!\left\\{(\boldsymbol{\xi}_{\mathbf{x}},\boldsymbol{\xi}_{\mathbf{y}},\boldsymbol{\xi}_{\mathbf{z}},\boldsymbol{\xi}_{\mathbf{u}})\left|\begin{array}[]{l}{\boldsymbol{\xi}_{\mathbf{x}}}\in\displaystyle{\frac{\alpha_{2}(A^{*}{\widehat{\mathbf{z}}}+\nabla
h({\widehat{\mathbf{x}}})+\partial\iota_{\cal
S}(\widehat{\mathbf{x}})+\delta({\widehat{\mathbf{x}}}-\widehat{\mathbf{u}}))-\alpha_{1}K^{*}\widehat{\mathbf{y}}}{(\langle
K\widehat{\mathbf{x}},\widehat{\mathbf{y}}\rangle-f^{*}(\widehat{\mathbf{y}}))^{2}}}\\\\[0.0pt]
{\boldsymbol{\xi}_{\mathbf{y}}}\in\displaystyle{\frac{\alpha_{1}({{\partial}f^{*}}(\widehat{\mathbf{y}})-K\widehat{\mathbf{x}})}{(\langle
K\widehat{\mathbf{x}},\widehat{\mathbf{y}}\rangle-f^{*}(\widehat{\mathbf{y}}))^{2}}}\\\\[0.0pt]
\boldsymbol{\xi}_{\mathbf{z}}=\displaystyle{\frac{A\widehat{\mathbf{x}}-\nabla
g^{*}(\widehat{\mathbf{z}})-\gamma{\widehat{\mathbf{z}}}}{\langle
K\widehat{\mathbf{x}},\widehat{\mathbf{y}}\rangle-f^{*}(\widehat{\mathbf{y}})}}\\\\[0.0pt]
{\boldsymbol{\xi}_{\mathbf{u}}}=\displaystyle{\frac{\delta(\widehat{\mathbf{u}}-{\widehat{\mathbf{x}}})}{\langle
K\widehat{\mathbf{x}},\widehat{\mathbf{y}}\rangle-f^{*}(\widehat{\mathbf{y}})}}\end{array}\right.\right\\}.$

######  Theorem 6.2.

Suppose that $f^{*}$ satisfies the calm condition over its effective domain
and $g$ is essentially strictly convex. Then there exists $\zeta>0$ such that
for all $k\geq K_{1}$

$\displaystyle{\text{\rm
dist}}(\mathbf{0},\partial\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1}))\leq\zeta(\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|+\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|).$

######  Proof 6.3.

Let $k\geq K_{1}$ be fixed. It holds

$\displaystyle{\text{\rm
dist}}(\mathbf{0},\partial\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1}))\leq{\text{\rm
dist}}(\mathbf{0},{\hat{\partial}}\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1})).$

Since $g$ is essentially strictly convex, $g^{*}$ is essentially smooth [29,
Theorem 26.3]. According to the third inclusion relation in (26), we have
$A{\mathbf{x}}^{k+1}-\gamma{\mathbf{z}}^{k+1}\in\partial
g^{*}({\mathbf{z}}^{k+1})$, which means ${\mathbf{z}}^{k+1}\in{\rm int}({\rm
dom}g^{*})$. In addition, $m\leq\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})\leq M$
and
$\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)>0$.

Thus, one can make use of the formula provided in Lemma 6.1 to characterize
the subdifferential of $\Gamma$ at
$({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1})$.

Invoking again (26), we have $-(A^{*}{\mathbf{z}}^{k}+\nabla
h({\mathbf{x}}^{k})-\theta_{k}K^{*}{\mathbf{y}}^{k+1}+\delta({\mathbf{x}}^{k+1}-{\mathbf{u}}^{k}))\in{\hat{\partial}}\iota_{\cal
S}({\mathbf{x}}^{k+1})$ and ${\mathbf{y}}^{k+1}\in\partial
f(K{\mathbf{x}}^{k})$ or, equivalently, $K{\mathbf{x}}^{k}\in\partial
f^{*}({\mathbf{y}}^{k+1})$, and $A{\mathbf{x}}^{k+1}-(\nabla
g^{*}({\mathbf{z}}^{k+1})+\gamma{\mathbf{z}}^{k+1})=0$.

Thus, for

$\displaystyle\boldsymbol{\xi}_{\mathbf{x}}^{k+1}:=$ $\displaystyle\
\frac{A^{*}{\mathbf{z}}^{k+1}+\nabla
h({\mathbf{x}}^{k+1})+\delta({\mathbf{x}}^{k+1}-{\mathbf{u}}^{k+1})}{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})}$
$\displaystyle-\ \frac{A^{*}{\mathbf{z}}^{k}+\nabla
h({\mathbf{x}}^{k})-\theta_{k}K^{*}{\mathbf{y}}^{k+1}+\delta({\mathbf{x}}^{k+1}-{\mathbf{u}}^{k})}{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})}$
$\displaystyle-\
\frac{\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)K^{*}{\mathbf{y}}^{k+1}}{(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1}))^{2}}$
$\displaystyle\boldsymbol{\xi}_{\mathbf{y}}^{k+1}:=$ $\displaystyle\
\frac{\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)(-K{\mathbf{x}}^{k+1}+K{\mathbf{x}}^{k})}{(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1}))^{2}},$
$\displaystyle{\boldsymbol{\xi}_{\mathbf{z}}^{k+1}}:=$ $\displaystyle\
\frac{A{\mathbf{x}}^{k+1}-(\nabla
g^{*}({\mathbf{z}}^{k+1})+\gamma{\mathbf{z}}^{k+1})}{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})}=0,\quad\boldsymbol{\xi}_{\mathbf{u}}^{k+1}:=\frac{\delta({\mathbf{u}}^{k+1}-{\mathbf{x}}^{k+1})}{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})},$

we have that
$(\boldsymbol{\xi}^{k+1}_{\mathbf{x}},\boldsymbol{\xi}^{k+1}_{\mathbf{y}},\boldsymbol{\xi}^{k+1}_{\mathbf{z}},\boldsymbol{\xi}^{k+1}_{\mathbf{u}})\in{\hat{\partial}}\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1}).$
Consequently,

(35) ${\text{\rm
dist}}(\mathbf{0},{\hat{\partial}}\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1}))\leq\|\boldsymbol{\xi}_{\mathbf{x}}^{k+1}\|+\|\boldsymbol{\xi}_{\mathbf{y}}^{k+1}\|+\|\boldsymbol{\xi}_{\mathbf{u}}^{k+1}\|.$

Due to the boundedness of the four sequences, the values

$B_{\mathbf{x}}:=\sup\limits_{k}\|{\mathbf{x}}^{k}\|,\
B_{\mathbf{y}}:=\sup\limits_{k}\|{\mathbf{y}}^{k}\|,\
B_{\mathbf{z}}:=\sup\limits_{k}\|{\mathbf{z}}^{k}\|,\
B_{\mathbf{u}}:=\sup\limits_{k}\|{\mathbf{u}}^{k}\|$

are finite. Since $\\{\theta_{k}\\}$ and $\\{f(K{\mathbf{x}}^{k})\\}$ are
bounded, the sequence
$\\{\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)\\}$
is also bounded. Let
$B_{\Psi}:=\sup\limits_{k}|\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)|<+\infty$.
Further, as
$\\{{\mathbf{z}}^{k}\\}\subseteq\operatorname*{int}(\operatorname*{dom}g^{*})$,
$g^{*}$ is Lipschitz continuous on the closure of $\\{{\mathbf{z}}^{k}\\}$. We
denote by $L_{g^{*}}$ the corresponding Lipschitz constant.

This being given, it is evident that

$\displaystyle\
|\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)-\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)|$
(36) $\displaystyle\leq$ $\displaystyle\
\varrho_{1}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\varrho_{2}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|+\varrho_{3}\|{\mathbf{u}}^{k+1}-{\mathbf{u}}^{k}\|,$

where
$\varrho_{1}:=B_{\mathbf{z}}\|A\|+\delta(B_{\mathbf{x}}+B_{\mathbf{u}})+L_{\nabla
h}$, $\varrho_{2}:=\|A\|B_{\mathbf{x}}+L_{g^{*}}+\gamma B_{\mathbf{z}}$,
$\varrho_{3}:=\delta(B_{\mathbf{x}}+B_{\mathbf{u}})$. Since

$\displaystyle\boldsymbol{\xi}_{\mathbf{x}}^{k+1}=$ $\displaystyle\
\frac{A^{*}({\mathbf{z}}^{k+1}-{\mathbf{z}}^{k})+\nabla
h({\mathbf{x}}^{k+1})-\nabla
h({\mathbf{x}}^{k})+\delta({\mathbf{u}}^{k}-{\mathbf{u}}^{k+1})}{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})}$
$\displaystyle+\\!\frac{\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)\frac{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})}{f(K{\mathbf{x}}^{k})}-\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)}{(\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1}))^{2}}K^{*}{\mathbf{y}}^{k+1},$

we obtain

$\displaystyle\|\boldsymbol{\xi}_{\mathbf{x}}^{k+1}\|\leq$ $\displaystyle\
\frac{1}{m}(L_{\nabla
h}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\|A\|\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|+\delta\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|)$
$\displaystyle+\frac{B_{\mathbf{y}}\|K\|}{m^{2}}\left|\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)\left(\frac{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})}{f(K{\mathbf{x}}^{k})}-1\right)\right|$
$\displaystyle+\frac{B_{\mathbf{y}}\|K\|}{m^{2}}\left|\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)-\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)\right|.$

From

$\displaystyle\left|\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)\left(\frac{\langle
K{\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1}\rangle-f^{*}({\mathbf{y}}^{k+1})}{f(K{\mathbf{x}}^{k})}-1\right)\right|$
$\displaystyle=$
$\displaystyle\left|\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)\frac{\langle
K({\mathbf{x}}^{k+1}-{\mathbf{x}}^{k}),{\mathbf{y}}^{k+1}\rangle}{f(K{\mathbf{x}}^{k})}\right|\leq\frac{B_{\Psi}B_{\mathbf{y}}\|K\|}{m}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|,$

and (6.3), it yields

$\displaystyle\|\boldsymbol{\xi}_{\mathbf{x}}^{k+1}\|\leq\eta_{1}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\eta_{2}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|+\eta_{3}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|,$

with $\eta_{1}:=\frac{L_{\nabla
h}}{m}+\frac{B_{\Psi}B_{\mathbf{y}}^{2}\|K\|^{2}}{m^{3}}+\rho_{1}\frac{B_{\mathbf{y}}\|K\|}{m^{2}}$,
$\eta_{2}:=\frac{\delta}{m}+\rho_{3}\frac{B_{\mathbf{y}}\|K\|}{m^{2}}$ and
$\eta_{3}:=\frac{\|A\|}{m}+\rho_{2}\frac{B_{\mathbf{y}}\|K\|}{m^{2}}$.

In addition, we have that

$\|\boldsymbol{\xi}_{\mathbf{y}}^{k+1}\|\leq
B_{\Psi}\frac{\|K\|}{m^{2}}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|\
\mbox{and}\
\|\boldsymbol{\xi}_{\mathbf{u}}^{k+1}\|\leq\frac{\delta|1-\beta|}{m\beta}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|,$

which, in the light of (35), leads to the conclusion.

###  6.2 $f$ is differentiable with Lipschitz continuous gradient over an open
set containing $K({\cal S})$ and $g$ is essentially strictly convex

In this subsection, the workhorse of our analysis will be the merit function
$\Pi$. The following statement is a direct consequence of [7, Lemma 2.1 (ii)].

######  Lemma 6.4.

Suppose Assumption 3.1 holds. Let $f$ be differentiable at
$K\widehat{\mathbf{x}}\in\operatorname*{int}(\operatorname*{dom}f)$ for
$\widehat{\mathbf{x}}\in{\cal S}$, and $g^{*}$ be differentiable at
${\widehat{\mathbf{z}}}\in\text{\rm int}({\text{\rm dom}}g^{*})$. Denote
$\alpha_{1}:=\Psi(\widehat{\mathbf{x}},\widehat{\mathbf{z}},\widehat{\mathbf{u}},\delta,\gamma)$
and $\alpha_{2}:=f(K\widehat{\mathbf{x}})$, and suppose that $\alpha_{1}>0$.
Then,

$\displaystyle{\hat{\partial}}\Pi(\widehat{\mathbf{x}},\widehat{\mathbf{z}},\widehat{\mathbf{u}})\\!=\\!\\!\left\\{\\!\\!(\boldsymbol{\xi}_{\mathbf{x}},\boldsymbol{\xi}_{\mathbf{z}},\boldsymbol{\xi}_{\mathbf{u}})\left|\begin{array}[]{l}{\boldsymbol{\xi}_{\mathbf{x}}}\in\displaystyle{\frac{\alpha_{2}(A^{*}{\widehat{\mathbf{z}}}+\nabla
h({\widehat{\mathbf{x}}})+\partial\iota_{\cal
S}(\widehat{\mathbf{x}})+\delta({\widehat{\mathbf{x}}}-\widehat{\mathbf{u}}))-\alpha_{1}K^{*}\nabla
f(K{\widehat{\mathbf{x}}})}{(f(K{\widehat{\mathbf{x}}}))^{2}}}\\\\[0.0pt]
\boldsymbol{\xi}_{\mathbf{z}}=\displaystyle{\frac{A\widehat{\mathbf{x}}-\nabla
g^{*}(\widehat{\mathbf{z}})-\gamma{\widehat{\mathbf{z}}}}{f(K{\widehat{\mathbf{x}}})}}\\\\[0.0pt]
{\boldsymbol{\xi}_{\mathbf{u}}}=\displaystyle{\frac{\delta(\widehat{\mathbf{u}}-{\widehat{\mathbf{x}}})}{f(K{\widehat{\mathbf{x}}})}}\end{array}\right.\\!\\!\right\\}.$

######  Theorem 6.5.

Suppose that $f$ is differentiable with Lipschitz continuous gradient on an
open set containing $K({\cal S})$, and $g$ is essentially strictly convex.
Then there exists $\zeta>0$ such that for all $k\geq{K}_{1}$

$\displaystyle{\text{\rm
dist}}(\mathbf{0},\partial\Pi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1}))\leq\zeta(\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|+\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|).$

######  Proof 6.6.

Let $k\geq K_{1}$ be fixed. As seen in the proof of Theorem 6.2,
${\mathbf{z}}^{k}\in\text{\rm int}({\text{\rm dom}}g^{*})$ and
${\Psi}({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)>0$.
Invoking (26) and Lemma 6.4, for

$\displaystyle\boldsymbol{\xi}_{\mathbf{x}}^{k+1}:=$ $\displaystyle\
\frac{A^{*}({\mathbf{z}}^{k+1}-{\mathbf{z}}^{k})+\nabla
h({\mathbf{x}}^{k+1})-\nabla
h({\mathbf{x}}^{k})+\delta({\mathbf{u}}^{k}-{\mathbf{u}}^{k+1})}{f(K{\mathbf{x}}^{k+1})}$
$\displaystyle+\\!\frac{\theta_{k}f(K{\mathbf{x}}^{k+1})K^{*}\nabla
f(K{\mathbf{x}}^{k})-\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)K^{*}\nabla
f(K{\mathbf{x}}^{k+1})}{(f(K{\mathbf{x}}^{k+1}))^{2}},$
$\displaystyle{\boldsymbol{\xi}_{\mathbf{z}}^{k+1}}:=$ $\displaystyle\
\frac{A{\mathbf{x}}^{k+1}-(\nabla
g^{*}({\mathbf{z}}^{k+1})+\gamma{\mathbf{z}}^{k+1})}{f(K{\mathbf{x}}^{k+1})}=0,\quad\boldsymbol{\xi}_{\mathbf{u}}^{k+1}:=\frac{\delta({\mathbf{u}}^{k+1}-{\mathbf{x}}^{k+1})}{f(K{\mathbf{x}}^{k+1})},$

it holds
$(\boldsymbol{\xi}^{k+1}_{\mathbf{x}},\boldsymbol{\xi}^{k+1}_{\mathbf{z}},\boldsymbol{\xi}^{k+1}_{\mathbf{u}})\in{\hat{\partial}}\Pi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1}).$
We have

$\displaystyle\|\boldsymbol{\xi}_{\mathbf{x}}^{k+1}\|\leq$ $\displaystyle\
\frac{1}{m}(L_{\nabla
h}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\|A\|\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|+\delta\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|)$
$\displaystyle+\frac{B_{\Psi}B_{\nabla
f}\|K\|}{m^{3}}|f(K{\mathbf{x}}^{k+1})-f(K{\mathbf{x}}^{k})|+\frac{B_{\Psi}\|K\|}{m^{2}}|\nabla
f(K{\mathbf{x}}^{k+1})-\nabla f(K{\mathbf{x}}^{k})|$
$\displaystyle+\frac{B_{\nabla
f}\|K\|}{m^{2}}\left|\Psi({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k},\delta,\gamma)-\Psi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1},\delta,\gamma)\right|,$

where $B_{\nabla f}:=\sup\limits_{k}\|\nabla f({\mathbf{x}}^{k})\|<+\infty$
and $B_{\Psi}$ has been introduced in the proof of Theorem 6.2. By denoting
with $L_{\nabla f}$ and $L_{f}$ the Lipschitz constants of $\nabla f$ and $f$
over the set $K({\cal S})$, respectively, and by using (6.3), it yields

$\displaystyle\|\boldsymbol{\xi}_{\mathbf{x}}^{k+1}\|\leq\eta_{1}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\eta_{2}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|+\eta_{3}\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|,$

with $\eta_{1}:=\frac{L_{\nabla h}}{m}+\frac{B_{\Psi}B_{\nabla
f}L_{f}\|K\|^{2}}{m^{3}}+\frac{B_{\Psi}L_{\nabla
f}\|K\|^{2}}{m^{2}}+\rho_{1}\frac{B_{\nabla f}\|K\|}{m^{2}}$,
$\eta_{2}:=\frac{\delta}{m}+\rho_{3}\frac{B_{\nabla f}\|K\|}{m^{2}}$ and
$\eta_{3}:=\frac{\|A\|}{m}+\rho_{2}\frac{B_{\nabla f}\|K\|}{m^{2}}$. In
addition, we have that

$\displaystyle\|\boldsymbol{\xi}_{\mathbf{u}}^{k+1}\|\leq\frac{\delta|1-\beta|}{m\beta}\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|,$

which, as

${\text{\rm
dist}}(\mathbf{0},\partial\Pi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1}))\leq{\text{\rm
dist}}(\mathbf{0},{\hat{\partial}}\Pi({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1}))\leq\|\boldsymbol{\xi}_{\mathbf{x}}^{k+1}\|+\|\boldsymbol{\xi}_{\mathbf{u}}^{k+1}\|,$

leads to the conclusion.

######  Remark 6.7 (Comments on the assumption of essential strict convexity).

The assumption of $g$ being essentially strictly convex can be enforced
without loss of generality, by replacing in the problem formulation the
functions $g$ and $h$ by
${\widetilde{g}}({\mathbf{x}}):=g({\mathbf{x}})+\frac{s}{2}\|{\mathbf{x}}\|^{2}$
and
${\widetilde{h}}({\mathbf{x}}):=h({\mathbf{x}})-\frac{s}{2}\|A{\mathbf{x}}\|^{2}$,
respectively, where $s>0$ can be arbitrarily chosen. Then, $\tilde{g}$ is
strongly convex, and so, essentially strictly convex. Such a reformulation
will affect the Lipschitz constant of $\nabla h$ and the proximal operator of
$g^{*}$. In our numerical experiments, we noticed that, for small $s>0$, the
algorithm exhibits comparable (or simply the same) numerical performance as
for $s=0$.

######  Remark 6.8.

In the two above settings, we also require that either $f^{*}$ satisfies the
calm condition over its effective domain or $f$ is differentiable with
Lipschitz continuous gradient over an open set containing $K({\cal S})$. We
note that these conditions can be satisfied in many applications. For example,
if $f$ is supercocercive, that is,
$\lim_{\|\mathbf{x}\|\rightarrow+\infty}\frac{f(\mathbf{x})}{\|\mathbf{x}\|}=+\infty$,
then $f^{*}$ is a real-valued convex function with full domain [4, Proposition
14.15], and so, it is locally Lipschitz (and, in particular, calm). This
applies, for instance, to example (b) in the introduction. Regarding example
(a), if $p=+\infty$, then $f^{*}=\|\cdot\|_{1}$, which satisfies the calm
condition. If $p\in(1,+\infty)$, noting that $K({\cal S})$ is a compact set
which does not contain the origin, then $f(x)=\|x\|_{p}$ is differentiable
with Lipschitz continuous gradient over an open set containing $K({\cal S})$.

###  6.3 Global convergence

The proof of the global convergence theorem is in line with the techniques and
ideas of [24, Theorem 4] and [11, Theorem 3.4].

######  Theorem 6.9.

Let $\varepsilon>0$. Suppose Assumption 3.1 and Assumption 4.4 hold,
$K_{\varepsilon}:=\\{{\mathbf{x}}\ |\ {\text{\rm dist}}({\mathbf{x}},A({\cal
S}))\leq\varepsilon\\}\subseteq\text{\rm int}(\operatorname*{dom}g)$, $g$ is
essentially strictly convex and one of the following conditions are fulfilled:

  * (i)

$f^{*}$ satisfies the calm condition over its effective domain and $\Gamma$
satisfies the KL property at every point of $K_{\varepsilon}\cap{\rm
dom}\,\partial(\Gamma)$.

  * (ii)

$f$ is differentiable with Lipschitz continuous gradient over an open set
containing $K({\cal S})$ and $\Pi$ satisfies the KL property at every point of
$K_{\varepsilon}\cap{\rm dom}\,\partial(\Pi)$.

Let
$\\{{\bm{W}}^{k}=({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})\\}$
be the sequence generated by Algorithm 4.3. Then,

$\sum_{k}\Big{(}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|+\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|\Big{)}<+\infty,$

and $\\{\mathbf{x}^{k}\\}$ converges to a limiting
$(2\kappa\varepsilon,(2\kappa+1)\varepsilon)$-lifted stationary point of (1),
where $\kappa$ is the Lipschitz constant of $g$ on $K_{\varepsilon}$.

In addition, if $g$ has full domain and is differentiable with $L_{\nabla
g}$-Lipschitz continuous gradient ($L_{\nabla g}>0$), then
$\\{\mathbf{x}^{k}\\}$ converges to a limiting $\left(\frac{L_{\nabla
g}\varepsilon^{2}}{2},\frac{L_{\nabla
g}\varepsilon^{2}}{2}+\varepsilon\right)$-lifted stationary point of (1).

######  Proof 6.10.

We proof the statement only in the setting of assumption (i). The proof of the
other case can be done analogously by using Theorem 6.5.

We recall that the sequence
$\\{\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})\\}_{k\geq
K_{1}}$ is nonincreasing and it converges to ${\bar{\theta}}$ as
$k\rightarrow+\infty$. Thus,
$\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})\geq{\bar{\theta}}$
for all $k\geq K_{1}$, which allows us to divide the proof into two cases.

Case I. There exists $K_{2}\geq K_{1}$ such that
$\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})={\bar{\theta}}$
for $k\geq K_{2}$. Then,
$({\mathbf{x}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1})=({\mathbf{x}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})$
for all $k\geq K_{2}$ due to ((i)), and the conclusion follows.

Case II.
$\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})>{\bar{\theta}}$
for all $k\geq K_{1}$. Let $\Omega$ denote the set of accumulation points of
$\\{({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})\\}$.
Then, $\Omega$ is compact. Invoking Theorem 5.4 (iii), according to the
uniformized KL property [6], there exist $\varrho>0$ and $\mu>0$ and a
desingularization function $\phi$ with the property that for all
$(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{u})$ with
${\text{dist}}((\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{u}),\Omega)<\varrho$
and
${\bar{\theta}}<\Gamma({\mathbf{x}},{\mathbf{y}},{\mathbf{z}},{\mathbf{u}})<{\bar{\theta}}+\mu$,
it holds
$\phi^{\prime}(\Gamma(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{u})-{\bar{\theta}}){\text{\rm{dist}}}(\mathbf{0},\partial\Gamma(\mathbf{x},\mathbf{y},\mathbf{z},\mathbf{u}))\geq
1$. Then, there exists $K_{2}\geq K_{1}$ such that
${\text{dist}}(({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k}),\Omega)<\varrho$
and
${\bar{\theta}}<\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})<{\bar{\theta}}+\mu$
for all $k\geq K_{2}$.

Thus, by invoking Theorem 5.7 and Theorem 6.2, for all $k\geq K_{2}$ it holds

$\displaystyle\phi(\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})-{\bar{\theta}})-\phi(\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1})-{\bar{\theta}})$
$\displaystyle\geq$ $\displaystyle\
\phi^{\prime}(\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})-{\bar{\theta}})\left(\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})-\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1})\right)$
$\displaystyle\geq$ $\displaystyle\
\frac{1}{{\text{\rm{dist}}}(\mathbf{0},\partial\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k}))}\left(\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})-\Gamma({\mathbf{x}}^{k+1},{\mathbf{y}}^{k+1},{\mathbf{z}}^{k+1},{\mathbf{u}}^{k+1})\right)$
$\displaystyle\geq$ $\displaystyle\
\frac{c}{{\text{\rm{dist}}}(\mathbf{0},\partial\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k}))}\left(\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|^{2}+\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|^{2}+\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|^{2}\right)$
$\displaystyle\geq$
$\displaystyle\frac{c}{3{\text{\rm{dist}}}(\mathbf{0},\partial\Gamma({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k}))}(\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|+\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|)^{2}$
$\displaystyle\geq$
$\displaystyle\frac{c}{3\zeta}(\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|+\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|),$

where $c$ and $\zeta$ are given as in Theorem 5.7 and Theorem 6.2. By
telescoping arguments, this yields

$\sum_{k}\Big{(}\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|+\|{\mathbf{u}}^{k}-{\mathbf{u}}^{k+1}\|+\|{\mathbf{z}}^{k}-{\mathbf{z}}^{k+1}\|\Big{)}<+\infty.$

Thus, $\\{{\mathbf{x}}^{k}\\}$ converges, and the conclusion holds by Theorem
5.5.

######  Remark 6.11.

If ${\cal S}$ is a semialgebraic set and $f$, $g$ and $h$ are semialgebraic
functions (that is, their graphs can be written as finite union or
intersection of sets described by polynomial inequalities), then $\Gamma$ and
$\Pi$ are also a semialgebraic functions. So, they satisfy the KL property at
every point of the domain of their subdifferential [2, 3].

######  Remark 6.12.

As seen in the proof of Theorem 5.5, every accumulation point
$(\overline{\mathbf{x}},\overline{\mathbf{y}},\overline{\mathbf{z}},\overline{\mathbf{u}})$
point of the sequence
$({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})$ need
to fulfill the system of optimality conditions (31). Because of the existence
of $\gamma>0$ in the third inclusion relation of (31), it is not feasible to
anticipate $\overline{\mathbf{x}}$ as a definitive limiting lifted stationary
point of (1), but rather only as an approximate one.

Consequently, a question arises regarding whether setting the sequence
${\gamma_{k}}$ to identically zero in the conceptual algorithm FSPS generates
a sequence that recovers the limiting lifted stationary points. The following
example illustrates that this is not the case.

Since the fourth update block in FSPS equivalently reads

${\mathbf{z}}^{k+1}:=\arg\min_{\mathbf{z}\in\mathbb{R}^{s}}\left\\{g^{*}({\mathbf{z}})-\langle{\mathbf{z}},A{\mathbf{x}}^{k+1}\rangle+\frac{\gamma_{k}}{2}\|{\mathbf{z}}\|^{2}\right\\},$

in the following example we will choose ${\mathbf{z}}^{k+1}$ as the minimum
norm solution of the optimization problem

$\min_{\mathbf{z}\in\mathbb{R}^{s}}\left\\{g^{*}({\mathbf{z}})-\langle{\mathbf{z}},A{\mathbf{x}}^{k+1}\rangle\right\\},$

for all $k\geq 0$.

Consider the problem (1) for ${\cal
S}={[0,1]^{2}}\subseteq\operatorname{\mathbb{R}}^{2}$, $A=K=I$, and
$g,h,f:\mathbb{R}^{2}\rightarrow\mathbb{R}$ given by
$g({\mathbf{x}})=\|{\mathbf{x}}\|_{1}$,
$h({\mathbf{x}})=\frac{1}{2}\|{\mathbf{x}}\|^{2}$ and
$f({\mathbf{x}})={\mathbf{e}}^{\top}{\mathbf{x}}+0.5$, where
${\mathbf{e}}=(1,1)^{\top}$. For $\beta=1$, $\\{\gamma_{k}\\}$ identically to
zero, $\\{\delta_{k}\\}$ identically to one, $\theta_{0}:=1$ and
${\mathbf{z}}^{0}={\mathbf{u}}^{0}={\mathbf{x}}^{0}:=(0,1)^{\top}$, FSPS
generates a sequence
$({\mathbf{x}}^{k},{\mathbf{y}}^{k},{\mathbf{z}}^{k},{\mathbf{u}}^{k})$ such
that

${\mathbf{z}}^{k}={\mathbf{u}}^{k}={\mathbf{x}}^{k}=\left\\{\begin{array}[]{rl}(1,0)^{\top},&\mbox{if}\
k\ \mbox{is odd},\\\ (0,1)^{\top},&\mbox{if}\ k\ \mbox{is
even},\end{array}\right.\quad{\mathbf{y}}^{k}={\mathbf{e}}\ \mbox{and}\
\theta_{k}=1\quad\forall k\geq 1.$

One can easily see that neither $(1,0)^{\top}$ nor $(0,1)^{\top}$ are limiting
lifted stationary point of (1).

##  7 Numerical results

In this section, we showcase numerical results to demonstrate the efficacy of
the proposed algorithmic framework. All algorithms are implemented using
MATLAB R2016a and executed on a desktop running Windows 10 equipped with an
Intel Core i7-7600U CPU processor (2.80GHz) and 16GB of memory. Subsequently,
all numerical results are conducted for the reformulated problems as indicated
in Remark 6.7.

###  7.1 Implementation details

In Algorithm 4.3, prior knowledge of $L_{\nabla h}$ is required. Furthermore,
the selection of $\delta_{k}$ might lean towards conservatism, potentially
impacting the numerical performance of the algorithm.

To address these issues, we propose an adaptation of Algorithm 4.3 by
integrating a nonmonotone line search strategy [34], denoted as Adaptive FSPS-
nls. This strategy enables larger step sizes $\delta_{k}$ while reducing
reliance on estimating the constant $L_{\nabla h}$. Specifically, the input
parameters $L_{\nabla h}$ and $\nu$ exert minimal influence on the performance
of Adaptive FSPS-nls since the nonmonotone line search aims to identify a
suitable $\delta_{k}$ at each iteration.

######  Algorithm 7.1 (Adaptive FSPS algorithm with nonmonotone line search).

Let $0<\beta<2$, $\nu>0$, $0<q<1$, $\delta_{0}>0$, $\gamma_{0}=1$, and
$\varepsilon>0$, $\eta>1$, $0<\mu<1,\;c>0$, $T,\ell,t\in{\mathbb{N}}$. Let
$({\mathbf{x}}^{0},{\mathbf{u}}^{0})$ be a given starting point. We use MaxIt
to indicate the maximal number of iterations.

$\displaystyle\text{For}\ k=0:{\rm MaxIt}\ \text{do}$ $\displaystyle\ \ \
\text{Set}\ \gamma_{k,0}:=\gamma_{k}.$ $\displaystyle\ \ \ \text{For}\
j=0:\ell-1\ \text{do}$ $\displaystyle\ \ \ \ \ \ \ \ \text{Set}\
\gamma_{k,j}:=\gamma_{k,0}q^{j}.$ $\displaystyle\ \ \ \ \ \ \ \ {Set}\
{\mathbf{z}}^{k+1,j}:=\operatorname{Prox}_{g^{*},\;1/\gamma_{k,j}}\left(\frac{A{\mathbf{x}}^{k}}{\gamma_{k,j}}\right).$
$\displaystyle\ \ \ \ \ \ \ \ \text{If}\
\theta_{k+1}:=\frac{{\rm\Psi}({\mathbf{x}}^{k},{\mathbf{z}}^{k+1,j},{\mathbf{u}}^{k},\delta_{k},\gamma_{k,j})}{f(K{\mathbf{x}}^{k})}>0,\
\text{then}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \text{Update}\
\gamma_{k}:=\gamma_{k,j},\ {\mathbf{z}}^{k+1}:={\mathbf{z}}^{k+1,j}.$ Break
End If End For $\displaystyle\ \ \ \text{Set}\ \delta_{k,0}:=2\nu+L_{\nabla
h}+\frac{2\|A\|^{2}}{\gamma_{k}}.$ $\displaystyle\ \ \ \text{Choose}\
{\mathbf{y}}^{k+1}\in\partial f(K{\mathbf{x}}^{k}).$ $\displaystyle\ \ \
\text{Set}\ {\mathbf{d}}^{k+1}:=\theta_{k+1}K^{*}{\mathbf{y}}^{k+1}-\nabla
h({\mathbf{x}}^{k})-A^{*}{\mathbf{z}}^{k+1}.$ $\displaystyle\ \ \ \text{For}\
s=0:t-1$ $\displaystyle\ \ \ \ \ \ \ \ \text{Set}\
\delta_{k,s}:=\mu\eta^{s}\delta_{k,0}.$ $\displaystyle\ \ \ \ \ \ \ \
\text{Set}\ \tilde{\mathbf{x}}^{k+1}:={\text{\rm Proj}}_{\cal
S}\left({\mathbf{u}}^{k}+\displaystyle{\frac{\mathbf{d}^{k+1}}{\delta_{k,s}}}\right).$
$\displaystyle\ \ \ \ \ \ \ \ \text{If}\
F(\tilde{\mathbf{x}}^{k+1})\leq\max\limits_{[k-T]_{+}\leq j\leq
k}F(\mathbf{x}^{j})-\frac{c}{2}||\mathbf{x}^{k}-\tilde{\mathbf{x}}^{k+1}||^{2},\
\text{then}$ $\displaystyle\ \ \ \ \ \ \ \ \ \ \ \ \text{Update}\
\mathbf{x}^{k+1}:=\tilde{\mathbf{x}}^{k+1}.$ Break $\displaystyle\ \ \ \ \ \ \
\ \ \text{End If}.$ $\displaystyle\ \ \ \text{End For}.$ $\displaystyle\ \ \
\text{Update}\
{\mathbf{u}}^{k+1}:={\mathbf{u}}^{k}-\beta({\mathbf{u}}^{k}-{\mathbf{x}}^{k+1}).$
$\displaystyle\ \ \ \text{Update}\ \gamma_{k+1}:=\gamma_{k},\
\delta_{k+1}:=\delta_{k}.$ $\displaystyle\ \ \ \ \text{If}\
\|{\mathbf{z}}^{k+1}\|>\min\left(\frac{\varepsilon}{\gamma_{k}},\sqrt{\frac{2\varepsilon}{\gamma_{k}}}\right),\
\text{then}$ $\displaystyle\ \ \ \ \ \ \ \ \text{Update}\
\gamma_{k+1}:=\gamma_{k}q,\ \delta_{k+1}:=2\nu+L_{\nabla
h}+\frac{2\|A\|^{2}}{\gamma_{k+1}}.$ End If End For

Through slight modifications to the nonmonotone line search strategy within
the Adaptive FSPS algorithm, an iterative scheme showcasing subsequential
convergence emerges. Nonetheless, we opt to omit the proof due to spatial
constraints.

###  7.2 Limited-angle CT reconstruction

We addressed the problem of computed tomography (CT) reconstruction from
limited-angle scanning, as described in (2).

In implementing Algorithm 7.1, we let
$f({\mathbf{x}}):=\|{\mathbf{x}}\|_{2}=\|\mathbf{x}\|$, $A=K=\nabla$. We
follow Remark 6.7 by setting
$g({\mathbf{x}})=\tau\|\mathbf{x}\|_{1}+\frac{s}{2}\|\mathbf{x}\|^{2}$ and
$h({\mathbf{x}})=\frac{1}{2}\|P\mathbf{x}-\mathbf{f}\|^{2}-\frac{s}{2}\|A\mathbf{x}\|^{2}$
where $s=0.1$ and $\tau=0.1$. We also adopted a two-stage approach with a warm
start strategy, where the last iterate of the first stage served as the
initial point for the second stage. The parameters employed for these stages
are outlined in Table 1.

Table 1: Parameters for Adaptive FSPS-nls. Stage | $\beta$ | $\nu$ | $\mu$ | $\eta$ | $q$ | $T$ | $c$ | $t$ | $\ell$ | MaxIt
---|---|---|---|---|---|---|---|---|---|---
1 | 1.1 | 1000 | 0.4 | 1.2 | 0.998 | 5 | 2e-4 | 250 | 1000 | 50
2 | 1.45 | 350 | 0.4 | 1.2 | 0.998 | 5 | 2e-4 | 250 | 1000 | 3000

The rationale behind employing a two-stage approach with different maximum
iteration numbers is twofold: the initial stage, with a smaller maximum
iteration limit, aims to explore a wider search space to identify a potential
vicinity that contains a promising stationary point. On the other hand, the
subsequent stage, characterized by a larger maximum iteration number, focuses
on a more refined local search, striving for increased precision in
pinpointing the stationary point.

We compared Adaptive FSPS-nls with two other reconstruction algorithms,
precisely, the ADMM algorithm from [32], and the clinical standard approach of
SART [1]. The ADMM approach in [32] has been designed to solve the model

$\min_{{\mathbf{x}}\in{\cal
B}}\frac{\|\nabla{\mathbf{x}}\|_{1}}{\|\nabla{\mathbf{x}}\|_{2}}+\frac{\lambda}{2}\|P{\mathbf{x}}-{\mathbf{f}}\|^{2},$

where ${\nabla}$, $P$, ${\mathbf{f}}$ and ${\cal B}$ are defined as in the
introduction, and $\lambda>0$ is the regularization parameter. Here, we follow
the choice and setup of $\lambda$ as suggested in [32].

Each algorithm was initialized with the zero vector, setting the maximum
iteration number MaxIt to 3000. The stopping criterion for Adaptive FSPS-nls
was defined as follows:

$\frac{\|{\mathbf{x}}^{k+1}-{\mathbf{x}}^{k}\|}{\max\\{{\text{eps}},\|{\mathbf{x}}^{k}\|\\}}\leq
10^{-5}\;\;\mbox{or}\;\;k>{\text{MaxIt}},$

where eps represents the machine precision. We utilized the default settings
for the ADMM algorithm as in [32]. Regarding the SART algorithm [1], we
conducted 5000 iterations.

We assessed performance based on two metrics: the root mean squared error
(RMSE) and the overall structural similarity index (SSIM) [33]. RMSE is
defined as (see [32]):

(37)
$\text{RMSE}({\mathbf{u}},{\mathbf{v}})=\frac{||{\mathbf{u}}-{{\mathbf{v}}}||}{N},$

where ${\mathbf{u}}$ and ${\mathbf{v}}$ represent the recovered and ground
truth images, respectively, and $N$ denotes the total number of pixels. SSIM
is computed as the mean of local similarity indices:

(38) $\text{SSIM}({\mathbf{u}},{{\mathbf{v}}})=\frac{1}{M}\sum_{i=1}^{M}{\rm
ssim}(u^{(i)},v^{(i)}),$

where $u^{(i)}$ and $v^{(i)}$ represent the $i$’th $8\times 8$ windows for
${\mathbf{u}}$ and ${\mathbf{v}}$, respectively, and $M$ is the total number
of such windows. The local similarity index is computed using the formula:
${\rm
ssim}(u^{(i)},v^{(i)})=\frac{(2\mu_{u}^{(i)}\mu_{v}^{(i)}+c_{1})(2\sigma_{uv}^{(i)}+c_{2})}{((\mu^{(i)})_{u}^{2}+(\mu^{(i)})_{v}^{2}+c_{1})((\sigma^{(i)}_{u})^{2}+(\sigma^{(i)}_{v})^{2}+c_{2})},$
where $\mu^{(i)}_{u}$ and $\mu^{(i)}_{v}$ represent the averages,
$(\sigma^{(i)}_{u})^{2}$ and $(\sigma^{(i)}_{v})^{2}$ denote the variances of
$u^{(i)}$ and $v^{(i)}$ and
$\sigma^{(i)}_{uv}=\frac{1}{63}\sum{(u^{(i)}-\mu_{u}^{(i)})(v^{(i)}-\mu^{(i)}_{v})}$.
The constants $c_{1}$ and $c_{2}$ are set to $0.05$ to stabilize the division
with a weak denominator.

Table 2: Parallel beam CT reconstruction of the Shepp-Logan phantom for different projection ranges. SD of | Range | SART [1] | ADMM [32] | Adaptive FSPS-nls
---|---|---|---|---
noise |  |  |  |
SSIM | RMSE | SSIM | RMSE | SSIM | RMSE
| 90∘ | 0.4023 | 1.8955e-03 | 0.9925 | 8.5365e-05 | 0.9954 | 6.9983e-05
$0$ | 120∘ | 0.4490 | 1.6604e-03 | 0.9989 | 4.5143e-05 | 0.9973 | 3.3886e-05
| 150∘ | 0.5249 | 1.4677e-03 | 0.9985 | 3.3352e-05 | 0.9997 | 1.9166e-05
| 90∘ | 0.3917 | 1.9016e-03 | 0.9921 | 8.9290e-05 | 0.9949 | 7.2713e-05
$0.001$ | 120∘ | 0.4390 | 1.6688e-03 | 0.9973 | 4.5668e-05 | 0.9987 | 3.5415e-05
| 150∘ | 0.5142 | 1.4758e-03 | 0.9984 | 3.4558e-05 | 0.9994 | 2.2316e-05

We conducted tests on parallel beam CT reconstruction of the Shepp-Logan
phantom using projection ranges of 90∘, 120∘, and 150∘. We assessed both
noiseless and noisy scenarios, the latter involving Gaussian noise with zero
mean and standard deviation (SD) $\sigma=0.001$. The performance results of
the three algorithms are summarized in Table 2. Both ADMM and Adaptive FSPS-
nls demonstrate superior performance to SART in terms of SSIM and RMSE.
Notably, Adaptive FSPS-nls exhibits a slightly better performance compared to
the ADMM method.

###  7.3 Robust sharp ratio minimization problem

We tested Adaptive FSPS-nls also on the robust sharp ratio minimization
problem defined in (3). The data
$((r_{i})_{i=1}^{m_{1}},({\mathbf{a}}_{i})_{i=1}^{m_{1}},{(C_{i})}_{i=1}^{m_{2}})$
were generated as follows: (1) each vector ${\mathbf{a}}_{i}$ was generated
such that each entry is drawn from a uniform distribution over the interval
$[0,1]$; (2) ${r_{i}}$ was set to be greater than
$\|{\mathbf{a}}_{i}\|_{\infty}$; (3) each matrix $C_{i}$ was generated such
that each eigenvalue conforms to a uniform distribution over the interval
$[10^{-3},1+10^{-3}]$.

We applied Adaptive FSPS-nls and Dinkelbach’s method [17, 22] to solve (3) and
measured their performances based on several metrics: the objective function
value ${\tt obj}$, the infeasibility measure ${\tt
infeas}:=\|\max(-{\mathbf{x}},0)\|_{1}+|\|\mathbf{x}\|_{1}-1|$, and the lifted
limiting stationarity residual

${\tt stat}:={\text{dist}}\big{(}{\bf 0},\ \left(A^{*}\partial
g(A{{\mathbf{x}}})+\nabla h({\mathbf{x}})+\partial\iota_{\cal
S}({{\mathbf{x}}})\right)f(K{\mathbf{x}})-(g(A{\mathbf{x}})+h({\mathbf{x}}))K^{*}\partial
f(K{{\mathbf{x}}})\big{)},$

all three evaluated at the last iterate. We used

$\frac{\|{\mathbf{x}}^{k}-{\mathbf{x}}^{k+1}\|}{\max(\|{\mathbf{x}}^{k+1}\|,{\text{eps}})}<10^{-6}\;\;\mbox{or}\;\;k>{\text{MaxIt}}$

as stopping criterion for both algorithms.

In implementing Algorithm 7.1, we let $f$, $\mathbf{r}$, $A$ and $K$ be given
as in Example (b). We set
$g(\mathbf{x})=\|{\mathbf{r}}-{\mathbf{x}}\|_{\infty}+\frac{s}{2}\|{\mathbf{x}}\|^{2}$
and $h(\mathbf{x})=-\frac{s}{2}\|A{\mathbf{x}}\|^{2}$ with $s=0.01$, by
following Remark 6.7. We take the parameters as follows: $\ell:=10^{4}$,
$L_{\nabla h}:=s\|A^{*}A\|$, $\nu:=20$, $\eta:=1.5$, $q:=0.995$,
$\mu:=10^{-3}$, $c:=10^{-4}$, $T:=5$, $\delta_{0}:=2\nu+L_{\nabla
h}+2\|A\|^{2}$, $t:=250$, and ${\text{\rm MaxIt}}:=500$.

In Fig. 2, we showcase the outcomes derived from numerical experiments
conducted using Adaptive FSPS-nls for different scenarios:
$(n,m_{1},m_{2})=(100,5,25)$, $(200,10,20)$, $(200,20,20)$, and $(300,5,15)$,
respectively. Additionally, we selected the parameter $\beta$ from the set
$\\{0.2,0.6,1,1.4,1.6,1.7,1.8\\}$. The presented results depict the objective
function values and the stationarity residual at the last iteration for
various $\beta$ choices.

Interestingly, the experiments revealed that the choices of $\beta$ have
relatively mild influence on the final outcomes, and that $\beta=1.6$ appears
to perform in a robust way across all the instances. Consequently, we opted to
set $\beta:=1.6$ for subsequent comparisons with Dinkelbach’s method.

For the compoarison of Adaptive FSPS-nls (FSPS) with Dinkelbach’s method (DM)
we also considered various scenarios for $(n,m_{1},m_{2})$, specifically
$(100,5,20)$, $(100,20,5)$, $(100,20,20)$, $(400,20,10)$, $(400,10,20)$, and
$(400,20,20)$, and we performed 50 trials for each configuration. The average
values of the considered performance metrics and the CPU time (in seconds) are
recorded in Table 3

The table data indicate that the Adaptive FSPS-nls method exhibits faster
convergence than Dinkelbach’s method and achieves superior results in general,
in terms of the objective function values ${\tt obj}$ and the infeasibility
measure ${\tt infeas}$. The methods are comparable in terms of the
performances for the stationarity residual ${\tt stat}$, while the Adaptive
FSPS-nls method requires much less time.

|
---|---
Figure 2: The objective function value (left) and the stationarity residual (right) at the last iterate, for various choices of $\beta$ in $\\{0.2,0.6,1,1.4,1.6,1.7,1.8\\}$, and different scenarios for $(n,m_{1},m_{2})$. Table 3: Adaptive FSPS-nls versus Dinkelbach’s method for the robust sharp ratio minimization problem. $(n,m_{1},m_{2})$ | obj | infeas | stat | CPU
---|---|---|---|---
| FSPS | DM | FSPS | DM | FSPS | DM | FSPS | DM
$(100,5,20)$ | 1.19 | 1.27 | 4.59e-9 | 4.65e-7 | 4.00e-7 | 3.52e-7 | 0.13 | 8.36
$(100,20,5)$ | 1.77 | 1.78 | 4.85e-9 | 5.16e-7 | 2.95e-7 | 3.58e-7 | 0.12 | 6.52
$(100,20,20)$ | 1.63 | 1.63 | 4.86e-9 | 4.51e-7 | 3.33e-7 | 3.39e-7 | 0.14 | 7.09
$(400,20,10)$ | 1.87 | 1.88 | 4.74e-9 | 4.75e-7 | 5.74e-5 | 6.47e-5 | 0.97 | 31.8
$(400,10,20)$ | 1.68 | 1.66 | 4.39e-9 | 4.85e-7 | 2.33e-5 | 2.71e-5 | 1.41 | 49.0
$(400,20,20)$ | 1.80 | 1.79 | 4.63e-9 | 4.04e-7 | 3.91e-5 | 3.88e-5 | 1.56 | 53.4

##  8 Conclusions

The paper concentrates on a specific class of fractional programs
characterized by linear compositions with nonsmooth elements in both the
numerator and denominator. We introduce an adaptive full-splitting proximal
subgradient algorithm with an extrapolated step to tackle challenges in
computing the proximal point of the linear coupling term within the numerator.
Our contributions include establishing the global convergence of the proposed
algorithm toward an approximate lifted stationary point under the KL
assumption, without imposing full-row rank assumptions on the linear
operators. We elaborate on the rationale behind converging to an approximate
lifted stationary point, illustrating through an example how pursuing an exact
solution might lead to divergence. To improve convergence performance, we
propose a practical version that incorporates a nonmonotone line search.
Finally, we substantiate our theoretical findings with simulations,
particularly in the context of limited-angle CT reconstruction and robust
sharp ratio minimization problem.

## References

  * [1] A. H. Andersen and A. Kak, Simultaneous algebraic reconstruction technique (sart): A superior implementation of the art algorithm, Ultrasonic Imaging 6 (1984), pp. 81–94.
  * [2] H. Attouch, J. Bolte, P. Redont and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: An approach based on the Kurdyka-Łojasiewicz inequality, Mathematics of Operations Research 35 (2010), pp. 438–457.
  * [3] H. Attouch, J. Bolte, and B. F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Mathematical Programming 137 (2013), pp. 91–129.
  * [4] H. H. Bauschke and P. L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces, second edition, Springer, 2017.
  * [5] J. Bolte, A. Daniilidis, and A. Lewis, The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM Journal on Optimization 17 (2007), pp. 1205–1223.
  * [6] J. Bolte, S. Sabach, and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Mathematical Programming 146 (2014), pp. 459–494.
  * [7] R. I. Boţ, M. N. Dao, and G. Li, Extrapolated proximal subgradient algorithms for nonconvex and nonsmooth fractional programs, Mathematics of Operations Research 47 (2022), pp. 2415–2443.
  * [8] R. I. Boţ, M.-N. Dao, G. Li, Inertial proximal block coordinate method for a class of nonsmooth sum-of-ratios optimization problems, SIAM Journal on Optimization 33 (2023), pp. 361–393.
  * [9] R. I. Boţ, E.-R. Csetnek, Proximal-gradient algorithms for fractional programming, Optimization 66 (2017), pp. 1383–1396.
  * [10] R. I. Boţ, A. Böhm, Variable smoothing for convex optimization problems using stochastic gradients, Journal of Scientific Computing 85 (2020), Article: 33.
  * [11] R. I. Boţ, D.-K. Nguyen, The proximal alternating direction method of multipliers in the nonconvex setting: convergence analysis and rates, Mathematics of Operations Research 45 (2020), pp. 682–712.
  * [12] R. I. Boţ, E. R. Csetnek, D.-K. Nguyen, A proximal minimization algorithm for structured nonconvex and nonsmooth problems, SIAM Journal on Optimization 29 (2019), pp. 1300–1328.
  * [13] S. Banert, R. I. Boţ, A general double-proximal gradient algorithm for d.c. programming, Mathematical Programming 178 (2019), pp. 301–326.
  * [14] L. Chen, S. He and S. Z. Zhang, When all risk-adjusted performance measures are the same: in praise of the Sharpe ratio, Quantitative Finance, 11 (2011), pp. 1439–1447.
  * [15] P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Modeling $\&$ Simulation 4 (2005), pp. 1168–1200.
  * [16] Y. Cui and J. S. Pang, Modern Nonconvex Nondifferentiable Optimization, MOS-SIAM Series on Optimization, 2021.
  * [17] W. Dinkelbach, On nonlinear fractional programming, Management Science 13 (1967), pp. 492–498.
  * [18] B. Grimmer, Provably faster gradient descent via long steps, arXiv:2307.06324, 2023.
  * [19] B. S. He, M. Tao, X. M. Yuan, A splitting method for separable convex programming, IMA Journal of Numerical Analysis 35 (2015), pp. 394–426.
  * [20] J. B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms, Springer, Berlin, 1993.
  * [21] M. Y. Hong, Z. Q. Luo, and M. Razaviyayn, Convergence analysis of alternating direction method of multipliers for a family of nonconvex problems, SIAM J. Optim., 26 (2016), pp. 337–364.
  * [22] T. Ibaraki, Parametric approaches to fractional programs, Mathematical Programming 26 (1983), pp. 345–362.
  * [23] A. C. Kak and M. Slaney, Principles of Computerized Tomographic Imaging, SIAM, Philadelphia, 2001.
  * [24] G. Li and T. K. Pong, Global convergence of splitting methods for nonconvex composite optimization, SIAM Journal on Optimization 25 (2015), pp. 2434–2460.
  * [25] Q. Li, L. X. Shen, N. Zhang and J. P. Zhou, A proximal algorithm with backtracked extrapolation for a class of structured fractional programming, Applied and Computational Harmonic Analysis 56 (2022), pp. 98–122.
  * [26] B. S. Mordukhovich, N. M. Nam and N. D. Yen, Fréchet subdifferential calculus and optimality conditions in nondifferentiable programming, Optimization 55 (2006), pp. 685–708.
  * [27] J.-S. Pang, A parametric linear complementarity technique for optimal portfolio selection with a risk-free asset, Operations Research 28 (1980), pp. 927–941.
  * [28] J.-S. Pang and M. Tao, Decomposition methods for computing directional stationary solutions of a class of nonsmooth nonconvex optimization problems, SIAM Journal on Optimization 28 (2018), pp. 1640–1669.
  * [29] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, 1970.
  * [30] R. T. Rockafellar and R. J. B. Wets, Variational Analysis, Springer, Berlin, 1998.
  * [31] M. Tao, Minimization of $L_{1}$ over $L_{2}$ for sparse signal recovery with convergence guarantee, SIAM Journal on Scientific Computing 44 (2022), pp. A770–A797.
  * [32] C. Wang, M. Tao, J. G. Nagy, and Y. Lou, Limited-angle CT reconstruction via the L1/L2 minimization, SIAM Journal on Imaging Sciences 14 (2021), pp. 749–777.
  * [33] Z. Wang, A. C. Bovik, H. R. Sheikh and E. P. Simoncelli, Image quality assessment: from error visibility to structural similarity, IEEE Transactions on Image Processing 13 (2004), pp. 600–612.
  * [34] S. J. Wright, R. D. Nowak and M. A. T. Figueiredo, Sparse reconstruction by separable approximation, IEEE Transactions on Signal Processing, 57 (2009), pp. 2479–2493.
  * [35] L. Y. Zeng, P. R. Yu, and T. K. Pong, Analysis and algorithms for some compressed sensing models based on L1/L2 minimization, SIAM Journal on Optimization 31 (2021), pp. 1576–1603.
  * [36] N. Zhang and Q. Li, First-order algorithms for a class of fractional optimization problems, SIAM Journal on Optimization 32 (2022), pp. 100–129.