# Inexact Version of Bregman Proximal Gradient Algorithm

Authors: S. Kabbadj
Journal: Abstract and Applied Analysis
 (2020)

---

## Abstract

The Bregman Proximal Gradient (BPG) algorithm is an algorithm for minimizing the sum of two convex functions, with one being nonsmooth. The supercoercivity of the objective function is necessary for the convergence of this algorithm precluding its use in many applications. In this paper, we give an inexact version of the BPG algorithm while circumventing the condition of supercoercivity by replacing it with a simple condition on the parameters of the problem. Our study covers the existing results, while giving other.


---

## Body

## 1. Introduction

We consider the following minimization problem:(1)infΨx≔fx+gx:x∈Rd.where f is a convex proper lower-semicontinuous (l.s.c.) function and g is a convex continuously differentiable function. This problem arises in many applications including compressed sensing [1], signal recovery [2], and phase retrieve problem [3]. One classical algorithm for solving this problem is the proximal gradient (PG) method:(2)xn≔argminfu+∇gxn−1,u+12λnu−xn−12n∈N∗.where λn is the stepsize on each iteration. The Proximal Gradient Method and its variants [4–14] have been one hot topic in optimization field for a long time due to their simple forms. A central property required in the analysis of gradient methods is that of the Lipschitz continuity of the gradient of the smooth part g. However, in many applications, the differentiable function does not have such a property, e.g., in the broad class of Poisson inverse problems. In [15], by introducing the Bregman distance [16] generated by some reference convex function h defined by(3)Dhx,y=hx−hy−x−y,∇hy,the authors could replace the intricate question of Lipschitz continuity of gradients by a convex condition easy to verify, which we call below LC property. Thereby, they proposed and studied the algorithm called NoLips defined by(4)xn=argminfu+∇gxn−1,u+1λnDhu,xn−1n∈N∗.where g=0. Equation (4) is the Bregman Proximal (BP) studied in [17–21].In this article, we give an inexact version of the (BPG) defined by(5)xn∈εn−argminfu+∇gxn−1,u+1λnDhu,xn−1.While circumventing the condition of supercoercivity required in [15, 22] by replacing it with a simple condition on the parameters of the problem, our study covers the existing results, while giving others.Our notation is fairly standard,.,. is the scalar product on Rd, and the associated norm ⋅. The closure of the set C (relative interior) is denoted by C¯ (riC, respectively). For any convex function f, we denote by(1)
domf=x∈Rd,fx<+∞ its effective domain(2)
∂εf⋅=v,fy≥f⋅+v,y−.−ε,∀y its ε−subdifferential(3)
argminf=x∈Rd,fx=inff its argmin f(4)
ε−argminf=x∈Rd,fx≤inff+ε its ε−argminf


## 2. Preliminary

