# Inexact Proximal Methods
for Weakly Convex Functions

Pham Duy Khanh111Department of Mathematics, Ho Chi Minh City University of
Education, Ho Chi Minh City, Vietnam. E-mail<EMAIL_ADDRESS>Boris S.
Mordukhovich222Department of Mathematics, Wayne State University, Detroit,
Michigan, USA. E-mail<EMAIL_ADDRESS>Research of this author was partly
supported by the US National Science Foundation under grants DMS-1808978 and
DMS-2204519, by the Australian Research Council under Discovery Project
DP-190100555, and by Project 111 of China under grant D21024. Vo Thanh
Phat333Department of Mathematics, Wayne State University, Detroit, Michigan,
USA. E-mail<EMAIL_ADDRESS>Research of this author was partly supported by
the US National Science Foundation under grants DMS-1808978 and DMS-2204519.
Dat Ba Tran444Department of Mathematics, Wayne State University, Detroit,
Michigan, USA. E-mail<EMAIL_ADDRESS>Research of this author was partly
supported by the US National Science Foundation under grant DMS-1808978 and
DMS-2204519.

Abstract. This paper proposes and develops inexact proximal methods for
finding stationary points of the sum of a smooth function and a nonsmooth
weakly convex one, where an error is present in the calculation of the
proximal mapping of the nonsmooth term. A general framework for finding zeros
of a continuous mapping is derived from our previous paper on this subject to
establish convergence properties of the inexact proximal point method when the
smooth term is vanished and of the inexact proximal gradient method when the
smooth term satisfies a descent condition. The inexact proximal point method
achieves global convergence with constructive convergence rates when the
Moreau envelope of the objective function satisfies the Kurdyka-Łojasiewicz
(KL) property. Meanwhile, when the smooth term is twice continuously
differentiable with a Lipschitz continuous gradient and a differentiable
approximation of the objective function satisfies the KL property, the inexact
proximal gradient method achieves the global convergence of iterates with
constructive convergence rates.
Key words: inexact proximal methods, weakly convex functions, forward-backward
envelopes, Kurdyka-Łojasiewicz property, global convergence, linear
convergence rates, proximal points
Mathematics Subject Classification (2020) 90C30, 90C52, 49M05

##  1 Introduction

This paper is devoted to numerical variational analysis of the following class
of optimization problems:

$\displaystyle{\rm minimize}\quad\varphi(x):=f(x)+g(x)\quad\text{ subject to
}\;x\in{\rm I\\!R}^{n},$ (1.1)

where $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ is a continuously
differentiable ($\mathcal{C}^{1}$-smooth) function, not necessary convex, and
where $g:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}:=(-\infty,\infty]$ is
a proper lower semicontinuous (l.s.c.) function. Since $g$ can be chosen as an
indicator function of a closed set, the setting of (1.1) encompasses various
problems problems of constrained optimization, which are studied with numerous
applications. This type of problem also appear in many practical models
arising, e.g., in machine learning [37, 46], compressed sensing [39], and
image processing [4, 34]. The proximal-type methods of our primal interest
here are among the most exploited tools for tackling problem (1.1) when $g$ is
convex. More specifically, Martinet first introduced in [27] the proximal
point method to deal with this problem when $f\equiv 0$ while the proximal
gradient method is designed in [6, 31] to solve (1.1) when $f$ is
$\mathcal{C}^{1}$-smooth with a Lipschitz continuous gradient. Each iteration
of these methods requires exact calculations for the proximal mapping

$\displaystyle\mbox{\rm Prox}_{\lambda g}(x):=\mathop{\rm argmin}_{y\in{\rm
I\\!R}^{n}}\big{\\{}{g(y)+(2\lambda)^{-1}}\left\|y-x\right\|^{2}\big{\\}},$
(1.2)

where $\lambda>0$ is a proximal parameter chosen in advance. Some choices of
$g$ allow us to find an explicit form for the proximal mapping in (1.2); see
e.g., [5, Section 6.9] and the repository in [15]. However, in many cases
important for practical applications, such a form either doesn’t exist, or is
very expensive to be determined computationally; see, e.g., [14, 18] and the
discussions therein. For these reasons, some proximal methods that only
require inexact information for the proximal mapping in (1.2) are designed.
Let us mention the following major developments in this vein:

$\bullet$ Rockafellar proposes in [40] an inexact proximal point method (IPPM)
for minimizing proper, l.s.c., convex functions with justifying its global
convergence. A linear convergence rate of the method is achieved when the
inverse of the subgradient mapping associated with the objective function is
Lipschitz continuous around the origin; see also [9].

$\bullet$ Schmidt et al. [42] study an inexact proximal gradient method (IPGM)
for (1.1) when $f$ is $\mathcal{C}^{1}$-smooth and convex with a Lipschitz
continuous gradient while $g$ is proper, l.s.c., and convex. A linear
convergence of function values achieved by the average of iterates is
established in [42]. If in addition $g$ is strongly convex, then it is shown
in [42] that the convergence is global.

$\bullet$ Bonettini et al. [13] design the inexact forward-backward (iFB)
algorithm for (1.1) and verify its convergence when $f$ is
$\mathcal{C}^{1}$-smooth (possibly nonconvex) with the Lipschitz continuous
gradient, when $g$ is proper, l.s.c., convex, and when $\varphi$ is bounded
from below. When the boundedness of the iterative sequence is assumed,
stationarity for all accumulation points of the iterative sequence is
established. If in addition $f$ is real analytic and $g$ is subanalytic, then
the iterative sequence has finite length and thus converges to a stationary
point of $\varphi$.

The main goal of this paper is to develop new inexact versions of both
proximal point and proximal gradient methods in the case where $f$ in (1.1) is
a smooth and generally nonconvex functions, while $g$ is weakly convex. The
latter notion was introduced by Nurminskii [33] as a weak counterpart of
strongly convex functions in the sense of Polyak [38]. We are not familiar
with inexact versions of the proximal point method for weakly convex function,
while referring the reader to the recent paper [10], where an exact version of
the proximal gradient method has been designed for weakly convex functions.
555After completing this paper that extends the scheme and results of inexact
reduced first-order methods from smooth optimization in our previous paper
[24] to nonsmooth problems of type (1.1) with weakly convex functions $g$, we
got familiar with preprint [7], which addresses problems this type assuming
that $f$ is smooth and convex. The authors of [7] develop inexact forward-
backward algorithms of the splitting type that is different of ours being
based on some sharpness ideas. As shown in [47], the class of weakly convex
functions is the largest class to study the proximal-type methods requiring
the single-valuedness of the proximal mapping. Observe also that, to the best
of our knowledge, no convergence rate for the iterative sequence generated by
IPGM his been established when $f$ is nonconvex. Furthermore, the assumptions
on the boundedness from below of $\varphi$ and the boundedness of the
iterative sequence as in [13] seem to be restrictive.

Having in mind the above discussion, we propose novel inexact proximal methods
to solve (1.1) when $g$ is a weakly convex function and $f$ is smooth but not
necessarily convex. The main ideas for these methods come mostly from a
general framework for finding zeros of continuous mappings, which is an
extension of the inexact reduced gradient methods (IRGM) for finding
stationary points of $\mathcal{C}^{1}$-smooth functions introduced in [24].
Specifically, such a framework allows us to establish the global convergence
with convergence rates of IPPM. The basic convergence properties of our novel
version of IPGM for (1.1) are also obtained by employing this general
framework together by employing the new notion of weak
$\varepsilon$-subdifferential for weakly convex functions and techniques for
dealing with approximate proximal mappings used in [42]. Our major
contributions can be briefly summarized as follows:

$\bullet$ Finding stationary accumulation points of IPPM for a weakly convex
function. Global convergence results with explicit convergence rates for this
method are obtained under the KL property for the Moreau envelope of the
objective function.

$\bullet$ Finding stationary accumulation points of IPGM for structured sums
(1.1) of $\mathcal{C}^{1}$-smooth functions $f$ satisfying a descent condition
and extended-real-valued weakly convex functions $g$. Global convergence
results with convergence rates are obtained for this method when the smooth
part is twice continuously differentiable ($\mathcal{C}^{2}$-smooth) with a
Lipschitz continuous gradient while an approximation of the objective function
satisfies the KL property.

Regarding numerical aspects in comparison with the iFB algorithm in [13] when
$g$ is convex, our new IPGM method exhibits some advantages in errors control.
More specifically, iFB uses the decreasing errors $\varepsilon_{k}=k^{-p}$
with $p>2$ in the approximation procedure of [13] for the proximal mapping
(1.2). When the number of iteration $k$ is large, the error $\varepsilon_{k}$
becomes too small, and thus the approximation procedure needs to run longer or
even cannot stop due to the round-off error of computers. On the other hand,
our method adapts the type of error introduced in [24], which does not need to
be decreased after each iteration. In minimization problems for smooth
functions, this error is automatically adjusted following the magnitude of the
exact gradient as illustrated numerically in [24, Section 6]. By using this
type of errors, our IPGM overcomes the numerical disadvantage of iFB mentioned
above.

The rest of the paper is organized as follows. Section 2 presents some basic
definitions and preliminary results used throughout the paper. The main part
of our work concerning the design and convergence properties of IPPM and IPGM
is given in Section 3, which is split into three subsections. This major
section also provides a comparison between the algorithm descriptions and
theoretical results obtained by IPGM and iFB in [13]. Numerical illustrations
for these methods demonstrating advantages of IPGM in errors control are
presented and discussed in the concluding Section 4. The concluding Section 5
discusses some directions of our future research.

##  2 Basic Definitions and Preliminaries

In this section, we recall some basic definitions and notation needed below
and present their properties that are used in what follows. All our
considerations are given in ${\rm I\\!R}^{n}$ with the Euclidean norm
$\|\cdot\|$ and inner product $\left\langle\cdot,\cdot\right\rangle$. Denoting
${\rm I\\!N}:=\\{1,2,\ldots\\}$ the collections of natural numbers and taking
any nonempty subset $I\subset{\rm I\\!N}$, the symbol
$x^{k}\stackrel{{\scriptstyle I}}{{\to}}\bar{x}$ means that $x^{k}\to\bar{x}$
as $k\to\infty$ with $k\in I$. We recall the following relaxation of the
Lipschitz continuity of the gradient $\nabla f$ employed in [2, 24].

######  Definition 2.1 (descent condition).

A continuously differentiable function $f:{\rm I\\!R}^{n}\rightarrow{\rm
I\\!R}$ is said to satisfy the descent condition with constant $L>0$ if

$\displaystyle f(x)\leq f(y)+\left\langle\nabla
f(y),x-y\right\rangle+\dfrac{L}{2}\left\|x-y\right\|^{2}\;\text{ for all
}\;x,y\in{\rm I\\!R}^{n}.$ (2.1)

######  Remark 2.2.

The descent condition (2.1) is equivalent to the convexity of
$\frac{L}{2}\left\|\cdot\right\|^{2}-f(\cdot)$ by the first-order
characterization of convex functions [32, Theorem 2.1.2]. This property is
strictly weaker than the Lipschitz continuity of $\nabla f$ as discussed in
[24, Section 2]. It is also shown in [16, Lemma 2.5] that the constant in the
descent condition for $f$ can be smaller than the constant of the Lipschitz
continuity for $\nabla f$ if $f$ is a Moreau envelope (2.5) of a weakly convex
function (Definition 2.4). Relationships between the two properties for
$\mathcal{C}^{2}$-smooth functions are given below.

######  Proposition 2.3.

Let $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ be a $\mathcal{C}^{2}$-smooth
function, and let $L>0$. Then the following assertions are equivalent:

  * (i)

$\left\|\nabla f(x)-\nabla f(y)\right\|\leq L\left\|x-y\right\|$ for all
$x,y\in{\rm I\\!R}^{n}$.

  * (ii)

$\left|f(x)-f(y)-\left\langle\nabla
f(y),x-y\right\rangle\right|\leq\dfrac{L}{2}\left\|x-y\right\|^{2}$ for all
$x,y\in{\rm I\\!R}^{n}.$

  * (iii)

$\left\|\nabla^{2}f(x)\right\|\leq L$ for all $x\in{\rm I\\!R}^{n}$.

[Proof.] The proof can be deduced from [32, Lemmas 1.2.2 and 1.2.3] and [43,
Lemma 8 of Ch. 5].

Next we recall the subdifferential constructions for proper extended-real-
valued functions $\varphi:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$
taken from [28, 29, 41] and used below. The (Fréchet) regular subdifferential
of $\varphi$ at $\bar{x}\in\mbox{\rm dom}\,\varphi$ is

$\displaystyle\widehat{\partial}\varphi(\bar{x}):=\Big{\\{}v\in{\rm
I\\!R}^{n}\;\Big{|}\;\liminf_{x\rightarrow\bar{x}}\dfrac{\varphi(x)-\varphi(\bar{x})-\left\langle
v,x-\bar{x}\right\rangle}{\left\|x-\bar{x}\right\|}\geq 0\Big{\\}},$ (2.2)

while the (Mordukhovich) limiting subdifferential of $\varphi$ at
$\bar{x}\in\mbox{\rm dom}\,\varphi$ is defined by

$\displaystyle\partial\varphi(\bar{x}):=\left\\{v\in{\rm
I\\!R}^{n}\;\big{|}\;\exists\,x^{k}\rightarrow\bar{x},\
\varphi(x^{k})\rightarrow\varphi(\bar{x}),\ \widehat{\partial}f(x^{k})\ni
v^{k}\rightarrow v\right\\}.$ (2.3)

When $\varphi$ is of class of $\mathcal{C}^{1}$-smooth functions, then both
subdifferentials in (2.2) and (2.3) reduce to the gradient
$\nabla\varphi(\bar{x})$. A necessary (but not sufficient) condition for
$\bar{x}\in{\rm I\\!R}^{n}$ to be a local minimizer of $\varphi$ is

$\displaystyle 0\in\partial\varphi(\bar{x}).$ (2.4)

A point that satisfies (2.4) is known in the literature as an
M$($ordukhovich$)$-stationary (or limiting-stationary) point of $\varphi$.
Since this paper does not deal with any other stationary concepts, we simply
use the stationary point term in what follows.

