# A Regularized Gradient Projection Method for the Minimization Problem

Authors: Yonghong Yao; Shin Min Kang; Wu Jigang; Pei-Xia Yang
Journal: Journal of Applied Mathematics
 (2012)

---

## Abstract

We investigate the following regularized gradient projection
algorithmxn+1=Pc(I−γn(∇f+αnI))xn, n≥0. Under some different control conditions, we prove that this gradient projection algorithm
strongly converges to the minimum norm solution of the minimization problem minx∈Cf(x).


---

## Body

## 1. Introduction

LetC be a nonempty closed and convex subset of a real Hilbert space H. Let f:H→R be a real-valued convex function.Consider the following constrained convex minimization problem:(1.1)min⁡x∈Cf(x).
Assume that (1.1) is consistent, that is, it has a solution and we use Ω to denote its solution set. If f is Fréchet differentiable, then x*∈C solves (1.1) if and only if x*∈C satisfies the following optimality condition:(1.2)〈∇f(x*),x-x*〉≥0,∀x∈C,
where ∇f denotes the gradient of f. Note that (1.2) can be rewritten as(1.3)〈x*-(x*-∇f(x*)),x-x*〉≥0,∀x∈C.
This shows that the minimization (1.1) is equivalent to the fixed point problem(1.4)PC(x*-γ∇f(x*))=x*,
where γ>0 is any constant and PC is the nearest point projection from H onto C. By using this relationship, the gradient-projection algorithm is usually applied to solve the minimization problem (1.1). This algorithm generates a sequence {xn} through the recursion:(1.5)xn+1=PC(xn-γn∇f(xn)),n≥0,
where the initial guess x0∈C is chosen arbitrarily and {γn} is a sequence of stepsizes which may be chosen in different ways. The gradient-projection algorithm (1.5) is a powerful tool for solving constrained convex optimization problems and has well been studied in the case of constant stepsizes γn=γ for all n. The reader can refer to [1–9] and the references therein. It is known [3] that if f has a Lipschitz continuous and strongly monotone gradient, then the sequence {xn} can be strongly convergent to a minimizer of f in C. If the gradient of f is only assumed to be Lipschitz continuous, then {xn} can only be weakly convergent if H is infinite dimensional. In order to get the strong convergence, Xu [10] studied the following regularized method:(1.6)xn+1=PC(I-γn(∇f+αnI))xn,n≥0,
where the sequences {θn}⊂(0,1) and {γn}⊂(0,∞) satisfy the following conditions:(1)
0<γn≤αn/(L+αn)2 for all n;(2)
limn→∞αn=0;(3)
∑n=0∞αnγn=∞;(4)
limn→∞(|γn-γn-1|+|αnγn-αn-1γn-1|/(αnγn)2)=0.Xu [10] proved that the sequence {xn} converges strongly to a minimizer of (1.1).Motivated by Xu’s work, in the present paper, we further investigate the gradient projection method (1.6). Under some different control conditions, we prove that this gradient projection algorithm strongly converges to the minimum norm solution of the minimization problem (1.1).


## 2. Preliminaries

