Nonsmooth/Nondifferentiable optimization

In Norkin (1978, 1980a) the so-called generalized differentiable functions were introduced and in Norkin (1978, 1980b), Mikhalevich, Gupal and Norkin (1987), Ermoliev and Norkin (1998) theory and methods of their local optimization was developed. Generalized differentiable functions enjoy many nice properties that make them a convenient model of nonconvexity and nonsmoothness in optimization problems. While a differentiable function f(y) admits a linear expansion at a given point x, i.e. f(y)=f(x)+<g(x),y-x>+o(x,|y-x|), a generalized differentiable function f(y) admits a qusilinear expansion, f(y)=f(x)+<g(y),y-x>+o(x,y,g) with (sub)gradients g taken not at x but at an evaluation point y. The class of generalized differentiable functions includes continuously differentiable, convex, concave, semismooth functions and is closed with respect to maximum, minimum, superposition and mathematical expectation operations. Generalized differentiable functions are locally Lipschitzian and may have no directional derivatives. Such kind of functions spring into being, for example, in areas of optimization of servicing systems, communication networks and other discrete event systems. They are used for construction of Newton’s type methods to solve generalized equations. There is a calculus of subgradients for compound generalized differentiable functions. In Mikhalevich, Gupal and Norkin (1987), Ermoliev and Norkin (1998) many methods of subgradient type (with projection on the constraint set, stochastic linearization, stochastic reduced subgradient, averaged subgradient and others) for solving nonconvex nonsmooth constrained optimization problems were developed and investigated.

In Gupal and Norkin (1977), Ermoliev , Norkin and Wets (1995), Ermoliev and Norkin (1998, 2004) we develop a stochastic smoothing approach to optimization of generally discontinuous functions by means of their approximation by smooth mollified (averaged) functions. The idea of the approach consists in approximation of the original problem by a family of nonconvex stochastic optimization problems and application to approximate problems all the technique developed in stochastic programming (methods of calculation of stochastic gradients without the exact calculation of multidimensional integrals, the technique of the nonconvex stochastic second Lyapunov method for the proof of convergence a.s. of stochastic approximation algorithms, acceleration technique for stochastic optimization methods, nonstationary stochastic optimization technique). Besides, in Ermoliev , Norkin and Wets (1995), Ermoliev and Norkin (1998, 2004) mollified (averaged) functions are employed to construct (mollifier) subdifferentials of discontinuous functions. The last concept has appeared as a result of application of ideas of distribution theory by L.Schwartz (or generalized function by S.Sobolev) to the range of nonsmooth optimization where quite different approaches have been used before. Optimality conditions in terms of mollifier subdifferentials of discontinuous functions are established. Convergence of the approximation scheme is proved, i.e. the convergence of minimums of approximation problems to minimums of the original problem. Convergence a.s. of stochastic finite-difference procedures for optimization of discontinuous functions is proved.

Selected references

Mikhalevich V.S., Gupal A.M. and Norkin V.I. Methods of Nonconvex Optimization (Abstract), Nauka, Moscow, 1987, 280 p. (In Russian).

Ermoliev Y.M., Norkin V.I. (2003). Methods for solution of nonconvex nonsmooth stochastic optimization problems, Kibernetika i sistemnyi analiz (in Russian, English translation in Cybernetics and Systems Analysis), 2003, N 5, 60-81.

Ermoliev Y.M., Norkin V.I. (1998). Stochastic generalized gradient method for solving nonconvex nonsmooth stochastic optimization problems, Kibernetika i sistemny analiz, 1998, N 2, 50-71 (see also IIASA Interim Report IR-97-021 , Abstract; English translation in Cybernetics and systems analysis, V. 34, N 2).

Norkin V.I. (1978). Nonlocal algorithms for minimization of nondifferentiable functions, Kibernetika, 1978, No.5, 44-48 (In Russian, English translation in Cybernetics, V. 14, No.5).

Norkin V.I. (1980a).Generalized differentiable functions, Kibernetika, 1980, No.1, 9-11 (In Russian, English translation in Cybernetics, V. 16, No.1)

Norkin V.I. (1980b). Nondifferentiable function minimization method with averaging of generalized gradients, Kibernetika, 1980, No.6, 88-89 (In Russian, English translation in Cybernetics, 1980, V. 16, No.6)

Gupal A.M. and Norkin V.I. (1977). Minimization algorithms for discontinues functions, Kibernetika, 1977, No.2, 101-107 (In Russian, English translation in Cybernetics, V. 13, No.2).

Ermoliev Yu.M., Norkin V.I. and Wets R.J-B. (1995). The minimization of semicontinuous functions: Mollifier subgradients, SIAM Journal on Control and Optimization, 1995, N 1, 149-167.

Ermoliev Y.M. and Norkin V.I. (1998). On Constrained Discontinuous Optimization, Proceedings of 3rd GAMM/IFIP Workshop (Neubiberg/Munchen, 1996), Stochastic optimization: Numerical methods and technical applications, Lecture Notes in Economics and Mathematical Systems 458, Berlin, Springer, 1998, 128-142.

Ermoliev Y.M., Norkin V.I. (2004). Stochastic Optimization of Risk Functions via Parametric Smoothing, in Dynamic Stochastic Optimization, Eds. K.Marti, Y.Ermoliev and G.Pflug, Lecture Notes in Economics and Mathematical Systems 532, Springer, 2004, 225-247; see also IIIASA Interim Report IR-03-033).