×

Strict convex regularizations, proximal points and augmented Lagrangians. (English) Zbl 1029.90069

Summary: Proximal Point Methods (PPM) can be traced to the pioneer works of J. Moreau [Bull. Soc. Math. Fr. 93, 273-299 (1965; Zbl 0136.12101)], B. Martinet [Rev. Franç. Inf. Rech. Opér. 4, No. R-3, 154-159 (1970; Zbl 0215.21103); C. R. Acad. Sci., Paris, Sér. A 274, 163-165 (1972; Zbl 0226.47032)] and R. T. Rockafellar [Math. Oper. Res. 1, 97-116 (1976; Zbl 0402.90076); SIAM J. Control Optim. 14, 877-898 (1976; Zbl 0358.90053)] who used as regularization function the square of the Euclidean norm. In this work, we study PPM in the context of optimization and we derive a class of such methods which contains Rockafellar’s result. We also present a less stringent criterion to the acceptance of an approximate solution to the subproblems that arise in the inner loops of PPM. Moreover, we introduce a new family of augmented Lagrangian methods for convex constrained optimization, that generalizes the \(P_E^+\) class presented in [B. Pertsekas, Constrained optimizationa nd Lagrange multipliers. Academic Press, New York (1982; Zbl 0572.90067)].

MSC:

90C30 Nonlinear programming
90C46 Optimality conditions and duality in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI EuDML Link

References:

[1] 1. A. AUSLENDER, R. COMINETTI and M. HADDOU, Asymptotic analysis for penalty and barrier methods in convex and linear programming. Math. Oper. Res. 22 (1997) 43-62. Zbl0872.90067 MR1436573 · Zbl 0872.90067 · doi:10.1287/moor.22.1.43
[2] 2. D. BERTSEKAS, Constrained Optimization and Lagrange Multipliers. Academic Press, New York (1982). MR690767 · Zbl 0572.90067
[3] 3. D. BERTSEKAS, Nonlinear Programming. Athena Scientific (1995). Zbl1015.90077 · Zbl 1015.90077
[4] 4. Y. CENSOR and J. ZENIOS, The proximal minimization algorithms with D-functions. J. Optim. Theory Appl. 73 (1992) 451-464. Zbl0794.90058 MR1164803 · Zbl 0794.90058 · doi:10.1007/BF00940051
[5] 5. J. GAUVIN, A necessary and sufficient condition to have bounded multipliers in nonconvex programming. Math. Programming 12 (1977) 136-138. Zbl0354.90075 MR489903 · Zbl 0354.90075 · doi:10.1007/BF01593777
[6] 6. A.M. GEOFFRION, Duality in non-linear programming, a simplified applications-oriented development. SIAM Rev. 13 (1971) 65-101. Zbl0232.90049 MR280199 · Zbl 0232.90049 · doi:10.1137/1013001
[7] 7. J.-B. HIRIART-URRUTY and C. LEMARÉCHAL, Convex analysis and minimization algorithms. II. Advanced theory and bundle methods. Springer-Verlag, Berlin (1993). Zbl0795.49002 MR1295240 · Zbl 0795.49002
[8] 8. C. HUMES and P. SILVA, An inexact classical proximal point algorithm viewed as a descent method in the optimization case. Technical Report RT-MAC 99-10. Instituto de Matemática e Estatística - USP (1999).
[9] 9. C. Jr. HUMES, Some comments on Lagrangian duality, optimality conditions and convexity. Investigación Oper. 2 (1991) 159-169.
[10] 10. A. IUSEM, Métodos de Ponto Proximal em Otimização. Instituto de Matemática Pura e Aplicada - CNPq (1995). Book from the 20^\circ Colóquio Brasileiro de Matemática.
[11] 11. A. IUSEM and M. TEBOULLE, On the convergence rate of entropic proximal minimization algorithms. Comput. Appl. Math. 12 (1993) 153-168. Zbl0803.90101 MR1268127 · Zbl 0803.90101
[12] 12. A. IUSEM, M. TEBOULLE and B. SVAITER, Entropy-like proximal methods in covex programming. Math. Oper. Res. 19 (1994) 790-814. Zbl0821.90092 MR1304625 · Zbl 0821.90092 · doi:10.1287/moor.19.4.790
[13] 13. P.-J. LAURENT, Approximation et Optimisation. Collection Enseignement des Sciences. Hermann (1972). Zbl0238.90058 MR467080 · Zbl 0238.90058
[14] 14. B. MARTINET, Régularisation d’inéquations variationelles par approximations successives. Rev. Française Inf. Rech. Oper. (1970) 154-159. Zbl0215.21103 MR298899 · Zbl 0215.21103
[15] 15. B. MARTINET, Détermination approché d’un point fixe d’une application pseudo-contractante, C.R. Acad. Sci. Paris 274A (1972) 163-165. Zbl0226.47032 MR290213 · Zbl 0226.47032
[16] 16. J. MOREAU, Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. France 93 (1965) 273-299. Zbl0136.12101 MR201952 · Zbl 0136.12101
[17] 17. R.T. ROCKAFELLAR, Extension of Fenchel’s duality theorem for convex functions. Duke Math. J. 33 (1966) 81-89. Zbl0138.09301 MR187062 · Zbl 0138.09301 · doi:10.1215/S0012-7094-66-03312-6
[18] 18. R.T. ROCKAFELLAR, Convex Analysis. Princeton University Press (1970). Zbl0932.90001 MR274683 · Zbl 0932.90001
[19] 19. R.T. ROCKAFELLAR, Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1 (1976) 97-116. Zbl0402.90076 MR418919 · Zbl 0402.90076 · doi:10.1287/moor.1.2.97
[20] 20. R.T. ROCKAFELLAR, Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 (1976) 887-898. Zbl0358.90053 MR410483 · Zbl 0358.90053 · doi:10.1137/0314056
[21] 21. R.T. ROCKAFELLAR and R.J.-B. WETS, Variational analysis [Fundamental Principles of Mathematical Sciences]. Springer-Verlag, Berlin, Grundlehren Math. Wiss. 317 (1998). Zbl0888.49001 MR1491362 · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3
[22] 22. M. SOLODOV and B. SVAITER, A hybrid projection-proximal point algorithm. J. Convex Anal. 6 (1999). Zbl0961.90128 MR1713951 · Zbl 0961.90128
[23] 23. M. SOLODOV and B. SVAITER, An inexact hybrid extragradient-proximal point algorithm using the enlargement of a maximal monotone operator. Set-Valued Analysis (to appear). Zbl0959.90038 MR1756912 · Zbl 0959.90038 · doi:10.1023/A:1008777829180
[24] 24. M. TEBOULLE, Entropic proximal methods with aplications to nonlinear programming. Math. Oper. Res. 17 (1992) 670-690. Zbl0766.90071 MR1177730 · Zbl 0766.90071 · doi:10.1287/moor.17.3.670
[25] 25. J. TIND and L.A. WOLSEY, An elementary survey of general duality theory in mathematical programming. Math. Programming 20 (1981) 241-261. Zbl0467.90061 MR632634 · Zbl 0467.90061 · doi:10.1007/BF01584248
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.