LetC be a nonempty closed convex subset of a real Hilbert space H. A mapping T:C→C is called nonexpansive if(2.1)‖Tx-Ty‖≤‖x-y‖,∀x,y∈C.
We will use Fix(T) to denote the set of fixed points of T, that is, Fix(T)={x∈C:x=Tx}. A mapping T:C→C is said to be ν-inverse strongly monotone (ν-ism), if there exists a constant ν>0 such that(2.2)〈x-y,Tx-Ty〉≥ν‖Tx-Ty‖2,∀x,y∈C.
Recall that the (nearest point or metric) projection from H onto C, denoted PC, assigns, to each x∈H, the unique point PC(x)∈C with the property(2.3)‖x-PC(x)‖=inf⁡{‖x-y‖:y∈C}.
It is well known that the metric projection PC of H onto C has the following basic properties:(a)
∥PC(x)-PC(y)∥≤∥x-y∥ for all x,y∈H;(b)
〈x-y,PC(x)-PC(y)〉≥∥PC(x)-PC(y)∥2 for every x,y∈H;(c)
〈x-PC(x),y-PC(x)〉≤0 for all x∈H,y∈C.Next we adopt the following notation:(i)
xn→x means that xn converges strongly to x;(ii)
xn⇀x means that xn converges weakly to x;(iii)
ωw(xn):={x:∃xnj⇀x} is the weak ω-limit set of the sequence {xn}.Lemma 2.1 (see [11]).
GivenT:H→H and letting V=I-T be the complement of T, given also S:H→H, (a)
T is nonexpansive if and only if V is (1/2)-ism;(b)
ifS is ν-ism, then, for γ>0, γS is (ν/γ)-ism;(c)
S is averaged if and only if the complement I-S is ν-ism for some ν>1/2.Lemma 2.2 (see [12], (demiclosedness principle)).
LetC be a closed and convex subset of a Hilbert space  H, and let  T:C→C be a nonexpansive mapping with  Fix(T)≠∅. If  {xn} is a sequence in  C weakly converging to  x and if  {(I-T)xn} converges strongly to  y, then
(2.4)(I-T)x=y.
In particular, if y=0, then x∈Fix(T).Lemma 2.3 (see [13]).
Let{xn} and  {yn} be bounded sequences in a Banach space  X, and let  {βn} be a sequence in  [0,1] with
(2.5)0<liminf⁡n→∞βn≤limsup⁡n→∞βn<1.
Suppose that
(2.6)xn+1=(1-βn)yn+βnxn
for all n≥0 and
(2.7)limsup⁡n→∞(‖yn+1-yn‖-‖xn+1-xn‖)≤0.
Then, limn→∞∥yn-xn∥=0.Lemma 2.4 (see [14]).
Assume that{an} is a sequence of nonnegative real numbers such that
(2.8)an+1≤(1-γn)an+δn,
where {γn} is a sequence in (0,1) and {δn} is a sequence such that(1)
∑n=1∞γn=∞;(2)
limsupn→∞(δn/γn)≤0 or ∑n=1∞|δn|<∞. Then, limn→∞an=0.


## 3. Main Result

