## Mirror Descent for Constrained Optimization Problems with Large Subgradient Values ∗

Fedor S. Stonyakin 1,2 , Alexey N. Stepanov , 1 Alexander A. Titov , and Alexander V. Gasnikov 2 2

1 V. I. Vernadsky Crimean Federal University, Simferopol, Russia, email: fedyor@mail.ru, stepanov.student@gmail.com .

2 Moscow Institute of Physics and Technology, Moscow, Russia, email: a.a.titov@phystech.edu, gasnikov@yandex.ru .

## Abstract

Based on the ideas of [2], we consider the problem of minimization of the Lipschitz-continuous non-smooth functional f with a nonpositive convex (generally, non-smooth) Lipschitz-continuous functional constraint. We propose some novel strategies of step-sizes and adaptive stopping rules in Mirror Descent algorithms for the considered class of problems. It is shown that the methods are applicable to the objective functionals of various levels of smoothness. Applying the restart technique to the Mirror Descent Algorithm there was proposed an optimal method of solving optimization problems with strongly convex objective functionals. Estimates of the rate of convergence of the considered algorithms are obtained depending on the level of smoothness of the objective functional. These estimates indicate the optimality of considered methods from the point of view of the theory of lower oracle bounds. In addition, the case of a quasi-convex objective and functional constraint was considered.

Keywords : non-smooth constrained optimization, quasi-convex functional, adaptive mirror descent, level of smoothness, optimal method.

∗ Stonyakin F.S., Stepanov A.N., Gasnikov A.V., Titov A.A. Mirror descent for constrained optimization problems with large subgradient values of functional constraints // Computer Research and Modeling, 2020, vol. 12, no. 2, pp. 301-317.

## 1. Introduction

Non-smooth convex constrained optimization problems play an important role in modern large-scale optimization and its applications [7,14]. There are a lot of methods to solve such problems, among which one can mention the Mirror Descent Method [3,8].

Recently, in [2] algorithms for Mirror Descent with both adaptive step selection and adaptive stopping criterion were proposed. In addition, an optimal method was proposed for the special class of convex constrained optimization problems, when the gradient of the objective functional satisfies Lipschitz property. For example, quadratic functionals do not satisfy the Lipschitz condition, but their gradient does. An adaptive Mirror Descent algorithm, based on the ideology of [9,10] was proposed to solve such problems in ( [2], Section 3.3).

In this paper we develop the above mentioned research and consider some modifications of algorithmic scheme ( [2], Section 3.3). More precisely, in proposed Algorithm 2 we consider a new approach to choosing a step in the method, as well as appropriate options for stopping criteria, which differ from [2]. It is important that we choose the non-productive step ( ∇ g x ( k ) is the subgradient g at the current point x k ) at the form h k = ε ‖∇ g x ( k ) ‖ instead of h k = ε ‖∇ g x ( k ) ‖ 2 in [2]. This circumstance, as well as the appropriate choice of the number of iterations (3.10), leads us to the fact that the method can run faster than the previous analogue ( [2], Section 3.3) in the case, when the values of the subgradients of the functional constraint g are large. Note that a method similar to Algorithm 2 was proposed in [8] for the case of convex Lipschitz continuous functionals.

This paper substantiates the convergence rate estimates for the proposed version of the Mirror Descent method, proves its optimality from the point of view of the theory of lower bounds for objective functionals of various smoothness levels: which have a Lipschitz continuous gradient or satisfy the Lipschitz (H¨lder) condition. o It is also shown that the obtained estimates of the convergence rate are preserved for quasi-convex [11, 13] objective functional and constraint (see e.g. [4], Exercise 2.7). Using the restart technique, the optimal method for strongly (quasi-)convex objective functionals is considered. The paper ends with some numerical experiments for geometric problems with functional constraints, which illustrate , that the proposed method can work faster compared to [2], Section 3.3. There are also given

some examples of more efficient methods in the case of large dimensionality. The contribution of this paper is as follows:

- -An analogue of the Mirror Descent method is considered ( [2], Section 3.3) for convex programming problems with another strategy for choosing a non-productive step. Estimates of the rate of its convergence and optimality are obtained in terms of lower bounds for convex objective functionals of various smoothness levels.
- -It is shown that the obtained convergence rate estimates will are also valid for the case of the minimization problems with quasi-convex objective functionals of different smoothness levels.
- -It is shown that for the H¨lder-continuous quasi-convex objective the o convergence rate is equal to O ( 1 ε 2 ) .
- - Numerical experiments for geometrical problems (the Fermat-TorricelliSteiner problem, the problem of the smallest covering ball) with convex constraints are presented. When (sub)gradient values of functional constraints are large the proposed method can work faster [2]. High-dimensional examples are also considered.
- -Using the restart technique, an optimal method was proposed for the class of minimization problems with strongly (quasi-)convex H¨lder-continuous o objective functionals with the complexity estimate equal to O ( 1 ε ) .
- - Numerical experiments for the minimization of quasi-convex functionals are given. An example of the smallest covering ball problem with a quasiconvex objective functional is also considered.

## 2. Problem Statement and Mirror Descent Basics

Let ( E, || · || ) be a normed finite-dimensional vector space and E ∗ be its conjugate space with the norm:

$$| | y | | _ { * } = \max _ { x } \{ \langle y, x \rangle, | | x | | \leqslant 1 \},$$

where 〈 y, x 〉 is the value of the continuous linear functional y at x ∈ E .

Let Q ⊂ E be a (simple) closed convex set. Consider the following problem:

$$f ( x ) \to \min _ { x \in Q },$$

s.t.

$$g ( x ) \leqslant 0$$

Assume that convex functional g satisfies the Lipschitz condition with a constant M g :

$$| g ( x ) - g ( y ) | \leqslant M _ { g } \| x - y \| \, \forall x, y \in X. \quad \quad \quad ( 2. 3 ) \\ \dots \quad \dots \quad \dots \quad \dots \quad \dots \quad \dots \quad \dots$$

We consider cases of convex and quasi-convex objective f . Let d : Q → R be a distance generating function (d.g.f) which is non-negative continuously differentiable and 1 -strongly convex w.r.t. the norm ‖ · ‖ , i.e.

$$\forall x, y, \in Q \ \langle \nabla d ( x ) - \nabla d ( y ), x - y \rangle \geqslant \| x - y \| ^ { 2 },$$

and assume that there is a constant Θ 0 , such that d x ( ∗ ) /lessorequalslant Θ 2 0 , where x ∗ is a solution of the problem (supposing that the problem is solvable).

For all x, y ∈ Q ⊂ E consider the corresponding Bregman divergence

$$V ( x, y ) = d ( y ) - d ( x ) - \langle \n$$

The proximal mapping operator is defined as follows:

