Convergence of a Proximal Point Algorithm for Solving Minimization Problems

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.

(ProQuest: ... denotes non-US-ASCII text omitted.)

Abdelouahed Hamdi 1 and M. A. Noor 2 and A. A. Mukheimer 1

Recommended by Yonghong Yao

1, Department of Mathematics, Prince Sultan University, P.O. Box 66833, Riyadh 11586, Saudi Arabia
2, Mathematics Department, COMSATS Institute of Information Technology, Islamabad, Pakistan

Received 16 January 2012; Accepted 4 February 2012

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: [figure omitted; refer to PDF] where f:^...n [arrow right]...∪{∞} 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 _...A5;c [figure omitted; refer to PDF] where _Dh is given by [figure omitted; refer to PDF] 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)||...4;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 ^x0 ∈^...n :f(^x0 )<∞, _c0 >0 .

(2) Compute the solution ^xk+1 by the iterative scheme: [figure omitted; refer to PDF] where {_ck } is a sequence of positive numbers and _Dh (·,·) is defined by (2.3).

For _Dh (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=1n_ck [arrow right]∞ with the following global rate of convergence estimate: [figure omitted; refer to PDF] 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: [figure omitted; refer to PDF] We show (see Section 4) that this new proximal method possesses the following rate estimate [figure omitted; refer to PDF] which is faster than (2.5). Further, the convergence in terms of the objective values occurs when _γn [arrow right]∞ which is weaker than _σn [arrow right]∞ .

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 ^...n and let h:S¯[arrow right]... be a finite-valued continuously differentiable function on S be and let _Dh defined by [figure omitted; refer to PDF]

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 S¯ ,

(b) h is strictly convex on S¯ ,

(c) for every λ∈... , the partial level sets _L1 (y,λ)={x∈S¯:_Dh (x,y)...4;λ} and _L2 (x,λ)={y∈S:_Dh (x,y)...4;λ} 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 )[arrow right]0 ,

(e) if {^xk } and {_yk } are sequences such that _yk [arrow right]^y* ∈S¯ , {^xk } is bounded and _Dh (^xk ,_yk )[arrow right]0 , then ^xk [arrow right]^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) _Dh (x,x)=0 and _Dh (x,y)...5;0 for x∈S¯ and y∈S ,

(ii) for all a , b∈S and c∈S¯ , [figure omitted; refer to PDF]

(iii): for all a,b∈S , [figure omitted; refer to PDF]

(iv) for all x∈S ^h* (∇h(x))=...x,∇h(x)...-h(x),

(v) let {^xk }∈S such that ^xk [arrow right]^x* ∈S , then _Dh (^x* ,^xk )[arrow right]0 and _Dh (^xk ,^x* )[arrow right]0 .

Lemma 2.4.

(i) Let g:^...n [arrow right]... be a strictly convex function such that [figure omitted; refer to PDF] then g is a Bregman function.

(ii) If g is a Bregman function, then g(x)+^{c[inverted perpendicular]} 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 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 ^x0 ∈^...n :f(^x0 )<∞, _c0 >0, A>0 .

Define _ν0 :=^x0 , _A0 :=A, k=0 .

(ii) Compute _αk =(^{(_Akck )2} +4_Akck -_Akck )/2 .

(iii) Compute the solution ^xk+1 by the iterative scheme: [figure omitted; refer to PDF]

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: ^x0 ∈^...n :f(^x0 )<∞, _c0 >0, A>0 .

Define _ν0 :=^x0 , _A0 :=A, k=0

(ii) Compute: _αk such that ^αk2 =(1-_αk )_Akck /L^L* .