In this section, we will state and prove our main result.Theorem 3.1.
LetC be a nonempty closed convex subset of a real Hilbert space  H. Let  f:C→R be a real-valued Fréchet differentiable convex function. Assume  Ω≠∅. Assume that the gradient  ∇f is  L-Lipschitzian. Let  {xn} be a sequence generated by the following hybrid gradient projection algorithm:
(3.1)xn+1=PC(I-γn(∇f+αnI))xn,n≥0,
where the sequences {θn}⊂(0,1) and {γn}⊂(0,2/(L+2αn)) satisfy the following conditions:(1)
limn→∞αn=0 and ∑n=0∞αn=∞;(2)
0<liminfn→∞γn≤limsupn→∞γn<2/L and limn→∞(γn+1-γn)=0. Then, the sequence {xn} generated by (3.1) converges to a minimizer x̂ of (1.1).Proof.
Note that the Lipschitz condition implies that the gradient∇f is (1/L)-ism [10]. Then, we have
(3.2)‖PC(I-γ(∇f+αI))x-PC(I-γ(∇f+αI))y‖2≤‖(I-γ(∇f+αI))x-(I-γ(∇f+αI))y‖2=‖(1-αγ)(x-y)-γ(∇f(x)-∇f(y))‖2=(1-αγ)2‖x-y‖2-2(1-αγ)γ〈x-y,∇f(x)-∇f(y)〉+γ2‖∇f(x)-∇f(y)‖2≤(1-αγ)2‖x-y‖2-2(1-αγ)γ1L‖∇f(x)-∇f(y)‖2+γ2‖∇f(x)-∇f(y)‖2.
If γ∈[0,2/(L+2α)], then 2(1-αγ)γ(1/L)≥γ2. It follows that
(3.3)‖PC(I-γ(∇f+αI))x-PC(I-γ(∇f+αI))y‖2≤(1-αγ)2‖x-y‖2.
Thus,
(3.4)‖PC(I-γ(∇f+αI))x-PC(I-γ(∇f+αI))y‖≤(1-αγ)‖x-y‖,
for all x,y∈C.
Take anyx*∈S. Since x*∈C solves the minimization problem (1.1) if and only if x* solves the fixed-point equation x*=PC(I-γ∇f)x* for any fixed positive number γ, so we have x*=PC(I-γn∇f)x* for all n≥0. From (3.1) and (3.4), we get
(3.5)‖xn+1-x*‖=‖PC(I-γn(∇f+αnI))xn-PC(I-γn∇f)x*‖=‖PC(I-γn(∇f+αnI))xn-PC(I-γn(∇f+αnI))x*‖+‖PC(I-γn(∇f+αnI))x*-PC(I-γn∇f)x*‖≤(1-αnγn)‖xn-x*‖+αnγn‖x*‖≤max⁡{‖xn-x*‖,‖x*‖}.
Thus, we deduce by induction that
(3.6)‖xn-x*‖≤max⁡{‖x0-x*‖,‖x*‖}.
This indicates that the sequence {xn} is bounded.
Since the gradient∇f is (1/L)-ism, γ∇f is (1/γL)-ism. So by Lemma 2.1, I-γn∇f is (γnL/2)-averaged; that is, I-γn∇f=(1-(γnL/2))I+(γnL/2)T for some nonexpansive mapping T. Since PC is (1/2)-averaged, PC=(I+S)/2 for some nonexpansive mapping S. Then, we can rewrite xn+1 as
(3.7)xn+1=12(I-γn(∇f+αnI))xn+12S(I-γn(∇f+αnI))xn=12(xn-γn∇f(xn))-12γnαnxn+12S(I-γn(∇f+αnI))xn=2-γnL4xn+γnL4Txn-12γnαnxn+12S(I-γn(∇f+αnI))xn=2-γnL4xn+2+γnL4yn,
where
(3.8)yn=42+γnL(γnL4Txn-12γnαnxn+12S(I-γn(∇f+αnI))xn).
It follows that
(3.9)∥yn+1-yn∥=‖42+γn+1L(γn+1L4Txn+1-12γn+1αn+1xn+1+12S(I-γn+1(∇f+αn+1I))xn+1)-42+γnL(γnL4Txn-12γnαnxn+12S(I-γn(∇f+αnI))xn)‖≤42+γn+1L‖(γn+1L4Txn+1-12γn+1αn+1xn+1+12S(I-γn+1(∇f+αn+1I))xn+1)-(γnL4Txn-12γnαnxn+12S(I-γn(∇f+αnI))xn)‖+|42+γn+1L-42+γnL|‖γnL4Txn-12γnαnxn+12S(I-γn(∇f+αnI))xn‖≤42+γn+1L(‖γn+1L4Txn+1-γnL4Txn‖+12γn+1αn+1‖xn+1‖+12γnαn‖xn‖)+22+γn+1L‖(I-γn+1(∇f+αn+1I))xn+1-(I-γn(∇f+αnI))xn‖+|42+γn+1L-42+γnL|‖γnL4Txn-12γnαnxn+12S(I-γn(∇f+αnI))xn‖.
Now we choose a constant M such that
(3.10)sup⁡n{‖xn‖,L‖Txn‖,‖∇f(xn)‖,‖γnL4Txn-12γnαnxn+12S(I-γn(∇f+αnI))xn‖}≤M.
We have the following estimates:
(3.11)‖γn+1L4Txn+1-γnL4Txn‖=‖γn+1L4(Txn+1-Txn)+(γn+1L4-γnL4)Txn‖≤γn+1L4‖Txn+1-Txn‖+|γn+1-γn|‖Txn‖4≤γn+1L4‖xn+1-xn‖+|γn+1-γn|M,‖(I-γn+1(∇f+αn+1I))xn+1-(I-γn(∇f+αnI))xn‖≤‖(I-γn+1∇f)xn+1-(I-γn+1∇f)xn‖+|γn+1-γn|‖∇f(xn)‖+γn+1αn+1∥xn+1∥+γnαn∥xn∥≤‖xn+1-xn‖+(|γn+1-γn|+γn+1αn+1+γnαn)M.
Thus, we deduce
(3.12)‖yn+1-yn‖≤42+γn+1L(γn+1L4‖xn+1-xn‖+|γn+1-γn|M+(γn+1αn+1+γnαn)M)+22+γn+1L(‖xn+1-xn‖+(|γn+1-γn|+γn+1αn+1+γnαn)M)+|42+γn+1L-42+γnL|M≤‖xn+1-xn‖+62+γn+1L(|γn+1-γn|+γn+1αn+1+γnαn)M+4L(2+γn+1L)(2+γnL)|γn+1-γn|M.
Note that αn→0 and γn+1-γn→0. Hence, by Lemma 2.3, we get
(3.13)limsup⁡n→∞(‖yn+1-yn‖-‖xn+1-xn‖)≤0.
It follows that
(3.14)lim⁡n→∞‖yn-xn‖=0.
Consequently,
(3.15)lim⁡n→∞∥xn+1-xn∥=lim⁡n→∞2+γnL4∥yn-xn∥=0.
Now we show that the weak limit set ωw(xn)⊂Ω. Choose any x̃∈ωw(xn). Since {xn} is bounded, there must exist a subsequence {xnj} of {xn} such that xnj⇀x̃. At the same time, the real number sequence {γnj} is bounded. Thus, there exists a subsequence {γnji} of {γnj} which converges to γ. Without loss of generality, we may assume that γnj→γ. Note that 0<liminfn→∞γn≤limsupn→∞γn<2/L. So, γ∈(0,2/L); that is, γnj→γ∈(0,2/L) as j→∞. Next, we only need to show that x̃∈Ω. First, from (3.15) we have that ∥xnj+1-xnj∥→0. Then, we have
(3.16)‖xnj-PC(I-γ∇f)xnj‖≤‖xnj-xnj+1‖+‖xnj+1-PC(I-γnj∇f)xnj‖+‖PC(I-γnj∇f)xnj-PC(I-γ∇f)xnj‖=‖PC(I-γnj(∇f+αnjI))xnj-PC(I-γnj∇f)xnj‖+‖PC(I-γnj∇f)xnj-PC(I-γ∇f)xnj‖+‖xnj-xnj+1‖≤αnjγnj‖xnj‖+|γnj-γ|‖∇f(xnj)‖+‖xnj-xnj+1‖⟶0.
Since γ∈(0,2/L), PC(I-γ∇f) is nonexpansive. It then follows from Lemma 2.2 (demiclosedness principle) that x̃∈Fix(PC(I-γ∇f)). Hence, x̃∈Ω because of Ω=Fix(PC(I-γ∇f)). So, ωw(xn)⊂Ω.
Finally, we prove thatxn→x̂, where x̂ is the minimum norm solution of (1.1). First, we show that limsupn→∞〈x̂,xn-x̂〉≥0. Observe that there exists a subsequence {xnj} of {xn} satisfying
(3.17)limsup⁡n→∞〈x̂,xn-x̂〉=lim⁡j→∞〈x̂,xnj-x̂〉.
Since {xnj} is bounded, there exists a subsequence {xnji} of {xnj} such that xnji⇀x̃. Without loss of generality, we assume that xnj⇀x̃. Then, we obtain
(3.18)limsup⁡n→∞〈x̂,xn-x̂〉=lim⁡j→∞〈x̂,xnj-x̂〉=〈x̂,x̃-x̂〉≥0.
Since γn<2/(L+2αn), γn/(1-αnγn)<2/L. So, I-(γn/(1-αnγn))∇f is nonexpansive. By using the property (b) of PC, we have
(3.19)‖xn+1-x̂‖2=‖PC(I-γn(∇f+αnI))xn-PC(x̂-γn∇f(x̂))‖2≤〈(I-γn(∇f+αnI))xn-(x̂-γn∇f(x̂)),xn+1-x̂〉=(1-αnγn)〈(I-γn1-αnγn∇f)xn-(I-γn1-αnγn∇f)x̂,xn+1-x̂〉-αnγn〈x̂,xn+1-x̂〉≤(1-αnγn)‖(I-γn1-αnγn∇f)xn-(I-γn1-αnγn∇f)x̂‖‖xn+1-x̂‖-αnγn〈x̂,xn+1-x̂〉≤(1-αnγn)‖xn-x̂‖‖xn+1-x̂‖-αnγn〈x̂,xn+1-x̂〉≤1-αnγn2‖xn-x̂‖2+12‖xn+1-x̂‖2-αnγn〈x̂,xn+1-x̂〉.
It follows that
(3.20)‖xn+1-x̂‖2≤(1-αnγn)‖xn-x̂‖2+αnγn〈-x̂,xn+1-x̂〉.
From Lemma 2.4, (3.18) and (3.20), we deduce that xn→x̂. This completes the proof.Remark 3.2.
We obtain the strong convergence of the regularized gradient projection method (3.1) under some different control conditions.Remark 3.3.
From the proof of result, we observe that our algorithm (3.1) converges to a special solution x̂ of the minimization (1.1). As a matter of fact, this special solution x̂ is the minimum-norm solution of the minimization (1.1). Finding the minimum-norm solution of practical problem is an interesting work due to its applications. A typical example is the least-squares solution to the constrained linear inverse problem; see, for example, [15]. For some related works on the minimum-norm solution and the minimization problems, please see [16–22].



---

*Source: 259813-2012-02-20.xml*