11institutetext: V.M.Glushkov Institute of Cybernetics, National Academy of
Sciences of Ukraine, Kyiv, 03178 Ukraine 22institutetext: Igor Sikorsky Kyiv
Polytechnic Institute, National Technical University of Ukraine, Kyiv, 03056,
Ukraine 33institutetext: Department of Mathematics, Chemnitz University of
Technology, Chemnitz, 09126, Germany

# Constrained Global Optimization by Smoothing††thanks: Supported by the
Volkswagen Foundation (Az.: 9C090, 2022), the German Research Foundation
(Project 416228727–SFB 1410), and the National Research Fund of Ukraine
(Project 2020.02/0121).

Vladimir Norkin 11 2 2 Alois Pichler 33 Anton Kozyriev 22

###### Abstract

This paper proposes a novel technique called ”successive stochastic smoothing”
that optimizes nonsmooth and discontinuous functions while considering various
constraints. Our methodology enables local and global optimization, making it
a powerful tool for many applications. First, a constrained problem is reduced
to an unconstrained one by the exact nonsmooth penalty function method, which
does not assume the existence of the objective function outside the feasible
area and does not require the selection of the penalty coefficient. This
reduction is exact in the case of minimization of a lower semicontinuous
function under convex constraints. Then the resulting objective function is
sequentially smoothed by the kernel method starting from relatively strong
smoothing and with a gradually vanishing degree of smoothing. The finite
difference stochastic gradient descent with trajectory averaging minimizes
each smoothed function locally. Finite differences over stochastic directions
sampled from the kernel estimate the stochastic gradients of the smoothed
functions. We investigate the convergence rate of such stochastic finite-
difference method on convex optimization problems. The ”successive smoothing”
algorithm uses the results of previous optimization runs to select the
starting point for optimizing a consecutive, less smoothed function. Smoothing
provides the ”successive smoothing” method with some global properties. We
illustrate the performance of the ”successive stochastic smoothing” method on
test-constrained optimization problems from the literature.

###### Keywords:

Constrained global optimization Exact penalty Smoothing Finite-difference
stochastic gradient.

##  1 Introduction

Global optimization is a relevant area of research. It is the subject of a
large number of articles in the fundamental encyclopedia of optimization [17],
as well as of recent monographs [23, 40, 43] among others. Most global
optimization methods are designed to optimize Lipschitz or smooth functions.
The focus of the present paper is on optimization of non-Lipschitzian
continuous as well as discontinuous functions, where gradient and subgradient
methods have no sense.

The need for global optimization of nonsmooth and discontinuous functions
arises in many applications: optimal control in parametric strategies [18,
sec. 15.1.3], [2, 26], training neural networks with discontinuous activation
functions [27] and neural networks with categorical features [44], engineering
optimization [9, 24, 45], probability optimization with discrete distribution,
lexicographic optimization, two-level optimization. Note that difficult
continuous problems with nonconvex inequality constraints can simply be
reduced to unconditional discontinuous optimization problems using exact
discontinuous penalty functions [3].

Relatively few ideas and methods are used for global optimization of
discontinuous functions: branch and bound methods, group random search methods
(genetic algorithms, simulated annealing), Nelder-Mead method, approximation
and smoothing methods. Problems of discontinuous optimization with constraints
are generally little discussed.

In a number of works, V.D. Batukhtin with co-authors [2], [3] proposed an
approximate method for optimizing discontinuous functions, in which the
original function is locally approximated by linear functions and is minimized
by generalized gradient methods that use gradients of linear approximations.
In these works, the theory of generalized approximation gradients of
discontinuous functions is also constructed and the necessary optimality
conditions are obtained.

In [21, 30] a smoothing method was developed and substantiated for local
unconstrained optimization of non-smooth Lipschitz functions and in [15, 22]
it was extended to discontinuous functions. In this method, the initial
function is approximated by a sequence of smooth averaged functions, and
iterative stochastic optimization methods are used for local optimization of
the latter. In [15] the theory of generalized mollified gradients of
discontinuous functions is constructed, connections with other known concepts
of generalized gradients are investigated and necessary optimality conditions
are obtained. The advantage of the proposed smoothing method is its geometric
transparency and the possibility to apply stochastic gradient methods to
optimization of nonconvex non-smooth and discontinuous functions.

But the disadvantage of both approaches, approximation and smoothing, is their
local nature, i.e., focusing on finding local minima.

In this article, we further develop the smoothing method to solve global
nonsmooth and discontinuous optimization problems under general (basically
convex) constraints. Previously, we reduce the problem of conditional
optimization to a problem of unconstrained optimization by exact penalty
function methods. The smoothing method was invented by V. Steklov (W.
Stekloff) [42] and has long been used in analysis and computational
mathematics [7, 15]. In the works [21, 29, 30] local Steklov smoothing, i.e.
averaging over hypercubes was used to study and optimize non-smooth Lipschitz
functions by stochastic finite-difference methods. To ensure the local
convergence of the method to stationary points of the optimization problem,
the smoothing parameter is directed to zero in coordination with steps of the
method. Subsequently, the finite-difference methods of local optimization by
the idea of smoothing were considered, for example, in the works [12, 34, 41].
In these methods usually the smoothing parameter is kept fixed and/or quite
small, i.e. smoothing is used just for local smoothing.

The important difference between the above mentioned works and the present
article is that the latter uses an iterative variable smoothing, starting with
a fairly large smoothing parameter and ending with a small parameter. This
strategy of changing the smoothing parameter gives the method some global
properties (see [30, pp. 135-137], [35]). As the smoothing parameter
decreases, the averaging functions uniformly or graphically approximate the
original function, so the minima of the approximate functions approach to the
minima of the original function. Regarding global optimization, the idea of
the smoothing method is that smoothing eliminates shallow small local minima
and does not much change the deep minima.

One more interesting application of the smoothing idea in optimization was
proposed in [1, 5]. The authors described the behavior of critical points of
the Steklov smoothed functions when changing the smoothing parameter by a
system of ordinary differential equations. If one takes as a starting point a
global minimum of a strongly smoothed function, then by solving these
equations one potentially can go over a critical curve to a global minimum of
the original function. Remark that this idea was also discussed in [30, pp.
135-137], [35]. However, this differentiable path following approach can only
be applied to the unconditional global optimization of functions given by
analytical expressions, for example, for polynomial functions.

In this paper, we propose a successive stochastic smoothing method combined
with critical path following for optimization of continuous and discontinuous
functions under constraints. The structure of the proposed approach is the
following.

First, the constrained problem is reduced an unconstrained one by some exact
penalty function method. In particular, it is proposed to use the exact
penalty method from [19, 35]. The method does not require the existence of the
objective function outside the feasible domain and does not require selection
of penalty coefficient. Discontinuous exact penalty functions can also be
employed [3].

For optimization of the obtained penalized unconstrained problems we use a
successive kernel smoothing method with gradual vanishing of the smoothing
parameter. Here kernel can be any probability density function dependent on
smoothing (width) parameter. The local convergence of the method is
theoretically validated for the case of non-Lipschitz continuous functions and
for the so-called strongly lower semicontinuous functions [15].

For the practical implementation of the smoothing method we exploit a
stochastic finite-difference representation of gradients of the smoothed
functions as in [42, 21, 30, 34, 41], namely we use central finite differences
in random directions as in [34, 41]. Having such finite difference stochastic
gradients, one can use contemporary stochastic optimization methods [4, 11,
12, 25, 31] for the optimization of the smoothed functions. In particular we
use stochastic finite-difference gradient method with trajectory averaging
[31] and with batch estimation of stochastic gradients.

In the literature (see, e.g., [34, 41]) the described approach is applied to
the local optimization of nonsmooth Lipschitzian or smooth convex functions.
In the present paper we extend this approach to optimization of non-
Lipschtzian continuous and discontinuous functions under convex constraints.
An important difference of our modification of the approach is that we
minimize a sequence of the smooth approximating functions starting from rough
approximations and moving to more and more accurate approximations. This
strategy provides the method some global properties as explained in [35], the
method avoids some shallow local minima. Another important element of our
method is critical path following, when transition from the minimum point of
one smoothed function to an initial point for the minimization of another
smoothed function is carried out by the Gelfand-Zetlin-Nesterov valley step
(cf. [20, 33]).

