Convergence Analysis of General Version of Gauss-Type Proximal Point Method for Metrically Regular Mappings

Md. Asraful Alom^1,2, Mohammed Harunor Rashid¹, Kalyan Kumer Dey¹

¹Department of Mathematics, University of Rajshahi, Rajshahi, Bangladesh.
²Department of Mathematics, Faculty of Civil Engineering, Khulna University of Engineering & Technology, Khulna, Bangladesh.

DOI: 10.4236/am.2016.711110                

Abstract

We introduce and study in the present paper the general version of Gauss-type proximal point algorithm (in short GG-PPA) for solving the inclusion , where T is a set-valued mapping which is not necessarily monotone acting from a Banach space X to a subset of a Banach space Y with locally closed graph. The convergence of the GG-PPA is present here by choosing a sequence of functions with , which is Lipschitz continuous in a neighbourhood O of the origin and when T is metrically regular. More precisely, semi-local and local convergence of GG-PPA are analyzed. Moreover, we present a numerical example to validate the convergence result of GG-PPA.

Keywords

Set-Valued Mappings, Metrically Regular Mappings, Lipschitz-Like Mapping, Local and Semi-Local Convergence

Received 7 January 2016; accepted 17 July 2016; published 20 July 2016

1. Introduction

We are concerned in this study with the problem of finding a point satisfying

(1)

Martinet [1] proposed the following algorithm for the first time for applying it to convex optimization by considering a sequence of scalars, which are different from zero:

(2)

Rockafellar [2] thoroughly explored the method (2) in the general framework of maximal monotone inclu- sions. In particular, Rockafellar ( [2] , Theorem 1) shows that when is an approximate solution of (2) and T is maximal monotone, then for a sequence of positive scalars the iteration (2) generates a sequence which is weakly convergent to a solution of (1) for any starting point. In [3] , Aragón Artacho et al. have been presented the general version of the proximal point algorithm (GPPA) (see Algorithm 1), for the case of nonmonotone mappings, for solving the inclusion (1).

Let. The subset of X, denoted by, is defined by

(3)

Thus we have the following algorithms which have been presented by Aragón Artacho et al. [3] :

Note that, for a starting point near to a solution, the sequences generated by Algorithm 1 are not uniquely defined and not every sequence is convergent. The results obtained in [3] guarantee the existence of one sequence, which is convergent. Therefore, from the viewpoint of numerical computation, we can assume that these kinds of methods are not suitable in practical application. This drawback motivates us to introduce a method “so- called” general version of Gauss-type proximal point algorithm (GG-PPA). The difference between Algorithm 1 and our proposed Algorithm 2 is that the GG-PPA generates sequences, whose every sequence is convergent, but this does not happen for Algorithm 1. Thus we propose here the GG-PPA as follows:

We observe, from Algorithm 2, that

1) if and then we assume a Hilbert space, this algorithm reduces to the classical pro- ximal point algorithm defined by (2).

2) if, Algorithm 2 is equivalent to the classical Gauss-type proximal point method, which has been introduced by Rashid et al. [4] .

A large number of authors have been studied on proximal point algorithm and have also found applications of this method to specific variational problems. Most of the study on this subject have been concentrated on various versions of the algorithm for solving inclusions involving monotone mappings, and specially, on monotone variational inequalities (see in [5] - [8] ). Spingarn [9] has been studied first weaker form of monotonicity and for details see in [10] .

There have a large study on local convergence analysis about Algorithm 1 (cf. [3] [11] [12] ), but there is no semilocal analysis for Algorithm 1. A huge number of contributions have been studied on semilocal analysis for the Gauss-Newton method (cf. [4] [13] - [16] ). In [4] , Rashid et al. have given a semilocal convergence analysis for the classical Gauss-type proximal point method. As our best knowledge, there is no study on semilocal analysis for Algorithm 2. Therefore we conclude that the contributions presented in this study are seems new.