(iii) Compute the solution ^xk+1 by the iterative scheme: [figure omitted; refer to PDF]

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 [figure omitted; refer to PDF] for all _αj ∈[0,1[ and A>0 .

Theorem 4.3.

For all x∈...AE;¯ such that f(x)<∞ , one has the following convergence rate estimate: [figure omitted; refer to PDF]

Proof.

Using the fact that _[varphi]0 (x):=f(^x0 )+A_Dh (x,^x0 ) , ^x0 ∈...AE; , and Lemma 4.2, we obtain [figure omitted; refer to PDF] Since ^{[1+(A/2)∑j=0k-1_cj ]2} ...5;^{(∑j=0k-1_cj )2} A/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 ...AE; such that Dom (∂f)¯⊂...AE; ,

(2) Im (∇h)=^...n or Im (∇h) is open,

(3) ∇h is Lipschitz continuous with coefficient L ,

then

(a) for all ^x0 ∈Dom (∇h) , the sequence {^xk } is well defined,

(b) the GGPPA possesses this following convergence rate estimate: [figure omitted; refer to PDF]

(c) f(^xk )-_f* [arrow right]0 , when ^∑k=0∞_ck =∞ ,

(d) [figure omitted; refer to PDF] if _ck ...5;c>0 .

Proof.

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

(b) Uses assumption (2.3) in the following manner [figure omitted; refer to PDF] and by taking x=^x* in (4.3), then we have [figure omitted; refer to PDF] Since ^x* is arbitrary, then (4.5) holds.

(c) Is obvious.

(d) It suffices to observe that if _ck ...5;c>0 , we have [figure omitted; refer to PDF]

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:^...n [arrow right]... is said to have a sharp minimum on ^...n if and only if there exists τ>0 such that [figure omitted; refer to PDF]

Theorem 4.6.

Under the same hypothesis as in Theorem 4.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 Theorem 4.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 [figure omitted; refer to PDF] 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: [figure omitted; refer to PDF] that is, _σn (f(^xn )-_f* )[arrow right]0 . Furthermore, if _ck ...5;c>0 , then one has [figure omitted; refer to PDF]

Proof.

Let ^x* 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 [figure omitted; refer to PDF] and by the convexity of f , we have [figure omitted; refer to PDF] Setting x=^xk in (5.5), we obtain [figure omitted; refer to PDF] and for x=^yk , we have [figure omitted; refer to PDF] Or again, if we set x=^x* in (5.5), and using the Cauchy-Schwartz inequality, we obtain [figure omitted; refer to PDF] that is, [figure omitted; refer to PDF] Since h is convex, ...^xk+1 -^yk ,Δ......4;0 . Then we can write [figure omitted; refer to PDF] that is, [figure omitted; refer to PDF] Using the relation ^||Δ||2 ...4;L...Δ,^yk -^xk+1 ... and the inequality (5.7), we get the relation [figure omitted; refer to PDF] For short we denote _Mk =||^yk -^x* || thus, (5.12) becomes [figure omitted; refer to PDF] Then by dividing both terms by L^Mk2 >0 , we get [figure omitted; refer to PDF] Since the left-side term is positive, then [figure omitted; refer to PDF] Now following Güler [17, page 410], we use the fact that ^(1+x)-1 ...4;1-2x/3, for all x∈[0,1/2] . To apply this inequality, it suffices to show that (_ck /L^Mk2 )_Wk+1 is less than or equal to 1/2 . This can be deduced from this relation (see Lemma 2.3 (ii)): [figure omitted; refer to PDF] Indeed, since _Dh (·,·)...5;0 , then (the proof of this next inequality can be found in the proof of Theorem 4.4-(b)) [figure omitted; refer to PDF] Therefore, 0<(_ck /L^Mk2 )_Wk+1 ...4;1/2 and we obtain [figure omitted; refer to PDF] To continue the proof, we will separate some different cases.

Case 1.

If f(^xk+1 )...4;f(^yk )...4;f(^xk )... . Then _Wk+1 ...4;_Vk ...4;_Wk and we have ^Vk-1 ...5;^Wk-1 . Thus, (5.18) becomes [figure omitted; refer to PDF] and by summation from k=0 to k=n , we get [figure omitted; refer to PDF] that is, [figure omitted; refer to PDF] Then, [figure omitted; refer to PDF] Since ^x* is an arbitrary solution, we can write [figure omitted; refer to PDF] and by multiplying both terms by _σn+1 =^∑k=0n_ck , we obtain [figure omitted; refer to PDF] 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* )[arrow right]0 , then ρ^{(xk+1 ,X* )-2} [arrow right]∞ ; hence, we obtain [figure omitted; refer to PDF] which implies [figure omitted; refer to PDF] that is, [figure omitted; refer to PDF]

Case 2.

If f(^xk+1 )...4;f(^xk )...4;f(^yk ).... Then _Wk+1 ...4;_Wk ...4;_Vk and we have ^Wk+1-1 ...5;^Wk-1 therefore; for n...5;k we have ^Wn+1-1 ...5;^Wk-1 . Thus, using inequality (5.18), we write [figure omitted; refer to PDF] and by summation from k=0 to k=n , we get [figure omitted; refer to PDF] Then, [figure omitted; refer to PDF] Since ^x* is an arbitrary solution, we can write [figure omitted; refer to PDF] and by multiplying both terms by _σn+1 =^∑k=0n_ck , we obtain [figure omitted; refer to PDF] 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* )[arrow right]0 , then ρ^{(xk+1 ,X* )-2} [arrow right]∞ ; hence, we obtain [figure omitted; refer to PDF] which implies, [figure omitted; refer to PDF] that is, [figure omitted; refer to PDF]