We also evaluate the performance of the proposed method on nonsmooth
Lipschitzian convex functions. We show that in this case the rate of
convergence is (roughly) proportional to $\sqrt{n/(Kt)}$, where $t$ is the
iteration number, $n$ is the dimension of the problem space, $K$ is the batch
size when estimating the stochastic gradients. This rate of convergence
corresponds to results of [34, 41].

##  2 Reduction of a constrained optimization problem to an unconstrained one
by exact penalty function methods

Let it be necessary to solve a conditional global optimization problem:

$f(x)\to\underset{x\in D\subseteq\mathbb{R}^{n}}{\mathop{\min}},$ (1)

where $f(x)$ is a lower semicontinuous function defined on a closed set
$D\subseteq\mathbb{R}^{n}$ such that $f(x)\to+\infty$ as
$\left\|x\right\|\to+\infty$ and $x\in D$ ; ${\mathbb{R}}^{n}$ is
$n$-dimensional Euclidean space; $\left\|\cdot\right\|$ is some norm in
${{\mathbb{R}}^{n}}$.

To apply smoothing method for constrained optimization problems without having
irregularities on boundaries, we first reduce the problem to an unconstrained
one. There are several ways to do this. For example, if

$D=\left\\{x|{{g}_{j}}(x)\leq
0,\,j=1,...,J\,;\,\,{{h}_{k}}(x)=0,\,k=1,...,K\right\\}$

then in the exact penalty function method, the Lipschitz function $f(x)$ is
replaced by functions:

$\Phi_{1}(x):=f\left(x\right)+M\left(\sum\nolimits_{j}{\max\left\\{0,{{g}_{j}}(x)\right\\}}+\sum\nolimits_{k}{\left|{{h}_{k}}(x)\right|}\right),$
$\Phi_{2}(x):=f\left(x\right)+M\rho_{D}(x),\;\;\;\;\;\rho_{D}(x)={{\inf}_{y\in
D}}\left\|y-x\right\|,$

with a sufficiently large penalty multiplier $M$ and then consider the problem
of unconditional optimization $\Phi_{i}(x),\;i=1,2,$ (cf. [38, Proposition
9.68]). Here it is assumed that the functions $f,{{g}_{j}},{{h}_{k}}$ are
defined over the whole space ${{\mathbb{R}}^{n}}$.

Let $f:D\to{{\mathbb{R}}^{1}}$ and the set $D\subseteq{{\mathbb{R}}^{n}}$ in
(1) is convex and closed, i.e., in the representation
$D=\left\\{x|{{g}_{j}}(x)\leq
0,\,j=1,...,J\,;\,\,{{h}_{k}}(x)=0,\,k=1,...,K\right\\}$ functions ${{g}_{j}}$
are continuous and convex, and ${{h}_{k}}$ are linear. Denote ${{\pi}_{D}}(x)$
the projection of the point $x$ on the set $D$. For a simple set $D$ given by
linear constraints, the problem of searching projection ${{\pi}_{D}}(x)$ is
either solved analytically or reduced to a quadratic programming problem. We
introduce penalty functions [19, 35, 36]:

$F_{1}(x):=f\left({{\pi}_{D}}(x)\right)+M\left(\sum\nolimits_{j=1}^{J}{\max\left\\{0,{{g}_{j}}(x)\right\\}}+\sum\nolimits_{k=1}^{K}{\left|{{h}_{k}}(x)\right|}\right),$
(2) $F_{2}(x):=f\left({\pi}_{D}(x)\right)+M\rho_{D}(x),\;\;\;\;M>0,$ (3)

and consider the unconstrained optimization problems:

$F_{i}(x)\to\min_{x\in\mathbb{R}^{n}},\;\;\;i=1,2...$ (4)

Note that in (2), (3) function $f$ may not be defined outside the feasible set
$D$.

###### Lemma 1

[19]. Let function $f$ be lower semicontinuous on a non-empty closed convex
set $D$, $M>0$. Then problems (1) and (4) are equivalent, i.e., each local
(global) minimum of one problem is a local (global) minimum of the another,
and the optimal values of the problems in the corresponding minima coincide.

###### Remark 1

If $D$ is a convex closed set, then function ${{\rho}_{D}}(x)$ is continuous
[38, Example 1.20] and the mapping ${{\pi}_{D}}(x)$ is single valued and
continuous on ${{\mathbb{R}}^{n}}$ [38, Example 2.25]. If function $f$ is
continuous (lower semicontinuous) on a convex closed set $D$, then function
(3) is continuous (lower semicontinuous) on $\mathbb{R}^{n}$.

###### Lemma 2

[19]. If function $f$ is Lipschitzian with constant $L$ on a convex set $D$,
then the function $F_{2}(x)$ defined by equality (3) is also Lipschitzian with
constant $(L+2M)$ on the whole space ${{\mathbb{R}}^{n}}$.

If some admissible point ${{x}_{0}}\in D$ is known, then the exact penalty
function can be constructed as follows [35, 36]. Let $x\notin D$ and $y(x)$ be
the nearest to $x$ point from the set $D$ lying on the segment connecting
${{x}_{0}}$ and $x$. Let us define the mapping