In the present paper, our aim is to study the semilocal convergence for the GG-PPA defined by Algorithm 2. The metric regularity property and Lipschitz-like property for set-valued mappings are mainly used in our study. The main results are convergence analysis, established in section 3, which based on the attraction region around the initial point and provide some sufficient conditions ensuring the convergence to a solution of any sequence generated by Algorithm 2. As a consequence, local convergence results for GG-PPA are obtained.

This paper is arranged as follows. In Section 2, some necessary notations, notions and preliminary results are presented. In Section 3, we consider the GG-PPA which is introduced in Section 1 and by using the concept of metric regularity property for the set valued mapping T, we will show the existence and present the convergence of the sequence generated by Algorithm 2. In Section 4, we present a numerical experiment to validate the semilocal convergence of Algorithm 2. In the last Section, we will give a summary of the major results to close our paper.

2. Notations and Preliminary Results

In the whole paper, we assume that X and Y are Banach spaces. Let F be a set-valued mapping from X into the subsets of Y, denoted by. Let and. The closed ball centered at x with radius r is denoted by. The domain, the inverse and the graph of F are respectively defined by

and

All the norms are denoted by. Let and. The distance from x to A is defined by

while the excess from the set C to the set A is defined by

From [4] , we recall the following definition of metric regularity for set-valued mapping.

Definition 1 Let be a set-valued mapping and let. Let and. Then F is said to be

1) metrically regular at on with constant if

(4)

2) metrically regular at if there exist constants and such that F is metrically regular at on with constant.

The infimum of the set of values for which (4) holds is the modulus of metric regularity, denoted by. The absence of metric regularity at for corresponds to. The inequality (4) has direct use in providing an estimate for how far a point x is from being a solution to the generalized equation and the expression measures the residual when.

Recall the definition of Lipschitz-like continuity for set-valued mapping from [17] . This notion was introduced by Aubin in [18] and has been studied extensively.

Definition 2 Let be a set-valued mapping and let. Let and. Then is said to be Lipchitz-like at on with constant M if the following inequqlity hold:

(5)

The following result establish the equivalence relation between metric regularity of a mapping F at and the Lipschitz-like continuity of the inverse at, which is obtained from the idea in [19] [20] .

Lemma 1 Let be a set valued mapping and. Let, then F is metrically regular at on if and only if its inverse is Lipschitz-like at on with constant such that

We recall the following statement of Lyusternik-Graves theorem for metrically regular mapping from [21] . This theorem plays an important role in the theory of metric regularity and proves the stability of metric regularity of a generalized equation under perturbations. For its statement, we use that a set is locally closed at if there exists such that the set is closed.

Lemma 2 Consider a mapping and any at which is locally closed. Let F be metrically regular at for with constant. Consider also a function which is Lipschitz continuous at with Lipschitz constant such that. Then the mapping is metric-

ally regular at for with constant.

We finished this section with the following lemma, which is known as Banach fixed point theorem proved in [22] .

Lemma 3 Let be a set-valued mapping. Let, and be such that

(6)

and

(7)

Then has a fixed point in, that is, there exists such that. If is additionally single-valued, then the fixed point of in is unique.

3. Convergence Analysis of GG-PPA

In this section, we assume that is a set-valued mapping with locally closed graph at such that T is metrically regular at with constant. Let be a (single-valued) function such that, which is Lipschitz continuous in a neighborhood O of 0 with a Lipschitz constant Let and define a mapping by

(8)

Then we obtain the following equivalence

(9)

In particular,

(10)

Let and let. Since is Lipschitz continuous on, app- lying the Lyusternik-Graves theorem (see Lemma 2) we assume that the mapping is metrically regular at

with constant, that is, by Lemma 1 we have the following inequality

(11)

Write

(12)

Then

(13)

The following lemma plays an important role for convergence analysis of the GG-PPA, which is due to [23] .

Lemma 4 Suppose that is metrically regular at on with constant such that (12) and (13) are satisfied. Let and. Then is Lipschitz-like at on with constant, that is,