$$\begin{array} {$$

We assume for simplicity that Mirr ( x p ) is easily computable.

## 3. Mirror Descent Algorithms: New Step-Sizes Strategies

Two Mirror Descent methods for optimization problems with one convex subdifferentiable functional constraint were proposed in [2]. The convergence of the first of them is obtained for the case of the Lipschitz-continuous objective functional (see [2], Section 3.1), while the convergence of the second is justified under the assumption that the gradient ∇ f satisfies Lipschitz property (see [2], p. 3.3). Let us remind namely, the second one.

Lemma 3.1. Let us define the following function:

$$\omega ( \tau ) = \max _ { x \in X } \{ f ($$

## Algorithm 1 Adaptive Mirror Descent

Require:

ε &gt;

0 Θ

,

0

:

d x

(

∗

)

/lessorequalslant

Θ

2

0

$$1 \colon \, x ^ { 0 } = a r g m i n _ { x \$$

2:

I

=:

3:

∅

N

0

4: repeat

←

5:

if g x

(

N

)

/lessorequalslant

ε

then

$$\begin{array} { l l } 6 \colon & \lambda ^ { \cdot }$$

x

7:

N

N

8:

∇

x

N

+1

N

=

Mirr

(

h

f

(

x

N

))

→

I

9:

else

$$\begin{array} { l l } 1 0 \colon & \quad M _ { N } = \| \nabla g ( x ^ { N } ) \| _ { * }, \, h _ { N } = \frac { \varepsilon } { M _ { N } ^ { 2 } } \\ 1 1 \cdot & \quad \varkappa ^ { N + 1 } - M i r r \ s l h \ s. \nabla a l \varkappa ^ { N } \bigcup \, / / \ \, \nolimits _ { n } \end{array}$$

x

11:

x

N

+1

=

Mirr

N

(

h

N

g x

(

N

))

12: end if

∇

/negationslash

13: N ← N +1 14: until 2 Θ 2 0 ε 2 /lessorequalslant ∑ j ∈ I 1 M 2 j + | I | Ensure: ¯ x N := argmin x , k k ∈ I f ( x k )

where τ is a positive number. Then for any y ∈ X

$$f ( y ) - f ( x _ { * } ) \leqslant \omega ( v _ { f } ( y, x _ { * } ) ),$$

where

/negationslash and v f ( y, x ∗ ) = 0 for ∇ f ( y ) = 0 .

$$& \vdots r e \\ & \quad v _ { f } ( y, x _ { * } ) = \left \langle \frac { \nabla f ( y ) } { \| \nabla f ( y ) \| }, y - x _ { * } \right \rangle \text{ for } \nabla f ( y ) \neq 0 \\ & \quad \omega \, v _ { f } ( u. x _ { * } ) = 0 \text{ for } \nabla f ( u ) = 0.$$

For Algorithm 1 the following theorem is valid.

Theorem 3.1. Let ε &gt; 0 be a fixed number and the stopping criterion of Algorithm 1 is satisfied. Then

$$\min _ { k \in I } v _ { f } ( x ^ { k }, x _ { * } ) < \varepsilon, \ \max _ { k \in I } g ( x ^ { k } ) \leqslant \varepsilon$$

Note, that Algorithm 1 works no more than

$$\ v o w v e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e w e h w e w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h s w w w h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e w e h w e w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h h w e h w e h h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e h w e w e h w e h w a l l w e n d e m m { \hat { N = 1 } }$$

iterations.

//

//

"productive steps"

"non-productive steps"

Now we will estimate the rate of convergence of the proposed method. For this we need the following auxiliary assumption ( [9], Lemma 3.2.1). Recall that x ∗ is the solution of the problem (2.1) - (2.2).

Basing on lemma 3.1 and theorem 3.1, we can estimate the rate of convergence of Algorithm 1 for a differentiable objective functional f with the Lipschitz-continuous gradient:

$$\| \nabla f ( x ) - \nabla f ( y ) \| _ { * } \leqslant L \| x - y \| \quad \forall x, y \in X.$$

Using the well-known inequality for exact solution x ∗ (see, for example, [9])

$$f ( x ) \leqslant f ( x _ { * } ) + \| \nabla f ( x _ { * } ) \| _ { * } \| x - x _ { * } \| + \frac { 1 } { 2 } L \| x - x _ { * } \| ^ { 2 } \\.$$

we can get that

$$\sum \nolimits _ { k \in I } & \circ \nolimits _ { k \in I } f ( x ^ { k } ) - f ( x _ { * } ) \leqslant \min _ { k \in I } \left \{ \| \nabla f ( x _ { * } ) \| _ { * } \| x ^ { k } - x _ { * } \| + \frac { 1 } { 2 } L \| x ^ { k } - x _ { * } \| ^ { 2 } \right \}. \\ \sum \nolimits _ { k \in I } & \circ \nolimits _ { k \in I } \cdot \quad \cdot \quad \cdot \quad \cdot \quad \cdot \cdot$$

Further, the following estimate is valid:

$$f ( x ) - f ( x _ { * } ) \leqslant \varepsilon \| \nabla f ( x _ { * } ) \| _ { * } + \frac { 1 } { 2 } L \varepsilon ^ { 2 }.$$

Corollary 3.1. Let f be differentiable on X and (3.9) holds. Then, after the stopping of Algorithm 1, the next inequality holds:

$$\min _ { 1 \leqslant k \leqslant N } f ( x ^ { k } ) - f ( x _ { * } ) \leqslant \varepsilon _ { f } + \frac { L \varepsilon ^ { 2 } } { 2 } = \varepsilon \cdot \| \nabla f ( x _ { * } ) \| _ { * } + \frac { L \varepsilon ^ { 2 } } { 2 }.$$

Let us observe a new version of the adaptive Mirror Descent method with another step selection strategy. A resembling idea was researched in [15] for Lipschitz-continuous functional. Note, that the following modification can be used to minimize functionals with different levels of smoothness. As earlier, we will consider the method for a fixed accuracy ε &gt; 0 , an initial approximation x 0 , and some value Θ 0 , such that V ( x , x 0 ∗ ) /lessorequalslant Θ 2 0 .

Note, that Algorithm 2 works during a fixed number of steps

$$\Phi _ { 1 } = \Phi _ { 2 } \Phi _ { 3 } \Phi _ { 4 } \Phi _ { 5 } \Phi _ { 6 } \Phi _ { 7 } \Phi _ { 8 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phicon \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi_ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 }
 \\ \Phi _ { 1 } = \Phi _ { 2 } \Phi _ { 3 } \Phi _ { 4 } \Phi _ { 5 } \Phi _ { 6 } \Phi _ { 7 } \Phi _ { 8 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi _ { 9 } \Phi }$$

The following theorem holds.

## Algorithm 2 Adaptive Mirror Descent

Require:

ε &gt;

0 Θ

,

0

:

d x

(

∗

)

/lessorequalslant

Θ

2

0

$$1 \colon \, x ^ { 0 } = a r g m i n _ { x \in X } \, d ( x )$$

2:

I

=:

3:

∅

N

0

4: repeat

←

5:

if g x

(

N

)

/lessorequalslant

ε

g x

(

N

)

∗

then

$$6 \colon \quad M _ { N } = \| \nabla f ( x ^ { N } ) \| _ { * }, \, h _ { N } = \frac { \varepsilon } { M _ { N } }$$

- 7: x N +1 = Mirr N ( h f ( x N )) // "productive steps"

8:

$$& \varepsilon ^ { N } ) \leqslant \varepsilon \| \nabla g ( x ^ { N } ) \| _ { * } \text{ then} \\ & \varepsilon = \| \nabla f ( x ^ { N } ) \| _ { * }, \, h _ { N } = \frac { \varepsilon } { M _ { N } } \\ & + 1 = M i r r _ { x ^ { N } } ( h _ { N } \nabla f ( x ^ { N } ) ) \, / \\ & \rightarrow I$$

N

I

9:

→

else

$$\begin{smallmatrix} \vdots & \text{max} \\ 1 0 \colon & M _ { N } = \| \nabla g ( x ^ { N } ) \| _ { * }, \, h _ { N } = \frac { \varepsilon } { M _ { N } } \\ 1 1 \colon & x ^ { N + 1 } = M i r r _ { x ^ { N } } ( h _ { N } \nabla g ( x ^ { N } ) ) \, \Big / \, \ " n o n \text{-producitive steps } " \\ 1 2 \colon & \text{end if } \end{smallmatrix}$$

- 12: end if

13:

N

N

+1

2

14:

until

2

←

Θ

0

2

ε Ensure: ¯ x N := argmin x , k k ∈ I f ( x k )

/lessorequalslant

N

Theorem 3.2. Let ε &gt; 0 be a fixed number and the stopping criterion of Algorithm 2 be satisfied. Then

$$\min _ { k \in I } v _ { f } ( x ^ { k }, x$$

Proof. 1) If k ∈ I ,

$$f. \ 1 ) & \text{ If } k \in I, \\ h _ { k }$$

/negationslash

2) If k ∈ I , then g x ( k ) ||∇ g x ( k ) || ∗ &gt; ε and g x ( k ) -g x ( ∗ ) ||∇ g x ( k ) || ∗ /greaterorequalslant g x ( k ) ||∇ g x ( k ) || ∗ &gt; ε . Therefore, the following inequalities hold

$$\text{the following inequalities no} \\ \varepsilon ^ { 2 } < h _ {$$

- 3) After summing up the inequalities (3.12) and (3.13) one can get

$$\sum _ { k \in I } \varepsilon v _ { f } ( x ^$$

$$\begin{array} {$$

After the stopping criterion of the algorithm holds one can get

$$\min _ { k \in I } v _ { f } ( x ^ { k }, x _ { * } ) \leqslant \varepsilon.$$

Further, for each k ∈ I g x ( k ) /lessorequalslant ε ||∇ g x ( k ) || ∗ /lessorequalslant εM g and

$$g ( \hat { x } ) & \leqslant \frac { 1 } { \sum _ { k \in I } h _ { k } } \sum _ { k \in I } h _ { k } g ( x ^ { k } ) \leqslant \varepsilon M _ { g }. \\ \intertext { a v e to show that the set of productive steps I is } _ { \alpha ^ { 2 } }$$

Now we have to show that the set of productive steps I is non-empty. If I = ∅ , then | J | = N and (2.3) means, that N /greaterorequalslant 2Θ 2 0 ε 2 . On the other hand, from (3.13) we have:

$$\frac { \varepsilon ^ { 2 } N } { 2 } < V ( x ^ { 0 }, x _ { * } ) \leqslant \Theta _ { 0 } ^ { 2 },$$

which leads us to the controversy, so I = ∅

/negationslash

.

Let us show how to estimate the quality of the solution by the function basing on the previous theorem. Note, that it is possible to take into account different levels of smoothness of the objective functional.

Corollary 3.2. Let f satisfy the Lipschitz condition

$$| f ( x ) - f ( y ) | \leqslant M _ { f } \| x - y \| \quad \forall x, y \in X.$$

Then, after the stopping of Algorithm 2, the following inequality holds:

$$\min _ { k \in I } f ( x ^ { k } ) - f ( x _ { * } ) \leqslant M _ { f } \varepsilon.$$

## 4. The case of a quasi-convex functionals

Let us consider the optimization problem (2.1) under the assumption of quasiconvexity of the objective functional f . The case of both quasi-convex f and

functional constraint g is observed in the Conclusions. Recall (see [5]) that function φ : Q → R is called quasi-convex, if

$$\phi \left ( ( 1 - \alpha ) x + \alpha y \right ) \leqslant \max \{ \phi ( x ), \phi ( y ) \} \ \forall \alpha \in [ 0 ; 1 ] \ \forall x, y \in Q.$$

As earlier, let g satisfy Lipschitz condition (2.3) with the constant M g .

Let us remind the definition of Clarke subdifferential. Let x 0 ∈ R n be a fixed point and h ∈ R n be a fixed direction. Denote

$$f _ { C l } ^ { \uparrow } ( x _ { 0 } ; h ) = \lim _ { x ^ { \prime } \rightarrow x _ { 0 } } \sup _ { \alpha \downarrow 0 } \frac { 1 } { \alpha } ( f ( x ^ { \prime } + \alpha h ) - f ( x ^ { \prime } ) ).$$

Value f ↑ Cl ( x 0 ; h ) is called Clarke subdifferential of functional f at the point x 0 in the direction h . This function is subadditive and positively homogeneous, thus we can define the subdifferential of the function f at the point x 0 as follows:

According to this,

$$\text{owns} \colon \\ \partial _ { C l } f ( x _ { 0 } ) & \coloneqq \left \{ v \in \mathbb { R } \ | \ f _ { C l } ^ { \uparrow } ( x _ { 0 } ; g ) \geqslant v g \ \forall g \in \mathbb { R } \right \}. \\ \text{ling to this,}$$

$$f _ { C l } ^ { \uparrow } ( x _ { 0 } ; h ) = \max _ { v \in \partial _ { C l } f ( x _ { 0 } ) } \langle v, h \rangle.$$

Note, that from now we will understand any element (vector) of the Clarke subdifferential as the subgradient of the quasi-convex (locally Lipschitz) functional f . For convex functional g , we understand the concept of a subgradient in the standard way.

Lemma 4.1. Let f : X → R . For any y ∈ Q , vector p y ∈ E ∗ and h &gt; 0 define z = Mirr y ( h · p y ) . Then for any x ∈ Q the next inequality holds:

$$h \langle p _ { y }, y - x \rangle \leqslant \frac { h ^ { 2 } } { 2 } \| p _ { y } \| _ { * } ^ { 2 } + V ( y, x ) - V ( z, x ).$$

Note, that for convex subdifferentiable functional f and subgradient p y = ∇ f ( y ) this inequality is modified as follows:

$$h ( f ( y ) - f ( x ) ) \leqslant \langle \nabla f ( y ), y - x \rangle \leqslant \frac { h ^ { 2 } } { 2 } \| \nabla f ( y ) \| _ { * } ^ { 2 } + V ( y, x ) - V ( z, x ).$$

Note that for quasi-convex objective f and constraint g instead of (sub)gradient ∇ f ( y ) in v f ( y, x ∗ ) (see (3.6)) we can consider a normal vector ∇ f ( y ) to a set of level of f at point y [9]. However, the (sub)gradient or Clarke subdifferential of f or g also can be used, if they are finite and nonzero.

Theorem 4.1. Let f be a quasi-convex functional. Then for Algorithm 1 after (3.10) steps (3.11) holds.

Remark 4.1. Let f satisfy the H¨lder condition ( o ν ∈ [0; 1) )

$$| f ( x ) - f ( y ) | \leqslant M _ { f, \, \nu } \| x - y \| ^ { \nu } \quad \forall x, y \in X.$$

For example, f ( x ) = √ x and f ( x ) = 4 √ x .

Let us note ( M f, ν /lessorequalslant M ν ) the following inequality ( [4], section 5; see [18] too)

which is true for small enough δ &gt; 0 for a /greaterorequalslant ε 0 &gt; 0 : f is a Lipshitzcontinuous at ε 0 -neighborhood of x ∗ from (3.11) for fixed ε 0 &gt; 0 due to (sub)differentiability of f . Then by (4.15) we have

$$M _ { \nu } a ^ { \nu } & \leqslant M _ { \nu } \left ( \frac { M _ { \nu } } { \delta } \right ) ^ { \frac { 1 - \nu } { 1 + \nu } } \frac { a ^ { 2 } } { 2 } + \delta, \\ \text{for small enough } \delta \ > \, 0 \text{ for } a \, \geqslant \, \varepsilon _ { 0 } \, > \, 0 \colon \, \ f \text{ is a Lisphitz}.$$

$$| f ( x ) - f ( y ) | \leqslant \frac { M _ { \nu } ^ { \frac { 2 } { 1 + \nu } } } { 2 \delta ^ { \frac { 1 - \nu } { 1 + \nu } } } \| x - y \| ^ { 2 } + \delta.$$

Set δ = ε , ε &gt; ε 0 . Then

$$\sim, \sim \sim _ { \mathcal { V } } \sim \dots \\ | f ( x ) - f ( y ) | & \leqslant \frac { M _ { \nu } ^ { \frac { 2 } { 1 + \nu } } } { \underbrace { 2 \varepsilon ^ { \frac { 1 - \nu } { 1 + \nu } } } _ { M } } \| x - y \| ^ { 2 } + \varepsilon. \\ y \text{ Lemma} \ 3. 1 \text{ after the stopping of Algorithm} \ 2, \varepsilon _ { 0 } \leqslant \min _ { k \in I } v _ { f } ( x ^ { k }, x _ { * } ) < \\ \text{e followin} \ \text{inequality} \ \text{holds}$$

Then by Lemma 3.1 after the stopping of Algorithm 2, ε 0 /lessorequalslant min k ∈ I v f ( x , x k ∗ ) &lt; ε means the following inequality holds

Note that for ε &lt; 1 the inequality (4.18) means

$$\psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psu _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \quad \psi _ { \ } \\ \text{that for $\varepsilon < 1$ the inequality $(4.18)$ means} \quad \widehat { \psi }$$

f ( ̂ x ) -f ∗ /lessorequalslant ̂ Mε for some ˆ M &gt; 0 . The another case of min k ∈ I v f ( x , x k ∗ ) &lt; ε /lessorequalslant ε 0 is not interesting due to Lipshitz-continuity of f at ε 0 -neighborhood of x ∗ . So, for problems with (quasi)convex H¨lder-continuous (sub)differentiable objective and cono vex Lipshitz-continuous functional constraints we can achieve an ε -solution after

$$O \left ( \frac { 1 } { \varepsilon ^ { 2 } } \right )$$

iterations of the Mirror Descent method. Obviously, this estimate is optimal. This estimate is optimal due to its optimality on a significantly narrower class of problems with Lipschitz-continuous objective functionals

## 5. Optimal methods for Mirror Descent on a class of non-smooth strongly convex problems

Consider the optimization problem under the assumption of strong convexity of the objective function and functional constraint with the parameter µ .

$$f ( x ) \to \min, \ g ( x ) \leqslant 0, \ x \in X$$

where X is a closed convex set.

Let the prox function d x ( ) be bounded on the unit sphere with respect to the chosen norm ‖ · ‖ :

$$d ( x ) \leqslant \Omega ^ { 2 }, \quad \forall x \in X \, \colon \| x \| \leqslant 1.$$

Let x 0 ∈ X and there exists R &gt; 0 0 , such that ‖ x 0 -x ∗ ‖ 2 /lessorequalslant R 2 0 .

We will propose methods which can guarantee an ε -solution ˆ x of the problem (5.19):

$$f ( \hat { x } ) - f ( x _ { * } ) \leqslant \varepsilon \text{ and } g ( \hat { x } ) \leqslant \varepsilon. \\. \quad. \quad. \quad. \quad. \quad. \quad. \quad.$$

The main idea is using the restart technique of Algorithm 2. Consider one well-known statement (see [1]).

Lemma 5.1. Let f and g be µ -strongly convex functionals with respect to the norm ‖ · ‖ on X x , ∗ = arg min x ∈ X f ( x ) , g x ( ) /lessorequalslant 0 ( ∀ x ∈ X ) and for some ε f &gt; 0 and ε g &gt; 0 the next inequalities hold:

$$f ( x ) - f ( x _ { * } ) \leqslant \varepsilon _ { f }, \ g ( x ) \leqslant \varepsilon _ { g }.$$

Then

$$\frac { \mu } { 2 } \| x - x _ { * } \| ^ { 2 } \leqslant \max \{ \varepsilon _ { f }, \varepsilon _ { g } \}.$$

Let us consider an analogue of Algorithm 2 for strongly convex problems. We must emphasize that for Algorithm 2 one can obtain effective estimates of the rate of convergence for the objective functionals with any level of

smoothness. According to Remark 4.1 we can apply our approach to H¨ldero continuous objective functionals.

Let us consider, in particular, the following example.

Let f ( x ) = max i =1 ,m f i ( x ) , where f i are differentiable at any x ∈ X and their gradients are Lipschitz-continuous:

$$\| \nabla f _ { i } ( x ) - \nabla f _ { i } ( y ) \| _ { * } \leqslant L _ { i } \| x - y \| \quad \forall x, y \in X, \ \forall i = \{ 1, m \}. \quad \quad ( 5. 2 3 )$$

Consider function τ : R + → R + :

$$\text{der function } \tau \colon \mathbb { R } ^ { + } \to \mathbb { R } ^ { + } \colon \\ \tau ( \delta ) & = \max \left \{ \delta \| \nabla f ( x _ { * } ) \| _ { * } + \frac { \delta ^ { 2 } L } { 2 }, \, \delta \right \},$$

where

$$L \coloneqq \max _ { i = \overline { 1, m } } \{ L _ { i } \}.$$

It is obvious that τ decreases, τ (0) = 0 , so for any ε &gt; 0 there exists

$$\hat { \varphi } ( \varepsilon ) > 0 \, \colon \, \tau ( \hat { \varphi } ( \varepsilon ) ) = \varepsilon.$$

## Algorithm 3 Restart procedure for Algorithm 3

Require: accuracy ε &gt; 0; initial point x 0 ; Ω s.t. d x ( ) /lessorequalslant Ω 2 ∀ x ∈ X : ‖ x ‖ /lessorequalslant 1; 0 2 R . 2

- 1: Set d 0 ( x ) = d ( x -x 0 R 0 ) . 2: Set p = 1 .

X d ; ( ); · strong convexity parameter µ R ; 0 such that ‖ x -x ∗ ‖ /lessorequalslant 0

- 3: repeat
- 4: Set R 2 p = R 2 0 · 2 -p .
- 6: Set x p as output of Algorithm 2 with accuracy ˆ( ϕ ε p ) , prox function d p -1 ( ) · and Ω 2 .
- 5: Set ε p = µR 2 p 2 .
- 7: d p ( x ) ← d ( x -x p R p ) . 8: Set p = p +1 .
- 9: until p &gt; log 2 µR 2 0 2 ε .

Theorem 5.1. Let ∇ f be Lipschitz-continuous, f and g be µ -strongly convex on X ⊂ R n and d x ( ) /lessorequalslant Ω 2 for all x ∈ X, such that ‖ x ‖ /lessorequalslant 1 . Let initial point x 0 ∈ X and R &gt; 0 0 satisfy

$$\| x ^ { 0 } - x _ { * } \| ^ { 2 } \leqslant R _ { 0 } ^ { 2 }.$$

Then for ̂ p = ⌈ log 2 µR 2 0 2 ε ⌉ output x ̂ p is an ε -solution of the problem (5.19), also, the following inequalities hold:

$$f ( x ^ { \widehat { p } } ) - f ( x _ { * } ) \leqslant & \varepsilon, \quad g ( x ^ { \widehat { p } } ) \leqslant M _ { g } \varepsilon,$$

$$\| x ^ { \widehat { p } } - x _ { * } \| ^ { 2 } \leqslant \frac { 2 \varepsilon } { \mu } \max \{ 1, M _ { g } \}.$$

The number of iterations of Algorithm 2 during the work of Algorithm 3 will not exceeds

The proof is given in Appendix.

$$\widehat { p } + \sum _ { p = 1 } ^ { \widehat { p } } \frac { 2 \Omega ^ { 2 } \max \{ 1, M _ { g } \} } { \hat { \varphi } ^ { 2 } ( \varepsilon _ { p } ) }, \ \ w h e r e \ \varepsilon _ { p } = \frac { \mu R _ { 0 } ^ { 2 } } { 2 ^ { p + 1 } }. \\ \text{proof is given in Appendix.} \\ \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \, \epsilon _ { \dots } \dots \end{matrix}$$

We can formulate the following corollary for the case M g /lessorequalslant 1 .

Corollary 5.1. Let ∇ f be Lipschitz-continuous, f and g be µ -strongly convex on X ⊂ R n and d x ( ) /lessorequalslant Ω 2 for all x ∈ X, such that ‖ x ‖ /lessorequalslant 1 . Let initial point x 0 ∈ X and R &gt; 0 0 satisfy

$$& \| x ^ { 0 } - x _ { * } \| ^ { 2 } \leqslant R _ { 0 } ^ { 2 }. \\ & \quad - \cap \, -$$

Then for M g /lessorequalslant 1 and ̂ p = ⌈ log 2 µR 2 0 2 ε ⌉ output x ̂ p is an ε -solution of the problem (5.19), also, the following inequalities hold:

$$f ( x ^ { \widehat { p } } ) - f ( x _ { * } ) \leqslant \varepsilon, \quad g ( x ^ { \widehat { p } } ) \leqslant M _ { g } \varepsilon, \\ \| x ^ { \widehat { p } } - x _ { * } \| ^ { 2 } \leqslant \frac { 2 \varepsilon } { \mu }. \\ \colon \colon \dots \colon \dots \colon \colon \colon \colon \dots \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \colon \end{cases}$$

The number of iterations of Algorithm 2 during the work of Algorithm 3 will not exceeds

Remark 5.1. The estimate of the number of iterations of Algorithm 2 can be detailed in the case of ε &lt; 1 . For any δ &lt; 1 there is such constant C , that τ ( δ ) /lessorequalslant Cδ for some constant C . So, we can suppose that ˆ( ϕ ε ) = ̂ C ε · for the corresponding constant ̂ C &gt; 0 . On the restart number p +1 of Algorithm 2 after no more than

$$\widehat { p } + \sum _ { p = 1 } ^ { \widehat { p } } \frac { 2 \Omega ^ { 2 } } { \hat { \varphi } ^ { 2 } ( \varepsilon _ { p } ) }, \text{ where } \varepsilon _ { p } = \frac { \mu R _ { 0 } ^ { 2 } } { 2 ^ { p + 1 } }. \\ \text{The estimate of the number of iterations of A} \\ \lambda \cdots \cdots \cdots \varepsilon \cdots \varepsilon \cdots \varepsilon \cdots \varepsilon \cdots \varepsilon \cdots \varepsilon.$$

$$k _ { p + 1 } = \left \lceil \frac { 2 \Omega ^ { 2 } R _ { p } ^ { 2 } } { \varepsilon _ { p + 1 } ^ { 2 } } \right \rceil \quad \ \ \ \ ( 5. 2 5 )$$

iterations of Algorithm 2, the output x p +1 satisfies the following inequality:

$$& f ( x ^ { p + 1 } ) - f ( x _ { * } ) \leqslant \widehat { C } \cdot \varepsilon _ { p + 1 }, \ \ g ( x ^ { p + 1 } ) \leqslant \varepsilon _ { p + 1 }, \\ & \quad \sim \varepsilon$$

̂ where ε p +1 = µR 2 p +1 2 . According to Lemma 5.1,

So, for all p /greaterorequalslant 0 ,

$$\| x ^ { p + 1 } - x _ { * } \| ^ { 2 } & \leqslant \frac { 2 \max \{ 1, \widehat { C } \} \varepsilon _ { p + 1 } } { \mu } = \max \{ 1, \widehat { C } \} \cdot R _ { p + 1 } ^ { 2 }. \\ \intertext {, for all } p \geqslant 0, & \quad \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \$$

‖ x p -x ∗ ‖ 2 /lessorequalslant max 1 { , C ̂ } · R 2 p = max 1 { , C ̂ } · R 2 0 · 2 -p . Note, that for all p /greaterorequalslant 1 the following inequalities hold:

$$f ( x ^ { p } ) - f ( x _ { * } ) & \leqslant \max \{ 1, \widehat { C } \} \cdot \frac { \mu R _ { 0 } ^ { 2 } } { 2 } \cdot 2 ^ { - p }, \quad g ( x _ { p } ) \leqslant \max \{ 1, \widehat { C } \} \cdot \frac { \mu R _ { 0 } ^ { 2 } } { 2 } \cdot 2 ^ { - p }. \\ \text{Thereby, if } p > \log _ { 2 } \frac { \mu R _ { 0 } ^ { 2 } } { 2 \varepsilon }, \text{then } x ^ { p } \text{ will be } \left ( \max \{ 1, \widehat { C } \} \varepsilon \right ) \text{-solution to the prob}.$$

$$\| x ^ { p } - x _ { * } \| ^ { 2 } \leqslant \max \{ 1, \widehat { C } \} \cdot R _ { 0 } ^ { 2 } \cdot 2 ^ { - p } \leqslant \frac { 2 \varepsilon } { \mu }. \\ \text{evaluate the total number of iterations $N$ of Algorit} \\ \iota R _ { 0 } ^ { 2 } \prod \nolimits \nolimits + \infty \nolimits \nolimits + \infty \nolimits + \infty \nolimits.$$

Thereby, if p &gt; log 2 µR 2 0 2 ε , then x p will be ( max 1 { , C ̂ } ε ) -solution to the problem, moreover:

Let us evaluate the total number of iterations N of Algorithm 2. Let ˆ = p ⌈ log 2 µR 2 0 2 ε ⌉ . According to (5.25), up to multiplication by a constant we have:

$$\text{ave} \colon \\ N & = \sum _ { p = 1 } ^ { \hat { p } } k _ { p } \leqslant \sum _ { p = 1 } ^ { \hat { p } } \left ( 1 + \frac { 2 \Omega ^ { 2 } R _ { p } ^ { 2 } } { \varepsilon _ { p + 1 } ^ { 2 } } \right ) = \sum _ { p = 1 } ^ { \hat { p } } \left ( 1 + \frac { 3 2 \Omega ^ { 2 } 2 ^ { p } } { \mu ^ { 2 } R _ { 0 } ^ { 2 } } \right ) \\ & \leqslant \hat { p } + \frac { 6 4 \Omega ^ { 2 } 2 ^ { \hat { p } } } { \mu ^ { 2 } R _ { 0 } ^ { 2 } } \leqslant \hat { p } + \frac { 6 4 \Omega ^ { 2 } } { \mu \varepsilon }. \\ \text{Note that the method can be anniled to solve the nroblam ( 2 1 ) in tb}$$

Note, that the method can be applied to solve the problem (2.1) in the case of strongly quasi-convex objective functional. As earlier, x ∗ is a solution of the optimization problem.

Remark 5.2. Function f : Q → R is called strongly quasi-convex [16], if if for each x ∈ Q

$$f ( x _ { * } ) - f ( x ) \geqslant \langle \nabla f ( x ), x _ { * } - x \rangle + \frac { \mu } { 2 } \| x _ { * } - x \| ^ { 2 },$$

where x ∗ is a nearest to x solution of the optimization problem.

Thus, the method and all the estimates in this paragraph are valid in the case of strongly quasi-convex objective H¨lder-continuous functionals. o

## 6. Numerical Experiments

All calculations were performed in CPython 3.7 on computer fitted with a 3core AMD Athlon II X3 450 processor with a clock frequency of 3.2 GHz. The computer's RAM was 8 GB. We indicate the operating time of the algorithms in minutes and seconds.

## 6.1 An analogue of the Fermat-Torricelli-Steiner problem

Example 6.1. Input data: n = 1000 , point coordinates A k = ( a 1 k , a 2 k , . . . , a nk ) ( k = 1 2 , , . . . , r ; r = 5 ) are represented by integers from the interval [ -10 10] , , objective functional ( M f = 1 )

$$f ( x ) & = \frac { 1 } { r } \sum _ { k = 1 } ^ { r } \sqrt { ( x _ { 1 } - a _ { 1 k } ) ^ { 2 } + ( x _ { 2 } - a _ { 2 k } ) ^ { 2 } + \dots + ( x _ { n } - a _ { n k } ) ^ { 2 } }, \\ \omega & = \frac { 1 } { r } \sin \omega \Delta _ { 0 } \Delta _ { 0 } \Delta _ { 0 } \Delta _ { 0 } \Delta _ { 0 } \Delta _ { 0 } \Delta _ { 0 }.$$

x 0 = (0 1 . ,..., 0 1) . ‖ (0 1 . ,..., 0 1) . ‖ , functional constraint

$$g _ { 1 }$$

$$\int _ { 0 } \dots \dots, \dots, \dots, \dots / \int _ { 0 } \\ g ( x ) = \max _ { m = 1, 2, 3, \dots, 2 0 } \{ g _ { m } ( x ) \} \leqslant 0, \\ g _ { 1 } ( x ) = \alpha _ { 1 1 } | x _ { 1 } | + \alpha _ { 1 2 } | x _ { 2 } | + \dots + \alpha _ { 1 n } | x _ { n } | - 1, \\ g _ { 2 } ( x ) = \alpha _ { 2 1 } | x _ { 1 } | + \alpha _ { 2 2 } | x _ { 2 } | + \dots + \alpha _ { 2 n } | x _ { n } | - 1, \\ \dots \\ g _ { m } ( x ) = \alpha _ { m 1 } | x _ { 1 } | + \alpha _ { m 2 } | x _ { 2 } | + \dots + \alpha _ { m n } | x _ { n } | - 1, \\ e \, \text{the coefficients} \, \alpha _ { 1 1 }, \alpha _ { 1 2 }, \dots, \alpha _ { m n } \, \text{are represented by the matrix}$$

where the coefficients α 11 , α 12 , . . . , α mn are represented by the matrix

$$\colon & \text{coefficients} \, \alpha _ { 1 1 }, \alpha _ { 1 2 }, \dots, \alpha _ { m n } \, \text{are represented by the matrix} \\ \begin{pmatrix} 1 & 1 & 1 & 1 & \dots & 1 & 1 \\ 1 & 2 & 2 & 2 & \dots & 2 & 2 \\ 1 & 3 & 3 & 3 & \dots & 3 & 3 \\ 1 & 2 & 3 & 4 & \dots & 999 & 1000 \\ 1 & 3 & 4 & 5 & \dots & 1000 & 1001 \\ \dots & \dots & \dots & \dots & \dots \\ 1 & 1 8 & 1 9 & 2 0 & \dots & 1 0 1 5 & 1 0 1 6 \end{pmatrix}. \quad \quad ( 6. 2 7 )$$

The results of Example 6.1 are presented in Table 1. As one can observe, Algorithm 2 works faster than Algorithm 1.

Table 1: Comparison of the results of the algorithms, Example 6.1.

| ε     | Iterations   | Time, MM:SS   | Iterations   | Time, MM:SS   |
|-------|--------------|---------------|--------------|---------------|
|       | Algorithm 1  | Algorithm 1   | Algorithm 2  | Algorithm 2   |
| 1 / 2 | 30824        | 02:58         | 17           | 00:00.1       |
| 1 / 4 | 61679        | 05:54         | 65           | 00:00.4       |
| 1 / 6 | -            | >05:00        | 145          | 00:01         |
| 1 / 8 | -            | >05:00        | 257          | 00:01         |

Table 2: Comparison of the results of the algorithms, Example 6.2.

| ε     | Iterations   | Time, MM:SS   | Iterations   | Time, MM:SS   |
|-------|--------------|---------------|--------------|---------------|
|       | Algorithm 1  | Algorithm 1   | Algorithm 2  | Algorithm 2   |
| 1 / 2 | 31264        | 03:01         | 17           | 00:00.1       |
| 1 / 4 | 65056        | 06:16         | 65           | 00:00.4       |
| 1 / 6 | -            | >05:00        | 145          | 00:01         |
| 1 / 8 | -            | >05:00        | 257          | 00:01         |

## 6.2 An analogue of the problem of the smallest covering circle

Example 6.2. Input data: n = 1000 , point coordinates A k = ( a 1 k , a 2 k , . . . , a nk ) ( k = 1 2 , , . . . , 5 interval [ 10 10] , , objective functional ( M = 1 )

$$\dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \ dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \ delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \ delta \ dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta dots \ delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots \delta \dots
x ^ { 0 } = \frac { ( 0. 1, \dots, \dots, 0. 1 ) } { n / \infty }. \text{functional constraint $( 6. 2 6 ). $ where the coefficients}$$

) are represented by integers from the -f x 0 = (0 1 . ,..., 0 1) . ‖ (0 1 . ,..., 0 1) . ‖ , functional constraint (6.26), where the coefficients α 11 , α 12 , . . . , α mn are represented by the matrix (6.27).

The results of Example 6.2 are presented in Table 2. As one can observe, Algorithm 2 works faster than Algorithm 1.

Table 3: Comparison of the results of the algorithms, Example 6.3.

| ε     | Iterations   | Time, MM:SS   | Iterations   | Time, MM:SS   |
|-------|--------------|---------------|--------------|---------------|
|       | Algorithm 1  | Algorithm 1   | Algorithm 2  | Algorithm 2   |
| 1 / 2 | -            | >05:00        | 17           | 00:00.1       |
| 1 / 4 | -            | >05:00        | 65           | 00:00.4       |
| 1 / 6 | -            | >05:00        | 145          | 00:01         |
| 1 / 8 | -            | >05:00        | 257          | 00:01         |

## 6.3 An example of a concave objective functional satisfying the H¨lder condition o

Example 6.3. Input data: n = 1000 , objective functional ( M f, / 1 2 = 1 )

$$f ( x ) = \frac { 1 } { n } \sum _ { i = 1 } ^ { n } \sqrt { x _ { i } },$$

x 0 = (0 1 . ,..., 0 1) . ‖ (0 1 . ,..., 0 1) . ‖ , X = { x = ( x , . . . , x 1 n ) | x i /greaterorequalslant 0 ∀ i, n ∑ i =1 x 2 i /lessorequalslant 1 } , functional constraint

$$s u a m \\ g ( x ) = \max _ { m = 1, 2, 3, \dots, 2 0 } \{ g _ { m } ( x ) \}, \\ g _ { 1 } ( x ) = \alpha _ { 1 1 } x _ { 1 } + \alpha _ { 1 2 } x _ { 2 } + \dots + \alpha _ { 1 n } x _ { n } - 1 \leqslant 0, \\ g _ { 2 } ( x ) = \alpha _ { 2 1 } x _ { 1 } + \alpha _ { 2 2 } x _ { 2 } + \dots + \alpha _ { 2 n } x _ { n } - 1 \leqslant 0, \\ \dots \\ g _ { m } ( x ) = \alpha _ { m 1 } x _ { 1 } + \alpha _ { m 2 } x _ { 2 } + \dots + \alpha _ { m n } x _ { n } - 1 \leqslant 0, \\ \text{ere the coefficients $\alpha_{1}$, $\alpha_{12}$, \dots, \alpha_{mn}$ are represented by the matrix (6.27).}$$

where the coefficients α 11 , α 12 , . . . , α mn are represented by the matrix (6.27).

The results of Example 6.3 are presented in Table 3. As one can observe, Algorithm 2 works faster than Algorithm 1.

## 6.4 Examples with large dimensions

Table 4 presents the results of Algorithm 2 for the dimension n = 3 · 10 5 . Because of the large dimensionality it is impossible to obtain the results for Algorithm 1 and its modified version, since the compiler composing the program code of the algorithm cannot process the input data due to the

Table 4: Some results of Algorithm 2 for n = 3 · 10 5 .

| ε     | Iterations   | Time, MM:SS   | Iterations   | Time, MM:SS   | Iterations   | Time, MM:SS   |
|-------|--------------|---------------|--------------|---------------|--------------|---------------|
|       | Example 6.1  | Example 6.1   | Example 6.2  | Example 6.2   | Example 6.3  | Example 6.3   |
| 1 / 2 | 17           | 00:38         | 17           | 00:37         | 17           | 00:37         |
| 1 / 4 | 65           | 02:28         | 65           | 02:33         | 65           | 02:24         |
| 1 / 6 | 145          | 05:32         | 145          | 05:52         | 145          | 05:27         |

integer overflow error. Execution of Algorithm 2 does not entail such an error.

## 6.5 An example a geometrical problem of a quasi-convex objective functional

Example 6.4. Suppose we are given several points A k (the centers of the balls ω k ). It is necessary to find the ball of the smallest radius R that covers these points. In other words, it is necessary to find the center of such a ball so that the maximum distance from the center to these points is the shortest possible. At the same time, we assume that the point (center) X can lie on some set, which is defined by functional constraint (6.28), where the coefficients α 11 , α 12 , . . . , α mn are represented by the matrix (6.27). The distance from X to each of the fixed points A k is determined as follows:

$$d ( X, A _ { k } ) = \begin{cases} X A _ { k } + ( \rho - 1 ) r _ { k }, & \text{if $|XA_{k}|>r_{k}$ (} r_{k}-radius \omega_{k}$, $\rho>1$)}, \\ \rho X A _ { k }, & \text{otherwise}, \end{cases}$$

where d X, A ( k ) =: f ( x ) is a concave function ( M f = ρ ). Note that d X, A ( k ) is non-smooth in points X: | XA k | = r k . For points of non-smoothness we use some element of Clarke subdifferential as analogue of subgradient.

Other input data: n = 1000 , ρ = 2 , x 0 = (0 1 . ,..., 0 1) . ‖ (0 1 . ,..., 0 1) . ‖ . The coordinates of the points A k are chosen in such a way that ‖ A k ‖ ∈ [1; 2] , the number of points A k is equal to 1000 and r k = 1 for all k = 1 100 , .

The results of Example 6.4 are presented in Table 5. As one can observe, Algorithm 2 works faster than Algorithm 1, however, the estimate rate with regard to the objective function is the same, but with regard to the constraints can be much worse.

Table 5: Comparison of the results of the algorithms, Example 6.4.

| ε      | Iterations   | Time, MM:SS   | Iterations   | Time, MM:SS   |
|--------|--------------|---------------|--------------|---------------|
|        | Algorithm 1  | Algorithm 1   | Algorithm 2  | Algorithm 2   |
| 1 / 2  | 4848         | 00:34         | 17           | 00:02         |
| 1 / 4  | 10132        | 01:17         | 65           | 00:09         |
| 1 / 6  | 15242        | 02:39         | 145          | 00:18         |
| 1 / 8  | 20437        | 03:10         | 257          | 00:36         |
| 1 / 10 | 25593        | 04:23         | 400          | 01:01         |
| 1 / 12 | 30742        | 05:11         | 577          | 01:46         |

## 7. Conclusion

Summing up, let's remark the conclusions of the article. There was proposed an analogue of adaptive Mirror Descent ( [2], Section 3.3) for convex programming problems with another step-size strategy. Estimates of the rate of its convergence were proved. Optimality in terms of lower bounds was stated. Moreover, it was shown, that proposed methods can be used to minimize quasi-convex objective functionals with different levels of smoothness. Also, using the restart technique an optimal method was proposed to solve optimization problems with strongly convex objective functionals. Some numerical experiments were carried out to solve geometrical problems with convex constraints. Advantages of proposed methods were demonstrated during these experiments. Numerical examples for the minimization of quasi-convex functionals were given. As the result, proposed methods work faster then ( [2], Section 3.3). However, functional constraint evaluation, generally, can deteriorate: g x (¯) &lt; M ε g instead of g x (¯) &lt; ε in [2].

In addition let us show how the main results of the work can be extended to the Lipschitz quasi-convex constraint.

Lemma 7.1. Lemma 3.1 is valid for v g ( y, x ∗ ) in the case of quasi-convex objective and constraint.

Let us consider the following modification of Algorithm 1 under the assumption of quasi-convexity of the objective functional and constraint. We can use the technique proposed in [12]. Namely, instead of the (sub)gradient

∇ f we should consider the following set

$$\hat { \ D f } ( x ) & = \{ p \ | \ \langle p, x - y \rangle \geqslant 0 \ \forall y \in X \colon \ f ( y ) \leqslant f ( x ) \}. \\ \dots \ \dots \ \cdot \ \cdot \ \cdot \ \cdot \quad \longrightarrow \ \cdots \ \cdots \ \cdots \ \cdots \ \cdots$$

/negationslash

Generally, this set is non-empty, closed and convex cone. Following [12], we assume that ˆ Df x ( ) = { } 0 . Hereinafter denote Df x ( ) as one arbitrary vector from ˆ Df x ( ) :

$$D f ( x ) \in \hat { D } f ( x ).$$

## Algorithm 4 Modification of MDA for quasi-convex constraint

IF

g x

(

k

)

/lessorequalslant

M ε

g

(productive steps)

x k +1 = Mirr x k ( h Df x f k ( k ))

ELSE (non-productive steps) x k +1 = Mirr x k ( h Dg x g k ( k ))

Let us choose the step-sizes as follows: h f k = C f ‖ Df x ( k ) ‖ ∗ , h g k = C g ‖ Dg x ( k ) ‖ ∗ . Denote N , N I J as the number of productive and non-productive steps during the work of the Algorithm respectively. Similar to [2] (see the proof of Theorem 3.2) the next inequality holds:

$$C _ { f } N _ { I } \min _ { k \in I } v _ { f } ( x _ { * }, x ^ { k } ) \leqslant \frac { 1 } { 2 } \sum _ { k \in I } ( h _ { k } ^ { f } ) ^ { 2 } \| D f ( x ^ { k } ) \| _ { 2 } ^ { 2 } - C _ { g } \sum _ { k \in J } v _ { g } ( x _ { * }, x ^ { k } ) +$$

Let C g = C f = ε, N /greaterorequalslant 2Θ 2 0 ε 2 . As g x ( k ) /greaterorequalslant M ε, k g ∈ J and using Lemma 7.1 for constraint g x ( ) with Lipschitz constant M g we get

$$& \colon \text{next inequality holds:} \\ & _ { f } ( x _ { * }, x ^ { k } ) \leqslant \frac { 1 } { 2 } \sum _ { k \in I } ( h _ { k } ^ { f } ) ^ { 2 } \| D f ( x ^ { k } ) \| _ { 2 } ^ { 2 } - C _ { g } \sum _ { k \in J } v _ { g } ( x _ { * }, \\ & \quad + \frac { 1 } { 2 } \sum _ { k \in J } ( h _ { k } ^ { g } ) ^ { 2 } \| D g ( x ^ { k } ) \| _ { 2 } ^ { 2 } + \Theta _ { 0 } ^ { 2 }. \\ & = \varepsilon, \ N \geqslant \frac { 2 \Theta _ { 0 } ^ { 2 } } { \varepsilon ^ { 2 } }. \ \text{As } g ( x ^ { k } ) \geqslant M _ { g } \varepsilon, \ k \in J \text{ and usi}$$

$$- v _ { g } ( x _ { * }, x ^ { k } ) & \leqslant ( g ( x _ { * } ) - g ( x ^ { k } ) ) / M _ { g } \leqslant - g ( x ^ { k } ) / M _ { g } \leqslant - \varepsilon. \\ \vdots \quad & = \cdots \cdots \cdots. \cdots \cdots. \cdots.$$

Theorem 7.1. Let f be quasi-convex, g be quasi-convex with Lipschitz constant M g . Then for Algorithm 3 after (3.10) steps (3.11) holds.

The authors are very grateful to Y. Nesterov for fruitful discussions.

## References

- [1] Bayandina A., Gasnikov A., Gasnikova E., Matsievsky S. Primaldual method of Mirror Descent for stochastic constrained optimization problems . // Journal of Computational Mathematics and Mathematical Physics 2018. V. 58, в'- 11. P. 1728-1736.

| [2]   | Bayandina A., Dvurechensky P., Gasnikov A., Stonyakin F., Titov A. Mirror descent and convex optimization problems with non- smooth inequality constraints. // Large-Scale and Distributed Optimiza- tion, Lect. Notes Math., 2227, Springer, Cham, 2018, 181вЂ'213.   |
|-------|------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------|
| [3]   | BeckA., Teboulle M. Mirror descent and nonlinear projected subgra- dient methods for convex optimization. // Operations Research Letters, 31(3): 167-175, 2003.                                                                                                        |
| [4]   | Gasnikov, A. Modern numerical optimization methods. The method of universal gradient descent. // M .: MIPT, 2018.                                                                                                                                                      |
| [5]   | Hazan, E., Levy, K., & Shalev-Shwartz, S. Beyond convexity: Stochastic quasi-convex optimization. // In Advances in Neural Infor- mation Processing Systems, pp. 1594-1602, 2015.                                                                                      |
| [6]   | Clarke F. Optimization and non-smooth analysis. // New York: John Wiley and Sons, 1983.                                                                                                                                                                                |
| [7]   | Ben-Tal A., Nemirovski A. Robust Truss Topology Design via Semidefinite Programming. // SIAM Journal on Optimization, 7(4): 991-1016, 1997.                                                                                                                            |
| [8]   | NemirovskyA., YudinD. Problem Complexity and Method Effi- ciency in Optimization. //J. Wiley & Sons, New York, 1983.                                                                                                                                                   |
| [9]   | NesterovY. Introductory Lectures on Convex Optimization: a basic course . Kluwer Academic Publishers, Massachusetts, 2004.                                                                                                                                             |
| [10]  | NesterovY. Subgradient methods for convex functions with nonstan- dard growth properties.                                                                                                                                                                              |
| [11]  | Nesterov, Y. Minimization methods for nonsmooth convex and quasi- convex functions. //Matekon, 29, 519-531, 1984.                                                                                                                                                      |
| [12]  | Nesterov, Y. Effective methods in nonlinear programming. // Radio and communication, 1989.                                                                                                                                                                             |
| [13]  | Konnov, I. On convergence properties of a subgradient method. //Op- timization Methods and Software, 18(1), 53-62, 2003.                                                                                                                                               |

- [14] Shpirko S., Nesterov Y. Primal-dual Subgradient Methods for Hugescale Linear Conic Problem. // SIAM Journal on Optimization, 24(3): 1444-1457, 2014.
- [15] Juditsky, A., &amp; Nemirovski, A. First order methods for nonsmooth convex large-scale optimization, i: general purpose methods. // Optimization for Machine Learning, 2010, 121-148.
- [16] Necoara, I., &amp; Nesterov, Y., Glineur, F Linear convergence of first order methods for non-strongly convex optimization. // Mathematical Programming, pp. 1-39, 2019.
- [17] Gower, R. M., Loizou, N., Qian, X., Sailanbayev, A., Shulgin, E., &amp; Richtarik, P. SGD: General Analysis and Improved Rates. // arXiv preprint arXiv:1901.09401, 2019.
- [18] F. Stonyakin, A.Gasnikov, P. Dvurechensky, M.Alkousa, A.Titov Generalized Mirror Prox for Monotone Variational Inequalities: Universality and Inexact Oracle. // arXiv.org e-Print archive. 2019. - URL: https://arxiv.org/pdf/1806.05140.pdf

## 8. Appendix: Proof of Theorem 5.1

Proof. Function d p ( x ) = d ( x -x p R p ) , defined in Algorithm 3, is 1 -strongly convex with respect to the norm ‖ ‖ . R p for all p /greaterorequalslant 0 . It is also easy to prove the following inequality

$$\| x ^ { p } - x _ { * } \| ^ { 2 } \leqslant R _ { p } ^ { 2 } \max \{ 1, M _ { g } \} \quad \forall p \geqslant 0.$$

If p = 0 the statement holds due to the choosing of x 0 and R 0 . Suppose that ‖ x p -x ∗ ‖ 2 /lessorequalslant R 2 p max 1 { , M g } for some p . Let us prove that ‖ x p +1 -x ∗ ‖ 2 /lessorequalslant R 2 p +1 max 1 { , M g } . As d p ( x ∗ ) /lessorequalslant Ω max 1 2 { , M g } , on the restart number ( p +1) after no more than iterations of Algorithm 2, for x p +1 = ¯ x N p +1 the next inequalities hold:

$$\Gamma \smallsetminus \mu \nu \ \theta \quad \Phi \quad \Psi \nu \nu \\ N _ { p + 1 } = \left \lceil \frac { 2 \Omega ^ { 2 } \max \{ 1, M _ { g } \} } { \hat { \varphi } ^ { 2 } ( \varepsilon _ { p + 1 } ) } \right \rceil \\ \text{:hm $2$ for $r^{p+1}=\bar{\tau}^{N_{p+1}$ t.he next ineq}$}$$

$$f ( x ^ { p + 1 } ) - f ( x _ { * } ) \leqslant \varepsilon _ { p + 1 }, \ \ g ( x ^ { p + 1 } ) \leqslant \varepsilon _ { p + 1 } M _ { g } \ \text{ if } \ \varepsilon _ { p + 1 } = \frac { \mu R _ { p + 1 } ^ { 2 } } { 2 }.$$

According to Lemma 5.1

$$\| x ^ { p + 1 } - x _ { * } \| ^ { 2 } \leqslant \frac { 2 \varepsilon _ { p + 1 } } { \mu } \max \{ 1, M _ { g } \} = R _ { p + 1 } ^ { 2 } \max \{ 1, M _ { g } \}.$$

So, for any p /greaterorequalslant 0 we have proved that

$$\| x ^ { p } - x _ { * } \| ^ { 2 } \leqslant R _ { p } ^ { 2 } \max \{ 1, M _ { g } \} = \frac { R _ { 0 } ^ { 2 } } { 2 ^ { p } } \max \{ 1, M _ { g } \},$$

$$f ( x ^ { p } ) & - f ( x _ { * } ) \leqslant \frac { \mu R _ { 0 } ^ { 2 } } { 2 ^ { p + 1 } }, \quad g ( x ^ { p } ) \leqslant \frac { \mu R _ { 0 } ^ { 2 } M _ { g } } { 2 ^ { p + 1 } }.$$

Consequently, p = ̂ p = ⌈ log 2 µR 2 0 2 ε ⌉ output x p is an ε -solution of the problem (5.19) and next inequalities hold:

$$\| x ^ { p } - x _ { * } \| ^ { 2 } \leqslant R _ { p } ^ { 2 } \max \{ 1, M _ { g } \} = \frac { R _ { 0 } ^ { 2 } } { 2 ^ { p } } \max \{ 1, M _ { g } \} \leqslant \frac { 2 \varepsilon } { \mu } \max \{ 1, M _ { g } \}.$$

Let K be the number of iterations of Algorithm 2 during the work of Algorithm 3, N p be the total number of iterations of Algorithm 2 on the restart number p . As function τ : R + → R + increases and for any ε &gt; 0 there exists ˆ( ϕ ε ) &gt; 0 : τ ( ˆ( ϕ ε )) = ε . It means that

$$\cdot \cdot \cdot \cdot \\ K = \sum _ { p = 1 } ^ { \widehat { p } } N _ { p } = \sum _ { p = 1 } ^ { \widehat { p } } \left \lceil \frac { 2 \Omega ^ { 2 } \max \{ 1, M _ { g } \} } { \hat { \varphi } ^ { 2 } ( \varepsilon _ { p } ) } \right \rceil \leq \widehat { p } + \sum _ { p = 1 } ^ { \widehat { p } } \frac { 2 \Omega ^ { 2 } \max \{ 1, M _ { g } \} } { \hat { \varphi } ^ { 2 } ( \varepsilon _ { p } ) }. \\ \cdot \cdot \cdot \\ \cdot \cdot \cdot \cdot \cdot \cdot$$

So, the number of iterations of Algorithm 2 during the work of Algorithm 3 will not exceeds

$$\widehat { p } + \sum _ { p = 1 } ^ { \widehat { p } } \frac { 2 \Omega ^ { 2 } \max \{ 1, M _ { g } \} } { \hat { \varphi } ^ { 2 } ( \varepsilon _ { p } ) }, \text{ where } \varepsilon _ { p } = \frac { \mu R _ { 0 } ^ { 2 } } { 2 ^ { p + 1 } }.$$

$$\widehat { p } + \sum _ { p = 1 } ^ { \widehat { p } } \frac { c } { 2 }$$
Fedor Stonyakin Alexey Stepanov Alexander Gasnikov Alexander Titov
Mirror Descent for Constrained Optimization Problems with Large Subgradient Values
Based on the ideas of arXiv:1710.06612, we consider the problem of
minimization of the Holder-continuous non-smooth functional $f$ with
non-positive convex (generally, non-smooth) Lipschitz-continuous functional
constraint. We propose some novel strategies of step-sizes and adaptive
stopping rules in Mirror Descent algorithms for the considered class of
problems. It is shown that the methods are applicable to the objective
functionals of various levels of smoothness. Applying the restart technique to
the Mirror Descent Algorithm there was proposed an optimal method to solve
optimization problems with strongly convex objective functionals. Estimates of
the rate of convergence of the considered algorithms are obtained depending on
the level of smoothness of the objective functional. These estimates indicate
the optimality of considered methods from the point of view of the theory of
lower oracle bounds. In addition, the case of a quasi-convex objective
functional and constraint was considered.