${p}_{D}(x)=\left\\{\begin{matrix}x,&x\in D,\\\ y(x),&x\notin D,\\\
\end{matrix}\right.$

and the penalty functions ${r}_{D}(x)=\left\|x-{p}_{D}(x)\right\|$ and
$F_{3}(x):=f({p}_{D}(x))+M{r}_{D}(x)$. Consider the unconstrained optimization
problem:

$F_{3}(x):=f({p}_{D}(x))+M{r}_{D}(x)\to{\min}_{x\in\mathbb{R}^{n}},\;\;\;M>0.$
(5)

###### Lemma 3

[36]. Let $D$ be a non-empty closed set. Then problems (1) and (5) are
globally equivalent, i.e., the global minimum of one task is the global
minimum of the other. Moreover, any local minimum of problem (5) is a local
minimum of problem (1). If $D$ is a convex closed set and ${{x}_{0}}$ is an
interior point of $D$, any local minimum of problem (1) is a local minimum of
problem (5).

##  3 Smoothed functions and their stochastic gradients

The idea of smoothing is widely used in analysis and optimization in different
forms. In what follows we use the so-called Steklov like smoothing ([42]).
This kind of smoothing allows to represent gradients of smoothed functions in
a convenient for optimization finite-difference form.

Let $\mu(x)$ be some probability kernel on ${{\mathbb{R}}^{n}}$, i.e.,
$\mu(x)\geq 0$ and $\int_{{{\mathbb{R}}^{n}}}{\mu(x)dx}=1$. Along with
function $F(x)$, $x\in\mathbb{R}^{n}$, consider the so-called Steklov-Schwartz
smoothed functions [15]

${{F}_{h}}(x)=\frac{1}{{{h}^{n}}}\int_{{{\mathbb{R}}^{n}}}{F(x+y)\mu({y}/{h}\;)dy}=\int_{{{\mathbb{R}}^{n}}}{F(x+hz)\mu(z)dz}.$
(6)

(it is assumed that the integrals exist), where $h>0$ is the smoothing
parameter. If the function $F(x)$ is locally Lipschitz, then ${{F}_{h}}(x)$ is
continuously differentiable and its gradient can be represented as

$\nabla{{F}_{h}}(x)=\frac{1}{{{h}^{n}}}\int_{{{\mathbb{R}}^{n}}}{\partial
F(x+y)\mu({y}/{h}\;)dy}=\int_{{{\mathbb{R}}^{n}}}{\partial F(x+hz)\mu(z)dz}$
(7)

(assuming that the integrals exist), where $\partial F(y)$ is the Clarke
subdifferential [8] of function $F(\cdot)$ at point $y$. The integral of a
multivalued mapping here is understood as the set of integrals of measurable
single-valued sections of the mapping $\partial F(\cdot)$ ([8, 30]). For non-
Lipschitzian functions the representation (7) is not defined, so the gradient
sampling methods [6] cannot be employed for minimization of $F$.

Classical Steklov smoothing [42] uses uniform distribution on the cube
$\\{x\in\mathbb{R}^{n}:\max_{i}|x_{i}|\leq h/2\\}$. Properties of Steklov-
smoothed functions were studied, e.g., in [7, 21, 30]. In [21, 30] on the
basis of Steklov smoothing, stochastic finite-difference optimization methods
were developed for optimization of nonsmooth Lipschitz functions.

###  3.1 Ball smoothing of continuous functions

Consider smoothed (or averaged) functions of the following form ([12, 41]):

${{F}_{h}}(x)=(v_{1})^{-1}\int_{{{V}_{1}}}{F(x+hy)dy},$ (8)

where $V_{1}=\left\\{y\in{{\mathbb{R}}^{n}}:\left\|y\right\|_{2}\leq
1\right\\}$ is the unit ball in $\mathbb{R}^{n}$ with volume $v_{1}$. The
gradient $\nabla{{F}_{h}}(x)$, when $F(x)$ continuous, is calculated by the
surface integral

$\displaystyle\nabla{{F}_{h}}(x)$ $\displaystyle=$
$\displaystyle\frac{n}{s_{1}}\int_{{S}_{1}}\frac{1}{2h}{\left(F(x+hy)-F(x-hy)\right)yds,}$

where $S_{1}=\left\\{y\in{{\mathbb{R}}^{n}}:\left\|y\right\|_{2}=1\right\\}$
is the unit sphere in $\mathbb{R}^{n}$ with square $s_{1}$.

Denote $\tilde{y}$ a random vector uniformly distributed on the unit sphere
${{S}_{1}}$, then the gradient $\nabla{{F}_{h}}(x)$ can be represented as
mathematical expectations ([12, 41]):

$\displaystyle\nabla{{F}_{h}}(x)$ $\displaystyle=$
$\displaystyle\frac{n}{h}{{\mathbb{E}}_{{\tilde{y}}}}\left(F(x+h\tilde{y})-F(x)\right)\tilde{y}=\frac{n}{2h}{{\mathbb{E}}_{{\tilde{y}}}}\left(F(x+h\tilde{y})-F(x-h\tilde{y})\right)\tilde{y}.$
(9)

For $L$-Lipschitz function $F$ it holds [41]:

${{\mathbb{E}}_{{\tilde{y}}}}{{\left\|\frac{1}{2h}\left(F(x+h\tilde{y})-F(x-h\tilde{y})\right)\tilde{y}\right\|}^{2}}\leq
C\cdot{{L}^{2}}/n,$ (10)

where $C$ is some absolute constant. Our experiments indicate that $C\leq 1$.

###  3.2 Smoothing of discontinuous functions

Smoothing of discontinuous functions for optimization purposes has some
peculiarities; smoothed functions do not uniformly approximate the original
function and may be not differentiable. We limit the consideration to the case
of the so-called strongly lower semicontinuous functions $F(x)$, which grow at
the infinity not faster than some power of $\|x\|$.

###### Definition 1

(strongly lower semicontinuous functions, [15]). Function $F:\
{{\mathbb{R}}^{n}}\to{{\mathbb{R}}^{1}}$ is called lower semicontinuous (lsc)
at point $x$ if $\underset{k\to\infty}{\mathop{\lim\inf}}\,F({{x}^{k}})\geq
F(x)$ for all sequences ${{x}^{k}}\to x$. Function $F:\
{{\mathbb{R}}^{n}}\to{{\mathbb{R}}^{1}}$ is called strongly lower
semicontinuous (strongly lsc) at point $x$, if it is lower semicontinuous at
$x$ and there exists a sequence ${{x}^{k}}\to x$ such that it is continuous at
$x^{k}$ (for all $x^{k}$) and $F({{x}^{k}})\to F(x)$. Function $F$ is called
strongly lower semicontinuous on $X\subseteq\mathbb{R}^{n}$ if this is the
case for all $x\in X$.

The property of strong lower semicontinuity is preserved under continuous
transformations. Assume that function $F$ satisfy the condition $|F(x)|\leq
c_{1}+c_{2}\|x\|^{c_{3}}$ for some constants $c_{1},c_{2},c_{3}\geq 0$ and let
$\mu(y)={{(2\pi)}^{-n/2}}{{e}^{-\,{\|y\,\,\|{{\,}^{2}}}/{2}\;}}$,
$y\in\mathbb{R}^{n}$, be the Gaussian kernel. Consider smoothed functions

$\displaystyle{F}_{h}(x)$ $\displaystyle=$
$\displaystyle\int_{\mathbb{R}^{n}}F(x+hy)\mu(y)dy=\frac{1}{(2\pi)^{n/2}h^{n}}\int_{\mathbb{R}^{n}}F(y)e^{-||y-x||^{2}/(2h^{2})}dy.$
(11)

If the function $F$ is not continuous, then we cannot expect the averaged
functions ${{F}_{h}}(x)$ to converge to $F$ uniformly. But we don’t need that.
We need such a convergence of the averaged functions ${{F}_{h}}(x)$ to $F$
that guarantees the convergence of the minima of ${{F}_{h}}(x)$ to the minima
of $F$. This property is provided by the so-called epi-convergence of
functions [38, Theorem 7.33].

###### Definition 2

(Epi-convergence [38]). A sequence of functions
$\\{{{F}^{k}}:{{\mathbb{R}}^{n}}\to\overline{\mathbb{R}},\ k\in\mathbb{N}\\}$
epi-converge to a function $F:{{\mathbb{R}}^{n}}\to\overline{\mathbb{R}}$ at a
point $x$, if

$\underset{k\to\infty}{\mathop{\lim\inf}}\,{{F}^{k}}({{x}^{k}})\geq F(x)$ for
all ${{x}^{k}}\to x$;

$\underset{k\to\infty}{\mathop{\lim}}\,{{F}^{k}}({{x}^{k}})=F(x)$ for some
sequence ${{x}^{k}}\to x$.

The sequence ${{\\{{{F}^{k}}\\}}_{k\in\mathbb{N}}}$ epi-converges to $F$, if
this is the case at every $x\in{{\mathbb{R}}^{n}}$.

###### Theorem 3.1

[15]. For a strongly semicontinuous locally integrable function
$F:{{\mathbb{R}}^{n}}\to\mathbb{R}$, any associated sequence of averaged
functions $\\{{{F}_{h}},\ h\in{{\mathbb{R}}_{+}}\\}$ epi-converges to $F$,
that is, for any sequence ${{h}^{k}}\downarrow 0$ the averaged functions
${F}_{h_{k}}$ epi-converge to $F$.

To optimize discontinuous functions, we approximate them by averaged
functions. The convolution of a discontinuous function with the corresponding
kernel (probability density) improves analytical properties of the resulting
function, but increases the computational complexity of the problem, since it
transforms the deterministic function into an expectation function, which is a
multidimensional integral. Therefore, such an approximation makes sense only
in combination with the corresponding stochastic optimization methods. First,
we study conditions of continuity and continuous differentiability of the
averaged functions.

Thus for the strongly lsc function $F$ the average functions ${{F}_{h}}$ epi-
converge to $F$ as $h\downarrow 0$ and each function ${{F}_{h}}$ is analytical
with the gradient [34]:

$\displaystyle\nabla{{F}_{h}}(x)$ $\displaystyle=$
$\displaystyle\frac{1}{h^{n+2}}\int_{\mathbb{R}^{n}}F(y)(y-x)\mu\left(\frac{y-x}{h}\right)dy$
(12) $\displaystyle=$
$\displaystyle\frac{1}{h}\int_{{{\mathbb{R}}^{n}}}F(x+hz)z\mu(z)dz=-\frac{1}{h}\int_{{{\mathbb{R}}^{n}}}F(x-hz)z\mu(z)dz$
$\displaystyle=$
$\displaystyle{\mathbb{E}_{\eta}}\frac{1}{2h}[F(x+h\mathbf{\eta})-F(x-h\mathbf{\eta})]\mathbf{\eta},$

where the random variable ${\bf\eta}$ has the standard normal distribution
$\mu(\cdot)$ in $\mathbb{R}^{n}$ and $\mathbb{E}_{\eta}$ denotes the
mathematical expectation over ${\bf\eta}$. Thus, the random vector

${{\xi}_{h}}(x,\mathbf{\eta})=\frac{1}{2h}[F(x+h\mathbf{\eta})-F(x-h\mathbf{\eta})]\mathbf{\eta}$
(13)

is an estimate of the gradient $\nabla{{F}_{h}}(x)$. For $L$-Lipschitz
function $F$ it holds [34]:

${{\mathbb{E}}_{{\tilde{y}}}}{{\left\|\frac{1}{2h}\left(F(x+h\tilde{y})-F(x-h\tilde{y})\right)\tilde{y}\right\|}^{2}}\leq
n{{L}^{2}}$ (14)

##  4 Stochastic finite-difference optimization methods for nonsmooth problems

First, we investigate the rate of convergence of the stochastic finite-
difference methods (with the trajectory averaging) on convex Lipschitz
functions. The following theorem establishes the rate of convergence of the
smoothing method in case of the batch calculation of gradient estimates. This
method allows parallelization of the gradient estimation.

###### Theorem 4.1

(A ball smoothing and a batch calculation of the finite-difference gradient
estimates). Let’s assume that the function $F(\cdot)$ is convex and Lipschitz
with some constant $L$ (in the Euclidean norm) on a convex compact set
$X\subseteq{{\text{R}}^{n}}$ and the estimate $\left\|X\right\|={{\sup}_{x\in
X}}\left\|x\right\|\leq D$ is true; the sequence $\left\\{{{x}_{t}}\right\\}$
is built recursively according to the following rule:

${{x}_{t+1}}={{\pi}_{X}}\left({{x}_{t}}-{{\rho}_{t}}{{\eta}_{t}}\right),\;\;\;{{x}_{1}}\in
X,\;\;\;t=1,2,\ldots,$ (15)

random directions $\eta_{t}$ in (15) are calculated as follows:

${{\eta}_{t}}=\frac{1}{K}\sum\limits_{k=1}^{K}{\frac{1}{2{{h}_{t}}}\left(F({{x}_{t}}+{{h}_{t}}\tilde{y}_{t}^{k})-F({{x}_{t}}-{{h}_{t}}\tilde{y}_{t}^{k})\right)\tilde{y}_{t}^{k}},$
(16)

where $\left\\{\tilde{y}_{t}^{k}\right\\}_{k=1}^{K}$ are independent random
vectors uniformly distributed on the unit sphere with the center at the origin
of coordinates. Then at a constant step
$\rho=\frac{D\sqrt{nK}}{L\sqrt{2T(C+K/n)}}$ and a constant smoothing parameter
$h_{t}=h$ the average point
${{\bar{x}}_{T}}=\frac{1}{T}\sum_{t=1}^{T}{{{x}_{t}}}$ satisfies the relation:

$\mathbb{E}{{F}_{h}}({{\bar{x}}_{T}})-\min_{x\in
X}{{F}_{h}}({{x}})\leq\frac{LD}{\sqrt{T}}\sqrt{\frac{2n}{K}}\left(C+\frac{K}{n}\right)^{1/2}.$

For the variable steps $\rho_{t}=\frac{D\sqrt{nK}}{L\sqrt{2t(C+K/n)}}$ and
$\bar{x}_{t}=\sum_{\tau=1}^{t}\rho_{t}x_{t}/\sum_{\tau=1}^{t}\rho_{t}$ it
holds

$\mathbb{E}{{F}_{h}}({{\bar{x}}_{t}})-\min_{x\in
X}{{F}_{h}}({{x}})\leq\frac{DL}{\sqrt{2}}\sqrt{\frac{n}{K}}\left(C+\frac{K}{n}\right)^{1/2}\frac{2+\ln{t}}{\sqrt{t}-1}.$

For the variable steps $\rho_{t}=\frac{D\sqrt{nK}}{L\sqrt{2t(C+K/n)}}$ and
smoothing parameters $h_{t}=L\rho_{t}/K$ for the averaged points
$\bar{x}_{t}=\sum_{\tau=1}^{t}\rho_{t}x_{t}/\sum_{\tau=1}^{t}\rho_{t}$ it
holds

$\displaystyle\mathbb{E}{F}({\bar{x}_{t}})-\min_{x\in X}{{F}}({{x}})$
$\displaystyle\leq$
$\displaystyle\frac{DL}{2}\sqrt{\frac{n}{K}}\left(2+C+\frac{K}{n}\right)^{1/2}\frac{2+\ln{t}}{\sqrt{t}-1}.$
(17)

Here $C$ is some absolute constant from inequality (10).

###### Proof

Let $x^{*}$ be any fixed point in $X$. By convexity of $X$ the following
inequalities are fulfilled:

$\begin{array}[]{lcl}{{\left\|{{x}^{*}}-{{x}_{t+1}}\right\|}^{2}}&=&{{\left\|{{x}^{*}}-{{\pi}_{X}}({{x}_{t}}-{{\rho}_{t}}{{\eta}_{t}})\right\|}^{2}}\leq{{\left\|{{x}^{*}}-{{x}_{t}}+{{\rho}_{t}}{{\eta}_{t}})\right\|}^{2}}\\\
&=&{{\left\|{{x}^{*}}-{{x}_{t}}\right\|}^{2}}+2{{\rho}_{t}}\left\langle{{\eta}_{t}},{{x}^{*}}-{{x}_{t}}\right\rangle+\rho_{t}^{2}{{\left\|{{\eta}_{t}}\right\|}^{2}}.\end{array}$