For our convenience, we consider a sequence of functions with which are Lipschitz continuous in a neighbourhood O of 0, the same for all k, with Lipschitz constants satisfying

(14)

We rewrite the mapping in (8) by substituting instead of g as follows:

(15)

Since by (14), then by Lyusternik-Graves theorem (see Lemma 2) and Lemma 1 we obtain that the mapping is Lipschitz-like at on with constant satisfying (11) and hence we have

(16)

Furthermore, we define, for each, the mapping by

(17)

and the set-valued mapping by

(18)

Then

(19)

The main result of this study given as follows, which provides some sufficient conditions ensuring the convergence of the GG-PPA with initial point.

Theorem 1 Suppose and that is metrically regular at on with constant, and let be defined in (12). Let and be such that

a),

b),

c).

Suppose that

(20)

Then there exists some such that any sequence generated by Algorithm 2 with initial point in converges to a solution of (1), that is, satisfies that.

Proof. Let

(21)

Then by assumption (b), (21) gives us

(22)

Assumption (c) and (20) allow us to take so that

(23)

We will proceed by mathematical induction and show that Algorithm 2 generates at least one sequence and any sequence generated by Algorithm 2 satisfies the following assertions

(24)

and

(25)

for each. Define

(26)

Since, by assumption (b) and (c), we have

(27)

It is trivial that (24) is true for. For showing that (25) is true for, we need to prove that exists, that is,. We will prove by applying Lemma 3 to the mapping with

. Let us check that both assertions (6) and (7) of Lemma 3 are hold with and. Noting that

by (10). Then by the mapping in (18) and the definition of excess e, we have

(28)

(noting that). Now, by the choice of, we have

(29)

Since, by the fact in assumption (a) and in assumption (c), for each, (29) implies that

(30)

that is, for each,. In particular,

(31)

Hence by using (31) and Lemma 1 for Lipschitz-like property in (28), we have

This shows that assertion (6) of Lemma 3 is satisfied. Now, we show that the assertion (7) of Lemma 3 is satisfied. Let. Then by assumption (a) and (27), we have

and by (30). By assumed Lipschitz-like property of, we have

(32)

Applying (19) in (32), we obtain

(33)

Then by (14), (33) reduces to

This implies that the assertion (7) of Lemma 3 is also satisfied. Since both assertions (6) and (7) of Lemma 3 are fulfilled, we can deduce there exists a fixed point such that, which translates to, that is, and hence.

Now, we show that (25) is hold for.

Note that by assumption (a). Then (13) is valid for (14). Since is Lipschitz-like at on, it follows from Lemma 4 that the mapping is Lipschitz-like at on

with constant for each. In particular, is Lipschitz-like at on with constant as by assumption (a) and the choice of. Furthermore, assumptions (a) and (c) imply that

(34)

It seems that. Then by Lemma 1 we can say that the mapping is metrically regular on

relative to with constant. Thus by applying Lemma 1, we have

(35)

and (23) implies that

(36)

Then from (16) and using (36), we obtain that

(37)

From Algorithm 2 and using (21) and (37), we obtain that

(38)

This implies that (25) is hold for.

Suppose that the points have been obtained, and (24) and (25) are true for. We will show that there exists a point such that (24) and (25) also hold for. Since (24) and (25) are true for each, we have the following inequality

(39)

This reflects that (24) holds for. Now with almost the same argument as we did for the case when, we can find that the mapping is also Lipschitz-like at on with

constant. Then by applying again Algorithm 2, we have

(40)

This shows that (25) holds for. Therefore, the proof is completed.

In the particular case, when is a solution of (1), that is, , Theorem 1 is reduced to the following corollary, which gives the local convergence of the sequence generated by the GG-PPA defined by Algorithm 2.

Corollary 1 Suppose that and that satisfies and that is metrically regular at

with constant. Let be such that and suppose that

(41)

Then there exists some such that any sequence generated by Algorithm 2 with initial point in converges to a solution of (1), that is, satisfies that.

