Computing proximal points of nonconvex functions
Tóm tắt
The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mapping was recently extended to nonconvex functions that are prox-regular and prox-bounded. In such a setting, the proximal point mapping is locally Lipschitz continuous and its set of fixed points coincide with the critical points of the original function. This suggests that the many uses of proximal points, and their corresponding proximal envelopes (Moreau envelopes), will have a natural extension from convex optimization to nonconvex optimization. For example, the inexact proximal point methods for convex optimization might be redesigned to work for nonconvex functions. In order to begin the practical implementation of proximal points in a nonconvex setting, a first crucial step would be to design efficient methods of approximating nonconvex proximal points. This would provide a solid foundation on which future design and analysis for nonconvex proximal point methods could flourish. In this paper we present a methodology based on the computation of proximal points of piecewise affine models of the nonconvex function. These models can be built with only the knowledge obtained from a black box providing, for each point, the function value and one subgradient. Convergence of the method is proved for the class of nonconvex functions that are prox-bounded and lower-
$${\mathcal{C}}^2$$
and encouraging preliminary numerical testing is reported.
Tài liệu tham khảo
Auslender A. (1987). Numerical methods for nondifferentiable convex optimization. Math. Program. Stud. 30: 102–126
Auslender A., Crouzeix J.P. and Fedit P. (1987). Penalty-proximal methods in convex programming. J. Optim. Theory Appl. 55(1): 1–21
Auslender A. and Haddou M. (1995). An interior-proximal method for convex linearly constrained problems and its extension to variational inequalities. Math. Program. 71(1, Ser. A): 77–100
Bellman R., Kalaba R. and Lockett J. (1966). Numerical Inversion of the Laplace Transform. Elsevier, Amsterdam
Bernard F. and Thibault L. (2004). Prox-regularity of functions and sets in Banach spaces. Set Valued Anal. 12(1-2): 25–47
Bernard F. and Thibault L. (2005). Prox-regular functions in Hilbert spaces. J. Math Anal. Appl. 303(1): 1–14
Bonnans J.F., Gilbert J., Lemaréchal C. and Sagastizábal C. (1995). A family of variable metric proximal methods. Math. Program. Ser. A 68: 15–47
Cominetti R. and Courdurier M. (2003). Coupling general penalty schemes for convex programming with the steepest descent and the proximal point algorithm. SIAM J. Optim. 13(3): 745–765 (electronic)
Correa R. and Lemaréchal C. (1993). Convergence of some algorithms for convex minimization. Math. Program. 62(2): 261–275
Dolan E. and Moré J. (2002). Benchmarking optimization software with performance profiles. Math. Program. 91(2, Ser. A): 201–213
Eckstein J. (1993). Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Math. Oper. Res. 18: 202–226
Frangioni A. (1996). Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. 23(11): 1099–1118
Fuduli A., Gaudioso M. and Giallombardo G. (2003). Minimizing nonconvex nonsmooth functions via cutting planes and proximity control. SIAM J. Optim. 14(3): 743–756 (electronic)
Güler O. (1992). New proximal point algorithms for convex minimization. SIAM J. Optim. 2: 649–664
Hare, W., Lewis, A.: Identifying active contraints via partial smoothness and prox-regularity. J. Convex Anal. 11, 251–266
Hiriart-Urruty, J.B., Lemaréchal, C.: Convex Analysis and Minimization Algorithms. No. 305–306 in Grund. der math. Wiss. Springer, Heidelberg (two volumes, 1993)
Kiwiel K. (1986). A method for solving certain quadratic programming problems arising in nonsmooth optimization. IMA J. Numer. Anal. 6: 137–152
Kiwiel K. (1991). Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization. Math. Program. 52(2, Ser. B): 285–302
Lemaréchal C. and Sagastizábal C. (1997). Variable metric bundle methods: from conceptual to implementable forms. Math. Program. Ser. A 76: 393–410
Lemaréchal C., Strodiot J.J. and Bihain A. (1981). On a bundle method for nonsmooth optimization. In: Mangasarian, O., Meyer, R., and Robinson, S. (eds) Nonlinear Programming, vol. 4, pp 245–282. Academic, New York
Lukšan L. and Vlček J. (1998). A bundle-Newton method for nonsmooth unconstrained minimization. Math. Program. 83(3, Ser. A): 373–391
Lukšan L. and Vlček J. (2001). Globally convergent variable metric method for nonconvex nondifferentiable unconstrained minimization. J. Optim. Theory Appl. 2: 407–430
Makela, M., Neittaanmaki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific, Singapore (1992)
Martinet B. (1970). Régularisation d’inéquations variationnelles par approximations successives. Rev. Française Informat. Recherche Opérationnelle 4(Ser. R-3): 154–158
Mifflin R. (1977). Semi-smooth and semi-convex functions in constrained optimization. SIAM J. Control Optim. 15: 959–972
Mifflin, R.: Convergence of a modification of lemaréchal’s algorithm for nonsmooth optimization. In: Progress in Nondifferentiable Optimization, IIASA Collaborative Proc., vol. 8, pp. 85–95. (Ser. CP-82) (1982)
Mifflin R. (1982). A modification and extension of Lemaréchal’s algorithm for nonsmooth minimization. Math. Program. Stud. 17: 77–90
Mifflin R. and Sagastizábal C. (2003). Primal-dual gradient structured functions: second-order results; links to epi-derivatives and partly smooth functions. SIAM J. Optim. 13(4): 1174–1194
Mifflin R., Sagastizábal C. (2004) \({\mathcal{VU}}\) -smoothness and proximal point results for some nonconvex functions. Optim. Meth. Softw. 19(5): 463–478
Mordukhovich B.S. (1976). Maximum principle in the problem of time optimal response with nonsmooth constraints. Prikl. Mat. Meh. 40(6): 1014–1023
Moreau J. (1965). Proximité et dualité dans un espace Hilbertien. Bulletin de la Société Mathématique de France 93: 273–299
Poliquin R.A. and Rockafellar R.T. (1996). Generalized Hessian properties of regularized nonsmooth functions. SIAM J. Optim. 6(4): 1121–1137
Poliquin R.A. and Rockafellar R.T. (1996). Prox-regular functions in Variational Analysis. Trans. Am. Math. Soc. 348(5): 1805–1838
Popova, N., Tarasov, V.: A modification of the cutting-plane method with accelerated convergence. In: Nondifferentiaible Optimization: Motivations and application, Lecture Notes in Economics and Mathematical Systems, pp. 284–290 (1984)
Rockafellar R. (1976). Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1: 97–116
Rockafellar R. (1976). Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14: 877–898
Rockafellar, R., Wets, R.B.: Variational Analysis. No. 317 in Grund. der math. Wiss. Springer, Heidelberg (1998)
Yosida K. (1964) Functional Analysis. Springer, Heidelberg