Let us take the conditional mathematical expectation from both parts of this
inequality with respect to $\sigma$-algebra generated by the random variable
$\left\\{{{x}_{t}}\right\\}$:

$\mathbb{E}\left[\left.{{\left\|{{x}^{*}}-{{x}_{t+1}}\right\|}^{2}}\right|{{x}_{t}}\right]\leq{{\left\|{{x}^{*}}-{{x}_{t}}\right\|}^{2}}+\frac{2{{\rho}_{t}}}{n}\left\langle\nabla{{F}_{h_{t}}}({{x}_{t}}),{{x}^{*}}-{{x}_{t}}\right\rangle+\rho_{t}^{2}\mathbb{E}\left[\left.{{\left\|{{\eta}_{t}}\right\|}^{2}}\right|{{x}_{t}}\right]$

Due to convexity of the functions $F$ and ${{F}_{h_{t}}}$ we have:
$\left\langle\nabla{{F}_{h_{t}}}({{x}_{t}}),{{x}^{*}}-{{x}_{t}}\right\rangle\leq{{F}_{h_{t}}}({{x}^{*}})-{{F}_{h_{t}}}({{x}_{t}})$.
As a result we obtain the inequality

$\displaystyle
2\rho_{t}\left({{F}_{h_{t}}}({{x}_{t}})-{{F}_{h_{t}}}({{x}^{*}})\right)$
$\displaystyle\leq$
$\displaystyle-n\mathbb{E}\left[\left.{{\left\|{{x}^{*}}-{{x}_{t+1}}\right\|}^{2}}\right|{{x}_{t}}\right]$
$\displaystyle+$ $\displaystyle
n{{\left\|{{x}^{*}}-{{x}_{t}}\right\|}^{2}}+\rho_{t}^{2}n\mathbb{E}\left[\left.{{\left\|{{\eta}_{t}}\right\|}^{2}}\right|{{x}_{t}}\right].$

Let us take the mathematical expectation of both sides of this inequality:

$\displaystyle
2\rho_{t}\left(\mathbb{E}{{F}_{h_{t}}}({{x}_{t}})-{{F}_{h_{t}}}({{x}^{*}})\right)$
$\displaystyle\leq$
$\displaystyle-n\mathbb{E}{{\left\|{{x}^{*}}-{{x}_{t+1}}\right\|}^{2}}$
$\displaystyle+$ $\displaystyle
n\mathbb{E}{{\left\|{{x}^{*}}-{{x}_{t}}\right\|}^{2}}+\rho_{t}^{2}n\mathbb{E}\text{E}\left[\left.{{\left\|{{\eta}_{t}}\right\|}^{2}}\right|{{x}_{t}}\right].$

Denote
$\eta_{t}^{k}=\frac{1}{2{{h}_{t}}}\left(F({{x}_{t}}+{{h}_{t}}\tilde{y}_{t}^{k})-F({{x}_{t}}-{{h}_{t}}\tilde{y}_{t}^{k})\right)\tilde{y}_{t}^{k};$

${{\bar{\eta}}_{t}}=\mathbb{E}\left[\eta_{t}^{k}|x_{t}\right]=\mathbb{E}\left[\frac{1}{2{{h}_{t}}}\left(F({{x}_{t}}+{{h}_{t}}\tilde{y}_{t}^{1})-F({{x}_{t}}-{{h}_{t}}\tilde{y}_{t}^{1})\right)\tilde{y}_{t}^{1}|x_{t}\right].$