Proof. Since is metrically regular at, there exist constants, and such that is metrically regular at on with constant. Then, for each, one has that

(42)

Let be such that. Choose such that and Then

(43)

and

(44)

Thus we can choose such that

(45)

Now it is routine to check that inequalities (a)-(c) of Theorem 1 are hold. Thus Theorem 1 is applicable to complete the proof of the corollary.

4. Numerical Experiment

We will provide, in this section, a numerical example to validate the semilocal convergence results of GG-PPA.

Example 1 Let. Define a set-valued mapping T on by. Consider a sequence of Lipschitz continuous function with, which is

defined by. Then Algorithm 2 generates a sequence which is converges to.

It is obvious from the statement that T is metrically regular at and is Lipschitz continuous on the neighborhood of 0 with Lipschitz constant. Consider. Then from (3), we have that

On the other hand, if we obtain that

Thus from (40), we obtain that

For the given values of, we see that. Thus, this implies that the sequence generated

by Algorithm 2 converges linearly. Then the following Table 1, obtained by using Mat lab program, indicates that the solution of the generalized equation is 0.5 when.

Moreover, in the case when, we can sketch the following Figure 1:

5. Conclusions

In this study, we have established semi-local and local convergence results for the general version of Gauss-type proximal point algorithm for solving generalized equation under the assumptions that, a sequence of functions with which is Lipschitz continuous in a neighbourhood O of the origin

Figure 1. Graphical representation of.

Table 1. Finding a solution of generalized equation.

and T is metrically regular. Moreover, we have presented a numerical experiment to validate the semilocal convergence result for Algorithm 2. For the case where, the question, whether the results are true for GG-PPA, is a little bit complicated. However, from the proof of the main theorem, one sees that all the results obtained in the present paper remain true provided that, for any, the following implication holds:

To see the detail proof of the above implication, one can refer to [17] .

Acknowledgements

