# Convergence of a Proximal Point Algorithm for Solving Minimization Problems

Authors: Abdelouahed Hamdi; M. A. Noor; A. A. Mukheimer
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We introduce and consider a proximal point algorithm for solving minimization problems using the technique of Güler. This proximal point algorithm is obtained by substituting the usual quadratic proximal term by a class of convex nonquadratic distance-like functions. It can be seen as an extragradient iterative scheme. We prove the convergence rate of this new proximal point method under mild assumptions. Furthermore, it is shown that this estimate rate is better than the available ones.


---

## Body

## 1. Introduction

The purpose of this paper is twofold. Firstly, it proposes an extension of the proximal point method introduced by Güler [1] in 1992, where the usual quadratic proximal term is substituted by a class of strictly convex distance-like functions, called Bregman functions. Secondly, it offers a general framework for the convergence analysis of the proximal point method of Güler. This framework is general enough to apply different classes of Bregman functions and still yield simple convergence proofs. The methods being analyzable in this context are called Güler's generalized proximal point algorithm, and are closely related to the Bregman proximal methods [2–5]. The analysis, we develop is different from the works in [4, 5], since our method is based on Güler's technique.


## 2. Preliminaries

To be more specific, we consider the minimization problem in the following form:(2.1)f*:=min⁡{f(x):x∈Rn},
where f:ℝn→ℝ∪{∞} is a closed proper convex function. To solve the problem (2.1), Teboulle [6], Chen and Teboulle [2, 6], Eckstein [4] and Burachik [3] proposed a general scheme using the Bregman proximal mappings of the type 𝒥c(2.2)Jc(y):=argmin⁡x∈Rn{f(x)+c-1Dh(x,y)},
where Dh is given by(2.3)Dh(x,y):=h(x)-h(y)-〈∇h(y),x-y〉,
with h is a strictly convex and continuously differentiable function.Throughout this paper,∥·∥ denotes the l2-norm and 〈·,·〉 denotes the Euclidean inner product in ℝn. Let G be a continuous single-valued mapping from ℝn into ℝn. The mapping G is Lipschitz continuous with Lipschitz constant L, if for all x,y∈ℝn,∥G(x)-G(y)∥≤L∥x-y∥. We denote also by ρ(x,X) the distance of x to the set X and it is given by ρ(x,X)=miny∈X∥x-y∥. Further notations and definitions used in this paper are standard in convex analysis and may be found in Rockafellar's book [7].This type of kernels was introduced first by [8] in 1967. The corresponding algorithm using these Bregman proximal mappings is called the Generalized Proximal Point Method (GPPM) and known also under the terminology of Bregman Proximal Methods. These proximal method solve (2.1) by considering a sequence of unconstrained minimization problems, which can be summed as follows.Algorithm 2.1.
(1) Initializex0∈ℝn:f(x0)<∞,c0>0.
(2) Compute the solutionxk+1 by the iterative scheme:
(2.4)xk+1:=argmin⁡x∈Rn{f(x)+ck-1Dh(x,xk)},
where {ck} is a sequence of positive numbers and Dh(·,·) is defined by (2.3).ForDh(x,y)=(1/2)∥x-y∥2, Algorithm 2.1 coincides with the classical proximal point algorithm(PPA) introduced by Moreau [9] and Martinet [10].Under mild assumptions on the data of (2.1) ergodic convergence was proved [2, 5] when σn=∑k=1nck→∞ with the following global rate of convergence estimate:(2.5)f(xn)-f(x)=O(1σn),∀x∈Rn.
Our purpose in this paper is to propose an algorithm of the same type as Algorithm 2.1 which has better convergence rate. To this goal, we propose to combine Güler's scheme [1] and the Bregman proximal method. The main difference concerns the generation of an additional sequence {yk}⊂ℝn in the unconstrained minimization (2.4) in such a way: (2.6)xk+1:=argmin⁡x∈Rn{f(x)+ck-1Dh(x,yk)}.
We show (see Section 4) that this new proximal method possesses the following rate estimate(2.7)f(xn)-f(x)=O(1γn2),∀x,γn=∑k=1nck,
which is faster than (2.5). Further, the convergence in terms of the objective values occurs when γn→∞ which is weaker than σn→∞.We briefly recall here the notion of Bregman functions called alsoD-functions introduced by Brègman ([8], 1967), developed and used in the proximal theory by [4, 6, 11–13]. Let S be an open subset of ℝn and let h:S¯→ℝ be a finite-valued continuously differentiable function on S be and let Dh defined by(2.8)Dh(x,y):=h(x)-h(y)-〈∇h(y),x-y〉,x∈S¯,y∈S.Definition 2.2.
h is called a Bregman function with zoneS or a D-function if:(a)
h is continuously differentiable on S and continuous on S¯,(b)
h is strictly convex on S¯,(c)
for everyλ∈ℝ, the partial level sets L1(y,λ)={x∈S¯:Dh(x,y)≤λ} and L2(x,λ)={y∈S:Dh(x,y)≤λ} are bounded for every y∈S and x∈S¯, respectively,(d)
if{yk}∈S is a convergent sequence with limit y*, then Dh(y*,yk)→0,(e)
if{xk} and {yk} are sequences such that yk→y*∈S¯, {xk} is bounded and Dh(xk,yk)→0, then xk→y*.From the above definition, we extract the following properties (see, for instance, [6, 13]).Lemma 2.3.
Leth be a Bregman function with zone S. Then,(i)
Dh(x,x)=0 and Dh(x,y)≥0 for x∈S¯ and y∈S,(ii)
for alla, b∈S and c∈S¯,
(2.9)Dh(c,a)+Dh(a,b)-Dh(c,b)=〈∇h(b)-∇h(a),c-a〉,(iii)
for alla,b∈S,
(2.10)Dh(a,b)+Dh(b,a)≤‖∇h(a)-∇h(b)‖×‖a-b‖.(iv)
for allx∈Sh*(∇h(x))=〈x,∇h(x)〉-h(x),(v)
let{xk}∈S such that xk→x*∈S, then Dh(x*,xk)→0 and Dh(xk,x*)→0.Lemma 2.4.
(i) Letg:ℝn→ℝ be a strictly convex function such that
(2.11)g∈C2(Rn),lim⁡‖x‖→∞g(x)‖x‖=+∞,
then g is a Bregman function.
(ii) Ifg is a Bregman function, then g(x)+c⊤x+d for any c∈ℝn,d∈ℝ, also is a Bregman function.Remark 2.5.
Dh(·,·) cannot be considered as a distance because of the lack of the triangle inequality and the symmetry property. Dh(·,·) is usually called an entropy distance.The paper is organized as follows. In Section3, we recall briefly the proximal point method of Güler. Section 4 will be devoted to the presentation and convergence analysis of the proposed algorithm. Finite convergence is shown in Section 5. Finally, in Section 6 we present an application of this method to solve variational inequalities problem.


