×

A unified framework for some inexact proximal point algorithms. (English) Zbl 1052.49013

Summary: We present a unified framework for the design and convergence analysis of a class of algorithms based on approximate solution of proximal point subproblems. Our development further enhances the constructive approximation approach of the recently proposed hybrid projection-proximal and extragradient-proximal methods. Specifically, we introduce an even more flexible error tolerance criterion, as well as provide a unified view of these two algorithms. Our general method possesses global convergence and local (super)linear rate of convergence under standard assumptions, while using a constructive approximation criterion suitable for a number of specific implementations. For example, we show that close to a regular solution of a monotone system of semismooth equations, two Newton iterations are sufficient to solve the proximal subproblem within the required error tolerance. Such systems of equations arise naturally when reformulating the nonlinear complementarity problem.

MSC:

49J40 Variational inequalities
47J20 Variational and other types of inequalities involving nonlinear operators (general)
65J15 Numerical solutions to equations with nonlinear operators
90C25 Convex programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)
90C48 Programming in abstract spaces
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] DOI: 10.1287/moor.26.2.248.10558 · Zbl 1082.65058
[2] DOI: 10.1090/S0002-9904-1975-13874-2 · Zbl 0332.49005
[3] Burachik R. S., Tech. Rep. 02/96 (1996)
[4] DOI: 10.1023/A:1008615624787 · Zbl 0882.90105
[5] Burachik R. S., Ill-posed variational problems and regularization techniques pp 49– (1999)
[6] Burachik R. S., Reformulation – Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods pp 25– (1999)
[7] DOI: 10.1023/A:1008730230603 · Zbl 0948.47050
[8] DOI: 10.1137/S0363012992235547 · Zbl 0918.90112
[9] Clarke F. H., Optimization and Nonsmooth Analysis (1983) · Zbl 0582.49001
[10] DOI: 10.1023/A:1022621905645 · Zbl 0902.90129
[11] DOI: 10.1137/0719025 · Zbl 0478.65030
[12] DOI: 10.1007/BF02680553 · Zbl 0920.90117
[13] Ferris M. C., Handbook of Applied Optimization (2000)
[14] DOI: 10.1007/BF02614396 · Zbl 0871.90097
[15] DOI: 10.1007/BF01585696 · Zbl 0756.90081
[16] Fukushima M., Reformulation – Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods (1999)
[17] DOI: 10.1016/S0168-2024(08)70034-1
[18] DOI: 10.1137/0329022 · Zbl 0737.90047
[19] DOI: 10.1016/S0167-6377(98)00023-6 · Zbl 0941.90070
[20] Lemaire B., New Methods of Optimization and Their Industrial Use. International Series of Numerical Mathematics 87 pp 73– (1989)
[21] DOI: 10.1023/A:1008705425484 · Zbl 0964.90046
[22] DOI: 10.1137/0315061 · Zbl 0376.90081
[23] DOI: 10.1090/S0002-9904-1967-11761-0 · Zbl 0179.19902
[24] DOI: 10.1007/BF02591989 · Zbl 0613.90097
[25] Pang J.-S., Handbook of Global Optimization pp 271– (1995)
[26] DOI: 10.1007/BF01580617 · Zbl 0808.90123
[27] DOI: 10.1137/0803021 · Zbl 0784.90082
[28] DOI: 10.1287/moor.18.1.227 · Zbl 0776.65037
[29] DOI: 10.1007/BF01581275 · Zbl 0780.90090
[30] Robinson S. M., Mathematical Programming Study 30 pp 45– (1987) · Zbl 0629.90079
[31] DOI: 10.1137/0314056 · Zbl 0358.90053
[32] Sagastizábal C. A., Inherently Parallel Algorithms in Feasibility and Optimization and their Applications, volume 8 of Studies in Computational Mathematics pp 441– (2001)
[33] Sibony M., Calcolo 7 pp 65– (1970) · Zbl 0225.35010
[34] DOI: 10.1137/S0363012997317475 · Zbl 0959.49007
[35] DOI: 10.1137/S1052623498337546 · Zbl 0955.90133
[36] Solodov M. V., Reformulation – Nonsmooth, Piecewise Smooth, Semismooth and Smoothing Methods pp 355– (1999)
[37] DOI: 10.1023/A:1008777829180 · Zbl 0959.90038
[38] Solodov M. V., Journal of Convex Analysis 6 pp 59– (1999)
[39] DOI: 10.1007/s101070050022
[40] Solodov M. V., Mathematical Programming 87 pp 189– (2000)
[41] DOI: 10.1287/moor.25.2.214.12222 · Zbl 0980.90097
[42] DOI: 10.1007/BF01204180 · Zbl 0791.65039
[43] DOI: 10.1007/BF01582258 · Zbl 0725.90079
[44] DOI: 10.1137/S0363012998338806 · Zbl 0997.90062
[45] Zhao Y.-B., SIAM Journal on Optimization 11 pp 962– (2001) · Zbl 1010.90084
[46] DOI: 10.1137/S1052623494250415 · Zbl 0855.47043
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.