We thank the editor and the referees for their comments. Research of this work is funded by the Ministry of Science and Technology, Bangladesh, grant No. 39.009.002.01.00.053.2014-2015/EAS-19. This support is greatly appreciated.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Martinet, B. (1970) Régularisation d’inéquations variationnelles par approximations successives. Revue Fran?aise D’automatique, Informatique, Recherche Opérationnelle, 3, 154-158.
[2]	Rockafellar, R.T. (1976) Monotone Operators and the Proximal Point Algorithm. SIAM Journal on Control and Optimization, 14, 877-898. http://dx.doi.org/10.1137/0314056
[3]	Aragón Artacho, F.J., Dontchev, A.L. and Geoffroy, M.H. (2007) Convergence of the Proximal Point Method for Metrically Regular Mappings. ESAIM: Proceedings, 17, 1-8. http://dx.doi.org/10.1051/proc:071701
[4]	Rashid, M.H., Wang, J.H. and Li., C. (2013) Convergence Analysis of Gauss-Type Proximal Point Method for Metrically Regular Mappings. Journal of Nonlinear and Convex Analysis, 14, 627-635.
[5]	Auslender, A. and Teboulle, M. (2000) Lagrangian Duality and Related Multiplier Methods for Variational Inequality Problems. SIAM Journal on Optimization, 10, 1097-1115. http://dx.doi.org/10.1137/S1052623499352656
[6]	Bauschke, H.H., Burke, J.V., Deutsch, F.R., Hundal, H.S. and Vanderwerff, J.D. (2005) A New Proximal Point Iteration that Converges Weakly But Not in Norm. Proceedings of the American Mathematical Society, 133, 1829-1835. http://dx.doi.org/10.1090/S0002-9939-05-07719-1
[7]	Anh, P.N., Muu, L.D., Nguyen, V.H. and Strodiot, J.J. (2005) Using the Banach Contraction Principle to Implement the Proximal Point Method for Multivalued Monotone Variational Inequalities. Journal of Optimization Theory and Applications, 124, 285-306. http://dx.doi.org/10.1007/s10957-004-0926-0
[8]	Yang, Z. and He, B. (2005) A Relaxed Approximate Proximal Point Algorithm. Annals of Operations Research, 133, 119-125. http://dx.doi.org/10.1007/s10479-004-5027-9
[9]	Spingarn, J.E. (1982) Submonotone Mappings and the Proximal Point Algorithm. Numerical Functional Analysis and Optimization, 4, 123-150. http://dx.doi.org/10.1080/01630568208816109
[10]	Iusem, A.N., Pennanen, T. and Svaiter, B.F. (2003) Inexact Variants of the Proximal Point Algorithm without Monotonicity. SIAM Journal on Optimization, 13, 1080-1097. http://dx.doi.org/10.1137/S1052623401399587
[11]	Aragón Artacho, F.J. and Geoffroy, M.H. (2007) Uniformity and Inexact Version of a Proximal Point Method for Metrically Regular Mappings. Journal of Mathematical Analysis and Applications, 335, 168-183. http://dx.doi.org/10.1016/j.jmaa.2007.01.050
[12]	Pennanen, T. (2002) Local Convergence of the Proximal Point Algorithm and Multiplier Methods without Monotonicity. Mathematics of Operations Research, 27, 170-191. http://dx.doi.org/10.1287/moor.27.1.170.331
[13]	Li, C. and Ng, K.F. (2007) Majorizing Functions and Convergence of the Gauss-Newton Method for Convex Composite Optimization. SIAM Journal on Optimization, 18, 613-642. http://dx.doi.org/10.1137/06065622X
[14]	Li, C., Zhang, W.H. and Jin, X.Q. (2004) Convergence and Uniqueness Properties of Gauss-Newton’s Method. Computers & Mathematics with Applications, 47, 1057-1067. http://dx.doi.org/10.1016/S0898-1221(04)90086-7
[15]	He, J.S., Wang, J.H. and Li, C. (2007) Newton’s Method for Underdetermined Systems of Equations under the Modified ?-Condition. Numerical Functional Analysis and Optimization, 28, 663-679. http://dx.doi.org/10.1080/01630560701348509
[16]	Xu, X.B. and Li, C. (2008) Convergence Criterion of Newton’s Method for Singular Systems with Constant Rank Derivatives. Journal of Mathematical Analysis and Applications, 345, 689-701. http://dx.doi.org/10.1016/j.jmaa.2008.04.009
[17]	Rashid, M.H., Yu, S.H., Li, C. and Wu, S.Y. (2013) Convergence Analysis of the Gauss-Newton-Type Method for Lipschitz-Like Mappings. Journal of Optimization Theory and Applications, 158, 216-233. http://dx.doi.org/10.1007/s10957-012-0206-3
[18]	Aubin, J.P. and Frankowska, H. (1990) Set-Valued Analysis. Birkh?user, Boston.
[19]	Rockafellar, R.T. and Wets, R.J-B. (1997) Variational Analysis. Springer-Verlag, Berlin.
[20]	Ioffe, A.D. (2000) Metric Regularity and Subdifferential Calculus. Russian Mathematical Surveys, 55, 501-558. http://dx.doi.org/10.1070/RM2000v055n03ABEH000292
[21]	Dontchev, A.L., Lewis, A.S. and Rockafellar, R.T. (2002) The Radius of Metric Regularity. Transactions of the AMS, 355, 493-517. http://dx.doi.org/10.1090/S0002-9947-02-03088-X
[22]	Dontchev, A.L. and Hager, W.W. (1994) An Inverse Mapping Theorem for Set-Valued Maps. Proceedings of the American Mathematical Society, 121, 481-498. http://dx.doi.org/10.1090/S0002-9939-1994-1215027-7
[23]	Rashid, M.H. (2014) Convergence Analysis of Gauss-Type Proximal Point Method for Variational Inequalities. Open Science Journal of Mathematics and Application, 2, 5-14.