zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.

MSC:
90C26Nonconvex programming, global optimization
49J52Nonsmooth analysis (other weak concepts of optimality)
65K10Optimization techniques (numerical methods)
49J53Set-valued and variational analysis
49M05Numerical methods in calculus of variations based on necessary conditions
Software:
PNEW
References:
[1]Auslender A. (1987). Numerical methods for nondifferentiable convex optimization. Math. Program. Stud. 30: 102–126
[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
[4]Bellman R., Kalaba R. and Lockett J. (1966). Numerical Inversion of the Laplace Transform. Elsevier, Amsterdam
[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
[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
[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
[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
[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
[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
[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)
[27]Mifflin R. (1982). A modification and extension of Lemaréchal’s algorithm for nonsmooth minimization. Math. Program. Stud. 17: 77–90
[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) 𝒱𝒰 -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
[31]Moreau J. (1965). Proximité et dualité dans un espace Hilbertien. Bulletin de la Société Mathématique de France 93: 273–299
[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