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.

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:

()

where f : ℝⁿ → ℝ ∪ {∞} 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

()

where D_h is given by

()

with h is a strictly convex and continuously differentiable function.

Throughout this paper, ∥·∥ denotes the l₂-norm and 〈·, ·〉 denotes the Euclidean inner product in ℝⁿ. Let G be a continuous single-valued mapping from ℝⁿ into ℝⁿ. The mapping G is Lipschitz continuous with Lipschitz constant L, if for all x, y ∈ ℝⁿ, ∥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) = min _y∈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) Initialize x⁰ ∈ ℝⁿ : f(x⁰) < ∞, c₀ > 0.

(2) Compute the solution x^k+1 by the iterative scheme:

()

where {c_k} is a sequence of positive numbers and D_h(·, ·) is defined by (2.3).

For D_h(x, y) = (1/2)∥x−y∥², 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

with the following global rate of convergence estimate:

()

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 {y_k} ⊂ ℝⁿ in the unconstrained minimization (2.4) in such a way:

()

We show (see Section 4) that this new proximal method possesses the following rate estimate

()

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 also D-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 ℝⁿ and let

be a finite-valued continuously differentiable function on S be and let D_h defined by

()

Definition 2.2. h is called a Bregman function with zone S or a D-function if:

(a)
h is continuously differentiable on S and continuous on ,
(b)
h is strictly convex on ,
(c)
for every λ ∈ ℝ, the partial level sets and L₂(x, λ) = {y ∈ S : D_h(x, y) ≤ λ} are bounded for every y ∈ S and , respectively,
(d)
if {y_k} ∈ S is a convergent sequence with limit y^*, then D_h(y^*, y_k) → 0,
(e)
if {x^k} and {y_k} are sequences such that , {x^k} is bounded and D_h(x^k, y_k) → 0, then x^k → y^*.

From the above definition, we extract the following properties (see, for instance, [6, 13]).

Lemma 2.3. Let h be a Bregman function with zone S. Then,

(i)
D_h(x, x) = 0 and D_h(x, y) ≥ 0 for and y ∈ S,
(ii)
for all a, b ∈ S and ,
()
(iii)
for all a, b ∈ S,
()
(iv)
for all
(v)
let {x^k} ∈ S such that x^k → x^* ∈ S, then D_h(x^*, x^k) → 0 and D_h(x^k, x^*) → 0.

Lemma 2.4. (i) Let g : ℝⁿ → ℝ be a strictly convex function such that

()

then g is a Bregman function.

(ii) If g is a Bregman function, then g(x) + c^⊤x + d for any c ∈ ℝⁿ, d ∈ ℝ, also is a Bregman function.

Remark 2.5. D_h(·, ·) cannot be considered as a distance because of the lack of the triangle inequality and the symmetry property. D_h(·, ·) is usually called an entropy distance.

The paper is organized as follows. In Section 3, 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) Initialize x⁰ ∈ ℝⁿ : f(x⁰) < ∞, c₀ > 0, A > 0.

Define ν₀ : = x⁰, A₀ : = A, k = 0.

(ii) Compute .

(iii) Compute the solution x^k+1 by the iterative scheme:

()

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 Section 3 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: x⁰ ∈ ℝⁿ : f(x⁰) < ∞, c₀ > 0, A > 0.

Define ν₀ : = x⁰, A₀ : = A, k = 0

(ii) Compute: α_k such that .

(iii) Compute the solution x^k+1 by the iterative scheme:

()

In this section we develop convergence results for the generalized Güler′s proximal point algorithm GGPPA presented in Section 4.2. Our analysis is basically based on the following lemma.

Lemma 4.2 ([1, page 654]). One has

()

