zbMATH — the first resource for mathematics

Computing proximal points of nonconvex functions. (English) Zbl 1168.90010
From authors’ abstract: The proximal point mapping is the basis of many optimization techniques for convex functions. By means of variational analysis, the concept of proximal mappings 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-\(C^2\) and encouraging preliminary numerical testing is reported.

90C26 Nonconvex programming, global optimization
49J52 Nonsmooth analysis
65K10 Numerical optimization and variational techniques
49J53 Set-valued and variational analysis
49M05 Numerical methods based on necessary conditions
Full Text: DOI
[1] Auslender A. (1987). Numerical methods for nondifferentiable convex optimization. Math. Program. Stud. 30: 102–126 · Zbl 0616.90052
[2] Auslender A., Crouzeix J.P. and Fedit P. (1987). Penalty-proximal methods in convex programming. J. Optim. Theory Appl. 55(1): 1–21 · Zbl 0622.90065 · doi:10.1007/BF00939042
[3] 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 · Zbl 0855.90095
[4] Bellman R., Kalaba R. and Lockett J. (1966). Numerical Inversion of the Laplace Transform. Elsevier, Amsterdam · Zbl 0147.14003
[5] Bernard F. and Thibault L. (2004). Prox-regularity of functions and sets in Banach spaces. Set Valued Anal. 12(1-2): 25–47 · Zbl 1046.49009 · doi:10.1023/B:SVAN.0000023403.87092.a2
[6] Bernard F. and Thibault L. (2005). Prox-regular functions in Hilbert spaces. J. Math Anal. Appl. 303(1): 1–14 · Zbl 1085.49020 · doi:10.1016/j.jmaa.2004.06.003
[7] 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 · Zbl 0832.90102
[8] 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) · Zbl 1049.90056 · doi:10.1137/S1052623401397242
[9] Correa R. and Lemaréchal C. (1993). Convergence of some algorithms for convex minimization. Math. Program. 62(2): 261–275 · Zbl 0805.90083 · doi:10.1007/BF01585170
[10] Dolan E. and Moré J. (2002). Benchmarking optimization software with performance profiles. Math. Program. 91(2, Ser. A): 201–213 · Zbl 1049.90004 · doi:10.1007/s101070100263
[11] Eckstein J. (1993). Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming. Math. Oper. Res. 18: 202–226 · Zbl 0807.47036 · doi:10.1287/moor.18.1.202
[12] Frangioni A. (1996). Solving semidefinite quadratic problems within nonsmooth optimization algorithms. Comput. Oper. Res. 23(11): 1099–1118 · Zbl 0871.90059 · doi:10.1016/0305-0548(96)00006-8
[13] 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) · Zbl 1079.90105 · doi:10.1137/S1052623402411459
[14] Güler O. (1992). New proximal point algorithms for convex minimization. SIAM J. Optim. 2: 649–664 · Zbl 0778.90052 · doi:10.1137/0802032
[15] Hare, W., Lewis, A.: Identifying active contraints via partial smoothness and prox-regularity. J. Convex Anal. 11, 251–266 · Zbl 1178.90314
[16] 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)
[17] Kiwiel K. (1986). A method for solving certain quadratic programming problems arising in nonsmooth optimization. IMA J. Numer. Anal. 6: 137–152 · Zbl 0603.65041 · doi:10.1093/imanum/6.2.137
[18] Kiwiel K. (1991). Exact penalty functions in proximal bundle methods for constrained convex nondifferentiable minimization. Math. Program. 52(2, Ser. B): 285–302 · Zbl 0754.90045 · doi:10.1007/BF01582892
[19] Lemaréchal C. and Sagastizábal C. (1997). Variable metric bundle methods: from conceptual to implementable forms. Math. Program. Ser. A 76: 393–410 · Zbl 0872.90072
[20] 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 · Zbl 0533.49023
[21] Lukšan L. and Vlček J. (1998). A bundle-Newton method for nonsmooth unconstrained minimization. Math. Program. 83(3, Ser. A): 373–391 · Zbl 0920.90132
[22] 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 · Zbl 1029.90060
[23] Makela, M., Neittaanmaki, P.: Nonsmooth Optimization: Analysis and Algorithms with Applications to Optimal Control. World Scientific, Singapore (1992)
[24] 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
[25] Mifflin R. (1977). Semi-smooth and semi-convex functions in constrained optimization. SIAM J. Control Optim. 15: 959–972 · Zbl 0376.90081 · doi:10.1137/0315061
[26] 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) · Zbl 0502.65039
[27] Mifflin R. (1982). A modification and extension of Lemaréchal’s algorithm for nonsmooth minimization. Math. Program. Stud. 17: 77–90 · Zbl 0476.65047
[28] 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 · Zbl 1036.90067 · doi:10.1137/S1052623402412441
[29] Mifflin R., Sagastizábal C. (2004) \({\mathcal{VU}}\) -smoothness and proximal point results for some nonconvex functions. Optim. Meth. Softw. 19(5): 463–478 · Zbl 1097.90059 · doi:10.1080/10556780410001704902
[30] Mordukhovich B.S. (1976). Maximum principle in the problem of time optimal response with nonsmooth constraints. Prikl. Mat. Meh. 40(6): 1014–1023 · Zbl 0362.49017
[31] Moreau J. (1965). Proximité et dualité dans un espace Hilbertien. Bulletin de la Société Mathématique de France 93: 273–299 · Zbl 0136.12101
[32] Poliquin R.A. and Rockafellar R.T. (1996). Generalized Hessian properties of regularized nonsmooth functions. SIAM J. Optim. 6(4): 1121–1137 · Zbl 0863.49010 · doi:10.1137/S1052623494279316
[33] Poliquin R.A. and Rockafellar R.T. (1996). Prox-regular functions in Variational Analysis. Trans. Am. Math. Soc. 348(5): 1805–1838 · Zbl 0861.49015 · doi:10.1090/S0002-9947-96-01544-9
[34] 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)
[35] Rockafellar R. (1976). Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1: 97–116 · Zbl 0402.90076 · doi:10.1287/moor.1.2.97
[36] Rockafellar R. (1976). Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14: 877–898 · Zbl 0358.90053 · doi:10.1137/0314056
[37] Rockafellar, R., Wets, R.B.: Variational Analysis. No. 317 in Grund. der math. Wiss. Springer, Heidelberg (1998)
[38] Yosida K. (1964) Functional Analysis. Springer, Heidelberg · Zbl 0152.32102
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.