Case 3.

If f(^xk )...4;f(^xk+1 )...4;f(^yk )... . In this case we observe that sequence {f(^xk )} 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 _ck ...5;c>0 for all k , then [figure omitted; refer to PDF]

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] O. Güler, "New proximal point algorithms for convex minimization," SIAM Journal on Optimization , vol. 2, no. 4, pp. 649-664, 1992.

[2] G. Chen, M. Teboulle, "Convergence analysis of a proximal-like minimization algorithm using Bregman functions," SIAM Journal on Optimization , vol. 3, no. 3, pp. 538-543, 1993.

[3] R. S. Burachik Generalized proximal point methods for the variationnal inequality problem , Ph.D. thesis, Instituto de Matemàtica Pura e Aplcada, Rio de Janeiro, Brazil, 1995.

[4] J. Eckstein, "Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming," Mathematics of Operations Research , vol. 18, no. 1, pp. 202-226, 1993.

[5] K. C. Kiwiel, "Proximal minimization methods with generalized Bregman functions," SIAM Journal on Control and Optimization , vol. 35, no. 4, pp. 1142-1168, 1997.

[6] M. Teboulle, "Entropic proximal mappings with applications to nonlinear programming," Mathematics of Operations Research , vol. 17, no. 3, pp. 670-690, 1992.

[7] R. T. Rockafellar Convex Analysis , vol. 28, of Princeton Mathematical Series, pp. xviii+451, Princeton University Press, Princeton, NJ, USA, 1970.

[8] L. M. Brègman, "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 , vol. 7, no. 3, pp. 620-631, 1967.

[9] J.-J. Moreau, "Proximitéet dualité dans un espace hilbertien," Bulletin de la Société Mathématique de France , vol. 93, pp. 273-299, 1965.

[10] B. Martinet Algorithmes pour la résolution de problèmes d'optimisation et de minimax , Thèse d'Etat, Université de Grenoble, 1972.

[11] Y. Censor, S. A. Zenios, "Proximal minimization algorithm with D -functions," Journal of Optimization Theory and Applications , vol. 73, no. 3, pp. 451-464, 1992.

[12] O. Güler, "Ergodic convergence in proximal point algorithms with Bregman functions," Advances in Optimization and Approximation , vol. 1, of Nonconvex Optimization and Its Applications, pp. 155-165, Kluwer Academic, Dordrecht, The Netherlands, 1994.

[13] Y. Censor, S. A. Zenios Parallel Optimization , of Numerical Mathematics and Scientific Computation, pp. xxviii+539, Oxford University Press, New York, NY, USA, 1997.

[14] Yu. E. Nesterov, "An approach to constructing optimal methods for minimization of smooth convex functions," Translated for O. Güler by V. Rachmanov, 1988 Èkonomika i Matematicheskie Metody , vol. 24, no. 3, pp. 509-517, 1988.

[15] A. N. Iusem, B. F. Svaiter, M. Teboulle, "Entropy-like proximal methods in convex programming," Mathematics of Operations Research , vol. 19, no. 4, pp. 790-814, 1994.

[16] M. C. Ferris, "Finite termination of the proximal point algorithm," Mathematical Programming , vol. 50, no. 3, pp. 359-366, 1991.

[17] O. Güler, "On the convergence of the proximal point algorithm for convex minimization," SIAM Journal on Control and Optimization , vol. 29, no. 2, pp. 403-419, 1991.

[18] M. Aslam Noor, "Some developments in general variational inequalities," Applied Mathematics and Computation , vol. 152, no. 1, pp. 199-277, 2004.

[19] Y. Yao, M. A. Noor, Y.-C. Liou, S. M. Kang, "Iterative algorithms for general multivalued variational inequalities," Abstract and Applied Analysis , vol. 2012, 2012., [email protected]; [email protected]; [email protected]; [email protected]

[20] M. A. Noor, K. I. Noor, E. Al-Said, "Iterative methods for solving nonconvex equilibrium variational inequalities," Applied Mathematics and Information Sciences , vol. 6, no. 1, pp. 65-69, 2012., [email protected]