for all α_j ∈ [0,1[ and A > 0.

Theorem 4.3. For all such that f(x) < ∞, one has the following convergence rate estimate:

()

Proof. Using the fact that ϕ₀(x) : = f(x⁰) + AD_h(x, x⁰), x⁰ ∈ 𝒮, and Lemma 4.2, we obtain

()

Since

, then (4.3) holds.

Theorem 4.4. Consider the sequence {x^k} generated by GGPPA and let x^* be a minimizer of f(x) on ℝⁿ. Assume that

(1)
h is a Bregman function with zone 𝒮 such that ,
(2)
Im(∇h) = ℝⁿ or Im(∇h) is open,
(3)
∇h is Lipschitz continuous with coefficient L,

then

(a)
for all x⁰ ∈ Dom (∇h), the sequence {x^k} is well defined,
(b)
the GGPPA possesses this following convergence rate estimate:
()
(c)
f(x^k) − f_* → 0, when ,
(d)

()
if c_k ≥ c > 0.

Proof. (a) Follows from [8, Theorem 4].

(b) Uses assumption (2.3) in the following manner

()

and by taking x = x^* in (4.3), then we have

()

Since x^* is arbitrary, then (4.5) holds.

(d) It suffices to observe that if c_k ≥ c > 0, we have

()

4.2. Finite Convergence

Note that the finite convergence property 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 function f : ℝⁿ → ℝ is said to have a sharp minimum on ℝⁿ if and only if there exists τ > 0 such that

()

Theorem 4.6. Under the same hypothesis as in Theorem 4.4 and by considering GGPPA with f having a sharp minimum on ℝⁿ and c_k being bounded, then there exists k such that 0 ∈ ∂f(x^k) and x^k ∈ X^*.

Proof. Straightforward, using Theorem 4.4 and [5, Theorem 6.1, page 1151].

5. Convergence Rate of GGPPA

If {x^k} is a sequence of points, one forms the sequence {zⁿ} of weighted averages given by

()

where c_k > 0. If the sequence {zⁿ} converges, then

is said to converge ergodically.

Theorem 5.1. GGPPA possesses the following convergence rate:

()

that is, σ_n(f(xⁿ) − f_*) → 0. Furthermore, if c_k ≥ c > 0, then one has

()

Proof. Let x^* be a minimizer of f. For brevity, we denote W_k = f(x^k) − f_*, V_k = f(y^k) − f_* and Δ = ∇h(y^k) − ∇h(x^k+1). At optimality in the unconstrained minimization in GGPPA, we can write

()

and by the convexity of f, we have

()

Setting x = x^k in (5.5), we obtain

()

and for x = y^k, we have

()

Or again, if we set x = x^* in (5.5), and using the Cauchy-Schwartz inequality, we obtain

()

that is,

()

Since h is convex, 〈x^k+1 − y^k, Δ〉 ≤ 0. Then we can write

()

that is,

()

Using the relation ∥Δ∥² ≤ L〈Δ, y^k − x^k+1〉 and the inequality (5.7), we get the relation

()

For short we denote M_k = ∥y^k − x^*∥ thus, (5.12) becomes

()

Then by dividing both terms by

, we get

()

Since the left-side term is positive, then

()

Now following Güler [17, page 410], we use the fact that (1+x)⁻¹ ≤ 1 − 2x/3, for all x ∈ [0,1/2]. To apply this inequality, it suffices to show that

is less than or equal to 1/2. This can be deduced from this relation (see Lemma 2.3 (ii)):

()

Indeed, since D_h(·, ·) ≥ 0, then (the proof of this next inequality can be found in the proof of Theorem 4.4-(b))

()

Therefore,

and we obtain

()

To continue the proof, we will separate some different cases.

Case 1. If . Then W_k+1 ≤ V_k ≤ W_k and we have . Thus, (5.18) becomes

()

and by summation from k = 0 to k = n, we get

()

that is,

()

Then,

()

Since x^* is an arbitrary solution, we can write

()

and by multiplying both terms by

, we obtain

()

Since y^k and x^k+1 converge to the same point (indeed, we can see it via the formula giving ν_k+1 in the algorithm GGPPA and ρ(x^k+1, X^*) → 0, then

; hence, we obtain

()

which implies

()

that is,

()

Case 2. If Then W_k+1 ≤ W_k ≤ V_k and we have therefore; for n ≥ k we have . Thus, using inequality (5.18), we write

()

and by summation from k = 0 to k = n, we get

()

Then,

()

Since x^* is an arbitrary solution, we can write

()

and by multiplying both terms by

, we obtain

()

Since y^k and x^k+1 converge to the same point (indeed, we can see it via the formula giving ν_k+1 in the algorithm GGPPA and ρ(x^k+1, X^*) → 0, then

; hence, we obtain

()

which implies,

()

that is,

()

Case 3. If . In this case we observe that sequence {f(x^k)} is increasing, which may imply a divergence of the approach.

Since f is convex, then the following convergence rate estimate can be derived directly.

Corollary 5.2. If one assumes that c_k ≥ c > 0 for all k, then

()

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].

Acknowledgments

The authors would like to thank Dr. Osman Güler for providing them with reference [12] and the English translation of the original paper of Nesterov [14].

References

1 Güler O., New proximal point algorithms for convex minimization, SIAM Journal on Optimization. (1992) 2, no. 4, 649–664, 1186167, https://doi.org/10.1137/0802032, ZBL0778.90052.
10.1137/0802032
Web of Science® Google Scholar
2 Chen G. and Teboulle M., Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM Journal on Optimization. (1993) 3, no. 3, 538–543, 1230155, https://doi.org/10.1137/0803026, ZBL0808.90103.
10.1137/0803026
Web of Science® Google Scholar
3 Burachik R. S., Generalized proximal point methods for the variationnal inequality problem, Ph.D. thesis, 1995, Instituto de Matemàtica Pura e Aplcada, Rio de Janeiro, Brazil.
Google Scholar
4 Eckstein J., Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming, Mathematics of Operations Research. (1993) 18, no. 1, 202–226, 1250114, https://doi.org/10.1287/moor.18.1.202, ZBL0807.47036.
10.1287/moor.18.1.202
Web of Science® Google Scholar
5 Kiwiel K. C., Proximal minimization methods with generalized Bregman functions, SIAM Journal on Control and Optimization. (1997) 35, no. 4, 1142–1168, 1453294, https://doi.org/10.1137/S0363012995281742, ZBL0890.65061.
10.1137/S0363012995281742
Web of Science® Google Scholar
6 Teboulle M., Entropic proximal mappings with applications to nonlinear programming, Mathematics of Operations Research. (1992) 17, no. 3, 670–690, 1177730, https://doi.org/10.1287/moor.17.3.670, ZBL0766.90071.
10.1287/moor.17.3.670
Web of Science® Google Scholar
7 Rockafellar R. T., Convex Analysis, 1970, 28, Princeton University Press, Princeton, NJ, USA, Princeton Mathematical Series, 0274683.
10.1515/9781400873173
Google Scholar
8 Brègman L. M., A relaxation method of finding a common point of convex sets and its application to the solution of problems in convex programming, USSR Computational Mathematics and Mathematical Physics. (1967) 7, no. 3, 620–631, 0215617.
10.1016/0041-5553(67)90040-7
Google Scholar
9 Moreau J.-J., Proximitéet dualité dans un espace hilbertien, Bulletin de la Société Mathématique de France. (1965) 93, 273–299, 0201952.
10.24033/bsmf.1625
Google Scholar
10 Martinet B., Algorithmes pour la résolution de problèmes d′optimisation et de minimax, Thèse d′Etat, 1972, Université de Grenoble.
Google Scholar
11 Censor Y. and Zenios S. A., Proximal minimization algorithm with D-functions, Journal of Optimization Theory and Applications. (1992) 73, no. 3, 451–464, 1164803, https://doi.org/10.1007/BF00940051.
10.1007/BF00940051
Web of Science® Google Scholar
12 Güler O., Ergodic convergence in proximal point algorithms with Bregman functions, Advances in Optimization and Approximation, 1994, 1, Kluwer Academic, Dordrecht, The Netherlands, 155–165, Nonconvex Optimization and Its Applications, 1336388, https://doi.org/10.1007/978%2D1%2D4613%2D3629%2D7_7, ZBL0828.90103.
10.1007/978-1-4613-3629-7_7
Google Scholar
13 Censor Y. and Zenios S. A., Parallel Optimization, 1997, Oxford University Press, New York, NY, USA, Numerical Mathematics and Scientific Computation, 1486040.
Google Scholar
14 Nesterov Yu. E., An approach to constructing optimal methods for minimization of smooth convex functions, Èkonomika i Matematicheskie Metody. (1988) 24, no. 3, 509–517, Translated for O. Güler by V. Rachmanov, 1988968064.
Google Scholar
15 Iusem A. N., Svaiter B. F., and Teboulle M., Entropy-like proximal methods in convex programming, Mathematics of Operations Research. (1994) 19, no. 4, 790–814, 1304625, https://doi.org/10.1287/moor.19.4.790, ZBL0821.90092.
10.1287/moor.19.4.790
Web of Science® Google Scholar
16 Ferris M. C., Finite termination of the proximal point algorithm, Mathematical Programming. (1991) 50, no. 3, 359–366, 1114237, https://doi.org/10.1007/BF01594944, ZBL0741.90051.
10.1007/BF01594944
Web of Science® Google Scholar
17 Güler O., On the convergence of the proximal point algorithm for convex minimization, SIAM Journal on Control and Optimization. (1991) 29, no. 2, 403–419, 1092735, https://doi.org/10.1137/0329022.
10.1137/0329022
Web of Science® Google Scholar
18 Aslam Noor M., Some developments in general variational inequalities, Applied Mathematics and Computation. (2004) 152, no. 1, 199–277, 2050063, https://doi.org/10.1016/S0096%2D3003(03)00558%2D7, ZBL1134.49304.
10.1016/S0096-3003(03)00558-7
Web of Science® Google Scholar
19 Yao Y., [email protected], Noor M. A., [email protected], Liou Y.-C., and [email protected], Kang S. M., [email protected], Iterative algorithms for general multivalued variational inequalities, Abstract and Applied Analysis. (2012) 2012, 10, 768272, https://doi.org/10.1155/2012/768272.
10.1155/2012/768272
Google Scholar
20 Noor M. A., [email protected], Noor K. I., and Al-Said E., Iterative methods for solving nonconvex equilibrium variational inequalities, Applied Mathematics and Information Sciences. (2012) 6, no. 1, 65–69.
Google Scholar

Citing Literature

All articles

Convergence of a Proximal Point Algorithm for Solving Minimization Problems

Abstract

1. Introduction

2. Preliminaries

3. Extragradient Algorithm

4. Main Result

4.1. Introduction

4.2. Finite Convergence

5. Convergence Rate of GGPPA

6. Conclusion

Acknowledgments

References

Citing Literature

References

Information

About Wiley Online Library

Help & Support

Opportunities

Connect with Wiley

Convergence of a Proximal Point Algorithm for Solving Minimization Problems

Abstract

1. Introduction

2. Preliminaries

3. Extragradient Algorithm

4. Main Result

4.1. Introduction

4.2. Finite Convergence

5. Convergence Rate of GGPPA

6. Conclusion

Acknowledgments

References

Citing Literature

References

Related

Information