×

The perturbed proximal point algorithm and some of its applications. (English) Zbl 0791.65039

The scope of the paper is to study the proximal point algorithm, i.e. solving the inclusion \(0 \in T \overline x\) by computing a sequence \(\{x^ n\}\) with \(x^{n+1} =(I+\lambda T)^{-1} x^ n\). Here \(T\) is a maximal monotone operator on a Hilbert space \(H\). The main results give conditions under which, if \(x^{n+1} = (I+\lambda T^ n)^{-1} x^ n+e^ n\), where \(T^ n\) is a perturbation of \(T\) and \(e^ n\) is an error term, the sequence still converges to a solution. The size of the perturbation is given in terms of a certain variational matrix. Numerical results are provided.

MSC:

65J15 Numerical solutions to equations with nonlinear operators
65K10 Numerical optimization and variational techniques
47H05 Monotone operators and generalizations
47H10 Fixed-point theorems
49J40 Variational inequalities
90C25 Convex programming
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Alart P (1985) Contribution à la résolution numérique des inclusions différentielles. Thèse de troisième cycle, USTL, Montpellier
[2] Alart P, Lemaire B (to appear) Penalization in nonclassical convex programming via variational convergence. Math Programming · Zbl 0748.90051
[3] Alexandre P (1988) Méthode des centres et pénalités extérieures associées à une méthode proximale en optimisation convexe. Mémoire de licence en informatique, Université de Liège
[4] Attouch H (1984) Variational Convergence for Functions and Operators. Applicable Mathematics Series. Pitman, London · Zbl 0561.49012
[5] Attouch H, Wets RJB (1986) Isometries for the Legendre-Fenchel transform. Trans Amer Math Soc 296(1):33-60 · Zbl 0607.49009
[6] Attouch H, Wets RJB (1987) Quantitative stability of variational systems, I. The epigraphical distance. Technical Report, University of California-Davis
[7] Attouch H, Wets RJB (1987) Quantitative stability of variational systems, II. A framework for nonlinear conditioning. Technical Report, AVAMAC, Université de Perpignan
[8] Attouch H, Wets RJB (1987) Quantitative stability of variational systems, III. ?-Approximate solutions. Report WP-87-25 IIASA, Laxenburg
[9] Auslender A (1987) Numerical methods for non-differentiable convex optimization. Math Programming Stud 30:102-126 · Zbl 0616.90052
[10] Auslender A, Crouzeix JP, Fedit P (1987) Penalty proximal methods in convex programming. J Optim Theory Appl 55(1):1-21 · Zbl 0622.90065
[11] Brezis H (1973) Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert. Studies in Mathematics and Its Applications, vol 5. North-Holland, Amsterdam
[12] Collinet S (1988) Association point proximal et pénalité exponentielle en programmation convexe. Mémoire de licence en informatique, Université de Liège
[13] Fedit P (1985) Contribution aux méthodes numériques en programmation mathématique non différentiable. Thèse de troisième cycle, Université de Clermont II
[14] Ferris M. Weak sharp minima and exact penalty functions. Computer Sciences Technical Report 779, University of Wisconsin, Madison
[15] Gowda S, Teboulle M (1990) A comparison of constraint qualifications in infinite-dimensional convex programming. SIAM J Control Optim 28(4):925-935 · Zbl 0713.49042
[16] Hartung J (1980) On exponential penalty function methods. Math Operationsforsch Statist Ser Optim 11(1):71-84 · Zbl 0514.90077
[17] Kaplan AA (1973) Characteristic properties of penalty functions. Soviet Math Dokl 14(3):849-852 · Zbl 0285.90065
[18] Kaplan AA (1978) On a convex programming method with internal regularization. Soviet Math Dokl 19(4):795-799 · Zbl 0423.90061
[19] Lemaire B (1971) Régularisation et pénalisation en optimisation convexe. Séminaire d’analyse convexe, exposé 17. Institut de Mathématique, USTL, Montpellier
[20] Lemair B (1987) The proximal algorithm. In: New Methods of Optimization and Their Industrial Use (Proc Symp Pau and Paris). International Series of Numerical Mathematics, vol 87. Birkhäuser-Verlag, Basel, pp 73-77
[21] Lemaire B (1988) Coupling optimization methods and variational convergence. In:Trends in Mathematical Optimization (KH Hoffmann, JB Hiriart-Urruty, C Lemarechal, J Zowe, eds). International Series of Numerical Mathematics, vol 84. Birkhäuser-Verlag, Basel, pp 163-179
[22] Martinet B (1972) Algorithmes pour la résolution de problèmes d’optimisation et de minimax. Thèse d’Etat, Université de Grenoble
[23] Minty GJ (1964) On the monotonicity of the gradient of a convex function. Pacific J Math 14:243-247 · Zbl 0123.10601
[24] Mouallif K (1987) Sur la convergence d’une méthode associant pénalisation et régularisation. Bull Soc Roy Sci Liège 56(2):175-180 · Zbl 0641.90065
[25] Mouallif K (1989) Convergence variationnelle et méthodes perturbées pour les problèmes d’optimisation et de point selle. Thèse d’Etat, Université de Liège
[26] Mouallif K, Tossings P (1987) Une méthode de pénalisation exponentielle associée à une régularisation proximale. Bull Soc Roy Sci Liège 56(2): 181-192 · Zbl 0623.90062
[27] Mouallif K, Tossings P (1990) Variational metric and exponential penalization. J Optim Theory Appl 67(1):185-192 · Zbl 0688.90043
[28] Murphy F (1974) A class of exponential penalty functions. SIAM J Control 12(4):679-687 · Zbl 0289.90038
[29] Rockafellar RT (1970) Convex Analysis. Princeton University Press, Princeton, NJ · Zbl 0193.18401
[30] Rockafellar RT (1970) On the maximal monotonicity of subdifferential mappings. Pacific J Math 33(1):209-216 · Zbl 0199.47101
[31] Rockafellar RT (1976) Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math Oper Res 1(2):97-116 · Zbl 0402.90076
[32] Rockafellar RT (1976) Monotone operators and the proximal point algorithm. SIAM J Control Optim 14(5):877-898 · Zbl 0358.90053
[33] Strodiot JJ, Nguyen VH (1979) An exponential penalty method for nondifferentiable minimax problems with general constraints. J Optim Theory Appl 27(2):205-219 · Zbl 0373.90064
[34] Strodiot JJ, Nguyen VH (1988) On the numerical treatment of the inclusion 0??f(x). In: Topics in Nonsmooth Mechanics (JJ Moreau, PD Panagiotopoulos, G Strang, eds). Birkhäuser-Verlag, Basel, pp 267-294
[35] Tossings P (1987-1988) Optimisation convexe. Séminaire d’analyse fonctionnelle appliquée, Université de Liège
[36] Tossings P (1990) Sur l’ordre de convergence de l’algorithme du point proximal perturbé. Bull Soc Roy Sci Liège 58(6):459-466
[37] Tossings P (1990) Sur les zéros des opérateurs maximaux monotones et applications. Thèse d’Etat, Université de Liège
[38] Tossings P (1991) Convergence variationnelle et opérateurs maximaux monotones d’un espace de Hilbert réel. Bull Soc Roy Sci Liège 60(2):103-132 · Zbl 0733.47047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.