In this section, we present the main results of the convergence of NoLips.Definition 1 (see [23]).
LetC be a convex, not empty of Rd.(i)
A convex functionh:Rd⟶−∞,+∞ is of Legendre on C if it verifies the three following conditions:(a)
C = int (dom h)(b)
h is differentiable on C(c)
lim∇hxi=+∞, for any sequence xi of C that converges towards a boundary point of C(ii)
The class of strictly convex functions verifyinga, b, and c is called the class of Legendre’s functions on C and denoted by EC.Definition 2 (see [23]).
LetF: Rd⟶−∞,+∞; we say that F is supercoercive if(6)liminfx⟶∞Fxx=∞.Consider the following assumptions.Assumption 1.
(i)
h: X⊂Rd⟶−∞,+∞ is of Legendre type
(ii)
g: X⟶−∞,+∞ is convex proper l.s.c. with domh⊂domg, which is differentiable on intdomh
(iii)
f: X⟶−∞,+∞ is convex proper lower semicontinuous (l.s.c.)
(iv)
dom
f
∩
int
dom
h
≠
∅
(v)
inf
Ψ
x
,
x
∈
dom
h
¯
>
−
∞
We consider the following minimization problem: (P): infΨx≔fx+gx:x∈domh¯.
Let the operatorTλ be defined by(7)Tλx=argminfu+∇gx,u−x+1λDhu,x.Lemma 1 (well-posedness of the method).
Under Assumption1, suppose one of the following assumptions holds:(i)
argminΨx,x∈domh¯ is nonempty and compact(ii)
∀λ>0,h+λf is supercoercive and the map Tλ defined in (7) is nonempty and single-valued from int (domh) to int (domh).Definition 3.
The couple (g, h) verified a Lipschitz-like/Convexity Condition (LC) if ∃L>0 with Lh-g convex on int (dom h).
By posing(8)proxλfhx≔argminfu+1λDhu,x,they showed that(9)Tλx=proxλfhoproxλphx,where pu=∇gx,u. The operator Tλ thus appears as composed of two operators prox. The NoLips algorithm then becomes(10)xn=Tλnxn−1,∀n∈N∗.Assumption 2.
(i)
argmin
Ψ
x
,
x
∈
dom
h
¯ is nonempty and compact or ∀λ>0,h+λf is supercoercive
(ii)
For everyx∈intdomh and r∈R, the level set L1x,r=y∈intdomh:Dhx,y≤r is bounded
(iii)
Ifxnn converges to some x in int (dom h), then Dhx,xn⟶0
(iv)
Reciprocally, if x in int (domh) and if xnn is such that Dhx,xn⟶0, then xn⟶x
(v)
∃
L
>
0 with Lh-g convex on int (dom h) (LC)Theorem 1 (Global Convergence).
Assume that(i)
domh¯=domh.(ii)
∑λn=+∞ and Assumptions 1 and 2 are satisfied. Then, the sequence xnn converges to some solution x∗ of (P).Our contribution is resumed in two essential points:(1)
Improvements of some assumptions:(a)
Supposef and g are both are convex (see [15, 22]), we show that we can reduce this hypothesis by supposing only that Ψ is convex, which allows to distinguish two interesting cases that are still not yet studied neither in the case of the BPG nor in the case PG:(i)
The nonsmooth partf is possibly not convex and the smooth part g is convex(ii)
The nonsmooth partf is convex and the smooth part g is possibly not convex(b)
The assumption is as follows:argminΨx,x∈domh¯ is compact or ∀λ>0,h+λf is supercoercive.This is a condition onf and g (see [15]), which precludes the application of NoLips for the functions Ψ non-supercoercive. In this work, we show that we can circumvent this condition by coupling the LC property with the bounded level sets as follows:(11)L2x,r=y∈S¯;Dhy,x≤r.It is a condition which relates to the parameterh and which is verified by most of the interesting Bregman distances.(2)
Inexact version of NoLips.We propose an inexact version of NoLips calledε−NoLips which verifies(12)xn=εn−argminfu+∇gxn−1,u+1λnDhu,xn−1,n∈N∗.The convergence result is established in Section4. This study covers the convergence results given for PG and BPG, by giving new results, in particular, the convergence of the inexact version of the interior method with Bregman distance studied in [24]; this result has not been established until now.We also note that the convergence of NoLips is given with the following condition:(13)domh¯=domh.It is for that and for the clarity of the hypothesis, we suppose in what follows that h:S¯⟶R, with S being an open convex set of Rd.


## 3. Main Results

