Strong Convergence of a Projected Gradient Method

Proposition 2.1 (See [9]). (1) The composite of finitely many averaged mappings is averaged. That is, if each of the mappings $$ is averaged, then so is the composite T₁, …, T_N. In particular, if T₁ is α₁-averaged and T₂ is α₂-averaged, where α₁, α₂ ∈ (0,1), then the composite T₁T₂ is α-averaged, where α = α₁α₂ − α₁α₂.

(2) T is ν-ism, then for γ > 0, γT is (ν/γ)-ism.

Lemma 2.2 (See [26]). Let {x_n} and {y_n} be bounded sequences in a Banach space X and let {β_n} be a sequence in [0,1] with

Suppose for all n ≥ 0 and Then, lim _n→∞∥y_n − x_n∥ = 0.

Lemma 2.3 (See [27] (demiclosedness principle)). Let C be a closed and convex subset of a Hilbert space H and let T : C → C be a nonexpansive mapping with Fix (T) ≠ ∅. If {x_n} is a sequence in C weakly converging to x and if {(I − T)x_n} converges strongly to y, then

In particular, if y = 0, then x ∈ Fix (T).

Lemma 2.4 (See [28]). Assume {a_n} is a sequence of nonnegative real numbers such that

where {γ_n} is a sequence in (0,1) and {δ_n} is a sequence such that

• (1)

  $$;

• (2)

  limsup _n→∞δ_n/γ_n ≤ 0 or $$.

Then, lim _n→∞a_n = 0.

Algorithm 3.1. For given x₀ ∈ C, compute the sequence {x_n} iteratively by

where σ > 0, γ > 0 are two constants and the real number sequence {θ_n}⊂[0,1].

Remark 3.2. In (3.1), we use two projections. Now, it is well-known that the advantage of projections, which makes them successful in real-word applications, is computational.

Theorem 3.3. Assume that the gradient ∇f is L-Lipschitzian and σρ < α. Let {x_n} be a sequence generated by (3.1), where γ ∈ (0,2/L) is a constant and the sequence {θ_n} satisfies the conditions: (i) lim _n→∞θ_n = 0 and (ii) $$. Then {x_n} converges to a minimizer $$ of (1.1) which solves the following variational inequality:

Proposition 3.4. It is well known that the metric projection P_C of H onto C has the following basic properties:

• (i)

  ∥P_C(x) − P_C(y)∥≤∥x − y∥, for all x, y ∈ H;

• (ii)

  〈x − y, P_C(x) − P_C(y)〉≥∥P_C(x) − P_C(y)∥², for every x, y ∈ H;

• (iii)

  〈x − P_C(x), y − P_C(x)〉≤0, for all x ∈ H, y ∈ C.

The Proof of Theorem 3.3 Let x^* ∈ S. First, from (2.8), we note that P_C(I − γ∇f)x^* = x^*. By (3.1), we have

Thus, by induction, we obtain

Note that the Lipschitz condition implies that the gradient ∇f is (1/L)-inverse strongly monotone (ism), which then implies that γ∇f is (1/γL)-ism. So, I − γ∇f is (γL/2)-averaged. Now since the projection P_C is (1/2)-averaged, we see that P_C(I − γ∇f) is ((2 + γL)/4)-averaged. Hence we have that

where R, T are nonexpansive and β = (2 + γL)/4 ∈ (0,1). Then we can rewrite (3.1) as where Set z_n = (1 − β)x_n + βTx_n for all n. Since {x_n} is bounded, we deduce {A(x_n)}, {B(x_n)}, and {Tx_n} are all bounded. Hence, there exists a constant M > 0 such that Thus, It follows that This together with Lemma 2.2 implies that So, Since we deduce Next we prove where x^* is the unique solution of VI (3.2).

Indeed, we can choose a subsequence $$ of {x_n} such that

Since $$ is bounded, there exists a subsequence of $$ which converges weakly to a point $$. Without loss of generality, we may assume that $$ converges weakly to $$. Since γ ∈ (0, 2/L), P_C(I − γ∇f) is nonexpansive. Thus, from (3.14) and Lemma 2.3, we have $$. Therefore, Finally, we show $$. By using the property of the projection P_C, we have It follows that It is obvious that $$. Then we can apply Lemma 2.4 to the last inequality to conclude that $$. The proof is completed.

Algorithm 3.5. For given x₀ ∈ C, compute the sequence {x_n} iteratively by

where σ > 0, γ > 0 are two constants and the real number sequence {θ_n}⊂[0,1].

Theorem 3.6. Assume that the gradient ∇f is L-Lipschitzian and σρ < α. Let {x_n} be a sequence generated by (3.20), where γ ∈ (0, 2/L) is a constant and the sequences {θ_n} satisfies the conditions: (i) lim _n→∞θ_n = 0 and (ii) $$. Then {x_n} converges to a minimizer $$ of (1.1) which is the minimum norm element in S.

Proof. As a consequence of Theorem 3.3, we obtain that the sequence {x_n} generated by (3.20) converges strongly to $$ which satisfies

This implies Thus, That is, $$ is the minimum norm element in S. This completes the proof.