Nonconvex Stochastic Programming

In Norkin (1983, 1986a,b), Mikhalevich, Gupal and Norkin (1987), Ermoliev and Norkin (1997, 1998) theory (and methods) of local nonconvex nonsmooth stochastic optimization is developed (see a review paper by Ermoliev and Norkin (2003)). The considered optimization problems consist in minimization of a nonconvex mathematical expectation function under constraints. The consideration is based on a concept of the so-called generalized differentiable function, Norkin (1986b). The class of generalized differentiable functions includes convex and concave functions and is closed with respect to maximum, minimum, superposition and mathematical expectation operations. Such functions appear, for example, in areas of optimization of servicing systems, communication networks and other discrete event systems, Ermoliev and Norkin (1997). There is a calculus of (stochastic) subgradients as measurable selections of multivalued subdifferential mappings for compound generalized differentiable functions. In Mikhalevich, Gupal and Norkin (1987) a number of methods of (stochastic) subgradient type (with projection on the constraint set, stochastic linearization, stochastic reduced subgradient, averaged stochastic subgradient and others) for solving nonconvex nonsmooth stochastic programming problems were developed and investigated. These methods do not require exact calculation of the expectation objective function, but use realizations of random function’s values and (sub)gradients obtained through Monte Carlo simulations.

In Norkin (1993a) the properties of (nonsmooth nonconvex) probability functions and stochastic subgradient methods for their optimization are studied. A probability function represents the probability that some real random variable depending on control parameters exceeds the prescribed threshold. Conditions of (some kind) quasi-concavity are established. Convergence of stochastic subgradient method with additional averaging of stochastic trajectories is established.

Selected references

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

Norkin V.I. (1983).Generalized gradient method in nonconvex nonsmooth optimization, Abstract of Candidate (Ph.D.) Thesis, Glushkov Institute of Cybernetics, Kiev, 1983, 16p. (In Russian).

Norkin V.I. (1986a). On random Lipschitz functions, Kibernetika, 1986, No.2, 66-71,76 (In Russian, English translation in Cybernetics, V. 22, No.2)

Norkin V.I. (1986b). Random generalized differentiable functions in nonconvex nonsmooth stochastic programming problems, Kibernetika, 1986, No.6, 98-102 (In Russian, English translation in Cybernetics, V. 22, No.6, 804-809).

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

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).

Ermoliev Y.M., Norkin V.I. (1997). Om nonsmooth and discontinuous problems of stochastic systems optimization, European J. of Operational Research, 1997, Vol. 101, 230-244.

Norkin V.I. (1993a). The Analysis and Optimization of Probability Functions, Working paper WP-93-6, Int. Inst. for Appl. Syst. Anal., Laxenburg, Austria, 1993.