In order to clarify the status of parameterh, we give the following definitions. Let S be a convex open subset of Rd and h:S¯⟶R. Let us consider the following hypotheses:H1: h is continuously differentiable on S.H2: h is continuous and strictly convex on S¯.H3: ∀r≥0,∀x∈S¯, the sets below are bounded(14)L2x,r=y∈S;Dhy,x≤r.H4: ∀r≥0,∀x∈S, the sets below are bounded(15)L2x,r=y∈S¯;Dhy,x≤r.H5: if xnn⊂S, then xn⟶x∗∈S¯, so(16)Dhx∗,xn⟶0.H6: if xnn⊂S, then Dhx∗,xn⟶0, so(17)xn⟶x∗.Definition 4.
(i)
h: S¯⟶R is a Bregman function on S or“D-function” if h verifies H1,H2,H3,H4,H5, and H6.
(ii)
D
h
.,.
:
S
¯
X
S
⟶
R such that ∀x∈S¯,∀y∈S:
(18)
D
h
x
,
y
=
h
x
−
h
y
−
x
−
y
,
∇
h
y
.Eq. (18) is called Bregman distance if h is a Bregman function. We put the following conditions:AS=h:S¯⟶RverifingH1,H2BS=h:S¯⟶RverifingH1,H2,H3,H4,H5andH6ES=h:S¯⟶R,the Legendre type of SProposition 1.
Let h andh′ verify H1.(19)∀λ,Dλh+h′.,.=λDh.,.+Dh′.,..Lemma 2.
∀
h
∈
A
S
,
∀
a
∈
S
¯
,
and
∀
b
,
c
∈
S
:
(20)
D
h
a
,
b
+
D
h
b
,
c
−
D
h
a
,
c
=
a
−
b
,
∇
h
c
−
∇
h
b
.Example 1.
IfS0=Rd and h0x=1/2x2, then(21)Dh0x,y=12x−y2.Example 2.
IfS1=R++d≔x∈Rd/xi>0,i=1,…,d and(22)h1x=∑i=1i=dxilogxi,∀x∈S1¯,with the convention 0log0=0, then ∀x,y∈S¯1XS1:(23)Dh1x,y=∑i=1dxilogxiyi+yi−xi.Example 3.
IfS2=−1,1d and h2x=−∑i=1i=d1−xi2, thenDh2x,y=h2x+∑i=1d1−xiyi/yi2,∀x,y∈S2¯XS2.Proposition 2 (see [19]).
h
i
∈
B
S
i
∩
E
S
i
,
i
=
0,1,2. We consider the following minimization problem:(24)p:infΨx≔fx+gx:x∈S¯.The following assumptions on the problem’s data are made throughout the paper (and referred to as the blanket assumptions).Assumption 3.
(i)
h
∈
A
S
∩
E
S
(ii)
g: Rd⟶−∞,+∞ is proper (l.s.c.) with S¯⊂dom g, which is and continuously differentiable on S¯
(iii)
f: Rd⟶−∞,+∞ is proper (l.s.c.)
(iv)
ri
dom
Ψ
∩
S
≠
∅
(v)
Ψ
∗
≔
inf
Ψ
x
,
x
∈
S
¯
>
−
∞
We consider the operatorTλ defined by ∀x∈S:(25)Tλx=argminfu+∇gx,u−x+1λDhu,x,u∈S¯.
We give in the following a series of lemmas allowing establishment of Theorem2, which assures the well-posedness of the method proposed in Section 4.Lemma 3.
∀
λ
>
0
and
∀
x
∈
S
:
(26)
T
λ
x
=
argmin
Ψ
u
+
1
λ
D
h
−
λ
g
u
,
x
,
u
∈
S
¯
.Proof.
∀
x
∈
S
⊂
dom
g
:
(27)
25
⟹
T
λ
x
=
argmin
f
u
+
g
x
+
∇
g
x
,
u
−
x
+
1
λ
D
h
u
,
x
,
u
∈
S
¯
.
When∀u∈S¯⊂domg, we have(28)fu+gx+∇gx,u−x+1λDhu,x=Ψu+gx−gu+∇gx,u−x+1λDhu,x=Ψu−Dgu,x+1λDhu,x=Ψu+1λDh−λgu,x.Lemma 4.
If the pair (g, h) verified the condition (LC), then ∃L>0,∀x∈S,∀u∈S¯:(i)
Dgu,x≤LDhu,x(ii)
∀λ∈]0,1/L[,Dh−λgu,x≥0Proof.
(i)
IfLh-g is convex on S, then
(29)
D
L
h
−
g
u
,
x
≥
0
,
∀
x
∈
S
,
∀
u
∈
S
.
Letu∈S¯/S. There exists a sequence unn⊂S such that un⟶u; then, we have
(30)
D
L
h
−
g
u
n
,
x
≥
0
,
Lh-g is continuous in S¯; then, DLh−gu,x≥0.
(ii)
Letλ∈]0,1/L[:
(31)
D
L
h
−
g
u
,
x
≥
0
⟹
L
D
h
u
,
x
≥
D
g
u
,
x
⟹
1
λ
D
h
u
,
x
≥
D
g
u
,
x
⟹
D
h
−
λ
g
u
,
x
≥
0.Lemma 5.
Ifh is the Legendre on S, then h−λg is also the Legendre on S, for all λ such that 0<λ<1/L.Proof.
Conditions (a) and (b) of Definition1 being verified, let us demonstrate that the condition (c) is verified too. Let xi be xi⟶x∗∈FrS=S¯/S:(32)∇hxi−λ∇gxi2≥∇hxi∇hxi−2λ∇gxi+λ2∇gxi2.Then,(33)limxi⟶x∗∈FrS∇h−λgxi=+∞.h−λg is strictly convex in S. Indeed, let x,y∈S,x≠y; we have Dh−λgx,y≥0:(34)Dh−λgx,y=0⟹Dhx,y=λDgx,y⟹Dhx,y≤λLDhx,y,h is strongly convex on S, x,y∈S,x≠y; then, Dhx,y≠0⟹1≤λL which is absurd. Hence, h−λg is strictly convex in S.Lemma 6.
Consider the following:(35)∀λ∈0,1L,∀u∈S,∂Dh−λg.,ux∗=∇h−λgx∗−∇h−λgu,ifx∗∈S,∅,if not.Proof.
Sinceh−λg is a Legendre function on S, Dh−λg.,u is also a Legendre. By application of Theorem 26.1 in [23], ∂Dh−λg.;u verifies the following:(i)
Ifx∗∈intdomDh−λg.,u=S, then(36)∂Dh−λg.,ux∗=∇Dh−λg.,ux∗.(ii)
Ifx∗∉S, then ∂Dh.,ux∗=∅.Theorem 2 (well-posedness of the method).
We assume that(i)
Ψ is convex.(ii)
The pair (g, h) verified the condition (LC).(iii)
∀r≥0,∀x∈S, the sets below are bounded:(37)L2x,r=y∈S;Dhy,x≤r.Then, ∀λ∈]0,1/L[ and the map Tλ defined in (25) is nonempty and single-valued from S to S.Proof.
∀
x
∈
S and Tλx is nonempty; for this, it is enough to demonstrate that ∀r∈R:(38)Lx,r=u∈S¯:Ψu+λ−1Dh−λgu,x≤r,which is closed and is bounded when it is nonempty:(39)u∈Lx,r⟹Ψu+λ−1Dh−λgu,x≤r⟹Dh−λgu,x≤λr−Ψ∗⟹Dhu,x≤λr−Ψ∗+λDgu,x⟹Dhu,x≤λr−Ψ∗≤λr−Ψ∗+LλDhu,x⟹Dhu,x≤λr−Ψ∗1−Lλ.
It follows that(40)Lx,r⊂L2x,λr−Ψ∗1−Lλ,thanks to H4;L2x,λr−Ψ∗/1−Lλ is bounded, which leads that Lx,r is bounded too, which shows that(41)Tλx≠∅.
Letx∗∈Tλx. Let us suppose that x∗∈S26⟹0∈∂Ψ⋅+1/λDh−λg.,xx∗, since ridomΨ∩ridomDh−λg.,x=ridomΨ∩riS¯=ridomΨ∩S≠∅, from [10], which allows to write that(42)0∈∂Ψx∗+∂1λDh−λg.,xx∗.
It follows that(43)∃u∈∂Ψx∗,such that(44)−λu∈∂Dh−λg.,xx∗is in contradiction with Lemma 6. Then, Tλx⊂S.
On the other hand,h−λg is strictly convex in S and Ψ is convex, so Ψ⋅+Dh−λg.,x is strongly convex in S. Then, Tλx has a unique value for all x∈S.Remark 1.
This result is liberated from the supercoercivity ofΨ and the simultaneous convexity of f and g, as required by Lemma 2 [15].Proposition 3.
∀
x
∈
S
,
∀
λ
∈
]
0
,
1
/
L
[
(45)
∇
h
−
λ
g
x
−
∇
h
−
λ
g
T
λ
x
λ
∈
∂
Ψ
T
λ
x
,
(46)
∃
x
¯
∈
S
,
∇
h
−
λ
g
x
−
∇
h
−
λ
g
x
¯
λ
∈
∂
ε
Ψ
x
¯
.Proof.
SinceTλx∈S, we have(47)0∈∂Ψ⋅+1λDh−λg.,xTλx⟹−∇1λDh−λg.,xTλx∈∂ΨTλx⟹45.
For (46), just take x¯=Tλx, since(48)∂ΨTλx⊂∂εΨTλx.Proposition 4.
∀
x
∈
S
,
∀
λ
∈
]
0
,
1
/
L
[:
(49)
T
λ
x
=
prox
λ
Ψ
h
−
λ
g
x
=
prox
λ
f
h
o
prox
λ
p
h
x
,where pu=∇gx,u.Proof.
The first equality is due to Lemma3. The second is established in [15].The first equality played a decisive role in the development of this paper.


## 4. Analysis of theε−NoLips Algorithm

In this section, we propose an Inexact Bregman Proximal Gradient Algorithm (IBPG), which is an inexact version of the BPG algorithm described in [15, 22]; the IBPG framework allows an error in the subgradient inclusion by using the error εn. We study two algorithms:(i)
Algorithm 1: inexact Bregman Proximal Gradient (IBPG) algorithm without relative error criterion(ii)
Algorithm 2: inexact Bregman Proximal Gradient (IBPG) algorithm with relative error criterion which we callε−NoLipsWe establish the main convergence properties of the proposed algorithms. In particular, we prove its global rate of convergence, showing that it shares the claimed sublinear rateO1/n of basic first-order methods such as the classical PG and BPG. We also derive a global convergence of the sequence generated by NoLips to a minimizer of (P).Assumptions 4.
(i)
h
∈
B
S
∩
E
S
(ii)
Ψ is convex
(iii)
The pair (g, h) verified the condition (LC)
(iv)
ArgminΨ≠∅
In our analysis,Ψ is supposed to be a convex function; it allows to distinguish two interesting cases:(i)
The nonsmooth partf is possibly not convex, and the smooth part g is convex(ii)
The nonsmooth partf is convex, and the smooth part g is possibly not convex
In what follows, the choice of the sequenceλn depends of the convexity of g.
Letλ¯ such that 0<λ¯<1/L, λ0≔0.
Ifg is not convex, then we choose(50)λn=λ,0<λ≤λ¯,n=1….
Ifg is convex, then we choose(51)λn≤λn+1≤λ¯,n=1….
In those conditions, we easily show that
∀
x
,
y
∈
S
,
∀
n
∈
N, 0<λn≤λ¯, such that(52)λn+1−λnDgx,y≥0,
We pose(53)hn=h−λng,n=1….Proposition 5.
The sequencexnn defined by (IBPG) exists and is verified for all n∈N∗:(54)xn∈εn−argminΨu+1λnDhnu,xn−1,u∈S¯.Proof.
Existence is deduced trivially from (45):(55)Ωn≔∇hnxn−1−∇hnxnλn∈∂εnΨxn⟹Ψu≥Ψxn+u−xn,Ωn−εn.
By applying Lemma2, we have(56)Ψu≥Ψxn+λn−1Dhnu,xn+Dhnxn,xn−1−Dhnu,xn−1−εn,⟹Ψxn+λn−1Dhnxn,xn−1≤Ψu+λn−1Dhnu,xn−1+εn,∀u∈S¯⟹xn∈Tλnεnxn−1,where Tλεx=ε−argminΨu+1/λDh−λgu,x.Remark 2.
This result shows that IBPG is an inexact version of BPG and this is exactly the BPG whenεn=0, i.e.:(i)
xn∈Tλnεnxn−1⟹xn≃Tλnxn−1(ii)
εn=0⟹xn=Tλnxn−1Proposition 6.
For alln∈N∗,(57)iΨxn−Ψxn−1≤−Dhnxn,xn−1+λnεn,(58)iiDhxn,xn−1+Dhxn−1,xn≤λ¯1−λ¯LΨxn−1−Ψxn+λnεn1−λ¯L.Proof.
(59)
55
⟹
λ
n
Ψ
x
n
−
Ψ
u
≤
D
h
n
u
,
x
n
−
1
−
D
h
n
u
,
x
n
−
D
h
n
x
n
,
x
n
−
1
+
ε
n
λ
n
.
We putu=xn−1 in (59), we get (57)
(ii)
Putu=xn−1 in (59), we have
(60)
D
h
n
x
n
,
x
n
−
1
+
D
h
n
x
n
−
1
,
x
n
≤
λ
n
Ψ
x
n
−
1
−
Ψ
x
n
+
λ
n
ε
n
⟹
D
h
x
n
,
x
n
−
1
+
D
h
x
n
−
1
,
x
n
≤
λ
n
Ψ
x
n
−
1
−
Ψ
x
n
+
λ
n
ε
n
+
λ
n
D
g
x
n
,
x
n
−
1
+
λ
n
D
g
x
n
−
1
,
x
n
⟹
D
h
x
n
,
x
n
−
1
+
D
h
x
n
−
1
,
x
n
≤
λ
¯
Ψ
x
n
−
1
−
Ψ
x
n
+
λ
n
ε
n
+
λ
¯
L
D
h
x
n
,
x
n
−
1
+
D
h
x
n
−
1
,
x
n
⟹
D
h
x
n
,
x
n
−
1
+
D
h
x
n
−
1
,
x
n
≤
λ
¯
1
−
λ
¯
L
Ψ
x
n
−
1
−
Ψ
x
n
+
λ
n
ε
n
1
−
λ
¯
L
.Corollary 1.
(i)
Ifεn=0, the sequence Ψxnn is nonincreasing
(ii)
Summability: if∑n=1∞λnεn<+∞, then ∑n=1∞Dhxn,xn−1<+∞ and ∑n=1∞Dhxn−1,xn<+∞Proof.
(i)
From (57), Dhnxn,xn−1≥0⟹Ψxn≤Ψxn−1,∀n∈N∗.
(ii)
From (58), ∑n=1n=pDhxn,xn−1+Dhxn−1,xn≤:
(61)
λ
¯
1
−
λ
¯
L
∑
n
=
1
n
=
p
Ψ
x
n
−
1
−
Ψ
x
n
+
1
1
−
λ
¯
L
∑
n
=
1
n
=
p
λ
n
ε
n
⟹
∑
n
=
1
n
=
p
D
h
x
n
,
x
n
−
1
+
D
h
x
n
−
1
,
x
n
≤
λ
¯
1
−
λ
¯
L
Ψ
x
0
−
Ψ
∗
+
1
1
−
λ
¯
L
∑
n
=
1
n
=
p
λ
n
ε
n
.In the following, we pose(62)tp≔∑n=1n=pλn,∀p∈N∗,t0=λ0=0,Anu=Dhnu,xn,∀u∈S¯,∀n∈N∗,Φxp≔minΨxk,1≤k≤p,∀p∈N∗.Proposition 7 (Global Estimate in Function Values).
(a) For allu∈S¯and∀p∈N∗,(63)Φxp−Ψu≤1tpDhu,x0+∑n=1∞λnεn.Proof.
We haveDhnu,xn−1=An−1u−λn−λn−1Dgu,xn−1; from (59), we have(64)λnΨxn−Ψu≤An−1u−Anu−Dhnxn,xn−1−λn−λn−1Dgu,xn−1+λnεn.
From (52), we have(65)λnΨxn−Ψu≤An−1u−Anu+λnεn⟹∑n=1n=pλnΨxn−Ψu≤∑n=1n=pAn−1u−Anu+∑n=1n=pλnεn⟹∑n=1n=pλnΨxn−Ψu≤A0u−Apu+∑n=1n=pλnεn⟹Φxp−Ψu∑n=1n=pλn≤A0u−Apu+∑n=1n=pλnεn,A0u=Dhu,x0 (λ0=0), so(66)Φxp−Ψu≤1tpDhu,x0+∑n=1∞λnεn.This theorem covers the evaluation of the global convergence rate given in6,12, as shown by the following corollary.Corollary 2.
We assume that(a)
εn=0,n=1,…(b)
λn=λ¯=1/2L,n=1,…(c)
x∗∈argminΨ
Then,(67)Ψxp−Ψ∗≤2LpDhx∗,x0,i.e., Ψxp−Ψ∗=O1/pProof.
Immediate consequence of Proposition7.Now, we derive a global convergence of the sequence generated by Algorithm1 to a minimizer of (P).Theorem 3.
We assume that∑λnεn<+∞, if one of the following assumptions holds:(i)
∃λ¯>0 such that λ¯≤λn≤λ¯, n=1,…(ii)
The sequenceΨxn is nonincreasing and ∑λn=+∞; then, (a) Ψxn⟶infΨ and (b) xn⟶x∗∈argminΨProof.
(a)
Suppose(i)
Letx∗∈argminΨ and we put u=x∗ in (69), we have(68)λ¯Ψxn−Ψx∗≤An−1x∗−Anx∗+λnεn,(69)Anx∗≤An−1x∗+λnεn,(70)∑λnεn<+∞⟹Anx∗⟶l∈R.(68) and (suppose (69)) ⟹Ψxn⟶infΨ.Suppose (ii)(71)Φxp=minΨxk,1≤k≤p=Ψxp.Foru=x∗∈argminΨ in (63), we have 0≤Ψxp−Ψx∗≤1/tpDhx∗,x0+∑n=1∞λnεn, so ∑λn=+∞⟹Ψxn⟶infΨ.
(b)
69
⟹
∃
α
>
0
,
A
n
x
∗
≤
α
A
n
x
∗
=
D
h
n
x
∗
,
x
n
=
D
h
x
∗
,
x
n
−
λ
n
D
g
x
∗
,
x
n, so(72)Dhx∗,xn≤α+λnDgx∗,xn⇓Dhx∗,xn≤α1−λ¯L.Then, Dhx∗,xn is bounded, and from H3, xn is bounded as well. Let u∗∈Adhxn; there exists then a subsequence xni of xn such that xni⟶u∗∈S. From H5, Dhu∗,xni⟶0. On the other hand,(73)0≤Dgu∗,xni≤L⋅Dhu∗,xni,so Dgu∗,xni⟶0;u∗∈argminΨ. Indeed,(74)infΨ≤Ψu∗≤lim¯Ψxni=infΨ⇓infΨ=Ψu∗,which shows that ⟹u∗∈argminΨ. Then,(75)Dhniu∗,xni=Dhu∗,xni−λniDgu∗,xni⟶0.
SinceDhniu∗,xni⟶0 and u∗∈argminΨ, we have(76)Dhnu∗,xn⟶0.
We have(77)Dhu∗,xn=Dhnu∗,xn+λnDgu∗,xn≤Dhnu∗,xn+L⋅λ¯Dhu∗,xn,so 1−L⋅λ¯Dhu∗,xn≤Dhnu∗,xn; then,(78)Dhu∗,xn⟶0,And from H6, we have xn⟶u∗∈argminΨ.
The IBPG algorithm generates a sequence such thatΨxnn does not necessarily be nonincreasing; for this reason and for improvement of the global estimate in function values, we now propose ε−NoLips which is an inexact version of BPG with a relative error criterion. Let σ such that 0≤σ<1 be given as follows.
In what follows, we will derive a convergence rate result (Theorem4) for the ε−NoLips framework. First, we need to establish a few technical lemmas.In the following,xnn denotes the sequence generated by ε−NoLips.Lemma 7.
For everyu∈S¯, for all n∈N∗,(79)λnΨxn−Ψu≤An−1u−Anu−1−σ1−λ¯LDhxn,xn−1.Proof.
Sinceλn−λn−1Dgu,xn−1≥0, we have from (62),(80)λnΨxn−Ψu≤−Dhnxn,xn−1+An−1u−Anu+λnεn.From Algorithm 2, we have(81)λnΨxn−Ψu≤An−1u−Anu+σ−1Dhnxn,xn−1.
From the condition LC, we have(82)λnΨxn−Ψu≤An−1u−Anu−1−σ1−λ¯LDhxn,xn−1.Algorithm 1: Inexact Bregman Proximal Gradient (IBPG).
(1) Input:x0∈S∩ridomΨ
(2) Forn=1,2,… with εn>0, we obtain ∇hnxn−1−∇hnxn/λn∈∂εnΨxnRemark 3.
We now notice thatΨxnn is nonincreasing. Just replace u with xn−1 in (79).Lemma 8.
For everyn∈N∗ and x∗∈argminΨ, we have(83)tnΨxn−Ψ∗+λn−1tn1−σ1−λ¯LDhxn,xn−1≤tn−1Ψxn−1−Ψ∗+An−1x∗−Anx∗.Proof.
Replacingu by xn−1 in (79), and since Anxn−1≥0 and An−1xn−1=0, we have(84)tn−1Ψxn−Ψ∗+tn−1λn−11−σ1−λ¯LDhxn,xn−1≤tn−1Ψxn−1−Ψ∗.
Replacingu by x∗ in (79), we have(85)λnΨxn−Ψx∗+1−σ1−λ¯LDhxn,xn−1+≤An−1x∗−Anx∗.
Sincetn−1+λn=tn, by adding (84) and (85), we have (83).Lemma 9.
For everyk∈N∗(86)tkΨxk−Ψ∗+1−σ1−λ¯L∑n=1n=kλn−1tnDhxn,xn−1≤A0x∗−Akx∗.Proof.
This result is obtained by adding inequality (83) from 1 to k t0=λ0=0.We are now ready to state the convergence rate result for theε−NoLips framework. This result improves and completes the one given in the Proposition 7.Theorem 4.
For everyk∈N∗, the following statements hold: we pose ρk≔∑n=1n=kλn−1tn. Consider(87)aΨxk−Ψ∗≤Dhx∗,x0tk,(88)bγk≔min1≤n≤kDhxn,xn−1≤Dhx∗,x01−σ1−λ¯Lρk.Proof.
From (86) and since A0x∗=Dhx∗,x0λ0=0 and Akx∗≥0, we immediately have (87) and (88).Corollary 3.
Consider an instance of theε−NoLips framework with λn=λ for every n∈N∗. Then, for every k∈N∗, the following statements hold:(89)aΨxk−Ψ∗=O1k,(90)bγk=min1≤n≤kDhxn,xn−1=O1k2.Proof.
t
k
=
k
λ and (87) ⟹ (90):(91)ρk=kk+12≥k22.and (88) ⟹ (90).Remark 4.
(87) and (89) represent exactly the convergence rate established in [15, 22]. (90) is a new result not established in [15, 22]; this result shows that γk converges to zero at a rate of O1/k2.Theorem 5.
If∑λn=+∞, then(a)
Ψxn⟶infΨ(b)
xn⟶x∗∈argminΨProof.
Replacing u byx∗ in (81), we have(92)1−σDhnxn,xn−1≤An−1x∗−Anx∗.
By adding the inequality (92) from 1 to k, we have(93)1−σ∑n=1n=kDhnxn,xn−1≤A0x∗−Akx∗.Akx∗≥0, so ∑n=1∞Dhnxn,xn−1<+∞. From (69), we have(94)∑n=1∞λnεn<+∞.
SinceΨxnn is nonincreasing and (94), by applying the Theorem 3 (ii), we have the results of Theorem 5.


## 5. Application to Nonnegative Linear Inverse Problem

In Poisson inverse problems (e.g., [25, 26]), we are given a nonnegative observation matrix A∈R+m×d and a noisy measurement vector b∈R+m, and the goal is to reconstruct the signal x∈R+d such that Ax≃b. We can naturally adopt the distance DAx,b to measure the residuals between two nonnegative points, with(95)DAx,b=∑i=1mai,xlogai,xbi+bi−ai,x,where ai denotes the ith line of A.In this section, we propose an approach for solving the nonnegative linear inverse problem defined by(96)Pα:infαx1+DAx,b:x∈R+d,α>0.We take(97)fx≔αx1,gx≔DAx,bhx≔h1x=∑i=1dxilogxi.It is shown in [15] that the couple (g, h) verified a Lipschitz-like/Convexity Condition (LC) on R+d for any L such that(98)L≥max1≤j≤d∑i=1maij=max1≤j≤dAj1,where Aj denotes the jth column of A.Forλn≔λ,∀n, Theorem 3 is applicable and global warrant of Algorithm 1 convergence to an optimal solution of Pα.Algorithm 2:
ε
−NoLips.
(1)
Input:x0∈S∩ridomΨ
(2)
Chooseλn>0 and find xn∈S,σn∈0,σ and εn≥0 such that
∇
h
n
x
n
−
1
−
∇
h
n
x
n
/
λ
n
∈
∂
ε
n
Ψ
x
n
,
λ
n
ε
n
≤
σ
n
D
h
n
x
n
,
x
n
−
1
(3)
Setn⟵n+1 and go to step 1Givenxn∈R++d, the iteration(99)xn+1≃Tλxnamounts to solving the one-dimensional problem:Forj=1,…d,(100)xjn+1≃argminαt+γjt+1λtlogtxjn+xjn−t,t>0,where γj is the jth component of ∇gxn.


## 6. Conclusion

The proposed algorithms constitute a unified frame for the existing algorithms BPG, BP, and PG, by giving others, in particular, the inexact version of the interior method with Bregman distance studied in [24]. More precisely,(i)
Whenεn=0,∀n∈N∗, our algorithm is the NoLips studied in [15, 22](ii)
Wheng=0, our algorithm is the inexact version of Bregman Proximal (BP) studied in [19](iii)
Whenεn=0,∀n∈N∗, and g=0, our algorithm is the Bregman Proximal (BP) studied in [17, 21](iv)
Whenf=0, our algorithm is the inexact version of the interior method with Bregman distance studied in [24](v)
Whenf=0 and εn=0,∀n∈N∗, our algorithm is the interior method with Bregman distance studied in [24](vi)
Whenh=1/2⋅2, our algorithm is the proximal gradient method (PG) and its variants [4–14, 27]Our analysis is different and more simple than the one given in [15, 22] and allows to reduce some hypothesis, in particular, the supercoercivity of Ψ as well as the simultaneous convexity of f and g.



---

*Source: 1963980-2020-04-01.xml*