Let $g:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ be a proper l.s.c.
function. Given a parameter value $\lambda>0$, the Moreau envelope
$e_{\lambda}g(\cdot):{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ and the proximal
mapping $\textit{\rm Prox}_{\lambda g}(\cdot):{\rm
I\\!R}^{n}\rightrightarrows{\rm I\\!R}^{n}$ are defined, respectively, as

$e_{\lambda}g(x):=\inf_{y\in{\rm I\\!R}^{n}}\Phi_{\lambda,x}(y),$ (2.5)
$\mbox{\rm Prox}_{\lambda g}(x):=\mathop{\rm argmin}_{y\in{\rm
I\\!R}^{n}}\Phi_{\lambda,x}(y),$ (2.6)

where the minimizing function $\Phi_{\lambda,x}:{\rm
I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ is given by

$\displaystyle\Phi_{\lambda,x}(y):=g(y)+(2\lambda)^{-1}\left\|y-x\right\|^{2}.$
(2.7)

A function $g:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ is called prox-
bounded if there exists $\lambda>0$ such that $e_{\lambda}g(x)>-\infty$ for
some $x\in{\rm I\\!R}^{n}.$ The supremum of all such $\lambda$ is the
threshhold $\lambda_{g}$ of prox-boundedness for $g$. When $g$ is a convex
function, it is prox-bounded with the threshhold $\lambda_{g}=\infty$.
Moreover, its proximal mapping $\mbox{\rm Prox}_{\lambda g}$ is single-valued
and continuous in this case, while its Moreau envelope $e_{\lambda}g$ is
convex and $\mathcal{C}^{1}$-smooth for any $\lambda>0$; see, e.g., [41,
Theorem 2.26]. These remarkable properties can be extended for the class of
weakly convex functions introduced by Nurminskii [33] in the way equivalent to
the following definition.

######  Definition 2.4.

A proper l.s.c. function $g:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ is
called $\varrho$-weakly convex for some $\varrho\geq 0$ if the quadratically
shifted function $g(\cdot)+\dfrac{\varrho}{2}\left\|\cdot\right\|^{2}$ is
convex.

It has been well recognized in the literature that the class of weakly convex
functions is rather large including any ${\cal C}^{2}$-smooth function as well
as many important settings in nonsmooth and nonconvex constrained
optimization; see, e.g., [10, 47] and the references therein.

######  Remark 2.5.

(i) If $g$ is $\varrho$-weakly convex with $\varrho\geq 0$, then it is also
$\rho$-weakly convex for all $\rho\geq\varrho.$ As a consequence, any convex
function is $\varrho$-weakly convex for any $\varrho\geq 0$.

(ii) $g$ is $\mathcal{C}^{1}$-smooth, it follows from Remark 2.2 that its
$\varrho$-weak convexity is equivalent to the descent property with constant
$\varrho$ of $-g$.

(iii) Suppose that $g:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ is a
$\varrho$-weakly convex function and that $\lambda\in(0,\varrho^{-1})$. Then
for any $x\in{\rm I\\!R}^{n}$, the minimizing function $\Phi_{\lambda,x}(y)$
in (2.7) is represented by

$\displaystyle\Phi_{\lambda,x}(y)=g(y)+\dfrac{\varrho}{2}\left\|y-x\right\|^{2}+\dfrac{\lambda^{-1}-\varrho}{2}\left\|y-x\right\|^{2},$

being strongly convex with constant $\lambda^{-1}-\varrho>0$ since
$g(y)+\dfrac{\varrho}{2}\left\|y-x\right\|^{2}$ is convex.

(iv) If $g$ is weakly convex, the regular and limiting subdifferentials agree
for all $x\in{\rm I\\!R}^{n}$, i.e., $g$ is lower regular on ${\rm I\\!R}^{n}$
in the sense of [28].

The next result taken from [47, Proposition 3.13] shows that the weak
convexity of a function is a necessary and sufficient condition for the
associated proximal mapping (1.2) to be single-valued.

######  Proposition 2.6.

Let $g:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ be proper, l.s.c., and
prox-bounded with the threshold $\lambda_{g}\in(0,\infty]$. Then the following
conditions are equivalent:

(i) For all $\lambda\in(0,\lambda_{g})$, the mapping $\mbox{\rm Prox}_{\lambda
g}$ is single-valued on ${\rm I\\!R}^{n}$.

(ii) $g$ is $\lambda_{g}^{-1}$-weakly convex, where we use the convention
$\infty^{-1}=0$.
In this case, the mapping $\mbox{\rm Prox}_{\lambda g}$ is Lipschitz
continuous on ${\rm I\\!R}^{n}$ for all $\lambda\in(0,\lambda_{g})$.

Let us now recall the notion of $\varepsilon$-subdifferential broadly used in
convex analysis, optimization, and their numerous applications; see, e.g.,
[19, 30].

######  Definition 2.7.

Let $g:{\rm I\\!R}^{n}\rightarrow\overline{{\rm I\\!R}}$ be a proper l.s.c.
function, and let $\varepsilon\geq 0$. Then the $\varepsilon$-subdifferential
of $g$ at some $\bar{x}\in\mbox{\rm dom}\,g$ is denoted by

$\displaystyle{\partial}_{\varepsilon}g(\bar{x}):=\left\\{v\in\mathbb{R}^{n}\;\big{|}\;\left\langle
v,x-\bar{x}\right\rangle\leq g(x)-g(\bar{x})+\varepsilon\;\mbox{ whenever
}\;x\in{\rm I\\!R}^{n}\right\\}.$ (2.8)

For convex quadratic functions important for proximal-type considerations, the
$\varepsilon$-subdifferential is explicitly calculated from the definition;
see [19, Example 1.2.2].

######  Proposition 2.8.

Let $A$ be any $n\times n$ symmetric positive-semidefinite matrix, let
$b\in{\rm I\\!R}^{n}$, and let $g:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ be a
convex quadratic function defined by $g(x):=\dfrac{1}{2}\left\langle
Ax,x\right\rangle+\left\langle b,x\right\rangle$ for all $x\in{\rm
I\\!R}^{n}$. Then

$\displaystyle\partial_{\varepsilon}g(x)=\Big{\\{}A(x+e)+b\;\Big{|}\;\dfrac{1}{2}\left\langle
Ae,e\right\rangle\leq\varepsilon\Big{\\}}\;\text{ for all }\;x\in{\rm
I\\!R}^{n},\;\varepsilon\geq 0.$

A direct consequence of Proposition 2.8 is the following formula, which plays
an important role in convergence analysis of inexact proximal gradient methods
for convex functions conducted in [42].

######  Corollary 2.9.

Given $\bar{x}\in{\rm I\\!R}^{n}$, $\lambda>0$, and
$g(x):=(2\lambda)^{-1}\left\|x-\bar{x}\right\|^{2}$, we have

$\partial_{\varepsilon}g(x)=\big{\\{}\lambda^{-1}(x-\bar{x}+e)\;\big{|}\;\|e\|^{2}\leq
2\lambda\varepsilon\big{\\}}\;\text{ for all }\;x\in{\rm
I\\!R}^{n},\;\varepsilon\geq 0.$

[Proof.] Apply Proposition 2.8 with $A:=I/\lambda$ and $b:=-\bar{x}/\lambda$.

Observe that the $\varepsilon$-subdifferential (2.8) may be empty for simple
weakly convex functions. Indeed, the function $g:{\rm I\\!R}\rightarrow{\rm
I\\!R}$ given by $g(x):=-x^{2}$ on ${\rm I\\!R}$ is obviously $2-$weakly
convex while

$\displaystyle\partial_{\varepsilon}g(0)=\left\\{v\in{\rm
I\\!R}\;\big{|}\;vx\leq-x^{2}+\varepsilon\;\mbox{ whenever }\;x\in{\rm
I\\!R}\right\\}=\emptyset\;\text{ for all }\;\varepsilon\geq 0.$

For our purposes in this paper, we propose to the following proximal-type
modification of $\varepsilon$-subgradients that allows us to deal with
$\varrho$-weakly convex functions.

######  Definition 2.10.

Let $\varrho$ and $\varepsilon$ be the nonnegative numbers. The weak
$\varepsilon$-subdifferential of a $\varrho$-weakly convex function $g:{\rm
I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ at $\bar{x}\in\mbox{\rm dom}\,g$ is
defined by

$\partial_{\varepsilon,\varrho}g(\bar{x}):=\big{\\{}v\in\mathbb{R}^{n}\;\big{|}\;\langle
v,x-\bar{x}\rangle\leq
g(x)-g(\bar{x})+\dfrac{\varrho}{2}\|x-\bar{x}\|^{2}+\varepsilon\;\text{ for
all }\;x\in{\rm I\\!R}^{n}\big{\\}}.$ (2.9)

######  Remark 2.11.

It is straightforward to deduce from the definition that:

(i) If $\varrho=0,$ i.e., $g$ is a convex function, then

$\displaystyle\partial_{\varepsilon,0}g(\bar{x})=\partial_{\varepsilon}g(\bar{x}).$

(ii) We have the equalities

$\displaystyle\partial_{\varepsilon,\varrho}g(\bar{x})=\bigcap_{\delta>0}\partial_{\varepsilon,\varrho+\delta}g(\bar{x})=\bigcap_{\delta>0}\partial_{\varepsilon+\delta,\varrho}g(\bar{x}).$

(iii) $0\in\partial_{\varepsilon,\varrho}g(\bar{x})$ if and only if $\bar{x}$
is an $\varepsilon$-solution for minimizing the convex function
$\widetilde{g}(\cdot):=g(\cdot)+\dfrac{\varrho}{2}\left\|\cdot-\bar{x}\right\|^{2}$.
The latter means that

$\displaystyle\widetilde{g}(\bar{x})\leq\widetilde{g}(x)+\varepsilon\;\mbox{
for all }\;x\in{\rm I\\!R}^{n}.$

The next proposition represents the $\varepsilon-$weak subdifferential of a
$\varrho$-weakly convex function $g$ via the $\varepsilon$-subdifferential of
the quadratic shifted function
$g(\cdot)+\dfrac{\varrho}{2}\left\|\cdot\right\|^{2}$ and provides a sum rule
for this new type of approximate subdifferentials.

######  Proposition 2.12.

Let $\varrho,\rho,\varepsilon$ be nonnegative numbers with
$\nu:=\varrho+\rho$, and let $g,h:{\rm I\\!R}^{n}\rightarrow\overline{\rm
I\\!R}$ be $\varrho$-weakly convex and $\rho$-weakly convex, respectively.
Then the following assertions hold:

(i) For any $\bar{x}\in\mbox{\rm dom}\,g$, we have the equality

$\displaystyle{\partial}_{\varepsilon,\varrho}g(\bar{x})=\partial_{\varepsilon}(g+\dfrac{\varrho}{2}\left\|\cdot\right\|^{2})(\bar{x})-\varrho\bar{x}.$

(ii) For any $\bar{x}\in\mbox{\rm dom}\,g\cap\mbox{\rm dom}\,h$, it holds

$\displaystyle\partial_{\varepsilon,\nu}(g+h)(\bar{x})\supset\bigcup\big{\\{}\partial_{\varepsilon_{1},\varrho}g(\bar{x})+\partial_{\varepsilon_{2},\rho}h(\bar{x})\;\big{|}\;\varepsilon_{i}\geq
0,\;\varepsilon_{1}+\varepsilon_{2}\leq\varepsilon\big{\\}}.$ (2.10)

When ${\rm ri}(\mbox{\rm dom}\,g)\cap{\rm ri}(\mbox{\rm
dom}\,h)\neq\emptyset$, the equality in (2.10) is satisfied, and as a
consequence we get

$\displaystyle\partial_{\varepsilon,\nu}(g+h)(\bar{x})\subset\partial_{\varepsilon,\varrho}g(\bar{x})+\partial_{\varepsilon,\rho}h(\bar{x}).$
(2.11)

[Proof.] (i) Since
$\varphi(\cdot):=g(\cdot)+\dfrac{\varrho}{2}\left\|\cdot\right\|^{2}$, is
convex, it follows that

$\displaystyle\partial_{\varepsilon,\varrho}g(\bar{x})$
$\displaystyle=\left\\{v\in\mathbb{R}^{n}\;\big{|}\;\left\langle
v,x-\bar{x}\right\rangle\leq
g(x)-g(\bar{x})+\dfrac{\varrho}{2}\left\|x-\bar{x}\right\|^{2}+\varepsilon,\
\forall x\in{\rm I\\!R}^{n}\right\\}$
$\displaystyle=\left\\{v\in\mathbb{R}^{n}\;\big{|}\;\left\langle
v+\varrho\bar{x},x-\bar{x}\right\rangle\leq
g(x)+\dfrac{\varrho}{2}\left\|x\right\|^{2}-g(\bar{x})-\dfrac{\varrho}{2}\left\|\bar{x}\right\|^{2}+\varepsilon,\
\forall x\in{\rm I\\!R}^{n}\right\\}$
$\displaystyle=\left\\{v\in\mathbb{R}^{n}\;\big{|}\;\left\langle
v+\varrho\bar{x},x-\bar{x}\right\rangle\leq\varphi(x)-\varphi(\bar{x})+\varepsilon,\
\forall x\in{\rm I\\!R}^{n}\right\\}$
$\displaystyle=\partial_{\varepsilon}\varphi(\bar{x})-\varrho\bar{x}\;\mbox{
whenever }\;\bar{x}\in\mbox{\rm dom}\,g.$

(ii) We deduce from the $\varrho$-weak convexity of $g$ and $\varrho$-weak
convexity of $h$ that $g(\cdot)+\dfrac{\varrho}{2}\left\|\cdot\right\|^{2}$
and $h(\cdot)+\dfrac{\rho}{2}\left\|\cdot\right\|^{2}$ are convex functions.
Using the sum rule for $\varepsilon$-subdifferentials from [19, Theorem 3.1.1]
gives us

$\displaystyle\partial_{\varepsilon}(g+h+\dfrac{\nu}{2}\left\|\cdot\right\|^{2})(\bar{x})$
$\displaystyle=\partial_{\varepsilon}(g+\dfrac{\varrho}{2}\left\|\cdot\right\|^{2}+h+\dfrac{\rho}{2}\left\|\cdot\right\|^{2})(\bar{x})$
$\displaystyle\supset\bigcup\left\\{\partial_{\varepsilon_{1}}(g+\dfrac{\varrho}{2}\left\|\cdot\right\|^{2})(\bar{x})+\partial_{\varepsilon_{2}}(h+\dfrac{\rho}{2}\left\|\cdot\right\|^{2})(\bar{x})\;\big{|}\;\varepsilon_{i}\geq
0,\;\varepsilon_{1}+\varepsilon_{2}\leq\varepsilon\right\\},$ (2.12)

where the equality holds if ${\rm ri}(\mbox{\rm
dom}\,(g+\frac{\varrho}{2}\left\|\cdot\right\|^{2}))\cap{\rm ri}(\mbox{\rm
dom}\,(h+\frac{\rho}{2}\left\|\cdot\right\|^{2}))\neq\emptyset$, or
equivalently if ${\rm ri}(\mbox{\rm dom}\,g)\cap{\rm ri}(\mbox{\rm
dom}\,h)\neq\emptyset$. Observe by (i) that

$\displaystyle\partial_{\varepsilon}(g+h+\dfrac{\nu}{2}\left\|\cdot\right\|^{2})(\bar{x})=\partial_{\varepsilon}(g+h)(\bar{x})+\nu\bar{x},$

and that for all $\varepsilon_{1},\varepsilon_{2}\geq 0$ with
$\varepsilon_{1}+\varepsilon_{2}\leq\varepsilon$ we have

$\displaystyle\partial_{\varepsilon_{1}}(g+\dfrac{\varrho}{2}\left\|\cdot\right\|^{2})(\bar{x})+\partial_{\varepsilon_{2}}(h+\dfrac{\rho}{2}\left\|\cdot\right\|^{2})(\bar{x})$
$\displaystyle=\partial_{\varepsilon_{1},\varrho}g(\bar{x})+\varrho\bar{x}+\partial_{\varepsilon_{2},\rho}h(\bar{x})+\rho\bar{x}$
$\displaystyle=\partial_{\varepsilon_{1},\varrho}g(\bar{x})+\partial_{\varepsilon_{2},\rho}h(\bar{x})+\nu\bar{x}.$

Then the inclusion in (2) implies that

$\displaystyle\partial_{\varepsilon,\nu}(g+h)(\bar{x})\supset\bigcup\left\\{\partial_{\varepsilon_{1},\varrho}(g)(\bar{x})+\partial_{\varepsilon_{2},\rho}(h)(\bar{x})\;\big{|}\;\varepsilon_{i}\geq
0,\;\varepsilon_{1}+\varepsilon_{2}\leq\varepsilon\right\\},$ (2.13)

where the equality holds if ${\rm ri}(\mbox{\rm dom}\,g)\cap{\rm ri}(\mbox{\rm
dom}\,h)\neq\emptyset$. When the latter condition is satisfied, we deduce from
Remark 2.11(iii) that

$\displaystyle\partial_{\varepsilon,\nu}(g+h)(\bar{x})$
$\displaystyle=\bigcup\left\\{\partial_{\varepsilon_{1},\varrho}g(\bar{x})+\partial_{\varepsilon_{2},\rho}h(\bar{x})\;\big{|}\;\varepsilon_{i}\geq
0,\;\varepsilon_{1}+\varepsilon_{2}\leq\varepsilon\right\\}$
$\displaystyle\subset\partial_{\varepsilon,\varrho}g(\bar{x})+\partial_{\varepsilon,\rho}h(\bar{x}),$

which completes the proof of the proposition.

In the remainder of this section, we recall and discuss the Kurdyka-
Łojasiewciz (KL) property as formulated in [3], which plays an important in
establishing global convergence with convergence rates of many optimization
methods; see, e.g., [1, 2, 3] among other references.

######  Definition 2.13.

We say that a function $f:{\rm I\\!R}^{n}\rightarrow\overline{{\rm I\\!R}}$
enjoys the KL property at $\bar{x}\in\mbox{\rm dom}\,\partial f$ if there
exist $\eta\in(0,\infty]$, a neighborhood $U$ of $\bar{x}$. and a concave
continuous function $\psi:[0,\eta)\rightarrow[0,\infty)$ such that:

(i) $\psi(0)=0$.

(ii) $\psi$ is $\mathcal{C}^{1}$-smooth on $(0,\eta)$.

(iii) $\psi^{\prime}>0$ on $(0,\eta)$.

(iv) For all $x\in U$ with $f(\bar{x})<f(x)<f(\bar{x})+\eta$, we have

$\displaystyle\psi^{\prime}\big{(}f(x)-f(\bar{x})\big{)}{\rm dist}(0,\partial
f(x))\geq 1.$ (2.14)

It has been realized that the KL property is satisfied in broad settings. In
particular, it holds at every nonstationary point of $f$; see [3, Lemma 2.1
and Remark 3.2(b)]. Furthermore, it is proved in the original paper by
Łojasiewicz [26] that any analytic function $f:{\rm I\\!R}^{n}\rightarrow{\rm
I\\!R}$ satisfies the KL property at every point $\bar{x}$ with
$\psi(t)=~{}Mt^{1-q}$ for some $q\in[0,1)$. This property also holds for
continuous semialgebraic functions, continuous subanalytic functions, and
functions definable in an o-minimal structure [11, 12]. The notions of
subanalytic sets and sub-analytic functions can be found in [12, 17] while the
discussion on semialgebraic functions can be found in [2, 8]. For the reader
convenience, we recall some fundamental properties of subanalytic and
semialgebraic functions in the next two remarks.

######  Remark 2.14.

Some basic properties of subanalytic functions and subanalytic sets in [17, p.
597] and [12, p. 1208] are summarized as follows:

(i) The class of subanalytic sets is closed under finite unions and
intersections.

(ii) The Cartesian product of subanalytic sets is subanalytic.

(iii) If $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}^{p}$ and $g:{\rm
I\\!R}^{p}\rightarrow{\rm I\\!R}^{m}$ are subanalytic mappings, with $f$ being
continuous, then the composition $g\circ f$ is subanalytic. In particular, the
class of continuous subanalytic functions is closed under algebraic
operations.

(iv) Analytic functions are subanalytic.

(v) The inverse image of a subanalytic set under a subanalytic mapping is a
subanalytic set.
It follows from (i), (ii), and (v) that if the functions $f_{i}:{\rm
I\\!R}^{n}\rightarrow{\rm I\\!R}$ for $i=1,\ldots,m$ are subanalytic, then the
mapping $F:=(f_{1},\ldots,f_{m})$ is subanalytic as well.

######  Remark 2.15.

The following properties of semialgebraic functions are useful in the
subsequent sections:

(i) Finite sums and products of semialgebraic functions are semialgebraic.

(ii) Composition of semialgebraic functions or mappings are semialgebraic.

(iii) Functions of the type $f(x):=\inf_{y\in S}h(x,y)$, where $h$ and $S$ are
semialgebraic, are semialgebraic.

(iv) Semialgebraic functions are subanalytic.

(v) Both regular subdifferential (2.2) and limiting subdifferential (2.3) of
semialgebraic functions are semialgebraic set-valued mappings.
The properties listed in (i)-(iii) can be found in [3, 8]. Property (iv) is
mentioned in [11, p. 1208] while the proof of (v) follows from [20,
Proposition 3.1]. As a consequence of (i) and (iii), the Moreau envelope of a
proper, l.s.c., semialgebraic function is also semialgebraic, and thus it is
subanalytic.

##  3 Inexact Proximal Methods for Weakly Convex Functions

In this main section of the paper, we design and justify appropriate versions
of the inexact proximal point method and the inexact proximal gradient method
for the class of structured optimization problems of type (1.1) with smooth
nonconvex functions $f$ and extended-real-valued weakly convex functions $g$.
The section is split into three subsections. Firstly, we consider a general
framework for finding zeros of a single-valued continuous mapping $G:{\rm
I\\!R}^{n}\rightarrow{\rm I\\!R}^{n}$ when only inexact information about $G$
is accessible. This scheme is a nonsmooth extension of our previous
developments in [24, Algorithm 1] to find stationary points of
$\mathcal{C}^{1}$-smooth functions.

###  3.1 A General Framework for Finding Zeros of Continuous Mappings

Here we propose the following inexact algorithm to solve the problem $G(x)=0$,
where $G\colon{\rm I\\!R}^{n}\to{\rm I\\!R}^{n}$ is a single-valued continuous
mapping.

######  Algorithm 1.

######  Step 0 (initialization).

Select a starting point $x^{1}\in{\rm I\\!R}^{n}$, initial radii
$\varepsilon_{1},r_{1}>0$, radius reduction factors $\mu,\theta\in(0,1)$. Set
$k:=1.$

######  Step 1 (inexact mapping).

Find some $g^{k}$ such that

$\displaystyle\left\|g^{k}-G(x^{k})\right\|\leq\varepsilon_{k}.$ (3.1)

######  Step 2 (radius update).

If $\left\|g^{k}\right\|\leq r_{k}+\varepsilon_{k}$ then $r_{k+1}:=\mu r_{k},$
$\varepsilon_{k+1}:=\theta\varepsilon_{k}$ and $d^{k}:=0$. Otherwise, set
$r_{k+1}:=r_{k},\;\varepsilon_{k+1}:=\varepsilon_{k}$, and

$\displaystyle d^{k}:=-{\rm
Proj}(0,\mathbb{B}(g^{k},\varepsilon_{k}))=-\dfrac{\left\|g^{k}\right\|-\varepsilon_{k}}{\left\|g^{k}\right\|}g^{k}.$
(3.2)

######  Step 3 (stepsize).

Choose a stepsize $t_{k}>0.$

######  Step 4 (iteration update).

Set $x^{k+1}:=x^{k}+t_{k}d^{k}.$ Increase $k$ by $1$ and go back to Step 1.

Following the analysis in [24, Section 4], we introduce the notion of null
iterations of Algorithm 1 and provide some fundamental properties related to
this notion.

######  Definition 3.1.

The $k^{\rm th}$ iteration of Algorithm 1 is called a null iteration if
$x^{k+1}=x^{k}$. The set of all null iterations is denoted by

$\mathcal{N}:=\left\\{k\in{\rm I\\!N}\;\big{|}\;x^{k+1}=x^{k}\right\\}.$

######  Remark 3.2.

We have the following properties of null iterations for Algorithm 1:

(i) $k\in\mathcal{N}$ if and only if either one of the following equivalent
conditions holds:

$\displaystyle d^{k}=0\Longleftrightarrow r_{k+1}=\mu
r_{k}\Longleftrightarrow\varepsilon_{k+1}=\theta\varepsilon_{k}\Longleftrightarrow\left\|g^{k}\right\|\leq
r_{k}+\varepsilon_{k}.$ (3.3)

(ii) $\varepsilon_{k}\downarrow 0$ if and only if $r_{k}\downarrow 0$, which
is equivalent to the set $\mathcal{N}$ being infinite.

(iii) Considering $k\notin\mathcal{N}$, it follows from
$\left\|g^{k}\right\|>r_{k}+\varepsilon_{k}$ and (3.2) in Step 2 that

$\left\|d^{k}\right\|=\left\|g^{k}\right\|-\varepsilon_{k}>r_{k}+\varepsilon_{k}-\varepsilon_{k}=r_{k}.$

As a consequence, if $\varepsilon_{k}\leq r_{k},$ we get
$\varepsilon_{k}\leq\left\|d^{k}\right\|,$ and hence

$\displaystyle\left\|G(x^{k})\right\|\leq\left\|g^{k}\right\|+\varepsilon_{k}=\left\|d^{k}\right\|+2\varepsilon_{k}\leq
3\left\|d^{k}\right\|.$ (3.4)

(iv) If $\mathcal{N}$ is finite, observe that for any natural number $k\geq
N:=\max{\mathcal{N}}+1$, the $k^{\rm th}$ iteration is not a null one and then
deduce from (iii) that

$\displaystyle
r_{k}=r_{N},\;\varepsilon_{k}=\varepsilon_{N}\quad\text{and}\quad\left\|g^{k}\right\|>r_{k}+\varepsilon_{k}=r_{N}+\varepsilon_{N},\;\left\|d^{k}\right\|>r_{k}=r_{N}.$

This tell us that $\left\\{g^{k}\right\\}$ and $\left\\{d^{k}\right\\}$ are
bounded away from $0.$

The next result reveals relationships between sequences of inexact mappings,
directions and radii generated by Algorithm 1. The proofs for (i) and (ii) are
similar to [24, Proposition 4.7], while the last assertion of this proposition
is deduced from (i), (ii), the continuity of $G$, and condition (3.1).

######  Proposition 3.3.

Let
$\left\\{g^{k}\right\\},\;\left\\{d^{k}\right\\},\;\left\\{\varepsilon_{k}\right\\}$,
and $\left\\{r_{k}\right\\}$ be sequences generated by Algorithm 1. Then the
following assertions hold:

(i) $\varepsilon_{k}\downarrow 0$ if and only if there is an infinite set
$I\subset{\rm I\\!N}$ such that $g^{k}\overset{I}{\rightarrow}0$.

(ii) For any infinite set $I\subset{\rm I\\!N}$, we have the equivalence

$\displaystyle g^{k}\overset{I}{\rightarrow}0\Longleftrightarrow
d^{k}\overset{I}{\rightarrow}0.$

If there exists some infinite set $I\subset{\rm I\\!N}$ such that either
$g^{k}\overset{I}{\rightarrow}0$ or $d^{k}\overset{I}{\rightarrow}0$, one has
$G(x^{k})\overset{I}{\rightarrow}0.$

Now we recall the classical results that describe important properties of
accumulation points generated by a sequence satisfying Ostrowski’s limiting
condition. Asserting (i) of Lemma 3.4 was first established in [35, Theorem
28.1], while assertion (ii) of this lemma is taken from [17, Theorems 8.3.9
and 8.3.10].

######  Lemma 3.4.

Let $\left\\{x^{k}\right\\}$ be a sequence satisfying the Ostrowski condition

$\displaystyle\lim_{k\rightarrow\infty}\|x^{k+1}-x^{k}\|=0.$

Then the following assertions hold:

(i) If the sequence $\left\\{x^{k}\right\\}$ is bounded, then the set of
accumulation points of $\left\\{x^{k}\right\\}$ is nonempty, compact, and
connected in ${\rm I\\!R}^{n}$.

(ii) If $\left\\{x^{k}\right\\}$ has an isolated accumulation point, then this
sequence converges to it.

The next theorem, which is a nonsmooth extension of [24, Theorem 5.3], reveals
major convergence properties of the sequence $\left\\{x^{k}\right\\}$
generated by Algorithm 1.

######  Theorem 3.5.

Let $\left\\{x^{k}\right\\}$ be the sequence of iterates generated by
Algorithm 1. Assume that $\left\\{t_{k}\right\\}$ is bounded from above and
$\sum_{k=1}^{\infty}\left\|d^{k}\right\|^{2}<\infty$. Then the following
assertions hold:

(i) $\varepsilon_{k}\downarrow 0$ and $r_{k}\downarrow 0$ as
$k\rightarrow\infty.$

Every accumulation point of $\left\\{x^{k}\right\\}$ is a zero of $G$, and we
have
$\displaystyle{\sum_{k=1}^{\infty}}\left\|x^{k+1}-x^{k}\right\|^{2}<\infty$.

(ii) If the sequence $\left\\{x^{k}\right\\}$ is bounded, then the set of
accumulation points of $\left\\{x^{k}\right\\}$ is nonempty, compact, and
connected.

(iii) If $\left\\{x^{k}\right\\}$ has an isolated accumulation point, then the
entire sequence converges to this point.

[Proof.] Since $\sum_{k=1}^{\infty}\left\|d^{k}\right\|^{2}<\infty$, we have
that $d^{k}\rightarrow 0$ as $k\to\infty$. It follows from Proposition 3.3 and
Remark 3.2(ii) that $\varepsilon_{k}\downarrow 0$ and $r_{k}\downarrow 0$,
which in turn justifies (i) and the convergence $G(x^{k})\rightarrow 0$ as
$k\to\infty$. This implies that every accumulation point of
$\left\\{x^{k}\right\\}$ is a zero of $G$ by taking into account the
continuity of $G$. Denoting by $M$ an upper bound of $\left\\{t_{k}\right\\}$
gives us

$\displaystyle\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|^{2}=\sum_{k=1}^{\infty}t_{k}^{2}\left\|d^{k}\right\|^{2}\leq
M^{2}\sum_{k=1}^{\infty}\left\|d^{k}\right\|^{2}<\infty,$

which implies (ii). The latter yields $\left\|x^{k+1}-x^{k}\right\|\rightarrow
0$ as $k\rightarrow\infty$, i.e. $\left\\{x^{k}\right\\}$ satisfies the
Ostrowski condition. Then (iii) follows from Lemma 3.4.

Now we are going to deal with non-null iterations, which are useful to
establish a global convergence of Algorithm 1 with convergence rates. If ${\rm
I\\!N}\setminus\mathcal{N}$ is finite, the the iterative sequence
$\left\\{x^{k}\right\\}$ converges finitely. Thus we consider the case where
${\rm I\\!N}\setminus\mathcal{N}$ is infinite and get the following
relationships between $\left\\{x^{k}\right\\}$ and
$\left\\{x^{k}\right\\}_{k\in{\rm I\\!N}\setminus\mathcal{N}}$ that are
verified similarly to the proof of [24, Proposition 4.6(iv) and (5.25)].

######  Proposition 3.6.

Let $\left\\{x^{k}\right\\}$ be the sequence generated by Algorithm 1. Assume
further that the set ${\rm I\\!N}\setminus\mathcal{N}$ is infinite and
renumerate it as $\left\\{j_{1},j_{2},\ldots\right\\}$. Then defining the
sequence $\left\\{z^{k}\right\\}$ by

$\displaystyle z^{k}:=x^{j_{k}}\quad\text{ for all }\;k\in{\rm I\\!N},$ (3.5)

we have that $z^{k+1}=x^{j_{k}+1}$, $z^{k}\neq z^{k+1}$ for all $k\in{\rm
I\\!N}$, and that the set of accumulation points of $\left\\{x^{k}\right\\}$
is the same as of $\left\\{z^{k}\right\\}$. Furthermore,
$x^{k}\rightarrow\bar{x}$ for some $\bar{x}\in{\rm I\\!R}^{n}$ if and only if
$z^{k}\rightarrow\bar{x}$ as $k\to\infty$.

The next two propositions, taken from [24, Theorems 5.3, 5.6, 5.9], reveals
convergence properties with convergence rates of Algorithm 1 when $G=\nabla
f$, where $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ is a
$\mathcal{C}^{1}$-smooth function satisfying the descent condition from
Definition 2.1.

######  Proposition 3.7.

Let $\left\\{x^{k}\right\\}$ be the sequence generated by Algorithm 1 with
$G=\nabla f$, where $f$ a $\mathcal{C}^{1}$-smooth function satisfying the
descent condition for some constant $L>0$. Assume that there exist
$0<\tau_{1}\leq\tau_{2}<2L$ such that

$\displaystyle t_{k}\in\left[\tau_{1},\tau_{2}\right]\;\text{ for all
}\;k\in{\rm I\\!N}.$ (3.6)

Then either $\inf f(x^{k})>-\infty$, or the following assertions hold:

(i) $\varepsilon_{k}\downarrow 0$ and $r_{k}\downarrow 0$ as $k\to\infty$.

(ii) Every accumulation point of $\left\\{x^{k}\right\\}$ is a stationary
point of $f$.

(iii) If the sequence $\left\\{x^{k}\right\\}$ is bounded, then the set of
accumulation points of $\left\\{x^{k}\right\\}$ is nonempty, compact, and
connected.

(iv) If $\left\\{x^{k}\right\\}$ has an isolated accumulation point, then the
entire sequence $\left\\{x^{k}\right\\}$ converges to it.

######  Proposition 3.8.

Let $\left\\{x^{k}\right\\}$ be the sequence generated by Algorithm 1 with
$G=\nabla f$, where $f$ a $\mathcal{C}^{1}$-smooth function satisfying the
descent condition for some constant $L>0$, and where $\left\\{t_{k}\right\\}$
is chosen as in (3.6). Assume that $f$ satisfies the KL property at some
accumulation point $\bar{x}$ of $\left\\{x^{k}\right\\}$. Then the entire
sequence $\left\\{x^{k}\right\\}$ converges to $\bar{x}$, which is a
stationary point of $f$. Supposing in addition that ${\rm
I\\!N}\setminus\mathcal{N}$ is infinite and the function given in the KL
property is $\psi(t):=Mt^{1-q}$ for some $M>0$ and $q\in(0,1)$, the following
convergence rates are guaranteed for the sequence $\left\\{z^{k}\right\\}$
defined as in (3.5):

(i) If $q\in(0,1/2]$, then the sequence $\left\\{z^{k}\right\\}$ converges
linearly to $\bar{x}$.

(ii) If $q\in(1/2,1)$, then there exists a positive constant $\gamma$ such
that

$\displaystyle\left\|z^{k}-\bar{x}\right\|\leq\gamma
k^{-\frac{1-q}{2q-1}}\;\text{ for all large }\;k\in{\rm I\\!N}.$

###  3.2 Inexact Proximal Point Method

Now we are ready to introduce and develop the inexact proximal point method
for finding stationary points of a $\varrho$-weakly convex function $g:{\rm
I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$. The algorithm is as follows.

######  Algorithm 2 (Inexact proximal point method for weakly convex
functions).

######  Step 0 (initialization).

Select a proximal parameter $\lambda\in\big{(}0,\varrho^{-1}\big{)}$ and some
$\tau_{1},\tau_{2}$ satisfying the conditions
$0<\tau_{1}\leq\tau_{2}<2\lambda$. Choose a starting point
$x^{1}\in\mathbb{R}^{n}$, initial radii $\varepsilon_{1},r_{1}>0$, and radius
reduction factors $\mu,\theta\in(0,1)$. Set $k:=1.$

######  Step 1 (inexact proximal mapping).

Find some $p^{k}$ and define $g^{k}$ such that

$\displaystyle\left\|p^{k}-\mbox{\rm Prox}_{\lambda
g}(x^{k})\right\|\leq\lambda\varepsilon_{k}\text{ and
}g^{k}:=\lambda^{-1}(x^{k}-p^{k}).$ (3.7)

######  Step 2 (radius update).

If $\left\|g^{k}\right\|\leq r_{k}+\varepsilon_{k}$, then $r_{k+1}:=\mu
r_{k},\varepsilon_{k+1}:=\theta\varepsilon_{k},d^{k}:=0$. Otherwise, set
$r_{k+1}:=r_{k},\;\varepsilon_{k+1}:=\varepsilon_{k}$, and

$\displaystyle
d^{k}:=-\dfrac{\left\|g^{k}\right\|-\varepsilon_{k}}{\left\|g^{k}\right\|}g^{k}.$

######  Step 3 (stepsize).

Choose a stepsize $t_{k}\in[\tau_{1},\tau_{2}].$

######  Step 4 (iteration update).

Set $x^{k+1}:=x^{k}+t_{k}d^{k}$. Increase $k$ by $1$ and go back to Step 1.

We recall some important properties of Moreau envelopes of weakly convex
functions that are useful in the convergence analysis of Algorithm 2.

######  Proposition 3.9.

Let $g:{\rm I\\!R}^{n}\rightarrow\overline{{\rm I\\!R}}$ be a $\varrho$-weakly
convex function, and let $\lambda\in(0,\varrho^{-1})$. Then the following
assertions holds:

(i) The Moreau envelope $e_{\lambda}g$ is $\mathcal{C}^{1}$-smooth and its
gradient calculated by

$\displaystyle\nabla e_{\lambda}g(x)=\lambda^{-1}(x-\mbox{\rm Prox}_{\lambda
g}(x)).$ (3.8)

(ii) The Moreau envelope $e_{\lambda}g$ satisfies the descent condition with
constant $\lambda^{-1}$ meaning that

$\displaystyle e_{\lambda}g(y)\leq e_{\lambda}g(x)+\left\langle\nabla
e_{\lambda}g(x),y-x\right\rangle+(2\lambda)^{-1}\left\|y-x\right\|^{2}\text{
for all }x,y\in{\rm I\\!R}^{n}.$ (3.9)

(iii) Every stationary point of $e_{\lambda}g$ is a stationary point of $g$.

[Proof.] Assertions (i) and (ii) follow from [16, Lemma 2.5]. Taking any $x$
with $\nabla e_{\lambda}g(x)=0$, we deduce from (3.8) that $x=\mbox{\rm
Prox}_{\lambda g}(x)$. By (2.6), $x$ solves the problem

$\displaystyle\mathop{\rm minimize}_{y\in{\rm
I\\!R}^{n}}\big{\\{}g(y)+(2\lambda)^{-1}\left\|y-x\right\|^{2}\big{\\}}.$

Applying the generalized Fermat rule and the subdifferential sum rule to the
function $y\mapsto g(y)+(2\lambda)^{-1}\left\|y-x\right\|^{2}$ gives us
$0\in\partial g(x)$, which verifies assertion (iii).

######  Remark 3.10.

Proposition 3.9(i) allows us to conclude that the inexact proximal point
method in Algorithm 2 is a special case of the general scheme to find zeros of
continuous functions proposed in Algorithm 1. Indeed, we can equivalently
rewrite condition (3.7) as follows:

$\displaystyle\left\|g^{k}-\nabla e_{\lambda}g(x^{k})\right\|$
$\displaystyle=\left\|\lambda^{-1}(x^{k}-p^{k})-\lambda^{-1}(x^{k}-{\rm
Prox}_{\lambda g}(x^{k}))\right\|$ $\displaystyle=\lambda^{-1}\left\|{\rm
Prox}_{\lambda g}(x^{k})-p^{k}\right\|\leq\varepsilon_{k}.$

Therefore, Algorithm 1 reduces to Algorithm 2 with $G:=\nabla e_{\lambda}g$
and $t_{k}\in[\tau_{1},\tau_{2}]$.

The next theorem, which is based on Proposition 3.9 and Theorem 3.7, reveals
convergence properties of the inexact proximal point Algorithm 1 to find
stationary points of weakly convex functions.

######  Theorem 3.11.

Let $g:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ be a $\varrho$-weakly
convex function with $\varrho>0$, and let $\left\\{x^{k}\right\\}$ be the
sequence generated by Algorithm 2. If
$\left\|x^{k}\right\|\not\rightarrow\infty$, then the following assertions
hold:

(i) $\varepsilon_{k}\downarrow 0$ and $r_{k}\downarrow 0$ as $k\to\infty$.

(ii) Every accumulation point of $\left\\{x^{k}\right\\}$ is a stationary
point of $g$.

(iii) If the sequence $\left\\{x^{k}\right\\}$ is bounded, then the set of
accumulation points of $\left\\{x^{k}\right\\}$ is nonempty, compact, and
connected.

(iv) If $\left\\{x^{k}\right\\}$ has an isolated accumulation point, then the
entire sequence $\left\\{x^{k}\right\\}$ converges to it.

[Proof.] It follows from Remark 3.10 that Algorithm 1 reduces to Algorithm 2
with $G=\nabla e_{\lambda}g$ and $t_{k}\in[\tau_{1},\tau_{2}]$ for all
$k\in{\rm I\\!N}$. By the descent property with constant $\lambda^{-1}$ of
$e_{\lambda}g$ from Proposition 3.9(ii) and the choices of
$\tau_{1},\tau_{2}$, the assumptions for Proposition 3.7 with
$f:=e_{\lambda}g$ and $L:=\lambda^{-1}$ are satisfied. This ensures the
fulfillment of assertions (i), (iii), (iv) and that every accumulation point
of $\left\\{x^{k}\right\\}$ is a stationary point of $e_{\lambda}g$. Combining
this with Proposition 3.9(iii) yields (ii) and completes the proof.

The final result of this subsection employs the KL property for Moreau
envelopes to establish the global convergence of the entire sequence of
iterates in Algorithm 2 to a stationary point of a weakly convex function with
giving constructive convergence rates.

######  Theorem 3.12.

Let $g:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ be a $\varrho$-weakly
convex function with $\varrho\geq 0$, and let $\left\\{x^{k}\right\\}$ be the
sequence generated by Algorithm 2 with $\varepsilon_{1}\leq r_{1}$ and
$\theta\leq\mu$. Assume that $e_{\lambda}g$ satisfies the KL property at some
accumulation point $\bar{x}$ of $\left\\{x^{k}\right\\}$. Then the entire
sequence $\left\\{x^{k}\right\\}$ converges to $\bar{x}$, which is a
stationary point of $g$. If ${\rm I\\!N}\setminus\mathcal{N}$ is infinite and
the function $\psi$ in the KL condition is $\psi(t):=Mt^{1-q}$ for some $M>0$
and $q\in(0,1)$, then the following convergence rates are guaranteed for the
sequence $\left\\{z^{k}\right\\}$ from (3.5):

(i) For $q\in(0,1/2]$, the sequence $\left\\{z^{k}\right\\}$ converges
linearly to $\bar{x}$.

(ii) For $q\in(1/2,1)$, there exists $\gamma>0$ such that

$\displaystyle\left\|z^{k}-\bar{x}\right\|\leq\gamma
k^{-\frac{1-q}{2q-1}}\;\text{ for all large }\;k\in{\rm I\\!N}.$

[Proof.] By Remark 3.10, Algorithm 2 reduces to Algorithm 1 with $G:=\nabla
e_{\lambda}g$ and $t_{k}\in[\tau_{1},\tau_{2}]$, $k\in{\rm I\\!N}$. If
$\left\\{x^{k}\right\\}$ has an accumulation point $\bar{x}$ and
$e_{\lambda}g$ satisfies the KL property at $\bar{x}$, then the assumptions of
Proposition 3.8 are satisfied for $f:=e_{\lambda}g$. Therefore, the claimed
results hold with taking into account that stationary points of $f$ are
stationary point of $g$ by Proposition 3.9(iii).

###  3.3 Inexact Proximal Gradient Method

In this subsection, we derive our major results on the new inexact proximal
gradient method to solve optimization problems of the type

$\displaystyle{\rm minimize}\quad\varphi(x):=f(x)+g(x),$ (3.10)

where $f:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ is a $\mathcal{C}^{1}$-smooth
function satisfying the descent condition (2.1) with some $L>0$, and where
$g:{\rm I\\!R}^{n}\rightarrow\overline{\rm I\\!R}$ is a proper, l.s.c.,
$\varrho$-weakly convex function with $\varrho\geq 0$. As mention in Section
1, the formally unconstrained framework of (3.10) covers problems of
constrained optimization via $x\in\mbox{\rm dom}\,g$.

Define the composite gradient mapping $T_{\lambda}:{\rm
I\\!R}^{n}\rightarrow{\rm I\\!R}^{n}$ as $\lambda\in(0,\varrho^{-1})$ with
$0^{-1}:=\infty$ by

$\displaystyle T_{\lambda}(x)=\mbox{\rm Prox}_{\lambda g}(F_{\lambda}(x)),$

where $F_{\lambda}(x):=x-\lambda\nabla f(x)$. The mapping $T_{\lambda}$ can be
expressed by (2.7) as

$\displaystyle T_{\lambda}(x)=\mathop{\rm argmin}_{y\in{\rm
I\\!R}^{n}}\Phi_{\lambda,F_{\lambda}(x)}(y),$ (3.11)

providing the following quadratic approximation of $\varphi$ (see [6]):

$\displaystyle T_{\lambda}(x)$ $\displaystyle=\mathop{\rm argmin}_{y\in{\rm
I\\!R}^{n}}\big{\\{}g(y)+(2\lambda)^{-1}\left\|y-(x-\lambda\nabla
f(x))\right\|^{2}\big{\\}}$ $\displaystyle=\mathop{\rm argmin}_{y\in{\rm
I\\!R}^{n}}\big{\\{}(\lambda/2)\left\|\nabla
f(x)\right\|^{2}+\left\langle\nabla
f(x),y-x\right\rangle+(2\lambda)^{-1}\left\|y-x\right\|^{2}+g(y)\big{\\}}$
$\displaystyle=\mathop{\rm argmin}_{y\in{\rm
I\\!R}^{n}}\big{\\{}f(x)+\left\langle\nabla
f(x),y-x\right\rangle+(2\lambda)^{-1}\left\|y-x\right\|^{2}+g(y)\big{\\}}.$
(3.12)

Define further the gradient mapping $G_{\lambda}:{\rm
I\\!R}^{n}\rightarrow{\rm I\\!R}^{n}$ by

$\displaystyle G_{\lambda}(x):=\lambda^{-1}(x-T_{\lambda}(x)).$ (3.13)

######  Remark 3.13.

By Proposition 2.6, $\mbox{\rm Prox}_{\lambda g}$ is continuous. Then the
continuity of $\nabla f$ yields this property for $F_{\lambda},T_{\lambda}$,
and $G_{\lambda}$. Moreover, $G_{\lambda}(x)=0$ implies that
$x=T_{\lambda}(x).$ It follows from (3.12) with taking into account the
generalized Fermat’s rule and the subdifferential sum rule that

$\displaystyle 0\in\nabla f(x)+\partial g(x)=\partial\varphi(x).$

Now we are ready to propose the inexact proximal gradient method (IPGM) to
find stationary points of the class of functions $\varphi$ given (3.10) under
the assumptions therein.

######  Algorithm 3 (Inexact proximal gradient method).

######  Step 0 (initialization).

Select a proximal parameter $\lambda\in\big{(}0,(L+\varrho)^{-1}\big{)},$ a
starting point $x^{1}\in\mathbb{R}^{n}$, initial radii
$\varepsilon_{1},r_{1}>0$, radius reduction factors $\mu,\theta\in(0,1)$, and
sequence of manually controlled errors
$\left\\{\rho_{k}\right\\}\subset[0,\infty)$. Set $k:=1.$

######  Step 1 (inexact proximal mapping).

Find a vector $p^{k}\in{\rm I\\!R}^{n}$ satisfying

$\displaystyle\Phi_{\lambda,F_{\lambda}(x^{k})}(p^{k})\leq\inf\Phi_{\lambda,F_{\lambda}(x^{k})}+\min\left\\{\dfrac{\lambda(1-\lambda\varrho)\varepsilon_{k}^{2}}{2},\rho_{k}\right\\}$
(3.14)

and define $g^{k}:=\lambda^{-1}(x^{k}-p^{k})$.

######  Step 2 (iteration update).

If $\left\|g^{k}\right\|\leq r_{k}+\varepsilon_{k}$, then $r_{k+1}:=\mu
r_{k},\varepsilon_{k+1}:=\theta\varepsilon_{k}$ and $x^{k+1}:=x^{k}.$
Otherwise, set $r_{k+1}:=r_{k},\varepsilon_{k+1}:=\varepsilon_{k}$, and
$x^{k+1}:=p^{k}$. Increase $k$ by $1$ and go back to Step 1.

The next proposition shows that the sequence $\left\\{x^{k}\right\\}$ in
Algorithm 3 is the one generated by Algorithm 1 for finding zeros of the
continuous mapping $G_{\lambda}$ from (3.13).

######  Proposition 3.14.

Let $\left\\{g^{k}\right\\},\left\\{r_{k}\right\\}$, and
$\left\\{\varepsilon_{k}\right\\}$ be the sequences generated by Algorithm 3,
and let the sequences of directions $\left\\{d^{k}\right\\}$ and stepsizes
$\left\\{t_{k}\right\\}$ be defined as

$\displaystyle d^{k}:=\begin{cases}0&\text{\rm if }\left\|g^{k}\right\|\leq
r_{k}+\varepsilon_{k},\\\
-\dfrac{\left\|g^{k}\right\|-\varepsilon_{k}}{\left\|g^{k}\right\|}g^{k}&\text{\rm
otherwise}\end{cases}\quad\text{ and }\quad
t_{k}:=\begin{cases}2\lambda&\text{\rm if }d^{k}=0,\\\
\lambda\dfrac{\left\|g^{k}\right\|}{\left\|d^{k}\right\|}&\text{\rm if
}d^{k}\neq 0.\end{cases}$ (3.15)

Then the following assertions hold for all $k\in{\rm I\\!N}:$

(i)
$\left\|p^{k}-T_{\lambda}(x^{k})\right\|\leq\min\left\\{\lambda\varepsilon_{k},\sqrt{\dfrac{2\rho_{k}}{\lambda^{-1}-\varrho}}\right\\}$.

(ii) $x^{k+1}=x^{k}+t_{k}d^{k}$.

(iii) $t_{k}\geq\lambda$ and if in addition $\varepsilon_{k}\leq r_{k}$, then
$t_{k}\leq 2\lambda$.

(iv) $\left\|g^{k}-G_{\lambda}(x^{k})\right\|\leq\varepsilon_{k}$ and
$\left\langle
G_{\lambda}(x^{k}),d^{k}\right\rangle\leq-\left\|d^{k}\right\|^{2}.$

[Proof.] By Remark 2.5(iii), the function $\Phi_{\lambda,F_{\lambda}(x^{k})}$
is strongly convex with constant $\lambda^{-1}-\varrho$. Using [32, Corollary
3.2.3] gives us the estimate

$\displaystyle\Phi_{\lambda,F_{\lambda}(x^{k})}(y)-\Phi_{\lambda,F_{\lambda}(x^{k})}(T_{\lambda}(x^{k}))\geq\dfrac{\lambda^{-1}-\varrho}{2}\left\|y-T_{\lambda}(x^{k})\right\|^{2}\text{
for all }y\in{\rm I\\!R}^{n}.$

Then the choice of $p^{k}$ in (3.14) yields

$\displaystyle\dfrac{\lambda^{-1}-\varrho}{2}\left\|p^{k}-T_{\lambda}(x^{k})\right\|^{2}\leq\min\left\\{\dfrac{\varepsilon_{k}^{2}\lambda^{2}(\lambda^{-1}-\varrho)}{2},\rho_{k}\right\\}.$

Dividing both sides by $\dfrac{\lambda^{-1}-\varrho}{2}>0$ and then taking the
square root verify assertion (i).

The two assertions (ii) and (iii) obviously hold if $d^{k}=0$. Otherwise,
$\left\|g^{k}\right\|>r_{k}+\varepsilon_{k}$ and
$\left\|d^{k}\right\|=\left\|g^{k}\right\|-\varepsilon_{k}$ from (3.15). By
using $g^{k}=\lambda^{-1}(x^{k}-p^{k})$ in Step 1, we get

$\displaystyle
t_{k}d^{k}=-\lambda\dfrac{\left\|g^{k}\right\|}{\left\|d^{k}\right\|}\cdot\dfrac{\left\|g^{k}\right\|-\varepsilon_{k}}{\left\|g^{k}\right\|}g^{k}=-\lambda
g^{k}=p^{k}-x^{k}.$

Combining this with $x^{k+1}=p^{k}$ from Step 2 yields
$x^{k}+t_{k}d^{k}=p^{k}=x^{k+1}$, which verifies (ii). Moreover,

$\displaystyle
t_{k}=\lambda\dfrac{\left\|g^{k}\right\|}{\left\|d^{k}\right\|}=\lambda\dfrac{\left\|g^{k}\right\|}{\left\|g^{k}\right\|-\varepsilon_{k}}\geq\lambda.$

Now taking into account that $\varepsilon_{k}\leq r_{k}$ brings us to

$\displaystyle\left\|d^{k}\right\|=\left\|g^{k}\right\|-\varepsilon_{k}>r_{k}+\varepsilon_{k}-\varepsilon_{k}=r_{k}\geq\varepsilon_{k},$

which in turn implies that

$\displaystyle
t_{k}=\lambda\dfrac{\left\|g^{k}\right\|}{\left\|d^{k}\right\|}=\lambda\dfrac{\left\|d^{k}\right\|+\varepsilon_{k}}{\left\|d^{k}\right\|}=\lambda\left(1+\dfrac{\varepsilon_{k}}{\left\|d^{k}\right\|}\right)\leq
2\lambda$

and therefore justifies assertion (iii).

By (i) and the constructions of $g^{k}$ in Step 1 as well as
$G_{\lambda}(x^{k})$ in (3.13), we get

$\displaystyle\left\|g^{k}-G_{\lambda}(x^{k})\right\|=\left\|\lambda^{-1}(x^{k}-p^{k})-\lambda^{-1}(x^{k}-T_{\lambda}(x^{k}))\right\|=\lambda^{-1}\left\|p^{k}-T_{\lambda}(x^{k})\right\|\leq\varepsilon_{k},$

which verifies the first assertion in (iv). The second assertion therein in
the case where $d^{k}\neq 0$ follows from the characterization of projections
by noting that $d^{k}=-{\rm Proj}(0|\mathbb{B}(g^{k},\varepsilon_{k}))$ and
$G_{\lambda}(x^{k})\in\mathbb{B}(g^{k},\varepsilon_{k})$. This completes the
proof of the proposition.

The following result addresses the inexact calculation of proximal points in
Step 1 of Algorithm 3.

######  Proposition 3.15.

For any $k\in{\rm I\\!N}$, there are
$\xi_{k}\in\partial_{\rho_{k},\varrho}g(p^{k})$ and $e^{k}\in{\rm I\\!R}^{n}$
with $\left\|e^{k}\right\|\leq\sqrt{2\lambda\rho_{k}}$ and

$\displaystyle 0=\xi_{k}+\lambda^{-1}(p^{k}-F_{\lambda}(x^{k})+e^{k}).$

[Proof.] Condition (3.14) tells us that $p^{k}$ is a $\rho_{k}$-solution to
the problem of minimizing the convex function
$\Phi_{\lambda,F_{\lambda}(x^{k})}$. It follows from [19, Theorem 1.1.5] that

$\displaystyle 0$
$\displaystyle\in\partial_{\rho_{k}}\Phi_{\lambda,F_{\lambda}(x^{k})}(p^{k}).$
(3.16)

Let $h:{\rm I\\!R}^{n}\rightarrow{\rm I\\!R}$ be the convex quadratic function
defined by $h(\cdot):=(2\lambda^{-1}\left\|\cdot-
F_{\lambda}(x^{k})\right\|^{2}.$ It follows from (2.7) that
$\Phi_{\lambda,F_{\lambda}(x^{k})}(\cdot)=g(\cdot)+h(\cdot).$ By Remark 2.11
and Proposition 2.12(ii), we have

$\displaystyle\partial_{\rho_{k}}\Phi_{\lambda,F_{\lambda}(x^{k})}(p^{k})\subset\partial_{\rho_{k},\varrho}\Phi_{\lambda,F_{\lambda}(x^{k})}(p^{k})$
$\displaystyle\subset{\partial}_{\rho_{k},\varrho}g(p^{k})+{\partial}_{\rho_{k},0}h(p^{k})={\partial}_{\rho_{k},\varrho}g(p^{k})+{\partial}_{\rho_{k}}h(p^{k}).$

Combining the latter with (3.16) lead us to the inclusion

$\displaystyle
0\in{\partial}_{\rho_{k},\varrho}g(p^{k})+{\partial}_{\rho_{k}}h(p^{k}).$
(3.17)

Furthermore, it follows from Corollary 2.9 that

$\displaystyle{\partial}_{\rho_{k}}h(p^{k})=\big{\\{}\lambda^{-1}(p^{k}-F_{\lambda}(x^{k})+e)\big{|}\left\|e\right\|\leq\sqrt{2\lambda\rho_{k}}\big{\\}}.$

Then (3.17) yields the existence of some
$\xi_{k}\in\partial_{\rho_{k},\varrho}g(p^{k})$ and $e^{k}\in{\rm I\\!R}^{n}$
with $\left\|e^{k}\right\|\leq\sqrt{2\lambda\rho_{k}}$ such that

$\displaystyle 0=\xi_{k}+\lambda^{-1}(p^{k}-F_{\lambda}(x^{k})+e^{k}),$

and thus we are done with the verification of this proposition.

The next proposition is crucial in deriving convergence properties of
Algorithm 3.

######  Proposition 3.16.

At iteration $k^{\rm th}$ of Algorithm 3, suppose that $\varepsilon_{k}\leq
r_{k}$. Then we have the estimate

$\displaystyle
C_{1}\left\|d^{k}\right\|^{2}\leq\varphi(x^{k})-\varphi(x^{k+1})+C_{2}\sqrt{\rho_{k}}\left\|d^{k}\right\|+\rho_{k},$
(3.18)

where the constants $C_{1}$ and $C_{2}$ are computed by

$\displaystyle C_{1}:=\lambda(1-\lambda(L+\varrho))\quad\text{ and }\quad
C_{2}:=2\left(\sqrt{\dfrac{2}{\lambda^{-1}-\varrho}}+\sqrt{2\lambda}\right).$
(3.19)

[Proof.] Estimate (3.16) obviously holds at null iterations, and so we suppose
that $k\notin\mathcal{N}$. It follows from (3.12) the composite gradient
mapping representation

$\displaystyle T_{\lambda}(x^{k})=\mathop{\rm argmin}_{y\in{\rm
I\\!R}^{n}}\big{\\{}f(x^{k})+\left\langle\nabla
f(x^{k}),y-x^{k}\right\rangle+(2\lambda)^{-1}\left\|y-x^{k}\right\|^{2}+g(y)\big{\\}}.$

Applying the generalized Fermat rule to this problem, we find
$\xi_{\lambda}(x^{k})\in\partial g(T_{\lambda}(x^{k}))$ such that

$\displaystyle 0=\nabla
f(x^{k})+\lambda^{-1}(T_{\lambda}(x^{k})-x^{k})+\xi_{\lambda}(x^{k})=\xi_{\lambda}(x^{k})+\lambda^{-1}(T_{\lambda}(x^{k})-F_{\lambda}(x^{k})).$
(3.20)

By Proposition 3.15, there exist
$\xi_{k}\in\partial_{\rho_{k},\varrho}g(p^{k})$ and $e^{k}\in{\rm I\\!R}^{n}$
with $\left\|e^{k}\right\|\leq\sqrt{2\lambda\rho_{k}}$ and

$\displaystyle 0=\xi_{k}+\lambda^{-1}(p^{k}-F_{\lambda}(x^{k})+e^{k}).$ (3.21)

It follows from (3.21), the descent property of $f$ with constant $L$, and the
first equality in (3.20) that

$\displaystyle\varphi(x^{k+1})$ $\displaystyle\overset{\eqref{descent
condition}}{=}f(x^{k+1})+g(x^{k+1})\leq f(x^{k})+t_{k}\left\langle\nabla
f(x^{k}),d^{k}\right\rangle+\dfrac{Lt_{k}^{2}}{2}\left\|d^{k}\right\|^{2}+g(x^{k+1})$
$\displaystyle\overset{\eqref{def xi
k}}{=}f(x^{k})+t_{k}\left\langle\dfrac{1}{\lambda}(x^{k}-T_{\lambda}(x^{k}))-\xi_{\lambda}(x^{k}),d^{k}\right\rangle+\dfrac{Lt_{k}^{2}}{2}\left\|d^{k}\right\|^{2}+g(x^{k+1})$
$\displaystyle\overset{\eqref{def G lambda}}{=}f(x^{k})+t_{k}\left\langle
G_{\lambda}(x^{k}),d^{k}\right\rangle+\dfrac{Lt_{k}^{2}}{2}\left\|d^{k}\right\|^{2}+g(x^{k+1})-t_{k}\left\langle\xi_{\lambda}(x^{k}),d^{k}\right\rangle$
$\displaystyle\leq\left(f(x^{k})-t_{k}\left\|d^{k}\right\|^{2}+\dfrac{Lt_{k}^{2}}{2}\left\|d^{k}\right\|^{2}\right)+\left(g(x^{k+1})+\left\langle\xi_{\lambda}(x^{k}),x^{k}-x^{k+1}\right\rangle\right),$
(3.22)

where the last inequality is implied by Proposition 3.14(ii,iv). The second
term on the right hand side in the latter inequality can be expressed as

$\displaystyle
g(x^{k+1})+\left\langle\xi_{\lambda}(x^{k}),x^{k}-x^{k+1}\right\rangle$
$\displaystyle=g(x^{k+1})+\left\langle\xi_{k},x^{k}-x^{k+1}\right\rangle+\left\langle\xi_{\lambda}(x^{k})-\xi_{k},x^{k}-x^{k+1}\right\rangle.$
(3.23)

Since $k\notin\mathcal{N},$ Step 2 gives us $x^{k+1}=p^{k}.$ Using the
definition of approximate subdifferential for weakly convex functions (2.10)
with taking into account $\xi_{k}\in\partial_{\rho_{k},\varrho}g(x^{k+1})$
gives us

$\displaystyle g(x^{k+1})+\left\langle\xi_{k},x^{k}-x^{k+1}\right\rangle$
$\displaystyle\leq
g(x^{k})+\dfrac{\varrho}{2}\left\|x^{k}-x^{k+1}\right\|^{2}+\rho_{k}$
$\displaystyle=g(x^{k})+\dfrac{\varrho
t_{k}^{2}}{2}\left\|d^{k}\right\|^{2}+\rho_{k}.$ (3.24)

Combining the equalities in (3.20), (3.21) with
$\left\|e^{k}\right\|\leq\sqrt{2\lambda\rho_{k}}$ and Proposition 3.14(i), we
get

$\displaystyle\left\langle\xi_{\lambda}(x^{k})-\xi_{k},x^{k}-x^{k+1}\right\rangle=\lambda^{-1}\left\langle
p^{k}+e^{k}-T_{\lambda}(x^{k}),x^{k}-x^{k+1}\right\rangle$
$\displaystyle\leq\lambda^{-1}\left\|p^{k}-T_{\lambda}(x^{k})+e^{k}\right\|\cdot\left\|x^{k}-x^{k+1}\leq\lambda^{-1}t_{k}\right\|\left(\left\|p^{k}-T_{\lambda}(x^{k})\right\|+\left\|e^{k}\right\|\right)\cdot\left\|d^{k}\right\|$
$\displaystyle\leq\dfrac{t_{k}}{\lambda}\left(\sqrt{\dfrac{2\rho_{k}}{\lambda^{-1}-\varrho}}+\sqrt{2\lambda\rho_{k}}\right)\left\|d^{k}\right\|.$
(3.25)

It follows from (3.23)–(3.3) the fulfillment of the estimate

$\displaystyle
g(x^{k+1})+\left\langle\xi_{\lambda}(x^{k}),x^{k}-x^{k+1}\right\rangle\leq
g(x^{k})+\dfrac{\varrho
t_{k}^{2}}{2}\left\|d^{k}\right\|^{2}+\rho_{k}+\dfrac{t_{k}}{\lambda}\left(\sqrt{\dfrac{2\rho_{k}}{\lambda^{-1}-\varrho}}+\sqrt{2\lambda\rho_{k}}\right)\left\|d^{k}\right\|.$
(3.26)

Since $\varepsilon_{k}\leq r_{k}$, Proposition 3.14(iii) tells us
$t_{k}\in[\lambda,2\lambda]$. Combining (3.26) with (3.22), $t_{k}\leq
2\lambda$, and $\varphi(x^{k})=f(x^{k})+g(x^{k})$ ensures that

$\displaystyle\varphi(x^{k+1})$
$\displaystyle\leq\varphi(x^{k})-t_{k}\left\|d^{k}\right\|^{2}+\dfrac{(L+\varrho)t_{k}^{2}}{2}\left\|d^{k}\right\|^{2}+\rho_{k}+\dfrac{t_{k}}{\lambda}\left(\sqrt{\dfrac{2\rho_{k}}{\lambda^{-1}-\varrho}}+\sqrt{2\lambda\rho_{k}}\right)\left\|d^{k}\right\|$
$\displaystyle\leq\varphi(x^{k})-\left(t_{k}-\dfrac{(L+\varrho)t_{k}^{2}}{2}\right)\left\|d^{k}\right\|^{2}+C_{2}\sqrt{\rho_{k}}\left\|d^{k}\right\|+\rho_{k}.$
(3.27)

By using $t_{k}\in[\lambda,2\lambda]$, we also arrive at

$\displaystyle\left(t_{k}-\dfrac{(L+\varrho)t_{k}^{2}}{2}\right)=t_{k}\left(1-\dfrac{(L+\varrho)t_{k}}{2}\right)\geq\lambda(1-\lambda(L+\varrho))=C_{1}.$

Finally, applying the latter to (3.3) leads us to

$\displaystyle\varphi(x^{k+1})$
$\displaystyle\leq\varphi(x^{k})-C_{1}\left\|d^{k}\right\|^{2}+C_{2}\sqrt{\rho_{k}}\left\|d^{k}\right\|+\rho_{k},$

which is claimed in the proposition.

The following major result for our IPGM considers two types of errors in
Algorithm 3 and shows that the algorithm generates stationary accumulation
points and converges to isolated stationary point.

######  Theorem 3.17.

Let $C_{1},C_{2}$ be defined in (3.19), and let $\left\\{x^{k}\right\\}$ be
the sequence generated by Algorithm 3 such that $\varepsilon_{1}\leq r_{1}$,
$\theta\leq\mu$, and either

$\displaystyle\sum_{k=1}^{\infty}\rho_{k}<\infty,\quad\text{ or
}\quad\rho_{k}=C\varepsilon_{k}^{2}\quad\text{ for all }\;k\in{\rm I\\!N},$
(3.28)

where $C=\min\left\\{\dfrac{C_{1}^{2}}{4C_{2}^{2}},\dfrac{C_{1}}{4}\right\\}$.
Assuming that b$\inf_{k\in{\rm I\\!N}}\varphi(x^{k})>-\infty$, we have the
assertions:

(i) $\varepsilon_{k},r_{k}\downarrow 0$ as $k\to\infty$.

(ii) Every accumulation point of $\left\\{x^{k}\right\\}$ is a stationary
point of $\varphi$ and $\left\|x^{k}-x^{k+1}\right\|\rightarrow 0$ as
$k\to\infty$.

(iii) If the sequence $\left\\{x^{k}\right\\}$ is bounded, then the set of
accumulation points of $\left\\{x^{k}\right\\}$ is nonempty, compact, and
connected.

(iv) If $\left\\{x^{k}\right\\}$ has an isolated accumulation point, then the
entire sequence $\left\\{x^{k}\right\\}$ converges to it.

[Proof.] It follows from Proposition 3.14 that $\left\\{x^{k}\right\\}$ is
indeed a sequence generated by Algorithm 1 for finding zeros of the continuous
mapping $G_{\lambda}$. By Theorem 3.5, it suffices to show that
${\sum_{k=1}^{\infty}}\left\|d^{k}\right\|^{2}<\infty$ to get all the
assertions in (i)-(iv). The conditions $\varepsilon_{1}\leq r_{1}$ and
$\theta\leq\mu$ yield $\varepsilon_{k}\leq r_{k}$, $k\in{\rm I\\!N}$. We
consider the two choices for $\left\\{\rho_{k}\right\\}$. Suppose first that
$\sum_{k=1}^{\infty}\rho_{k}<\infty$. It follows from Proposition 3.16 that

$\displaystyle
C_{1}\left\|d^{k}\right\|^{2}\leq\varphi(x^{k})-\varphi(x^{k+1})+C_{2}\sqrt{\rho_{k}}\left\|d^{k}\right\|+\rho_{k}.$
(3.29)

Summing up both sides of the latter inequality over $k=1,2,\ldots$ gives us

$\displaystyle
C_{1}\sum_{k=1}^{m}\left\|d^{k}\right\|^{2}\leq\varphi(x^{1})-\varphi(x^{m+1})+C_{2}\sum_{k=1}^{m}\sqrt{\rho_{k}}\left\|d^{k}\right\|+\sum_{k=1}^{m}\rho_{k}\;\text{
for all }\;m\in{\rm I\\!N}.$

Since $\inf_{k\in{\rm I\\!N}}\varphi(x^{k})>-\infty$ and
$\sum_{k=1}^{\infty}\rho_{k}<\infty$, we get

$\displaystyle C_{1}\sum_{k=1}^{m}\left\|d^{k}\right\|^{2}\leq
C_{3}+C_{2}\sum_{k=1}^{m}\sqrt{\rho_{k}}\left\|d^{k}\right\|\;\text{ for all
}\;m\in{\rm I\\!N},$

where $C_{3}:=\varphi(x^{1})-\inf_{k\in{\rm
I\\!N}}\varphi(x^{k})+\sum_{k=1}^{\infty}\rho_{k}<\infty$. It implies by the
Cauchy-Schwarz inequality that

$\displaystyle C_{1}\sum_{k=1}^{m}\left\|d^{k}\right\|^{2}\leq
C_{3}+C_{2}\sqrt{\sum_{k=1}^{m}\rho_{k}}\sqrt{\sum_{k=1}^{m}\left\|d^{k}\right\|^{2}}$
$\displaystyle\leq
C_{3}+C_{2}\sqrt{\sum_{k=1}^{\infty}\rho_{k}}\sqrt{\sum_{k=1}^{m}\left\|d^{k}\right\|^{2}}=C_{3}+C_{4}\sqrt{\sum_{k=1}^{m}\left\|d^{k}\right\|^{2}},$

where $C_{4}:=C_{2}\sqrt{\sum_{k=1}^{\infty}\rho_{k}}$. Therefore, we arrive
at

$\displaystyle
C_{1}\left(\sqrt{\sum_{k=1}^{m}\left\|d^{k}\right\|^{2}}-\dfrac{C_{4}}{2C_{1}}\right)^{2}-\dfrac{C_{4}^{2}}{4C_{1}}=C_{1}\sum_{k=1}^{m}\left\|d^{k}\right\|^{2}-C_{4}\sqrt{\sum_{k=1}^{m}\left\|d^{k}\right\|^{2}}\leq
C_{3}\;\text{ for all }\;m\in{\rm I\\!N},$

which gives us the desired condition
$\sum_{k=1}^{\infty}\left\|d^{k}\right\|^{2}<\infty$.
Suppose now that
$\rho_{k}=\min\left\\{\dfrac{C_{1}^{2}}{4C_{2}^{2}},\dfrac{C_{1}}{4}\right\\}\varepsilon_{k}^{2}$
for any $k\in{\rm I\\!N}$ and show that (3.29) yields

$\displaystyle\dfrac{C_{1}}{4}\left\|d^{k}\right\|^{2}\leq\varphi(x^{k})-\varphi(x^{k+1})\;\text{
whenever }\;k\in{\rm I\\!N}.$ (3.30)

If $k\in\mathcal{N}$, inequality (3.30) is obviously satisfied since both
sides are zeros. Otherwise, we get

$\displaystyle\left\|d^{k}\right\|=\left\|g^{k}\right\|-\varepsilon_{k}>r_{k}+\varepsilon_{k}-\varepsilon_{k}=r_{k}\geq\varepsilon_{k}.$

Therefore, the choice of $\left\\{\rho_{k}\right\\}$ leads us to the
inequalities

$\displaystyle C_{2}\sqrt{\rho_{k}}\left\|d^{k}\right\|+\rho_{k}\leq
C_{2}\dfrac{C_{1}}{2C_{2}}\varepsilon_{k}\left\|d^{k}\right\|+\dfrac{C_{1}}{4}\varepsilon_{k}^{2}\leq\dfrac{3C_{1}}{4}\left\|d^{k}\right\|^{2}.$

Combining this with (3.29), we arrive at

$\displaystyle
C_{1}\left\|d^{k}\right\|^{2}\leq\varphi(x^{k})-\varphi(x^{k+1})+\dfrac{3C_{1}}{4}\left\|d^{k}\right\|^{2},$

which implies in turn the fulfillment of (3.30). Summing up both sides of
(3.30) over $k=1,2,\ldots$ with taking into account that $\inf_{k\in{\rm
I\\!N}}\varphi(x^{k})>-\infty$ verifies
$\sum_{k=1}^{\infty}\left\|d^{k}\right\|^{2}<\infty$ and completes the proof.

######  Remark 3.18.

The choice of and arbitrary sequence $\left\\{\rho_{k}\right\\}$ satisfying
$\sum_{k=1}^{\infty}\rho_{k}<\infty$ may not ensure the decreasing property of
$\left\\{\varphi(x^{k})\right\\}.$ However, if we select
$\rho_{k}:=C\varepsilon_{k}^{2}$ for all $k\in{\rm I\\!N}$ with
$C:=\min\left\\{\dfrac{C_{1}^{2}}{4C_{2}^{2}},\dfrac{C_{1}}{4}\right\\}$, the
sequence $\left\\{\varphi(x^{k})\right\\}$ is decreasing due to

$\displaystyle\dfrac{C_{1}}{4}\left\|d^{k}\right\|^{2}\leq\varphi(x^{k})-\varphi(x^{k+1})\;\text{
for all }\;k\in{\rm I\\!N}.$ (3.31)

Our next goal is to establish the global convergence of the sequence
$\left\\{x^{k}\right\\}$ generated by Algorithm 3. First we recall the notion
of forward-backward envelopes introduced by Patrinos and Bemporad [36] and
then being largely used to the design and justification of numerical methods
in various composite frameworks of optimization; see, e.g., [21, 22, 23, 44,
45] with the references therein.

######  Definition 3.19 (forward-backward envelopes).

Let $\varphi=f+g$ be given as in (3.10) and let $\lambda\in(0,\varrho^{-1})$.
The forward-backward envelope (FBE) of $\varphi$ is given by

$\varphi_{\lambda}(x):=\inf_{y\in{\rm
I\\!R}^{n}}\big{\\{}f(x)+\left\langle\nabla
f(x),y-x\right\rangle+(2\lambda)^{-1}\left\|y-x\right\|^{2}+g(y)\big{\\}}.$

The FBE $\varphi_{\lambda}$ is majorized by $\varphi$, i.e.,
$\varphi_{\lambda}(x)\leq\varphi(x)$ for all $x\in{\rm I\\!R}^{n}$. This
definition can be rewritten via the Moreau envelope (2.5) of $g$ as

$\displaystyle\varphi_{\lambda}(x)$
$\displaystyle=f(x)-\frac{\lambda}{2}\|\nabla f(x)\|^{2}+\inf_{y\in{\rm
I\\!R}^{n}}\big{\\{}g(y)+(2\lambda)^{-1}\left\|y-(x-\lambda\nabla
f(x))\right\|^{2}\big{\\}}$
$\displaystyle=f(x)-\dfrac{\lambda}{2}\left\|\nabla
f(x)\right\|^{2}+\inf_{y\in{\rm I\\!R}^{n}}\Phi_{\lambda,F_{\lambda}(x)}(y)$
$\displaystyle=f(x)-\frac{\lambda}{2}\|\nabla
f(x)\|^{2}+e_{\lambda}g(x-\lambda\nabla f(x)).$

When $f$ is $\mathcal{C}^{2}$-smooth, it follows from the latter equality and
Proposition 3.9 that the FBE $\varphi_{\lambda}$ of $\varphi$ is
$\mathcal{C}^{1}$-smooth with the gradient given by

$\displaystyle\nabla\varphi_{\lambda}(x)$
$\displaystyle=\lambda^{-1}(I-\lambda\nabla^{2}f(x))(x-\text{\rm
Prox}_{\lambda g}(x-\lambda\nabla f(x)))$
$\displaystyle=\lambda^{-1}(I-\lambda\nabla^{2}f(x))(x-T_{\lambda}(x)).$
(3.32)

Consider the following approximation of the objective function $\varphi$:

$\displaystyle\begin{cases}\mathcal{F}_{\lambda}:{\rm I\\!R}^{n}\times{\rm
I\\!R}\rightarrow{\rm I\\!R},\\\
\mathcal{F}_{\lambda}(x,\varepsilon)=\varphi_{\lambda}(x)+\mathscr{C}\varepsilon^{2}\text{
for all }x\in{\rm I\\!R}^{n},\;\varepsilon\in{\rm I\\!R},\end{cases}$ (3.33)

where
$\mathscr{C}=\min\left\\{\dfrac{\lambda(1-\lambda\varrho)}{2},\dfrac{C_{1}^{2}}{4C_{2}^{2}},\dfrac{C_{1}}{4}\right\\}$
with $C_{1},C_{2}$ defined in (3.19).

The next proposition provides important properties of $\mathcal{F}_{\lambda}$
related to $\left\\{x^{k}\right\\}$, which are used below to establish
convergence results for the iterative sequence $\left\\{x^{k}\right\\}$.

######  Proposition 3.20.

Let $\varphi$ be defined in (3.10), where $f$ is a $\mathcal{C}^{2}$-smooth
function with $L$-Lipschitz gradient, and let $\left\\{x^{k}\right\\}$ be the
sequence generated by Algorithm 3 with $\varepsilon_{1}\leq
r_{1},\theta\leq\mu$ and $\rho_{k}=C\varepsilon_{k}^{2}$ for all $k\in{\rm
I\\!N}$, where $C$ is taken from Theorem 3.17. Then for all $k\notin{\rm
I\\!N}$, there are constants $a_{1},a_{2}>0$ such that:

(i)
$\varphi(x^{k+1})\leq\mathcal{F}_{\lambda}(x^{k},\varepsilon_{k})\leq\varphi(x^{k})+\mathscr{C}\varepsilon_{k}^{2}$.

(ii) $\varphi(x^{k})-\varphi(x^{k+1})\geq
a_{1}\left\|x^{k+1}-x^{k}\right\|^{2}$.

(iii) $\left\|\nabla\mathcal{F}_{\lambda}(x^{k},\varepsilon_{k})\right\|\leq
a_{2}\left\|x^{k}-x^{k+1}\right\|$.

[Proof.] Pick $k\notin\mathcal{N}$ and deduce from the second inequality in
(i) that $\varphi_{\lambda}(x^{k})\leq\varphi(x^{k})$. It follows by the
constructions of $\mathscr{C},C$, and $\rho_{k}$ that

$\displaystyle\min\Big{\\{}\dfrac{\lambda(1-\lambda\varrho)}{2}\varepsilon_{k}^{2},\rho_{k}\Big{\\}}$
$\displaystyle=\min\Big{\\{}\dfrac{\lambda(1-\lambda\varrho)}{2}\varepsilon_{k}^{2},\dfrac{C_{1}}{4C_{2}^{2}}\varepsilon_{k}^{2},\dfrac{C_{1}}{4}\varepsilon_{k}^{2}\Big{\\}}=\mathscr{C}\varepsilon_{k}^{2}.$
(3.34)

Since $k\notin\mathcal{N}$, the vector $x^{k+1}=p^{k}$ is a
$\mathscr{C}\varepsilon_{k}^{2}$-solution to subproblem (3.14). Combining this
with (3.14), (3.34), and the $L$-descent property of $f$ as in (2.1), we get
that

$\displaystyle\varphi_{\lambda}(x^{k})$
$\displaystyle=f(x^{k})-\dfrac{\lambda}{2}\left\|\nabla
f(x^{k})\right\|^{2}+\inf_{y\in{\rm
I\\!R}^{n}}\Phi_{\lambda,F_{\lambda}(x^{k})}(y)$ $\displaystyle\geq
f(x^{k})-\dfrac{\lambda}{2}\left\|\nabla
f(x^{k})\right\|^{2}+\Phi_{\lambda,F_{\lambda}(x^{k})}(x^{k+1})-\mathscr{C}\varepsilon_{k}^{2}$
$\displaystyle=f(x^{k})-\dfrac{\lambda}{2}\left\|\nabla
f(x^{k})\right\|^{2}+g(x^{k+1})+\dfrac{1}{2\lambda}\left\|x^{k+1}-(x^{k}-\lambda\nabla
f(x^{k}))\right\|^{2}-\mathscr{C}\varepsilon_{k}^{2}$
$\displaystyle=f(x^{k})+\left\langle\nabla
f(x^{k}),x^{k+1}-x^{k}\right\rangle+\dfrac{1}{2\lambda}\left\|x^{k+1}-x^{k}\right\|^{2}+g(x^{k+1})-\mathscr{C}\varepsilon_{k}^{2}$
$\displaystyle\geq
f(x^{k+1})-\dfrac{L}{2}\left\|x^{k+1}-x^{k}\right\|^{2}+\dfrac{1}{2\lambda}\left\|x^{k+1}-x^{k}\right\|^{2}+g(x^{k+1})-\mathscr{C}\varepsilon_{k}^{2}$
$\displaystyle\geq\varphi(x^{k+1})-\mathscr{C}\varepsilon_{k}^{2},$

where the last inequality is deduced from $\lambda^{-1}>L$. Therefore, (i) is
justified.

It follows from $\varepsilon_{1}\leq r_{1}$ and $\theta\leq\mu$ that
$\varepsilon_{k}\leq r_{k}$. By Proposition 3.14(iii), we have $t_{k}\leq
2\lambda.$ Combining this with (3.31) and the relation
$x^{k+1}=x^{k}+t_{k}d^{k}$, we get

$\displaystyle\varphi(x^{k})-\varphi(x^{k+1})$
$\displaystyle\geq\dfrac{C_{1}}{4}\left\|d^{k}\right\|^{2}=\dfrac{C_{1}}{4t_{k}^{2}}\left\|x^{k+1}-x^{k}\right\|^{2}$
$\displaystyle\geq\dfrac{C_{1}}{16\lambda^{2}}\left\|x^{k+1}-x^{k}\right\|^{2},$

which justifies (ii) with $a_{1}:=C_{1}/16\lambda^{2}$.

To verify (iii), we first observe that
$\nabla\mathcal{F}_{\lambda}(x^{k},\varepsilon_{k})=(\nabla\varphi_{\lambda}(x^{k}),2\mathscr{C}\varepsilon_{k}).$
Since $\nabla f$ is $L$-Lipschitz, it follows from Proposition 2.3 that
$\left\|\nabla^{2}f(x^{k})\right\|\leq L$, and hence

$\displaystyle\left\|I-\lambda\nabla^{2}f(x^{k})\right\|\leq\left\|I\right\|+\lambda\left\|\nabla^{2}f(x^{k})\right\|\leq
1+\lambda L.$ (3.35)

Using the representation of $\nabla\varphi_{\lambda}$ in (3.3) and the latter
estimate give us

$\displaystyle\left\|\nabla\varphi_{\lambda}(x^{k})\right\|$
$\displaystyle=\lambda^{-1}\left\|(I-\lambda\nabla^{2}f(x^{k}))(x^{k}-T_{\lambda}(x^{k}))\right\|$
$\displaystyle\leq\lambda^{-1}\left\|I-\lambda\nabla^{2}f(x^{k})\right\|\cdot\left\|x^{k}-T_{\lambda}(x^{k})\right\|$
$\displaystyle\leq\lambda^{-1}(1+\lambda
L)\left\|x^{k}-T_{\lambda}(x^{k})\right\|$
$\displaystyle\leq(\lambda^{-1}+L)\left\|x^{k}-x^{k+1}\right\|+\lambda^{-1}(1+\lambda
L)\left\|x^{k+1}-T_{\lambda}(x^{k})\right\|.$ (3.36)

Furthermore, it follows from $x^{k+1}=p^{k}$ and Proposition 3.14(i) that
$\lambda^{-1}\left\|x^{k+1}-T_{\lambda}(x^{k})\right\|\leq\varepsilon_{k}$.
Combining the latter with (3.3) ensures that

$\displaystyle\left\|\nabla\varphi_{\lambda}(x^{k})\right\|\leq(\lambda^{-1}+L)\left\|x^{k}-x^{k+1}\right\|+(1+\lambda
L)\varepsilon_{k}.$ (3.37)

Remembering that $\varepsilon_{k}\leq r_{k}$ and $k\notin\mathcal{N}$ allows
us to deduce from Remark 3.2(iii) that
$\varepsilon_{k}\leq\left\|d^{k}\right\|$. Since $t_{k}\geq\lambda$ by
Proposition 3.14, we get

$\displaystyle\varepsilon_{k}\leq\left\|d^{k}\right\|=t_{k}^{-1}\left\|x^{k}-x^{k+1}\right\|\leq\lambda^{-1}\left\|x^{k}-x^{k+1}\right\|.$
(3.38)

Combining finally (3.37) and (3.38) with the representation of
$\nabla\mathcal{F}_{\lambda}$ gives us

$\displaystyle\left\|\nabla\mathcal{F}_{\lambda}(x^{k},\varepsilon_{k})\right\|$
$\displaystyle\leq\left\|\nabla\varphi_{\lambda}(x^{k})\right\|+2\mathscr{C}\varepsilon_{k}$
$\displaystyle\leq(\lambda^{-1}+L)\left\|x^{k}-x^{k+1}\right\|+(1+\lambda
L)\varepsilon_{k}+2\mathscr{C}\varepsilon_{k}$
$\displaystyle\leq(\lambda^{-1}+L)\left\|x^{k}-x^{k+1}\right\|+(1+\lambda
L+2\mathscr{C})\lambda^{-1}\left\|x^{k}-x^{k+1}\right\|$
$\displaystyle=2(\lambda^{-1}+L+\mathscr{C}\lambda^{-1})\left\|x^{k}-x^{k+1}\right\|,$

which justifies (iii) with $a_{2}:=2(\lambda^{-1}+L+\mathscr{C}\lambda^{-1})$
and thus completes the proof.

The next result inspired by [3, Theorem 2] is useful to establish the
convergence rates below.

######  Lemma 3.21.

Let $\left\\{s_{k}\right\\}$ be a decreasing sequence of positive numbers, and
let $\alpha>1$ and $\beta>0$ be some constants. Suppose that $s_{k}\downarrow
0$ as $k\to\infty$, and that for all large $k\in{\rm I\\!N}$ we have

$\displaystyle s_{k}^{\alpha}\leq\beta(s_{k-1}-s_{k}).$ (3.39)

Then there exists a number $\gamma>0$ such that

$\displaystyle s_{k}\leq\gamma k^{-\frac{1}{\alpha-1}}\;\text{ whenever
}\;k\in{\rm I\\!N}\;\text{ is sufficiently large}.$

[Proof.] Let $N\in{\rm I\\!N}$ be such that (3.39) holds for all $k\geq N$.
Defining

$\displaystyle\bar{\mu}:=\min\left\\{\dfrac{\alpha-1}{2\beta},(2^{\frac{\alpha-1}{\alpha}}-1)s^{1-\alpha}_{N-1}\right\\}>0,$

we are going to show that

$\displaystyle s_{k}^{1-\alpha}-s_{k-1}^{1-\alpha}\geq\bar{\mu}\;\text{ for
all }\;k\geq N.$ (3.40)

Consider the two cases for $k.$

Case 1: $s_{k}^{-\alpha}>2s_{k-1}^{-\alpha}$. Since $1-\alpha<0$, we have
$s_{k}^{1-\alpha}>2^{\frac{\alpha-1}{\alpha}}s^{1-\alpha}_{k-1}$. Then the
decreasing property of $\left\\{s_{k}\right\\}$ yields the desired result:

$\displaystyle
s_{k}^{1-\alpha}-s_{k-1}^{1-\alpha}>(2^{\frac{\alpha-1}{\alpha}}-1)s_{k-1}^{1-\alpha}\geq(2^{\frac{\alpha-1}{\alpha}}-1)s^{1-\alpha}_{N-1}\geq\bar{\mu}.$

Case 2: $s_{k}^{-\alpha}\leq 2s_{k-1}^{-\alpha}$. It follows from (3.39) and
the decreasing property of $\left\\{s_{k}\right\\}$ that

$\displaystyle 1$ $\displaystyle\leq\beta(s_{k-1}-s_{k})s_{k}^{-\alpha}\leq
2\beta(s_{k-1}-s_{k})s_{k-1}^{-\alpha}$ $\displaystyle\leq
2\beta\int_{s_{k}}^{s_{k-1}}s^{-\alpha}ds=\dfrac{2\beta}{1-\alpha}(s_{k-1}^{1-\alpha}-s_{k}^{1-\alpha}),$

which implies by $\alpha>1$ that

$\displaystyle
s_{k}^{1-\alpha}-s_{k-1}^{1-\alpha}\geq\dfrac{\alpha-1}{2\beta}\geq\bar{\mu}.$

Fixing some $K>2N$ and summing up (3.40) over $k=N+1,\ldots,K$, we get that
$s_{K}^{1-\alpha}-s_{N}^{1-\alpha}\geq\bar{\mu}(K-N)$. This allows us to
verify the estimates

$\displaystyle
s_{K}\leq\left[s_{N}^{1-\alpha}+\bar{\mu}(K-N)\right]^{\frac{1}{1-\alpha}}\leq\left(\dfrac{\bar{\mu}}{2}\right)^{\frac{1}{1-\alpha}}K^{\frac{1}{1-\alpha}}$

and therefore complete the proof of the lemma.

Now we are ready to establish the global convergence and obtain convergence
rates of our IPGM Algorithm 3 under the KL property of $\mathcal{F}_{\lambda}$
from (3.33).

######  Theorem 3.22.

Let $\varphi$ be defined in (3.10), where $f$ is a $\mathcal{C}^{2}$-smooth
function with $L$-Lipschitz gradient, and let $\left\\{x^{k}\right\\}$ be the
sequence generated by Algorithm 3 satisfying $\varepsilon_{1}\leq
r_{1},\theta\leq\mu$ and $\rho_{k}=C\varepsilon_{k}^{2}$ for all $k\in{\rm
I\\!N}$ with $C$ taken from Theorem 3.17. Assume further that the set ${\rm
I\\!N}\setminus\mathcal{N}$ is infinite, that $\left\\{x^{k}\right\\}$ has an
accumulation point $\bar{x}$, and that the function $\mathcal{F}_{\lambda}$ in
(3.33) satisfies the KL property from Definition 2.13 at $(\bar{x},0)$. Then
we have the assertions:

(i) $\bar{x}$ is a stationary point of $\varphi$ and the sequence
$\left\\{x^{k}\right\\}$ converges to $\bar{x}$ having finite length, i.e.,

$\displaystyle\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|<\infty.$

(ii) If in addition the KL property of $\mathcal{F}_{\lambda}$ at
$(\bar{x},0)$ holds with $\psi(t):=Mt^{1-q}$ for some $M>0$ and $q\in(0,1)$,
then the following convergence rates are guaranteed for the sequence
$\left\\{z^{k}\right\\}$ from (3.5):

$\bullet$ For $q\in(0,1/2]$, the sequence $\left\\{z^{k}\right\\}$ converges
linearly to $\bar{x}$.

$\bullet$ For $q\in(1/2,1)$, there exists a positive constant $\gamma$ such
that

$\displaystyle\left\|z^{k}-\bar{x}\right\|\leq\gamma
k^{-\frac{1-q}{2q-1}}\;\text{ for sufficiently large }\;k\in{\rm I\\!N}.$

[Proof.] (i) It follows from Proposition 3.14 that $\left\\{x^{k}\right\\}$ is
a sequence generated by Algorithm 1 for finding zeros of the continuous
mapping $G_{\lambda}$. Then the imposed assumptions guarantee that all the
conditions of Proposition 3.6 are satisfied. Suppose that ${\rm
I\\!N}\setminus\mathcal{N}=\left\\{j_{1},j_{2},\ldots\right\\}$, and let
$\left\\{z^{k}\right\\}$ be taken from(3.5) while
$\left\\{\sigma_{k}\right\\}$ is defined by $\sigma_{k}:=\varepsilon_{j_{k}}$
for all $k\in{\rm I\\!N}$. Since $\bar{x}$ is an accumulation point of
$\left\\{x^{k}\right\\}$, it is also an accumulation point of
$\left\\{z^{k}\right\\}$ by Proposition 3.6. Therefore, we can find an
infinite index subset $I\subset{\rm I\\!N}$ such that
$z^{k}\overset{I}{\rightarrow}\bar{x}$. Fix any $k\in{\rm I\\!N}$. By taking
into account that $j_{k}\notin\mathcal{N}$ and using the construction of
$\left\\{z^{k}\right\\},\left\\{\varepsilon_{j_{k}}\right\\}$ and
$z^{k+1}=x^{j_{k}+1}$ in Proposition 3.6, we deduce from Proposition 3.20 that

$\displaystyle\varphi(z^{k+1})\leq\mathcal{F}_{\lambda}(z^{k},\sigma_{k})\leq\varphi(z^{k})+\mathscr{C}\sigma_{k}^{2},$
(3.41) $\displaystyle\varphi(z^{k})-\varphi(z^{k+1})\geq
a_{1}\left\|z^{k+1}-z^{k}\right\|^{2},$ (3.42)
$\displaystyle\left\|\nabla\mathcal{F}_{\lambda}(z^{k},\sigma_{k})\right\|\leq
a_{2}\left\|z^{k+1}-z^{k}\right\|$ (3.43)

whenever $k\in{\rm I\\!N}$, where $a_{1},a_{2}$ are some fixed positive
constants. It follows from (3.42) and $z^{k}\neq z^{k+1}$ for all $k\in{\rm
I\\!N}$ in Proposition 3.6 that $\left\\{\varphi(z^{k})\right\\}$ is strictly
decreasing. Combining this with the lower semicontinuity of $\varphi$ gives us
the relationships

$\displaystyle\inf_{k\in{\rm I\\!N}}\varphi(x^{k})=\inf_{k\in{\rm
I\\!N}}\varphi(z^{k})=\lim_{k\rightarrow\infty}\varphi(z^{k})=\lim_{k\overset{I}{\rightarrow}\infty}\varphi(z^{k})\geq\varphi(\bar{x})>-\infty.$
(3.44)

This shows together with the imposed assumptions tells us that all the
requirements of Theorem 3.17 are satisfied. Thus it follows from assertions
(i) and (ii) of Theorem 3.17 that $\bar{x}$ is a stationary point of
$\varphi$, that $\varepsilon_{k}\downarrow 0$, and that
$\left\|x^{k}-x^{k+1}\right\|\rightarrow 0$ as $k\to\infty$. The constructions
of $\left\\{z^{k}\right\\}$ and $\left\\{\sigma_{k}\right\\}$ together with
$z^{k+1}=x^{j_{k}+1}$ for all $k\in{\rm I\\!N}$ yield
$\left\|z^{k+1}-z^{k}\right\|\rightarrow 0$ and $\sigma_{k}\downarrow 0$.
Combining the latter with (3.41), the continuity of $\mathcal{F}_{\lambda}$,
and the condition $\varphi_{\lambda}(x)\leq\varphi(x)$ for all $x\in{\rm
I\\!R}^{n}$, we get

$\displaystyle\lim_{k\rightarrow\infty}\varphi(z^{k})=\lim_{k\overset{I}{\rightarrow}\infty}\varphi(z^{k+1})\leq\lim_{k\overset{I}{\rightarrow}\infty}\mathcal{F}_{\lambda}(z^{k},\sigma_{k})=\mathcal{F}_{\lambda}(\bar{x},0)=\varphi_{\lambda}(\bar{x})\leq\varphi(\bar{x}),$

which brings us by taking (3.44) into account to

$\displaystyle\lim_{k\rightarrow\infty}\varphi(z^{k})=\lim_{k\rightarrow\infty}\mathcal{F}_{\lambda}(z^{k},\sigma_{k})=\varphi(\bar{x})=\mathcal{F}_{\lambda}(\bar{x},0).$
(3.45)

Involving now the KL property of $\mathcal{F}_{\lambda}$ at
$\bar{y}:=(\bar{x},0)$, we find numbers $\eta>0,\nu>0$ and a continuous
concave function $\psi:[0,\eta)\rightarrow[0,\infty)$ satisfying the
conditions: $\psi(0)=0$, $\psi$ is $\mathcal{C}^{1}$ on $(0,\eta)$,
$\psi^{\prime}(s)>0$ for all $s\in(0,\eta)$, and for all $y\in{\rm
I\\!R}^{n}\times{\rm I\\!R}$ such that $\left\|y-\bar{y}\right\|<\nu$ with
$\varphi(\bar{x})<\mathcal{F}_{\lambda}(y)<\varphi(\bar{x})+\eta$ we have

$\displaystyle\psi^{\prime}(\mathcal{F}_{\lambda}(y)-\varphi(\bar{x}))\left\|\nabla\mathcal{F}_{\lambda}(y)\right\|\geq
1.$ (3.46)

For any $k\in{\rm I\\!N}$, set $y^{k}:=(z^{k},\sigma_{k})$ and by using
(3.45), (3.41), and $\sigma_{k}\downarrow 0$ find $k_{1}\in{\rm I\\!N}$ such
that

$\displaystyle\varphi(\bar{x})<\varphi(z^{k})\leq\mathcal{F}_{\lambda}(y^{k-1})<\varphi(\bar{x})+\eta\quad\text{
and }\quad\sigma_{k}<\nu/4\;\text{ whenever }\;k\geq k_{1}.$ (3.47)

Since $\bar{x}$ is an accumulation point of $\left\\{z^{k}\right\\}$ with
$\left\|z^{k+1}-z^{k}\right\|\rightarrow 0$, and since $\psi$ is continuous at
$0$ with $\psi(0)=0$, suppose without loss of generality that

$\displaystyle\left\|z^{k_{1}-1}-\bar{x}\right\|<\nu/4,\quad\left\|z^{k_{1}}-z^{k_{1}-1}\right\|<\nu/8,\;\mbox{
and }\;a_{2}a_{1}^{-1}\psi(\varphi(z^{k_{1}})-\varphi(\bar{x}))<\nu/4.$ (3.48)

We claim that if $k\geq k_{1}$ and $\left\|y^{k-1}-\bar{y}\right\|<\nu$, then

$\displaystyle
2\left\|z^{k+1}-z^{k}\right\|\leq\phi_{k}+\left\|z^{k}-z^{k-1}\right\|,$
(3.49)

where
$\phi_{k}:=a_{2}a_{1}^{-1}\left[\psi(\varphi(z^{k})-\varphi(\bar{x}))-\psi(\varphi(z^{k+1})-\varphi(\bar{x}))\right]$.
To verify this, fix such $k$. Since $\left\|y^{k-1}-\bar{y}\right\|<\nu$ and
$k\geq k_{1}$, it follows from the first assertion in (3.47) that inequality
(3.46) holds for $y=y^{k-1},$ i.e.,

$\displaystyle\psi^{\prime}(\mathcal{F}_{\lambda}(y^{k-1})-\varphi(\bar{x}))\left\|\nabla\mathcal{F}_{\lambda}(y^{k-1})\right\|\geq
1.$ (3.50)

The latter implies by (3.43) that

$\displaystyle\psi^{\prime}(\mathcal{F}_{\lambda}(y^{k-1})-\varphi(\bar{x}))\geq\dfrac{1}{\left\|\nabla\mathcal{F}_{\lambda}(y^{k-1})\right\|}\geq\dfrac{1}{a_{2}\left\|z^{k}-z^{k-1}\right\|}.$
(3.51)

Since $\psi$ is concave, $\psi^{\prime}$ is nonincreasing. It follows from
(3.41) that
$\mathcal{F}_{\lambda}(y^{k-1})-\varphi(\bar{x})\geq\varphi(z^{k})-\varphi(\bar{x})$,
and the nonincreasing property implies therefore that

$\displaystyle\dfrac{1}{a_{2}\left\|z^{k}-z^{k-1}\right\|}\leq\psi^{\prime}(\mathcal{F}_{\lambda}(y^{k-1})-\varphi(\bar{x}))\leq\psi^{\prime}(\varphi(z^{k})-\varphi(\bar{x})).$

Combining the latter with the concavity of $\psi$ and condition (3.42) brings
us to the inequalities

$\displaystyle\psi(\varphi(z^{k})-\varphi(\bar{x}))-\psi(\varphi(z^{k+1})-\varphi(\bar{x}))\geq\psi^{\prime}(\varphi(z^{k})-\varphi(\bar{x}))(\varphi(z^{k})-\varphi(z^{k+1}))$
$\displaystyle\geq\psi^{\prime}(\varphi(z^{k})-\varphi(\bar{x}))a_{1}\left\|z^{k+1}-z^{k}\right\|^{2}\geq\dfrac{a_{1}\left\|z^{k+1}-z^{k}\right\|^{2}}{a_{2}\left\|z^{k}-z^{k-1}\right\|}.$

This can be equivalently written as

$\displaystyle\left\|z^{k+1}-z^{k}\right\|^{2}\leq\phi_{k}\left\|z^{k}-z^{k-1}\right\|,$

which implies in turn by using $2\sqrt{uv}\leq u+v$ that

$\displaystyle
2\left\|z^{k+1}-z^{k}\right\|\leq\phi_{k}+\left\|z^{k}-z^{k-1}\right\|$

and thus verifies the above claim.

Now we show that inequality (3.49) holds for all $k\geq k_{1}$ by induction.
This is obviously true for $k=k_{1}$ since
$\left\|y^{k_{1}-1}-\bar{y}\right\|\leq\left\|z^{k_{1}-1}-\bar{x}\right\|+\sigma_{k_{1}}<\nu/2$.
Suppose that it holds for $k_{1},k_{1}+1,\ldots,K-1.$ Summing up inequality
(3.49) over $k=k_{1},k_{1}+1,\ldots,K-1$, we get

$\displaystyle 2\sum_{k=k_{1}}^{K-1}\left\|z^{k+1}-z^{k}\right\|$
$\displaystyle\leq\sum_{k=k_{1}}^{K-1}\left\|z^{k}-z^{k-1}\right\|+\sum_{k=k_{1}}^{K-1}\phi_{k}$
$\displaystyle\leq\sum_{k=k_{1}}^{K-1}\left\|z^{k+1}-z^{k}\right\|+\left\|z^{k_{1}}-z^{k_{1}-1}\right\|+\dfrac{a_{2}}{a_{1}}\psi(\varphi(z^{k_{1}})-\varphi(\bar{x})),$

which implies in turn that

$\displaystyle\sum_{k=k_{1}}^{K-1}\left\|z^{k+1}-z^{k}\right\|\leq\left\|z^{k_{1}}-z^{k_{1}-1}\right\|+\dfrac{a_{2}}{a_{1}}\psi(\varphi(z^{k_{1}})-\varphi(\bar{x})).$
(3.52)

Employing the triangle inequality gives us

$\displaystyle\left\|z^{K-1}-\bar{x}\right\|$
$\displaystyle\leq\left\|z^{k_{1}}-\bar{x}\right\|+\sum_{k=k_{1}}^{K-1}\left\|z^{k+1}-z^{k}\right\|$
$\displaystyle\leq\left\|z^{k_{1}-1}-\bar{x}\right\|+2\left\|z^{k_{1}}-z^{k_{1}-1}\right\|+\dfrac{a_{2}}{a_{1}}\psi(\varphi(z^{k_{1}})-\varphi(\bar{x}))<\dfrac{3\nu}{4}.$

Since $\sigma_{K-1}<\nu/4$ by (3.47), we get that

$\left\|y^{K-1}-\bar{y}\right\|\leq\left\|z^{K-1}-\bar{x}\right\|+\sigma_{K-1}<\nu,$

and thus inequality (3.49) holds for $k=K$. Letting $K\rightarrow\infty$ in
(3.49) gives us

$\displaystyle\sum_{k=1}^{\infty}\left\|z^{k+1}-z^{k}\right\|<\infty.$

The latter means that $\left\\{z^{k}\right\\}$ is a Cauchy sequence, and hence
it converges to $\bar{x}$. Therefore, $\left\\{x^{k}\right\\}$ converges to
$\bar{x}$ as well, and moreover we have

$\displaystyle\sum_{k=1}^{\infty}\left\|x^{k+1}-x^{k}\right\|=\sum_{k\in\mathcal{N}}\left\|x^{k+1}-x^{k}\right\|+\sum_{k\notin\mathcal{N}}\left\|x^{k+1}-x^{k}\right\|$
$\displaystyle=\sum_{k\in{\rm
I\\!N}}\left\|x^{j_{k}+1}-x^{j_{k}}\right\|=\sum_{k=1}^{\infty}\left\|z^{k+1}-z^{k}\right\|<\infty,$

which verifies assertion (i).

(ii) For any $p\in{\rm I\\!N},$ set
$s_{p}:=\sum_{k=p}^{\infty}\left\|z^{k+1}-z^{k}\right\|$, which is a finite
number. The triangle inequality yields $\left\|z^{p}-\bar{x}\right\|\leq
s_{p}$, it suffices to establish the convergence rates for $s_{p}$. To
proceed, take any $p\geq k_{1}$, where $k_{1}$ satisfies (3.47) and (3.48). It
follows from the proof of (i) that

$\displaystyle
2\left\|z^{k+1}-z^{k}\right\|\leq\phi_{k}+\left\|z^{k}-z^{k-1}\right\|\text{
for all }k\geq p.$

Summing up the above inequality over $k=p,p+1,\ldots$, we get

$\displaystyle 2\sum_{k=p}^{\infty}\left\|z^{k+1}-z^{k}\right\|$
$\displaystyle\leq\sum_{k=p}^{\infty}\left\|z^{k}-z^{k-1}\right\|+\sum_{k=p}^{\infty}\phi_{k}$
$\displaystyle\leq\sum_{k=p}^{\infty}\left\|z^{k+1}-z^{k}\right\|+\left\|z^{p}-z^{p-1}\right\|+\dfrac{a_{2}}{a_{1}}\psi(\varphi(z^{p})-\varphi(\bar{x})),$

which implies in turn that

$\displaystyle
s_{p}\leq\left\|z^{p}-z^{p-1}\right\|+\dfrac{a_{2}}{a_{1}}(\varphi(z^{p})-\varphi(\bar{x}))^{1-q}.$
(3.53)

It follows from (3.50) by using $\psi^{\prime}(t)=(1-q)Mt^{-q}$ for all $t>0$
that

$(\mathcal{F}_{\lambda}(y^{p-1})-\varphi(\bar{x}))^{q}\leq
M(1-q)\left\|\nabla\mathcal{F}_{\lambda}(y^{k-1})\right\|.$

Combining this with $\varphi(z^{p})\leq\mathcal{F}_{\lambda}(y^{p-1})$ from
(3.41) and $q\in(0,1),$ we get

$\displaystyle\dfrac{a_{2}}{a_{1}}(\varphi(z^{p})-\varphi(\bar{x}))^{1-q}$
$\displaystyle\leq\dfrac{a_{2}}{a_{1}}(\mathcal{F}_{\lambda}(y^{p-1})-\varphi(\bar{x}))^{1-q}$
$\displaystyle\leq\dfrac{a_{2}}{a_{1}}(M(1-q)\left\|\nabla\mathcal{F}_{\lambda}(y^{p-1})\right\|)^{\frac{1-q}{q}}.$

The latter together with (3.53) and (3.43) gives us

$\displaystyle s_{p}$
$\displaystyle\leq\left\|z^{p}-z^{p-1}\right\|+\dfrac{a_{2}}{a_{1}}(M(1-q)\left\|\nabla\mathcal{F}_{\lambda}(y^{p-1})\right\|))^{\frac{1-q}{q}}$
$\displaystyle\leq\left\|z^{p}-z^{p-1}\right\|+\dfrac{a_{2}}{a_{1}}(M(1-q)a_{2}\left\|z^{p}-z^{p-1}\right\|)^{\frac{1-q}{q}}\text{
for all }p\geq k_{1}.$ (3.54)

We consider the two possible cases for $q.$

Case 1: $q\in(0,1/2]$, or equivalently, $(1-q)/q\geq 1$. Since
$\left\|z^{k+1}-z^{k}\right\|\rightarrow 0$ in this case, we can assume that
$M(1-q)a_{2}\left\|z^{p}-z^{p-1}\right\|<1$ for all $k\geq p_{1}$ and thus
deduce from (3.54) that

$\displaystyle s_{p}$
$\displaystyle\leq\left\|z^{p}-z^{p-1}\right\|+\dfrac{a_{2}}{a_{1}}(M(1-q)a_{2}\left\|z^{p}-z^{p-1}\right\|)$
$\displaystyle\leq\left(1+\dfrac{M(1-q)a_{2}^{2}}{a_{1}}\right)\left\|z^{p}-z^{p-1}\right\|=\alpha(s_{p-1}-s_{p}),$

where $\alpha:=\left(1+\dfrac{M(1-q)a_{2}^{2}}{a_{1}}\right)$. The above
estimate can be rewritten as

$\displaystyle s_{p}\leq\dfrac{\alpha}{1+\alpha}s_{p-1}\text{ for all }p\geq
k_{1},$

which implies that $\left\\{s_{k}\right\\}$ linearly converges to $0.$
Therefore, $\left\\{z^{k}\right\\}$ linearly converges to $\bar{x}$ as
$k\to\infty$.

Case 2: $q\in(1/2,1),$ or equivalently, $(1-q)/q\in(0,1)$. It follows from
(3.54) in this case that

$\displaystyle
s_{p}\leq\left(1+\dfrac{a_{2}}{a_{1}}(M(1-q)a_{2})^{\frac{1-q}{q}}\right)\left\|z^{p}-z^{p-1}\right\|^{\frac{1-q}{q}},$

which can be rewritten as

$\displaystyle s_{p}^{\frac{q}{1-q}}\leq\beta(s_{p-1}-s_{p})\text{ for all
}p\geq k_{1},\;\mbox{ with
}\;\beta:=\left[1+\dfrac{a_{2}}{a_{1}}(M(1-q)a_{2})^{\frac{1-q}{q}}\right]^{\frac{q}{1-q}}.$

By Lemma 3.21 with $\alpha:=q/(1-q)$, there exists a positive constant
$\gamma$ such that

$\displaystyle s_{k}\leq\gamma k^{-\frac{1-q}{2q-1}}\;\text{ for sufficiently
large }\;k\in{\rm I\\!N}.$

This completes the proof of the theorem.

######  Remark 3.23 (comments on the KL assumption).

Let us now discuss some efficient conditions on $f$ and $g$, which guarantee
the KL property of $\mathcal{F}_{\lambda}$ given in (3.33) by

$\displaystyle\mathcal{F}_{\lambda}(x,\varepsilon)=f(x)-\frac{\lambda}{2}\|\nabla
f(x)\|^{2}+e_{\lambda}g(x-\lambda\nabla f(x))+\mathscr{C}\varepsilon^{2}.$

(i) $f$ is analytic and $g$ is semialgebraic. Indeed, it follows from Remark
2.15 that $x\mapsto e_{\lambda}g(x)$ is semialgebraic, and thus is
subanalytic. Since $f$ is analytic, [25, Proposition 2.2.3] tells us that all
the partial derivatives of $f$ is analytic. Using [25, Proposition 2.2.8], we
deduce that $x\mapsto\left\|\nabla f(x)\right\|^{2}$ is analytic, and thus
$(x,\varepsilon)\mapsto f(x)-\dfrac{\lambda}{2}\left\|\nabla
f(x)\right\|^{2}+\mathscr{C}\varepsilon^{2}$ is analytic. Since all the
partial derivatives of $f$ is analytic, Remark 2.14 also tells us that $\nabla
f$ is subanalytic. Since the functions $x\mapsto e_{\lambda}g(x)$ and
$x\mapsto x-\lambda\nabla f(x)$ are continuous, we deduce from Remark
2.14(iii) that $e_{\lambda}g(x-\lambda\nabla f(x))$ is subanalytic,
continuous, and so is $\mathcal{F}_{\lambda}$. By the continuity of
$\mathcal{F}_{\lambda}$, the KL property of $\mathcal{F}_{\lambda}$ is
satisfied for $\psi(t):=Mt^{1-q}$ with $M>0$ and $q\in[0,1)$.

(ii) $f$ and $g$ are semialgebraic functions. Indeed, similarly to (i),
$e_{\lambda}g$ is a semialgebraic function. By Remark 2.15(v), the mapping
$x\mapsto\nabla f(x)$ is also semialgebraic. Since $\left\|\cdot\right\|^{2}$
is a polynomial function, Remark 2.15(i,ii) tells us again that
$\mathcal{F}_{\lambda}$ is semialgebraic. Thus it is subanalytic by
Remark2.15(iv). Therefore, the KL property of $\mathcal{F}_{\lambda}$ is
satisfied for $\psi(t):=Mt^{1-q}$ with $M>0$ and $q\in[0,1)$.

######  Remark 3.24 (comparison between IPGM and iFB).

Let us now compare the major issues in the algorithm description and the
obtained results for IPGM given in Theorems 3.17 and 3.22 with that of the
inexact forward-backward (iFB) algorithm in [13, Theorem 8] to solve problem
(3.10) when the function $g$ is convex. The iFB algorithm from [13] can be
written as follows:

######  Algorithm 4 (inexact forward-backward (iFB)).

######  Step 0.

Choose $\lambda\in(0,L^{-1})$, a starting point $x^{1}$ and a sequence of
errors $\omega_{k}$ such that $\sum_{k=1}^{\infty}\sqrt{\omega_{k}}<\infty$.
Set $k:=1$.

######  Step 1.

Compute $p^{k}$ such that

$\displaystyle\Phi_{\lambda,F_{\lambda}(x^{k})}(p^{k})\leq\inf\Phi_{\lambda,F_{\lambda}(x^{k})}+\omega_{k},$
(3.55) $\displaystyle\left\langle\nabla
f(x^{k}),p^{k}-x^{k}\right\rangle+(2\lambda)^{-1}\left\|p^{k}-x^{k}\right\|^{2}+g(p^{k})<g(x^{k}).$
(3.56)

######  Step 2.

Set $x^{k+1}:=p^{k}.$ Increase $k$ by $1$ and go back to Step 1.

We comments on the following issues.

(i) Algorithm description. The main difference between IPGM and iFB is the
choice of stopping criterion for the subproblem of finding approximate
solution $p^{k}$ to $T_{\lambda}(x^{k})$ at each iteration. Although both
algorithms use the condition (3.55) for finding $p^{k}$, the selections of
$\omega_{k}$ are different. The error $\omega_{k}$ in iFB needs to satisfy the
condition $\sum_{k=1}^{\infty}\sqrt{\omega_{k}}<\infty$. On the other hand, it
follows from Algorithm 3 and Theorem 3.17 that IPGM considers two selections
for $\omega_{k}$ which are either

$\displaystyle\omega_{k}:$
$\displaystyle=\min\left\\{\dfrac{\lambda\varepsilon_{k}^{2}}{2},\rho_{k}\right\\}\;\text{
with }\;\sum_{k=1}^{\infty}\rho_{k}<\infty,\;\text{ or }$ (3.57)
$\displaystyle\omega_{k}:$
$\displaystyle=\mathscr{C}\varepsilon_{k}^{2}\;\text{ with
}\;\mathscr{C}:=\min\left\\{\dfrac{\lambda}{2},\dfrac{C_{1}^{2}}{4C_{2}^{2}},\dfrac{C_{1}}{4}\right\\},$
(3.58)

where $C_{1},C_{2}$ are defined in Proposition 3.16. Step 2 of Algorithm 3
shows that $\varepsilon_{k}$ doesn’t need to decrease after an iteration. This
number is reduced only when $\left\|g^{k}\right\|$ is sufficiently small,
which holds when $x^{k}$ is near the exact solution of problem (3.10). When
$k\rightarrow\infty$, the convergence rate to $0$ of
$\left\\{\rho_{k}\right\\}$ in the first choice (3.57) is slower than that of
iFB. In the second selection (3.58), the error $\omega_{k}$ of the subproblem
is independent with $k$. The approximate solution $p^{k}$ for the subproblem
of iFB needs to satisfy condition (3.56), which ensures the sufficient
decrease property of the sequence $\left\\{\varphi(x^{k})\right\\}$. This
property is guaranteed for IPGM if the second choice of error (3.58) is
employed; see Remark 3.18.

(ii) Stationary accumulation points. Theorem 8(i) of [13] requires that the
smooth part $f$ has a Lipschitz gradient, that the function $\varphi$ is
bounded from below, and that the sequence $\left\\{x^{k}\right\\}$ is bounded.
On the other hand, our Theorem 3.17 requires that the smooth part satisfies
only the $L$-descent condition, which is strictly weaker than the Lipschitz
continuity of $\nabla f$. This allows us to work with broader classes of
functions by replacing the usual Euclidean distance by the Bregman distance.
The boundedness of $\left\\{x^{k}\right\\}$ and the boundedness from below of
$\varphi$ are not required in Theorem 3.17. The latter property is relaxed to
$\inf_{k\rightarrow\infty}\varphi(x^{k})>-\infty$.

(iii) Global convergence. Theorem 8(ii) of [13] requires that the smooth part
$f$ is analytic and that the nonsmooth part $g$ is subanalytic. On the other
hand, the global convergence analysis in our Theorem 3.22 is based on the KL
property of $\mathcal{F}_{\lambda}$. It follows from Remark 3.23 that the
latter property holds when $g$ is semialgebraic and $f$ is either analytic, or
semialgebraic.

(iv) Convergence rate. The rate of convergence for $\left\\{x^{k}\right\\}$ is
established in Theorem 3.22 under the KL property of $\mathcal{F}_{\lambda}$,
while not any type of convergence rate for iFB is given in [13]. Instead, [13,
Theorem 9] presents a convergence rate for function values in the variable
metric inexact linesearch-based algorithm.

##  4 Numerical Experiments

In this section, we compare the numerical efficiency of our IPGM with iFB in
Algorithm 4 for a variant of the nonconvex image restoration problem taken
from [44]. To proceed, given a vector $b\in{\rm I\\!R}^{n}$, matrices
$A\in{\rm I\\!R}^{n\times n}$, and $B\in{\rm I\\!R}^{m\times n}$ together with
a number $\gamma>0$, we consider the following problem:

$\text{minimize
}\quad\varphi(x):=\sum_{i=1}^{n}\log(1+(Ax-b)_{i}^{2})+\gamma\|Bx\|_{1}\quad\text{subject
to}\quad x\in{\rm I\\!R}^{n},$ (4.1)

where $\left\|u\right\|_{1}:=\sum_{i=1}^{n}|u_{i}|$ for any $u\in{\rm
I\\!R}^{n}.$

It can be seen thatn(4.1) is a special case of (3.10) with
$f(x):=\sum_{i=1}^{n}\log(1+(Ax-b)_{i}^{2})$ and $g(x):=\gamma\|Bx\|_{1}$.
Indeed, $g$ is clearly convex while $f$ is continuously differentiable with
the gradient

$\displaystyle\nabla f(x)=2A^{T}u,\;\text{ where
}\;u_{i}=\frac{(Ax-b)_{i}}{1+(Ax-b)_{i}^{2}},\;i=1,\ldots,n,\quad\text{for all
}\;x\in{\rm I\\!R}^{n}.$

The smooth part $f$ is also considered in [13, Section 4.1] for an image
deblurring and denoising problem. It follows from [13, (4.2)] that $\nabla f$
is Lipschitz continuous with constant
$L=2\left\|A\right\|_{1}\left\|A\right\|_{\infty}$, where

$\displaystyle\left\|A\right\|_{1}=\max_{1\leq j\leq
n}\sum_{i=1}^{n}|a_{ij}|,\quad\left\|A\right\|_{\infty}=\max_{1\leq i\leq
n}\sum_{j=1}^{n}|a_{ij}|,\quad A=[a_{ij}]_{i,j=\overline{1,n}}.$

Moreover, $f$ is analytic it is expressed as finite sums and compositions of
analytic functions, $g$ is semialgebraic and $\varphi$ is bounded from below
by $0$ Therefore, the assumptions on the objective function in Theorem 3.22
and [13, Theorem 8] are satisfied, and so both IPGM and iFB are applicable to
solve (4.1).

Problem (4.1) is studied in [44] when the matrix $B$ is square and orthogonal.
In this section, we consider $A\in{\rm I\\!R}^{n\times n},\;b\in{\rm
I\\!R}^{n},\;B\in{\rm I\\!R}^{m\times n}$ generated randomly, with i.i.d.
(identically and independent distributed) standard Gaussian entries, where
$m,n$ need not to be equal. The number $\gamma$ is chosen as either $10^{-3}$,
or $10^{-6}$. We provide two numerical experiments to illustrate how the
difference in the stopping criteria for the subproblems of iFB and IPGM affect
their performance.

  * •

In the first experiment, we let iFB run for 2000 iterations and record the
function value obtained by this method. Then IPGM runs until its function
value is lower than the recorded one of iFB.

  * •

In the second experiment, we let both algorithms run until
$\left\|g^{k}\right\|\leq 10^{-1}$, where
$g^{k}:=\dfrac{1}{\lambda}\left\|x^{k}-p^{k}\right\|$. We also stop the
algorithms if they either reach the maximum number of iterations of
$2,000,000$, or the time limit of $4000$ seconds.

More detailed information for the testing data used in the experiments is
presented in Table 1, where ”TN” stands for test number.

Experiment 1 | Experiment 2
---|---
TN | m | n | $\gamma$ | TN | m | n | $\gamma$
1 | 200 | 200 | $10^{-3}$ | 1 | 200 | 200 | $10^{-3}$
2 | 400 | 400 | $10^{-3}$ | 2 | 400 | 400 | $10^{-3}$
3 | 800 | 800 | $10^{-3}$ | 3 | 800 | 800 | $10^{-3}$
4 | 1600 | 1600 | $10^{-3}$ | 4 | 1600 | 1600 | $10^{-3}$
5 | 200 | 800 | $10^{-3}$ | 5 | 200 | 800 | $10^{-3}$
6 | 400 | 1600 | $10^{-3}$ | 6 | 400 | 1600 | $10^{-3}$
7 | 800 | 200 | $10^{-3}$ | 7 | 800 | 200 | $10^{-3}$
8 | 1600 | 400 | $10^{-3}$ | 8 | 1600 | 400 | $10^{-3}$
9 | 200 | 200 | $10^{-6}$ | 9 | 200 | 200 | $10^{-6}$
10 | 400 | 400 | $10^{-6}$ | 10 | 400 | 400 | $10^{-6}$
11 | 800 | 800 | $10^{-6}$ | 11 | 800 | 800 | $10^{-6}$
12 | 1600 | 1600 | $10^{-6}$ | 12 | 1600 | 1600 | $10^{-6}$
13 | 200 | 800 | $10^{-6}$ | 13 | 200 | 800 | $10^{-6}$
14 | 400 | 1600 | $10^{-6}$ | 14 | 400 | 1600 | $10^{-6}$
15 | 800 | 200 | $10^{-6}$ | 15 | 800 | 200 | $10^{-6}$
16 | 1600 | 400 | $10^{-6}$ | 16 | 1600 | 400 | $10^{-6}$
Table 1: Testing data

Now we describe the setting for both algorithms in the tests. Firstly, the
proximal parameter is chosen as $\lambda=1/2L$ to ensure that
$\lambda\in(0,L^{-1})$ for both algorithms. The starting point is chosen as
$x^{1}:=0_{{\rm I\\!R}^{n}}$. At any iteration of each algorithm, the step of
finding an approximation proximal point $p^{k}$ satisfying (3.55) is
equivalent to solving approximately the optimization problem

$\min\quad\Phi_{\lambda,F_{\lambda}(x^{k})}(p):=(2\lambda)^{-1}\left\|p-F_{\lambda}(x^{k})\right\|^{2}+\gamma\left\|Bx\right\|_{1}.$
(4.2)

The dual problem of (4.2) is given as

$\displaystyle\max\quad\Psi_{\lambda,k}(y):$
$\displaystyle=-\dfrac{\lambda}{2}\left\|B^{*}y\right\|^{2}+\left\langle
BF_{\lambda}(x^{k}),y\right\rangle-\delta_{\gamma\mathbb{B}^{\infty}}(y),$
(4.3)

where $\mathbb{B}^{\infty}:=\left\\{y\in{\rm
I\\!R}^{m}\;|\;\max_{i=1,\ldots,m}|y_{i}|\leq 1\right\\}$. In our tests, the
dual sequence $\\{y^{l}\\}$ to solve problem (4.3) is generated by means of
the Fast Iterative Shrinkage-Thresholding Algorithm (FISTA) from [6] and the
primal sequence in it is chosen as $p^{l}:=-\lambda
B^{*}y^{l}+F_{\lambda}(x^{k})$. The following main stopping criterion is used
in both IPGM and iFB:

$\displaystyle\Phi_{\lambda,F_{\lambda}(x^{k})}(p^{l})-\Psi_{\lambda,k}(y^{l})\leq\omega_{k},$
(4.4)

where the choice of $\omega_{k}$ depends on the method. Namely, the settings
for IPGM and iFB are as follows:

  * •

IPGM: $\omega_{k}=\mathscr{C}\varepsilon_{k}^{2}$, where
$\mathscr{C}:=\min\left\\{\dfrac{\lambda(1-\lambda\varrho)}{2},\dfrac{C_{1}^{2}}{4C_{2}^{2}},\dfrac{C_{1}}{4}\right\\}$
with $C_{1},C_{2}$ defined in Proposition 3.16. Since $g$ is convex, we get
$\varrho=0,$ and thus

$\displaystyle C_{1}=\lambda(1-\lambda L)=\dfrac{\lambda}{2}\text{ and
}C_{2}=2(\sqrt{2\lambda}+\sqrt{2\lambda})=4\sqrt{2\lambda}.$

Therefore, $\mathscr{C}=\dfrac{\lambda}{512}$. The initial radii
$\varepsilon_{1}$ and $r_{1}$ and the radius reduction factors $\mu,\theta$
are chosen as

$\displaystyle\varepsilon_{1}=r_{1}=\sqrt{\dfrac{100}{\mathscr{C}}}\;\text{
and }\;\mu=\theta=\dfrac{1}{2}.$

  * •

iFB: $\omega_{k}=\dfrac{1}{k^{4}}.$ This is a typical choice for $\omega_{k}$
to ensure that $\sum_{k=1}^{\infty}\sqrt{\omega_{k}}<\infty.$

All numerical experiments are conducted on a computer with 10th Gen Intel(R)
Core(TM) i5-10400 (6-Core 12M Cache, 2.9GHz to 4.3GHz) and 16GB RAM memory.
The codes are written in MATLAB R2021a. The result for the tests is presented
in the following tables, where “iter” is the number of iterations, and where
“fval” and “error” are the values of the objective function $\varphi$ and the
error $\omega_{k}$ required for the subproblem at the last iteration,
respectively.

| IPGM | iFB
---|---|---
TN | iter | fval | $\left\|g^{k}\right\|$ | error | $\varepsilon_{k}$ | time | iter | fval | $\left\|g^{k}\right\|$ | error | time
1 | 2014 | 28.59 | 3.2E+01 | 1.5E-06 | 1.0E+01 | 3.75 | 2000 | 28.60 | 3.2E+01 | 6.3E-14 | 3.88
2 | 2013 | 78.09 | 9.2E+01 | 6.0E-06 | 3.9E+01 | 11.36 | 2000 | 78.10 | 9.2E+01 | 6.3E-14 | 11.46
3 | 2013 | 211.12 | 3.0E+02 | 6.0E-06 | 7.6E+01 | 38.47 | 2000 | 211.17 | 3.0E+02 | 6.3E-14 | 42.98
4 | 2012 | 586.02 | 7.8E+02 | 2.4E-05 | 3.0E+02 | 340.72 | 2000 | 586.10 | 7.8E+02 | 6.3E-14 | 342
5 | 2013 | 237.33 | 2.9E+02 | 6.0E-06 | 7.6E+01 | 7.96 | 2000 | 237.37 | 2.9E+02 | 6.3E-14 | 8.18
6 | 2012 | 566.36 | 7.6E+02 | 2.4E-05 | 3.0E+02 | 30.3 | 2000 | 566.44 | 7.6E+02 | 6.3E-14 | 31.49
7 | 2014 | 38.91 | 3.3E+01 | 1.5E-06 | 1.0E+01 | 24.59 | 2000 | 38.92 | 3.3E+01 | 6.3E-14 | 20.76
8 | 2013 | 97.56 | 9.6E+01 | 6.0E-06 | 3.9E+01 | 281.07 | 2000 | 97.58 | 9.6E+01 | 6.3E-14 | 307.96
9 | 2014 | 28.43 | 3.2E+01 | 1.5E-06 | 1.0E+01 | 3.8 | 2000 | 28.44 | 3.2E+01 | 6.3E-14 | 4.97
10 | 2013 | 77.82 | 9.2E+01 | 6.0E-06 | 3.9E+01 | 9.21 | 2000 | 77.84 | 9.2E+01 | 6.3E-14 | 9.18
11 | 2013 | 210.71 | 3.0E+02 | 6.0E-06 | 7.6E+01 | 36.15 | 2000 | 210.76 | 3.0E+02 | 6.3E-14 | 36.41
12 | 2012 | 585.48 | 7.8E+02 | 2.4E-05 | 3.0E+02 | 392.7 | 2000 | 585.56 | 7.8E+02 | 6.3E-14 | 388.58
13 | 2013 | 237.24 | 2.9E+02 | 6.0E-06 | 7.6E+01 | 8.14 | 2000 | 237.28 | 2.9E+02 | 6.3E-14 | 8.06
14 | 2012 | 566.23 | 7.6E+02 | 2.4E-05 | 3.0E+02 | 30.38 | 2000 | 566.31 | 7.6E+02 | 6.3E-14 | 32.21
15 | 2013 | 38.24 | 3.3E+01 | 1.5E-06 | 1.0E+01 | 20.1 | 2000 | 38.24 | 3.3E+01 | 6.3E-14 | 20.06
16 | 2013 | 96.56 | 9.7E+01 | 6.0E-06 | 3.9E+01 | 306.7 | 2000 | 96.58 | 9.7E+01 | 6.3E-14 | 305.78
Table 2: Result of the first experiment  | IPGM | iFB
---|---|---
TN | iter | fval | $\left\|g^{k}\right\|$ | error | $\varepsilon_{k}$ | time | iter | fval | $\left\|g^{k}\right\|$ | error | time
1 | 786439 | 0.92 | 1.0E-01 | 2.3E-11 | 4.0E-02 | 1953.72 | 10530 | 10.32 | 8.8E+00 | 8.1E-17 | 4000
2 | 786866 | 2.95 | 6.3E-01 | 3.6E-10 | 3.1E-01 | 4000 | 9827 | 36.76 | 3.1E+01 | 1.1E-16 | 4000
3 | 193820 | 24.17 | 1.2E+01 | 2.3E-08 | 4.8E+00 | 4000 | 7785 | 114.19 | 1.1E+02 | 2.7E-16 | 4000
4 | 23461 | 227.81 | 1.8E+02 | 1.5E-06 | 7.5E+01 | 4000 | 8200 | 361.19 | 3.6E+02 | 2.2E-16 | 4000
5 | 921886 | 13.67 | 3.0E+00 | 1.5E-09 | 1.2E+00 | 4000 | 12124 | 119.70 | 8.3E+01 | 4.6E-17 | 4000
6 | 251253 | 73.71 | 3.0E+01 | 2.3E-08 | 9.4E+00 | 4000 | 10507 | 307.73 | 3.1E+02 | 8.2E-17 | 4000
CT 7 | 381454 | 4.96 | 4.0E-01 | 3.6E-10 | 1.6E-01 | 4000 | 7835 | 20.81 | 1.5E+01 | 2.7E-16 | 4000
8 | 45168 | 26.97 | 1.1E+01 | 9.3E-08 | 4.9E+00 | 4000 | 6908 | 58.10 | 4.4E+01 | 4.4E-16 | 4000
9 | 1127533 | 0.28 | 1.0E-01 | 2.3E-11 | 4.0E-02 | 2515.67 | 50316 | 2.45 | 3.0E+00 | 1.6E-19 | 4000
10 | 690078 | 1.73 | 7.5E-01 | 3.6E-10 | 3.1E-01 | 4000 | 43018 | 15.86 | 1.0E+01 | 2.9E-19 | 4000
11 | 184279 | 23.11 | 1.3E+01 | 2.3E-08 | 4.8E+00 | 4000 | 39672 | 52.81 | 3.4E+01 | 4.0E-19 | 4000
12 | 21417 | 235.58 | 1.9E+02 | 1.5E-06 | 7.5E+01 | 4000 | 23285 | 226.89 | 1.8E+02 | 3.4E-18 | 4000
13 | 922893 | 12.94 | 3.0E+00 | 1.5E-09 | 1.2E+00 | 4000 | 52519 | 66.71 | 3.3E+01 | 1.3E-19 | 4000
14 | 253962 | 72.51 | 3.0E+01 | 2.3E-08 | 9.4E+00 | 4000 | 52220 | 145.44 | 9.6E+01 | 1.3E-19 | 4000
15 | 389506 | 1.82 | 5.5E-01 | 3.6E-10 | 1.6E-01 | 4000 | 35987 | 8.76 | 3.6E+00 | 6.0E-19 | 4000
16 | 38703 | 25.86 | 1.3E+01 | 9.3E-08 | 4.9E+00 | 4000 | 30827 | 28.76 | 1.4E+01 | 1.1E-18 | 4000
Table 3: Result of the second experiment

The results in the tests can be summarized as follows:

$\bullet$ Table 2 shows that the performances of the two algorithms are
typically the same when the number of iterations is small.

$\bullet$ Table 3 shows that when the large number of iterations is required,
IPGM has advantages on the errors control. It can be seen from this table that
the error required for subproblems of IPGM is larger than that of iFB.
Therefore, IPGM requires less time to solve subproblems than iFB, which makes
it faster. Eventually, in all tests in Table 3 except Test 12 and Test 16, iFB
stagnates at the number of iteration much smaller than IPGM, and thus IPGM
attains smaller objective function than iFB.

##  5  Conclusions and Further Research

In this paper, we propose and develop inexact proximal point and inexact
proximal gradient methods to solve problems of weakly convex optimization and
nonconvex composite optimization. These methods achieve stationary
accumulation points and, under additional assumptions on the KL property of
the envelopes, the global linear convergence. The convergence analysis of the
developed algorithms are based on the general framework of finding zeros of
continuous mappings when only inexact information for such mappings is
accessible. A new approximate subdifferential for weakly convex functions is
employed to simplify the convergence analysis of the aforementioned methods.

Our future research includes detailed and efficient numerical analysis and
experiments to solve subproblems of the proposed methods. We also intend to
find conditions ensuring the convergence to local/global minimizers of our
inexact methods. The obtained results would allow us to develop new
applications in important classes of models in machine learning, statistic,
and related disciplines.

## References

  * [1] P.-A. Absil, R. Mahony and B. Andrews, Convergence of the iterates of descent methods for analytic cost functions, SIAM J. Optim. 16 (2005), 531–547.
  * [2] 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, Math. Program. 137 (2013), 91–129.
  * [3] 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 property, Math. Oper. Res. 35 (2010), 438–457.
  * [4] G. R. Ayers and J. C. Dainty, Iterative blind deconvolution method and its applications, Optim. Lett. 13 (1988), 547–549.
  * [5] A. Beck, First-Order Methods in Optimization, SIAM, Philadelphia, PA, 2017.
  * [6] A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci. 2 (2009), 183–202.
  * [7] E. Bednarchuk, G. Bruccola, G. Serivanti and T. H. Tran, Convergence analysis of an inexact forward-backward algorithm for problems involving weakly convex functions, arXiv:2303.14021 (2023).
  * [8] R. Benedetti and J.-J. Risler, Real Algebraic and Semialgebraic Sets, Hermann, Éditeur des Sciences et des Arts, Paris (1990).
  * [9] D. P. Bertsekas, Nonlinear Programming, 3rd edition, Athena Scientific, Belmont, MA, 2016.
  * [10] A. Bohm and S. J. Wright, Variable smoothing for weakly convex composite functions, J. Optim. Theory Appl. 188 (2021), 628–649.
  * [11] J. Bolte, A. Daniilidis and A. Lewis, The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems, SIAM J. Optim. 17 (2007), 1205–1223.
  * [12] J. Bolte, A. Daniilidis and A. Lewis and M. Shiota, Clarke subgradients of stratifiable functions, SIAM J. Optim. 18— (2007), 556–572.
  * [13] S. Bonettini, M. Prato and S. Rebegoldi, Convergence of inexact forwardbackward algorithms using the forward-backward envelope, SIAM J. Optim. 30 (2020), 3069–3097.
  * [14] J.-F. Cai, E. J. Candés and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim. 20 (2010), 1956–1982.
  * [15] G. Chierchia, E. Chouzenoux, P. L. Combettes and J.-C. Pesquet, The Proximity Operator Repository, http://proximity-operator.net/index.html, 2016.
  * [16] D. Davis and D. Drusviatskiy, Proximal methods avoid active strict saddles of weakly convex functions, Found. Comput. Math. 22 (2022), 561–606.
  * [17] F. Facchinei and J.-S. Pang, Finite-Dimensional Variational Inequalities and Complementarity Problems, Vols. I, II, Springer, New York, 2003.
  * [18] J. Fadili and G. Peyré, Total variation projection with first order schemes, IEEE Trans. Image Process. 20 (2011), 657–669.
  * [19] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms, Vols. I and II, Springer, Berlin, 1993.
  * [20] A. D. Ioffe, An invitation to tame optimization, SIAM J. Optim. 19 (2009), 1894–1917.
  * [21] P. D. Khanh, B. S. Mordukhovich and V. T. Phat, A generalized Newton method for subgradient systems, Math. Oper. Res. DOI 10.1287/moor.2022.1320 (2022).
  * [22] P. D. Khanh, B. S. Mordukhovich, V. T. Phat and D. B. Tran, Generalized damped Newton algorithms in nonsmooth optimization via second-order subdifferentials, J. Global Optim. 86 (2023), 93–122.
  * [23] P. D. Khanh, B. S. Mordukhovich, V. T. Phat and D. B. Tran, Globally convergent coderivative-based generalized Newton methods in nonsmooth optimization, Math. Program. DOI 10.1007/s10107-023-01980-2.
  * [24] P. D. Khanh, B. S. Mordukhovich and D. B. Tran, Inexact reduced gradient methods in nonconvex optimization, arXiv:2204.01806 (2022).
  * [25] S. G. Krantz and H. R. Parks, A Primer of Real Analytic Functions, 2nd edition, Birkhäuser, Basel, 2002.
  * [26] S. Łojasiewicz, Ensembles Semi-Analytiques, Institut des Hautes Etudes Scientifiques, Bures-sur-Yvette (Seine-et-Oise), France, 1965.
  * [27] B. Martinet, Regularisation d’indquations variationelles par approximations successives, Rev. Francaise Inf. Rech. Oper. (1970), 154–159.
  * [28] B. S. Mordukhovich, Variational Analysis and Generalized Differentiation, I: Basic Theory, II: Applications, Springer, Berlin, 2006.
  * [29] B. S. Mordukhovich, Variational Analysis and Applications, Springer, Cham, Switzerland, 2018.
  * [30] B. S. Mordukhovich and N. M. Nam, Convex Analysis and Beyond, Vol. I: Basic Theory, Springer, Cham, Switzerland.
  * [31] Yu. Nesterov, Gradient methods for minimizing composite functions, Math. Program. 140 (2013), 125–161.
  * [32] Yu. Nesterov, Lectures on Convex Optimization, 2nd edition, Springer, Cham, Switzerland, 2018.
  * [33] E. A. Nurminskii, The quasigradient method for the solving of the nonlinear programming problems, Cybernetics 9 (1973), 145–150.
  * [34] P. Ochs, Y. Chen, T. Brox and T. Pock, iPiano: Inertial proximal algorithm for nonconvex optimization, SIAM J. Imaging Sci. 7 (2014), 1388–1419.
  * [35] A. Ostrowski, Solution of Equations and Systems of Equations, 2nd edition, Academic Press, New York, 1966.
  * [36] P. Patrinos and A. Bemporad, Proximal Newton methods for convex composite optimization, IEEE Conference on Decision and Control (2013), 2358–2363.
  * [37] K. Pelckmans, J. De Brabanter, B. De Moor and J. A. K. Suykens, Convex clustering shrinkage, In: PASCAL Workshop on Statistics and Optimization of Clustering, pp. 1–6. London, UK, 2005.
  * [38] B. T. Polyak, Existence theorems and convergence of minimizing sequences in extremum problems with restrictions, Soviet Math. Dokl. 7 (1966), 72–75.
  * [39] M. Raginsky, R. Willett, Z. Harmany and R. Marcia, Compressed sensing performance bounds under Poisson noise, IEEE Trans. Signal Process 58 (2010), 3990–4002.
  * [40] R. T. Rockafellar, Monotone operators and the proximal point algorithm, SIAM J. Control Optim. 14 (1976), 877–898.
  * [41] R. T. Rockafellar and R. J-B Wets, Variational Analysis, Springer, Berlin, 1998.
  * [42] M. Schmidt, N. L. Roux and F. R. Bach, Convergence rates of inexact proximal-gradient methods for convex optimization, Adv. Neural. Inf. Process. Syst. 24 (2011), 1458–1466.
  * [43] A. Sidford, Introduction to Optimization Theory, Lecture Notes, https://web.stanford.edu/~sidford/courses/19fa_opt_theory/fa19_opt_theory.html.
  * [44] A. Themelis, L. Stella and P. Patrinos, Forward–backward quasi-Newton methods for nonsmooth optimization problems, Comput. Optim. Appl. 67 (2017), 443–487.
  * [45] A. Themelis, L. Stella and P. Patrinos, Forward-backward envelope for the sum of two nonconvex functions, further properties and nonmonotone linesearch algorithms, SIAM J. Optim. 28 (2018), 2274–2303.
  * [46] R. Tibshirani, Regression shrinkage and selection via the Lasso, J. R. Stat. Soc. 58 (1996), 267–288.
  * [47] X. Wang, On Chebyshev functions and Klee functions, J. Math. Anal. Appl. 368 (2010), 293–310.