## 3. Extragradient Algorithm

In 1992, Güler [1] has developed a new proximal point approach similar to the classical one (PPA) based on the idea stated by Nesterov [14].Güler's proximal point algorithm (GPPA) can be summed up as follows.Algorithm 3.1.
(i) Initializex0∈ℝn:f(x0)<∞,c0>0,A>0.
Defineν0:=x0,A0:=A,k=0.
(ii) Computeαk=((Akck)2+4Akck-Akck)/2.
(iii) Compute the solutionxk+1 by the iterative scheme:
(3.1)yk=(1-αk)xk+αkνk,xk+1:=argmin⁡z∈Rn{f(z)+(2ck)-1‖z-yk‖2},νk+1=νk-xk+1-ykαk,Ak+1=(1-αk)Ak.For the convergence analysis, see Güler [1].Remark 3.2.
The GPPA can be seen as a suitable conjugate gradient type modification of the PPA of Rockafellar applied to (2.1).


## 4. Main Result

### 4.1. Introduction

The method that we are proposing is a modification of Güler's new proximal point approach GPPA discussed in Section3 and can be considered as a nonlinear (or a nonquadratic) version of GPPA with Bregman kernels. In this paper it is shown that this method, which we call BGPPA possesses the strong convergence results obtained by Güler [1] and therefore this new scheme provides faster (global) convergence rates than the classical Bregman proximal point methods (cf. [2, 4–6, 11, 13, 15]). In this paper, we propose the following algorithm generalizing Güler's proximal point algorithm and summed up as follows.Algorithm 4.1.
(i) Initialize:x0∈ℝn:f(x0)<∞,c0>0,A>0.
Defineν0:=x0,A0:=A,k=0
(ii) Compute:αk such that αk2=(1-αk)Akck/LL*.
(iii) Compute the solutionxk+1 by the iterative scheme:
(4.1)yk=(1-αk)xk+αkνk,xk+1:=argmin⁡z∈Rn{f(z)+(ck)-1Dh(z,yk)},νk+1=∇h*(∇h(νk)+xk+1-ykαk),Ak+1=(1-αk)Ak.In this section we develop convergence results for the generalized Güler's proximal point algorithm GGPPA presented in Section4.2. Our analysis is basically based on the following lemma.Lemma 4.2 ([1, page 654]).
One has(4.2)∏j=0k-1(1-αj)≤1[1+(A/2)∑j=0k-1cj]2
for all αj∈[0,1[ and A>0.Theorem 4.3.
For allx∈𝒮¯ such that f(x)<∞, one has the following convergence rate estimate:
(4.3)f(xk)-f(x)≤4(f(x0)-f(x)+ADh(x,x0))A(∑j=0k-1cj)2.Proof.
Using the fact thatϕ0(x):=f(x0)+ADh(x,x0), x0∈𝒮, and Lemma 4.2, we obtain
(4.4)f(xk)-f(x)≤∏j=0k-1(1-αj)(ϕ0(x)-f(x))≤1[1+(A/2)∑j=0k-1cj]2(f(x0)+ADh(x,x0)-f(x)).
Since [1+(A/2)∑j=0k-1cj]2≥(∑j=0k-1cj)2A/4, then (4.3) holds.Theorem 4.4.
Consider the sequence{xk} generated by GGPPA and let x* be a minimizer of f(x) on ℝn. Assume that(1)
h is a Bregman function with zone 𝒮 such that Dom(∂f)¯⊂𝒮,(2)
Im(∇h)=ℝn or Im(∇h) is open,(3)
∇h is Lipschitz continuous with coefficient L,then(a)
for allx0∈Dom(∇h), the sequence {xk} is well defined,(b)
the GGPPA possesses this following convergence rate estimate:(4.5)f(xk)-f*≤4(f(x0)-f*+ρ(x0,X*)2(AL)/2)A(∑j=0k-1cj)2,(c)
f(xk)-f*→0, when ∑k=0∞ck=∞,(d)
(4.6)f(xk)-f*=O(1k2)
if ck≥c>0.Proof.
(a) Follows from [8, Theorem 4].
(b) Uses assumption (2.3) in the following manner
(4.7)Dh(x,x0)=h(x)-h(x0)-〈∇h(x0),x-x0〉≤|∫01[∇h(x0+t(x-x0))-∇h(x0)]‖x-x0‖dt|≤L‖x-x0‖2∫01tdt≤L2‖x-x0‖2,
and by taking x=x* in (4.3), then we have
(4.8)f(xk)-f*≤4(f(x0)-f*+(AL/2)‖x*-x0‖2)A(∑j=0k-1cj)2.
Since x* is arbitrary, then (4.5) holds.
(c) Is obvious.
(d) It suffices to observe that ifck≥c>0, we have
(4.9)(∑j=0k-1cj)2≥(∑j=0k-1c)2=ck2.


### 4.2. Finite Convergence

Note that thefinite convergenceproperty was established for the classical proximal point algorithm in the case of sharp minima, see, for example, [16]. Recently, Kiwiel [5] has extended this property to his generalized Bregman proximal method (BPM). In the following theorem we prove that Algorithm 3.1 has this property. Our proof is based on Kiwiel's one [5, Theorem 6.1 page 1151].Definition 4.5.
A closed proper convex functionf:ℝn→ℝ is said to have a sharp minimum on ℝn if and only if there exists τ>0 such that
(4.10)f(x)≥min⁡Rnf+τmin⁡z∈Argminf‖x-z‖∀x.Theorem 4.6.
Under the same hypothesis as in Theorem4.4 and by considering GGPPA with f having a sharp minimum on ℝn and ck being bounded, then there exists k such that 0∈∂f(xk) and xk∈X*.Proof.
Straightforward, using Theorem4.4 and [5, Theorem 6.1, page 1151].


## 4.1. Introduction

The method that we are proposing is a modification of Güler's new proximal point approach GPPA discussed in Section3 and can be considered as a nonlinear (or a nonquadratic) version of GPPA with Bregman kernels. In this paper it is shown that this method, which we call BGPPA possesses the strong convergence results obtained by Güler [1] and therefore this new scheme provides faster (global) convergence rates than the classical Bregman proximal point methods (cf. [2, 4–6, 11, 13, 15]). In this paper, we propose the following algorithm generalizing Güler's proximal point algorithm and summed up as follows.Algorithm 4.1.
(i) Initialize:x0∈ℝn:f(x0)<∞,c0>0,A>0.
Defineν0:=x0,A0:=A,k=0
(ii) Compute:αk such that αk2=(1-αk)Akck/LL*.
(iii) Compute the solutionxk+1 by the iterative scheme:
(4.1)yk=(1-αk)xk+αkνk,xk+1:=argmin⁡z∈Rn{f(z)+(ck)-1Dh(z,yk)},νk+1=∇h*(∇h(νk)+xk+1-ykαk),Ak+1=(1-αk)Ak.In this section we develop convergence results for the generalized Güler's proximal point algorithm GGPPA presented in Section4.2. Our analysis is basically based on the following lemma.Lemma 4.2 ([1, page 654]).
One has(4.2)∏j=0k-1(1-αj)≤1[1+(A/2)∑j=0k-1cj]2
for all αj∈[0,1[ and A>0.Theorem 4.3.
For allx∈𝒮¯ such that f(x)<∞, one has the following convergence rate estimate:
(4.3)f(xk)-f(x)≤4(f(x0)-f(x)+ADh(x,x0))A(∑j=0k-1cj)2.Proof.
Using the fact thatϕ0(x):=f(x0)+ADh(x,x0), x0∈𝒮, and Lemma 4.2, we obtain
(4.4)f(xk)-f(x)≤∏j=0k-1(1-αj)(ϕ0(x)-f(x))≤1[1+(A/2)∑j=0k-1cj]2(f(x0)+ADh(x,x0)-f(x)).
Since [1+(A/2)∑j=0k-1cj]2≥(∑j=0k-1cj)2A/4, then (4.3) holds.Theorem 4.4.
Consider the sequence{xk} generated by GGPPA and let x* be a minimizer of f(x) on ℝn. Assume that(1)
h is a Bregman function with zone 𝒮 such that Dom(∂f)¯⊂𝒮,(2)
Im(∇h)=ℝn or Im(∇h) is open,(3)
∇h is Lipschitz continuous with coefficient L,then(a)
for allx0∈Dom(∇h), the sequence {xk} is well defined,(b)
the GGPPA possesses this following convergence rate estimate:(4.5)f(xk)-f*≤4(f(x0)-f*+ρ(x0,X*)2(AL)/2)A(∑j=0k-1cj)2,(c)
f(xk)-f*→0, when ∑k=0∞ck=∞,(d)
(4.6)f(xk)-f*=O(1k2)
if ck≥c>0.Proof.
(a) Follows from [8, Theorem 4].
(b) Uses assumption (2.3) in the following manner
(4.7)Dh(x,x0)=h(x)-h(x0)-〈∇h(x0),x-x0〉≤|∫01[∇h(x0+t(x-x0))-∇h(x0)]‖x-x0‖dt|≤L‖x-x0‖2∫01tdt≤L2‖x-x0‖2,
and by taking x=x* in (4.3), then we have
(4.8)f(xk)-f*≤4(f(x0)-f*+(AL/2)‖x*-x0‖2)A(∑j=0k-1cj)2.
Since x* is arbitrary, then (4.5) holds.
(c) Is obvious.
(d) It suffices to observe that ifck≥c>0, we have
(4.9)(∑j=0k-1cj)2≥(∑j=0k-1c)2=ck2.


## 4.2. Finite Convergence

Note that thefinite convergenceproperty was established for the classical proximal point algorithm in the case of sharp minima, see, for example, [16]. Recently, Kiwiel [5] has extended this property to his generalized Bregman proximal method (BPM). In the following theorem we prove that Algorithm 3.1 has this property. Our proof is based on Kiwiel's one [5, Theorem 6.1 page 1151].Definition 4.5.
A closed proper convex functionf:ℝn→ℝ is said to have a sharp minimum on ℝn if and only if there exists τ>0 such that
(4.10)f(x)≥min⁡Rnf+τmin⁡z∈Argminf‖x-z‖∀x.Theorem 4.6.
Under the same hypothesis as in Theorem4.4 and by considering GGPPA with f having a sharp minimum on ℝn and ck being bounded, then there exists k such that 0∈∂f(xk) and xk∈X*.Proof.
Straightforward, using Theorem4.4 and [5, Theorem 6.1, page 1151].


## 5. Convergence Rate of GGPPA

If{xk} is a sequence of points, one forms the sequence {zn} of weighted averages given by(5.1)zn=∑k=1nckσnxk,σn=∑k=1nck,
where ck>0. If the sequence {zn} converges, then {xk}k is said to converge ergodically.Theorem 5.1.
GGPPA possesses the following convergence rate:(5.2)f(xn)-f*=o(1σn),
that is, σn(f(xn)-f*)→0. Furthermore, if ck≥c>0, then one has
(5.3)f(xn)-f*=o(1n).Proof.
Letx* be a minimizer of f. For brevity, we denote Wk=f(xk)-f*,Vk=f(yk)-f* and Δ=∇h(yk)-∇h(xk+1). At optimality in the unconstrained minimization in GGPPA, we can write
(5.4)Δck∈∂f(xk+1),
and by the convexity of f, we have
(5.5)ck(f(xk+1)-f(x))≤〈xk+1-x,Δ〉.
Setting x=xk in (5.5), we obtain
(5.6)ck(Wk-Wk+1)≥〈xk-xk+1,Δ〉,
and for x=yk, we have
(5.7)ck(Vk-Wk+1)≥〈yk-xk+1,Δ〉.
Or again, if we set x=x* in (5.5), and using the Cauchy-Schwartz inequality, we obtain
(5.8)ck(f(xk+1)-f*)≤〈xk+1-x*,Δ〉,
that is,
(5.9)ckWk+1≤〈xk+1-yk,Δ〉+〈yk-x*,Δ〉.
Since h is convex, 〈xk+1-yk,Δ〉≤0. Then we can write
(5.10)ckWk+1≤〈yk-x*,Δ〉,
that is,
(5.11)ck2Wk+12≤‖yk-x*‖2‖Δ‖2.
Using the relation ∥Δ∥2≤L〈Δ,yk-xk+1〉 and the inequality (5.7), we get the relation
(5.12)ck2Wk+12≤Lck(Vk-Wk+1)‖yk-x*‖2.
For short we denote Mk=∥yk-x*∥ thus, (5.12) becomes
(5.13)ckWk+12+LMk2Wk+1≤LMk2Vk.
Then by dividing both terms by LMk2>0, we get
(5.14)Wk+1(ckLMk2Wk+1+1)≤Vk.
Since the left-side term is positive, then
(5.15)Vk-1≤Wk+1-1(ckLMk2Wk+1+1)-1.
Now following Güler [17, page 410], we use the fact that (1+x)-1≤1-2x/3,forallx∈[0,1/2]. To apply this inequality, it suffices to show that (ck/LMk2)Wk+1 is less than or equal to 1/2. This can be deduced from this relation (see Lemma 2.3 (ii)):
(5.16)ckWk+1≤〈Δ,xk+1-x*〉=Dh(x*,yk)-Dh(x*,xk+1)-Dh(xk+1,yk).
Indeed, since Dh(·,·)≥0, then (the proof of this next inequality can be found in the proof of Theorem 4.4-(b))
(5.17)ckWk+1≤Dh(x*,yk)≤L2‖x*-yk‖2=LMk22.
Therefore, 0<(ck/LMk2)Wk+1≤1/2 and we obtain
(5.18)0≤Vk-1≤Wk+1-1(1-2ck3LMk2Wk+1).
To continue the proof, we will separate some different cases. Case 1.
Iff(xk+1)≤f(yk)≤f(xk)̲. Then Wk+1≤Vk≤Wk and we have Vk-1≥Wk-1. Thus, (5.18) becomes
(5.19)Wk-1≤Vk-1≤Wk+1-1(1-2ck3LMk2Wk+1),
and by summation from k=0 to k=n, we get
(5.20)0≤∑k=0nWk-1≤∑k=0nWk+1-1-∑k=0n2ck3LMk2,
that is,
(5.21)0≤W0-1≤Wn+1-1-∑k=0n2ck3LMk2.
Then,
(5.22)0≤Wn+1≤3L2∑k=0nck‖yk-x*‖-2.
Since x* is an arbitrary solution, we can write
(5.23)0≤Wn+1≤3L2∑k=0nckρ(yk,X*)-2,
and by multiplying both terms by σn+1=∑k=0nck, we obtain
(5.24)0≤σn+1Wn+1≤3L2∑k=0n(ck/σn+1)ρ(yk,X*)-2.
Since yk and xk+1 converge to the same point (indeed, we can see it via the formula giving νk+1 in the algorithm GGPPA and ρ(xk+1,X*)→0, then ρ(xk+1,X*)-2→∞; hence, we obtain
(5.25)0≤σn+1(f(xn+1)-f*)⟶0,
which implies
(5.26)f(xn+1)-f*=o(1σn+1),
that is,
(5.27)f(xn)-f*=o(1σn).Case 2.
Iff(xk+1)≤f(xk)≤f(yk).̲ Then Wk+1≤Wk≤Vk and we have Wk+1-1≥Wk-1 therefore; for n≥k we have Wn+1-1≥Wk-1. Thus, using inequality (5.18), we write
(5.28)Wn+1-1≥Wk+1-1≥2ck3LMk2,
and by summation from k=0 to k=n, we get
(5.29)(n+1)Wn+1-1≥∑k=0n2ck3LMk2.
Then,
(5.30)0≤Wn+1≤3L(n+1)2∑k=0nck‖yk-x*‖-2.
Since x* is an arbitrary solution, we can write
(5.31)0≤Wn+1≤3L(n+1)2∑k=0nckρ(yk,X*)-2,
and by multiplying both terms by σn+1=∑k=0nck, we obtain
(5.32)0≤σn+1Wn+1≤3L2∑k=0n(ck/(n+1)σn+1)ρ(yk,X*)-2.
Since yk and xk+1 converge to the same point (indeed, we can see it via the formula giving νk+1 in the algorithm GGPPA and ρ(xk+1,X*)→0, then ρ(xk+1,X*)-2→∞; hence, we obtain
(5.33)0≤σn+1(f(xn+1)-f*)⟶0,
which implies,
(5.34)f(xn+1)-f*=o(1σn+1),
that is,
(5.35)f(xn)-f*=o(1σn).Case 3.
Iff(xk)≤f(xk+1)≤f(yk)̲. In this case we observe that sequence {f(xk)}is increasing, which may imply a divergence of the approach.Sincef is convex, then the following convergence rate estimate can be derived directly.Corollary 5.2.
If one assumes thatck≥c>0 for all k, then
(5.36)f(zn)-f*=o(1n).


## 6. Conclusion

We have introduced an extragradient method to minimize convex problems. The algorithm is based on a generalization of the technique originally proposed by Nesterov [14] and readapted by Güler in [1, 17], where the usual quadratic proximal term was substituted by a class of convex nonquadratic distance-like functions. The new algorithm has a better theoretical convergence rate compared to the available ones. This motivates naturally the study of the numerical efficiency of the new algorithm and its application to solve variational inequality problems [18, 19]. Also, further efforts are needed to consider the given study for nonconvex situations and apply it to solve nonconvex equilibrium problems [20].



---

*Source: 142862-2012-04-17.xml*