By (9) it holds,
$\mathbb{E}\left[\eta_{t}^{k}|{{x}_{t}}\right]={{{\bar{\eta}}}_{t}}=n^{-1}\nabla
F_{h_{t}}(x_{t})$ for all $k$. For the expression
$\mathbb{E}\left[\left.{{\left\|{{\eta}_{t}}\right\|}^{2}}\right|{{x}_{t}}\right]$
the following estimates holds true:

$\begin{array}[]{lcl}\mathbb{E}\left[\left.{{\left\|{{\eta}_{t}}\right\|}^{2}}\right|{{x}_{t}}\right]&=&\mathbb{E}\left[{{\left\|\frac{1}{K}\sum\limits_{k=1}^{K}{\eta_{t}^{k}}\right\|}^{2}}|{{x}_{t}}\right]=\mathbb{E}\left[{{\left\|\frac{1}{K}\sum\limits_{k=1}^{K}{\left(\eta_{t}^{k}-{{{\bar{\eta}}}_{t}}\right)}+{{{\bar{\eta}}}_{t}}\right\|}^{2}}|{{x}_{t}}\right]\\\
&\leq&2\mathbb{E}\left[{{\left\|\frac{1}{K}\sum\limits_{k=1}^{K}{\left(\eta_{t}^{k}-{{{\bar{\eta}}}_{t}}\right)}\right\|}^{2}}|{{x}_{t}}\right]+2\mathbb{E}\left[\left\|\bar{\eta}_{t}\right\|^{2}|x_{t}\right]\\\
&=&\frac{2}{{{K}^{2}}}\sum\limits_{k=1}^{K}{\mathbb{E}\left[{{\left(\eta_{t}^{k}-{{{\bar{\eta}}}_{t}}\right)}^{2}}|{{x}_{t}}\right]}+2\mathbb{E}\left[\left\|\bar{\eta}_{t}\right\|^{2}|x_{t}\right]\\\
&\leq&\frac{2}{{{K}^{2}}}\sum\limits_{k=1}^{K}{\left(\mathbb{E}\left[{{\left\|\eta_{t}^{k}\right\|}^{2}}|{{x}_{t}}\right]-\mathbb{E}\left[\left\|\bar{\eta}_{t}\right\|^{2}|x_{t}\right]\right)}+2\mathbb{E}\left[\left\|\bar{\eta}_{t}\right\|^{2}|x_{t}\right]\\\
&=&\frac{2}{{{K}^{2}}}\sum\limits_{k=1}^{K}{\left(\mathbb{E}\left[{{\left\|\eta_{t}^{k}\right\|}^{2}}|{{x}_{t}}\right]\right)}-\frac{2}{K}\mathbb{E}\left[\left\|\bar{\eta}_{t}\right\|^{2}|x_{t}\right]+2\mathbb{E}\left[\left\|\bar{\eta}_{t}\right\|^{2}|x_{t}\right]\\\
&=&\frac{2}{K}\mathbb{E}\left[{{\left\|\eta_{t}^{1}\right\|}^{2}}|{{x}_{t}}\right]+2\left(1-\frac{1}{K}\right)\mathbb{E}\left[\left\|\bar{\eta}_{t}\right\|^{2}|x_{t}\right]\\\
&\leq&\frac{{2C{L}^{2}}}{Kn}+\frac{2(1-{1}/{K})}{{{n}^{2}}}{{\left\|\nabla{{F}_{h_{t}}}({{x}_{t}})\right\|}^{2}}\leq\frac{{2C{L}^{2}}}{Kn}+\frac{{2{L}^{2}}}{{{n}^{2}}}\left(1-\frac{1}{K}\right).\end{array}$

As a result we have the inequality:

$\displaystyle D({x}_{t})$ $\displaystyle=$ $\displaystyle
2\rho_{t}\left(\mathbb{E}{{F}_{h_{t}}}({{x}_{t}})-{{F}_{h_{t}}}({{x}^{*}})\right)$
$\displaystyle\leq$ $\displaystyle
n\mathbb{E}{{\left\|{{x}^{*}}-{{x}_{t}}\right\|}^{2}}-n\mathbb{E}{{\left\|{{x}^{*}}-{{x}_{t+1}}\right\|}^{2}}+\rho_{t}^{2}n\mathbb{E}\mathbb{E}\left[\left.{{\left\|{{\eta}_{t}}\right\|}^{2}}\right|{{x}_{t}}\right]$
$\displaystyle\leq$ $\displaystyle
n\mathbb{E}{{\left\|{{x}^{*}}-{{x}_{t}}\right\|}^{2}}-n\mathbb{E}{{\left\|{{x}^{*}}-{{x}_{t+1}}\right\|}^{2}}+\frac{2\rho_{t}^{2}L^{2}}{K}\left(C+\frac{K}{n}\right).$

Now let us sum these inequalities over $t$ from 1 to $T$,

$2\sum_{t=1}^{T}\rho_{t}\left(\mathbb{E}{{F}_{h_{t}}}({{x}_{t}})-{{F}_{h_{t}}}({{x}^{*}})\right)\leq
n\mathbb{E}{{\left\|{{x}^{*}}-{{x}_{1}}\right\|}^{2}}+\frac{2L^{2}}{K}\left(C+\frac{K}{n}\right)\sum_{t=1}^{T}\rho_{t}^{2}.$

First, consider the case of the fixed smoothing parameter $h_{t}=h$ for all
$t$ and let $x^{*}$ be such that $F_{h}(x^{*})=\min_{x\in X}F_{h}(x)$. Let us
subdivide both sides of the above inequality by $2\sum_{t=1}^{T}\rho_{t}$. For
the average point
$\bar{x}_{T}=\sum_{t=1}^{T}\rho_{t}x_{t}/\sum_{t=1}^{T}\rho_{t}$ due to
convexity of $F_{h}$ we have

$\displaystyle\mathbb{E}{{F}_{h}}({\bar{x}_{t}})-\min_{x\in X}F_{h}(x)$
$\displaystyle\leq$
$\displaystyle\frac{\sum_{t=1}^{T}\rho_{t}\left(\mathbb{E}{{F}_{h}}({{x}_{t}})-\min_{x\in
X}F_{h}(x)\right)}{\sum_{t=1}^{T}\rho_{t}}$ (20) $\displaystyle\leq$
$\displaystyle\frac{n\mathbb{E}{{\left\|{{x}^{*}}-{{x}_{1}}\right\|}^{2}}}{2\sum_{t=1}^{T}\rho_{t}}+\frac{L^{2}}{K}\left(C+\frac{K}{n}\right)\frac{\sum_{t=1}^{T}\rho_{t}^{2}}{\sum_{t=1}^{T}\rho_{t}}$

For the constant step size ${{\rho}_{t}}\equiv\rho$ and
$\bar{x}_{T}=T^{-1}\sum_{t=1}^{T}\rho_{t}$, we obtain

$\mathbb{E}{{F}_{h}}({{\bar{x}}_{T}})-\min_{x\in
X}F_{h}(x)\leq\frac{n{{D}^{2}}}{2T\rho}+\frac{{{L}^{2}}\rho}{K}\left({C}+\frac{K}{n}\right).$
(21)

For minimizing the right hand side of (21), let us take
$\rho=\frac{D\sqrt{nK}}{L\sqrt{2T(C+K/n)}}$, then we obtain

$\displaystyle\mathbb{E}{{F}_{h}}({{\bar{x}}_{T}})-\min_{x\in X}F_{h}(x)$
$\displaystyle\leq$
$\displaystyle\frac{LD}{\sqrt{T}}\sqrt{\frac{2n}{K}}\left(C+\frac{K}{n}\right)^{1/2}.$

For the variable steps $\rho_{t}=\frac{D\sqrt{nK}}{L\sqrt{2t(C+K/n)}}$ and
$\bar{x}_{t}=\sum_{\tau=1}^{t}\rho_{t}x_{t}/\sum_{\tau=1}^{t}\rho_{t}$, from
(20) we obtain

$\displaystyle\mathbb{E}{{F}_{h}}({{\bar{x}}_{t}})-\min_{x\in X}F_{h}(x)$
$\displaystyle=$
$\displaystyle\frac{DL}{\sqrt{2}}\sqrt{\frac{n}{K}}\left(C+\frac{K}{n}\right)^{1/2}\frac{\left(1+\sum_{\tau=1}^{t}\tau^{-1}\right)}{\sum_{\tau=1}^{t}\tau^{-1/2}}$
$\displaystyle\leq$
$\displaystyle\frac{DL}{\sqrt{2}}\sqrt{\frac{n}{K}}\left(C+\frac{K}{n}\right)^{1/2}\frac{2+\ln{t}}{\sqrt{t}-1}.$

Now consider the case of a variable smoothing parameter $h_{t}$ and let
$x^{*}$ be such that $F(x^{*})=\min_{x\in X}F(x)$. Since
$|F(x)-F_{h_{t}}(x)|\leq Lh_{t}$ for $x\in X$, then
$|F_{h_{t}}(x_{t})-F(x_{t})|\leq Lh_{t}$, $|F_{h_{t}}(x^{*})-F(x^{*})|\leq
Lh_{t}$, and we obtain the estimate:

$\begin{array}[]{l}2\sum_{t=1}^{T}\rho_{t}\left(\mathbb{E}{F}({{x}_{t}})-\min_{x\in
X}{{F}}({{x}})\right)=2\sum_{t=1}^{T}\rho_{t}\left(\mathbb{E}{F}({{x}_{t}})-{{F}}({{x}^{*}})\right)\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\leq
2\sum_{t=1}^{T}\rho_{t}\left(\mathbb{E}{{F}_{h_{t}}}({{x}_{t}})-{{F}_{h_{t}}}({{x}^{*}})\right)+4\sum_{t=1}^{T}L\rho_{t}h_{t}\\\
\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\leq
nD^{2}+\frac{2L^{2}}{K}\left(C+\frac{K}{n}\right)\sum_{t=1}^{T}\rho_{t}^{2}+4\sum_{t=1}^{T}L\rho_{t}h_{t}.\end{array}$

By dividing this inequality by $\sum_{t=1}^{t}\rho_{\tau}$ for
$\bar{x}_{t}=\sum_{\tau=1}^{t}\rho_{\tau}x_{\tau}/\sum_{\tau=1}^{t}\rho_{\tau}$
and $\rho_{t}=\frac{D\sqrt{nK}}{L\sqrt{2t(C+K/n)}}$, $h_{t}=L\rho_{t}/K$, we
obtain:

$\displaystyle\mathbb{E}{F}({\bar{x}_{t}})-\min_{x\in
X}{{F}}({{x}})\leq\frac{nD^{2}}{2\sum_{\tau=1}^{t}\rho_{\tau}}+\frac{L^{2}}{K}\left(C+\frac{K}{n}\right)\frac{\sum_{\tau=1}^{t}\rho_{\tau}^{2}}{\sum_{\tau=1}^{t}\rho_{\tau}}+2L\frac{\sum_{\tau=1}^{t}\rho_{\tau}h_{\tau}}{\sum_{\tau=1}^{t}\rho_{\tau}}$
$\displaystyle=\frac{nD^{2}}{2\sum_{\tau=1}^{t}\rho_{\tau}}+\frac{L^{2}}{K}\left(2+C+\frac{K}{n}\right)\frac{\sum_{\tau=1}^{t}\rho_{\tau}^{2}}{\sum_{\tau=1}^{t}\rho_{\tau}}=\frac{DL}{2}\sqrt{\frac{n}{K}\left(2+C+\frac{K}{n}\right)}\frac{2+\ln{t}}{\sqrt{t}-1}.$

###### Theorem 4.2

(Gaussian smoothing with batch estimation of the finite-difference gradient).
In conditions of Theorem 4.1, where instead ball smoothing the gaussian
smoothing is used, i.e. random vectors $\tilde{y}_{t}^{k}$ in (16) have the
standard normal distribution, the following estimates hold true. At a constant
step $\rho=\frac{D}{L\sqrt{2T(1+(n-1)/K)}}$ and a constant smoothing parameter
$h_{t}=h$ the average point
${{\bar{x}}_{T}}=\frac{1}{T}\sum_{t=1}^{T}{{{x}_{t}}}$ satisfies the relation:

$\mathbb{E}{{F}_{h}}({{\bar{x}}_{T}})-\min_{x\in
X}{{F}_{h}}({{x}})\leq\frac{LD}{\sqrt{T}}\sqrt{2\left(1+\frac{n-1}{K}\right)}.$

For steps $\rho_{t}=\frac{D}{L\sqrt{2t(1+(n-1)/K)}}$ and
$\bar{x}_{t}=\sum_{\tau=1}^{t}\rho_{t}x_{t}/\sum_{\tau=1}^{t}\rho_{t}$ it
holds

$\mathbb{E}{{F}_{h}}({{\bar{x}}_{t}})-\min_{x\in
X}{{F}_{h}}({{x}})\leq{LD\sqrt{2}}\left({1+\frac{n-1}{K}}\right)^{1/2}\frac{2+\ln{t}}{\sqrt{t}-1}.$

For the variable steps $\rho_{t}=\frac{D}{L\sqrt{t(1+(n+3)/K)}}$ and smoothing
parameters $h_{t}=L\rho_{t}/K$ for the averaged points
$\bar{x}_{t}=\sum_{\tau=1}^{t}\rho_{t}x_{t}/\sum_{\tau=1}^{t}\rho_{t}$ it
holds

$\displaystyle\mathbb{E}{F}({\bar{x}_{t}})-\min_{x\in X}{{F}}({{x}})$
$\displaystyle\leq$
$\displaystyle\frac{DL}{2}\left({1+\frac{n+3}{K}}\right)^{1/2}\frac{2+\ln{t}}{\sqrt{t}-1}.$
(22)

###### Proof

The proof of this theorem basically repeats the proof of Theorem 4.1, only
instead of properties (9), (10) the relations (12), (14) are used.

There are related results on the rate of convergence of finite-difference
methods for smooth functions (cf. [11, 12, 41]). In Theorems 4.1, 4.2 we do
not assume differentiability of the objective function. From the obtained
results (Theorem 4.1) on the rate of convergence of the stochastic smoothing
method on the class of convex nonsmooth functions, the following conclusions
can be drawn regarding the parameters of the method in optimizing the smoothed
function ${{F}_{h}}$. The step multiplier $\rho$ should be proportional to
$\sqrt{n}$, the square root of the dimension of the space of the variables,
and the estimate $D$ of the Euclidean distance from the starting point
${{x}_{0}}$ to the minimum point ${{x}^{*}}$.

The direction ${{\eta}_{t}}$ in the method should be normalized to the
Lipschitz constant $L$ of the objective function, or to the estimation of this
constant as in the adaptive methods Adam [25] and AdaGrad [11]. The batch size
parameter $K$ allows to reduce dependence of the rate of convergence on the
dimension $n$.

###  4.1 Stochastic finite-difference gradient methods for nonconvex problems

In the proposed approach to the optimization of nonsmooth and discontinuous
functions under constraints, first the initial problem (1) is reduced by the
method of exact nonsmooth penalties to the problem of unconditional
optimization (4), (5) (see Sec. 2), then the modified objective function is
smoothed and approximated by smooth mathematical expectation functions (6),
(8), (11) (Sec. 3).

In conditions of Theorem 3.1 a sequence of smoothed averaged functions
${{F}_{h}}$ epi-graphically converges to $F$ as $h\to 0$. Then by [38, Theorem
7.33] global minimums of ${{F}_{h}}$ converge to the global minimums of $F$ as
$h\to 0$. Convergence of local minimums was studied in [15, 13]. For the
gradients of the smoothed functions stochastic finite-difference
representations (9), (12) hold true. The latter can be used for optimization
of the smoothed functions by contemporary efficient stochastic optimization
methods [4], in particular: Nemirovsky-Yudin trajectory averaging method [32,
31], Polyak’s method (heavy ball) [37]; Gelfand-Zetlin-Nesterov method (ravine
step method) [20, 33] and its stochastic generalizations; Adaptive stochastic
gradient methods [11, 25]. Performance of the one of these method [31] in the
convex case is evaluated in Theorems 4.1, 4.2. Generalizations of these
methods to the nonconvex smooth and nonsmooth cases are available in the works
of [16, 21, 28, 30, 39].

##  5 Global optimization by smoothing

One heuristic background of applying smoothing method for the global
optimization purposes is that smoothing eliminates shallow local minimums and
little chainges wide and deep ones. The other justification is provided by
properties of critical points/paths of smoothed functions, cf. [30, p.
135-137], [1, 5, 35].

The smoothing method in global optimization consists in approximation of a
multi-extremal function by a sequence of the so-called smoothed (or averaged)
functions and optimization of the latter by some suitable available methods.
When the smoothing parameter goes down, the averaged functions uniformly (or
epi-graphically) converge to the original function, so the global minima of
the approximate functions converge to the global minima of the original one.

The transition from a minimum point of one smoothed function to the starting
point for minimizing another smoothed function is carried out by the Gelfand-
Tsetlin-Nesterov ravine step method ([20, 33]). In this method, if we have two
points at the bottom of a valley, we can find the direction of the valley and
guess a starting point to descend further to the bottom of the valley, and so
on.

To minimize smoothed functions ${{F}_{h}}(x)$, any smooth optimization methods
can be used, if their gradients can be calculated analytically, numerically,
or estimated statistically. This is easy to do for one-dimensional functions
[35] and for separable functions
$F(x)=\sum\nolimits_{i}{{{f}_{i1}}({{x}_{1}})\times...\times{{f}_{in}}({{x}_{n}})}$.
For example, [1, 5] exploits analytical smoothing of the polynomial functions
to derive differential equation for critical curves of the set
$\\{(x,h):\nabla{{F}_{h}}(x)=0,h\geq 0\\}$.

In general, stochastic finite-difference methods ([4, 11, 12, 14, 16, 21, 25,
30, 37]) can be used for minimization of functions ${{F}_{h}}(\cdot)$ at each
smoothing stage.

##  6 Algorithm of the stochastic successive smoothing method

Algorithm of the stochastic successive smoothing method consists of the
following steps.

  1. 1.

Reduce the problem of conditional optimization to the problem of unconditional
optimization of some coercive function;

  2. 2.

Select a decreasing sequence of smoothing parameters with a sufficiently large
initial value of the smoothing parameter;

  3. 3.

Minimize successively the smoothed functions by some effective deterministic
or stochastic method, using the results of minimizing the previous smoothed
functions to start minimization of the subsequent smoothed function.

The results of testing of the stochastic successive smoothing method on some
small dimensional global optimization (box constrained) problems are presented
in [26], [35, 36]. Below we present an example of solution a larger test
problem.

###### Example 1

Largest Small Polygon [10]. Find the polygon of maximal area, among polygons
with $n$ sides and diameter $d\leq 1$. If $({{r}_{i}},{{\theta}_{i}})$ are the
coordinates of the vertices of the polygon, the problem is to find

$f_{n}^{*}=\underset{r,\,\varphi}{\mathop{\max}}\,\left[f(r,\varphi)=\frac{1}{2}\sum\limits_{i=1}^{n-1}{{{r}_{i+1}}{{r}_{i}}\sin{{\varphi}_{i+1}}}\right]$

subject to the constraints:

$\begin{array}[]{l}{{\left(r_{i}^{2}+r_{j}^{2}-2{{r}_{i}}{{r}_{j}}\cos\sum\nolimits_{k=i+1}^{j}{{{\varphi}_{k}}}\right)}^{{1}/{2}\;}}\leq
1,\;\;\;1\leq i<j\leq n;\\\
{{\theta}_{i}}=\sum\nolimits_{k=1}^{i}{{{\varphi}_{k}}},1\leq i\leq
n;\;\;\;\sum_{i=1}^{n}{{{\varphi}_{i}}}\leq\pi;\\\ {{r}_{i}}\geq
0,\;\;0\leq{{\varphi}_{i}}\leq{2\pi}/{n},\;\;1\leq i\leq
n;\;\;\;\;{{r}_{1}}={{\varphi}_{1}}=0.\end{array}$

Here $r=({{r}_{1}},...,{{r}_{n}})$,
$\varphi=({{\varphi}_{1}},...,{{\varphi}_{n}})$. It is known that
$f_{3}^{*}={\sqrt{3}}/{4}\;\approx 0.4330$, $f_{4}^{*}=0.5$,
$\underset{n\to\infty}{\mathop{\lim}}\,f_{n}^{*}={\pi}/{4}\;\approx 0.7854$.
Optimal polygons approach to the circle of diameter 1 as $n\to\infty$. First
we transform the constrained problem to an unconstrained problem
$\underset{r,\,\varphi}{\mathop{\max}}\,{{F}_{3}}(r,\varphi)$ by the following
penalty functions with penalty coefficients ${{p}_{1}},{{p}_{2}},{{p}_{3}}>0$:

  1. 1.

${{F}_{1}}(r,\varphi)=\left\\{\begin{matrix}f(r,\varphi),&\sum\nolimits_{i=1}^{n}{{{\varphi}_{i}}}\leq\pi,\\\
f(r,\lambda\varphi)+{{p}_{1}}\left(\sum\nolimits_{i=1}^{n}{{{\varphi}_{i}}}-\pi\right),&otherwise,\\\
\end{matrix}\right.$,
$\lambda={\pi}/{\sum\nolimits_{i=1}^{n}{{{\varphi}_{i}}}}\;$, ${{p}_{1}}=1$;

  2. 2.

${{F}_{2}}(r,\varphi)={{F}_{1}}(r,\varphi)+{{p}_{2}}\max\left\\{0,\sum\nolimits_{i<j}{\left(\sqrt{r_{diag}}-1\right)}\right\\}$,
${{p}_{2}}=1$,
$r_{diag}=r_{i}^{2}+r_{j}^{2}-2{{r}_{i}}{{r}_{j}}\cos\sum\nolimits_{k=i+1}^{j}{{{\varphi}_{k}}}$;

  3. 3.

${{F}_{3}}(r,\varphi)={{F}_{2}}(\hat{r},\hat{\varphi})+{{p}_{3}}\left(\left\|r-\hat{r}\right\|+\left\|\varphi-\hat{\varphi}\right\|\right)$,
${{p}_{3}}=10$.

Here $\hat{r}$ and $\hat{\varphi}$ are projections of vectors $r$ and
$\varphi$ on the cubes ${{[0,1]}^{n}}$ and ${{[0,{2\pi}/{n}\;]}^{n}}$,
respectively. We solved the problem
$\underset{r,\,\varphi}{\mathop{\max}}\,{{F}_{3}}(r,\varphi)$ by the
stochastic smoothing method, results are presented in the Table 1. Further
examples of solving stochastic storage optimal control problems by the
stochastic successive smoothing method can be found in [26].

Table 1: Optimal polygons $n$ | 3 | 4 | 20 | 50 | 100 | 200 | 500
---|---|---|---|---|---|---|---
Smoothing |  |  |  |  |  |  |
Iterations | 100 | 200 | 500 | 1000 | 2000 | 2000 | 4000
Func. calc. | 4040 | 11256 | 132264 | 620620 | 2465232 | 3521760 | 15627906
Max. achived | 0.4300 | 0.4994 | 0.7680 | 0.7763 | 0.7788 | 0.7697 | 0.7588
Ideal value | 0.4330 | 0.5000 | 0.7854 | 0.7854 | 0.7854 | 0.7854 | 0.7854

##  7 Conclusions

In the paper, the stochastic successive smoothing method ([35]) is extended to
general conditional optimization problems with nonsmooth and discontinuous
functions. Initially, the conditional problem is transformed to an
unconditional one by a modified exact penalty function method, in which one
need not to select the value of the penalty factor. Then the unconditional
problem is approximated by a sequence of smoothed (averaged) functions
starting from strong smoothing with a gradual decrease in the degree of
smoothing. Modern methods of stochastic gradient optimization can be used to
optimize approximate smoothed functions. In this respect, we show that
gradients of the smoothed functions can be estimated by means of finite
differences in stochastic directions. The transition from the optimization of
one smoothed function to the optimization of the next function is carried out
using the Gelfand-Zetlin-Nesterov method but unlike this method for the local
decent we use many step stochastic procedure. The applied sequential smoothing
eliminates shallow local minima of the original problem, so the method gets
some global properties.

##  8 Acknowledgements

The research of the first author was supported by the Volkswagen Foundation
(Az.: 9C090, 2022) and the National Research Fund of Ukraine (Project
2020.02/0121). The research of the second author was supported by the German
Research Foundation (Project 416228727–SFB 1410). The work of the third author
was supported by the National Research Fund of Ukraine (Project 2020.02/0121).

## References

  * [1] Arıkan, O., Burachik, R.S., Kaya, C.Y.: Steklov regularization and trajectory methods for univariate global optimization. J. of Global Optimization 76, 91–120 (2020)
  * [2] Batukhtin, V.D., Mayboroda, L.A.: Discontinuous Extremum Problems. Gippokrat, St. Petersburg (1995), (In Russian).
  * [3] Batukhtin, V.: On solving discontinuous extremal problems. Journal of Optimization Theory and Applications 77, 575–589 (1993)
  * [4] Bottou, L., Curtis, F.E., Nocedal, J.: Optimization methods for large-scale machine learning. SIAM review 60(2), 223–311 (2018)
  * [5] Burachik, R.S., Kaya, C.Y.: Steklov convexification and a trajectory method for global optimization of multivariate quartic polynomials. Mathematical Programming 189(1-2), 187–216 (2021)
  * [6] Burke, J.V., Curtis, F.E., Lewis, A.S., Overton, M.L., Simões, L.E.A.: Gradient sampling methods for nonsmooth optimization. In: Bagirov, A.M., et al. (eds.) Numerical nonsmooth optimization, pp. 201–225. Springer (2020)
  * [7] Chagas, J.Q., Diehl, N.M., Guidolin, P.L.: Some properties for the steklov averages. arXiv preprint arXiv:1707.06368 (2017)
  * [8] Clarke, F.H.: Optimization and nonsmooth analysis. SIAM (1990)
  * [9] Conn, A.R., Mongeau, M.: Discontinuous piecewise linear optimization. Mathematical programming 80(3), 315–380 (1998)
  * [10] Dolan, E.D., Moré, J.J., Munson, T.S.: Benchmarking optimization software with cops 3.0. Tech. rep., Argonne National Lab., Argonne, IL (US) (2004)
  * [11] Duchi, J., Hazan, E., Singer, Y.: Adaptive subgradient methods for online learning and stochastic optimization. J. of machine learning research 12(7), 2121–2159 (2011)
  * [12] Duchi, J.C., Jordan, M.I., Wainwright, M.J., Wibisono, A.: Optimal rates for zero-order convex optimization: The power of two function evaluations. IEEE Transactions on Information Theory 61(5), 2788–2806 (2015)
  * [13] Ermol’ev, Y.M., Norkin, V.: Stochastic generalized gradient method for nonconvex nonsmooth stochastic optimization. Cybernetics and Systems Analysis 34(2), 196–215 (1998). https://doi.org/10.1007/BF02742069
  * [14] Ermoliev, Y.M.: Methods of stochastic programming. Nauka, Moscow (1976)
  * [15] Ermoliev, Y.M., Norkin, V.I., Wets, R.J.B.: The minimization of semicontinuous functions: Mollifier subgradients. SIAM Journal on Control and Optimization 33, 149–167 (1995)
  * [16] Ermoliev, Y.M., Norkin, V.: Solution of nonconvex nonsmooth stochastic optimization problems. Cybernetics and Systems Analysis 39, 701–715 (2003). https://doi.org/10.1023/B:CASA.0000012091.84864.65
  * [17] Floudas, C.A., Pardalos, P.M. (eds.): Encyclopedia of Optimization. Springer (2009)
  * [18] Floudas, C., Pardalos, P., Adjiman, C. (eds.): Handbook of Test Problems in Local and Global Optimization. Kluwer Academic Publishers, Dordreht (1999)
  * [19] Galvan, G., Sciandrone, M., Lucidi, S.: A parameter-free unconstrained reformulation for nonsmooth problems with convex constraints. Computational Optimization and Applications 80, 33–53 (2021)
  * [20] Gel’fand, I.M., Tsetlin, M.L.: Some methods of control for complex systems. Russian Mathematical Surveys 17(1), 95–117 (1962). https://doi.org/10.1070/rm1962v017n01abeh001124
  * [21] Gupal, A.M.: Stochastic Methods for Solving Nonsmooth Extremal Problems. Naukova Dumka, Kyiv (1979), (in Russian)
  * [22] Gupal, A.M., Norkin, V.I.: Algorithm for the minimization of discontinuous functions. Cybernetics 13(2), 220–223 (1977). https://doi.org/10.1007/BF01073313
  * [23] Horst, R., Pardalos, P.M.: Handbook of global optimization, vol. 2. Springer (2013)
  * [24] Imo, I.I., Leech, D.J.: Discontinuous optimization in batch production using sumt. The International Journal of Production Research 22(2), 313–321 (1984)
  * [25] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980v9 (2017). https://doi.org/10.48550/arXiv.1412.6980
  * [26] Knopov, P., Norkin, V.: Stochastic optimization methods for the stochastic storage process control. In: Blondin, M.J., et al. (eds.) Intelligent Control and Smart Energy Management. Renewable Resources and Transportation, Springer Optimization and Its Applications, vol. 181, pp. 79–111. Springer Nature Switzerland AG (2022). https://doi.org/10.1007/978-3-030-84474-5_3
  * [27] Longo, M., Opschoor, J.A.A., Disch, N., Schwab, C., Zech, J.: De rham compatible deep neural network fem. arXiv preprint arXiv:2201.05395 (2022)
  * [28] Mai, V., Johansson, M.: Convergence of a stochastic gradient method with momentum for non-smooth non-convex optimization. In: International conference on machine learning. pp. 6630–6639. PMLR (2020)
  * [29] Mayne, D.Q., Polak, E.: Nondifferential optimization via adaptive smoothing. Journal of Optimization Theory and Applications 43(4), 601–613 (1984)
  * [30] Mikhalevich, V.S., Gupal, A.M., Norkin, V.I.: Methods of Nonconvex Optimization. Nauka, Moscow (1987), (in Russian)
  * [31] Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization 19(4), 1574–1609 (2009)
  * [32] Nemirovsky, A., Yudin, D.: Informational Complexity and Efficient Methods for Solution of Convex Extremal Problems. J. Wiley & Sons, New York (1983)
  * [33] Nesterov, Y.: A method of solving a convex programming problem with convergence rate. Soviet Math. Dokl. 27(2), 372–376 (1983)
  * [34] Nesterov, Y., Spokoiny, V.: Random gradient-free minimization of convex functions. Foundations of Computational Mathematics 17, 527–566 (2017)
  * [35] Norkin, V.I.: A stochastic smoothing method for nonsmooth global optimization. Cybernetics and Computer Technologies pp. 5–14 (2020). https://doi.org/10.34229/2707-451X.20.1.1
  * [36] Norkin, V.I.: The projective exact penalty method for general constrained optimization. Preprint. https://optimization-online.org/?p=20458 (2022)
  * [37] Polyak, B.: Introduction to Optimization. Optimization Software, Inc. Publ. Division (1987)
  * [38] Rockafellar, R.T., Wets, R.J.B.: Variational analysis. Grundlehren der mathematischen Wissenschaften, Springer, 1st ed. 1998, 3rd printing, springer edn. (2009)
  * [39] Ruszczyński, A.: Convergence of a stochastic subgradient method with averaging for nonsmooth nonconvex constrained optimization. Optimization Letters 14(7), 1615–1625 (2020)
  * [40] Sergeyev, Y.D., Kvasov, D.E.: Deterministic Global Optimization. Springer, New York (2017). https://doi.org/10.1007/978-1-4939-7199-2
  * [41] Shamir, O.: An optimal algorithm for bandit and zero-order convex optimization with two-point feedback. The Journal of Machine Learning Research 18(1), 1703–1713 (2017)
  * [42] Stekloff, W.: Sur les expressions asymptotiques de certaines fonctions, définies par les équations différentielles linéaires du second ordre, et leurs applications au probléme du développement d’une fonction arbitraire en séries procédant suivant les-dites fonctions. Communications de la Société mathématique de Kharkow 10, 97–199 (1907), http://mi.mathnet.ru/eng/khmo/v10/p97, (In French).
  * [43] Strongin, R.G., Sergeyev, Y.D.: Global Optimization with Non-Convex Constraints: Sequential and Parallel Algorithms. Kluwer Academic Publishers, Dordrecht (2000). 3rd ed. By Springer (2014) (2014)
  * [44] Ustimenko, A., Prokhorenkova, L.: Stochasticrank: Global optimization of scale-free discrete functions. In: Int. Conf. on Machine Learning. pp. 9669–9679. PMLR (2020)
  * [45] Yang, X.S.: Engineering optimization: an introduction with metaheuristic applications. John Wiley & Sons (2010)