# General formulation

Some necessary or\and sufficient conditions are known (See Optimality conditions. KKT and Convex optimization problem)

• In fact, there might be very challenging to recognize the convenient form of optimization problem.
• Analytical solution of KKT could be inviable

## Iterative methods

Typically, the methods generate an infinite sequence of approximate solutions

which for a finite number of steps (or better - time) converges to an optimal (at least one of the optimal) solution $x_*$.

def GeneralScheme(x, epsilon):
while not StopCriterion(x, epsilon):
OracleResponse = RequestOracle(x)
x = NextPoint(x, OracleResponse)
return x


# Challenges

## Unsolvability

In general, optimization problems are unsolvable. ¯\(ツ)

Consider the following simple optimization problem of a function over unit cube:

We assume, that the objective function $f (\cdot) : \mathbb{R}^n \to \mathbb{R}$ is Lipschitz continuous on $\mathbb{B}^n$:

with some constant $L$ (Lipschitz constant). Here $\mathbb{B}^n$ - the $n$- dimensional unit cube $\mathbb{B}^n = \{x \in \mathbb{R}^n \mid 0 \leq x_i \leq 1, i = 1, \ldots, n\}$.

Our goal is to find such $\tilde{x}: \vert f(\tilde{x}) - f^*\vert \leq \varepsilon$ for some positive $\varepsilon$. Here $f^*$ is the global minimizer of the problem. Uniform grid with $p$ points on each dimension guarantees at least this quality

which means, that

Our goal is to find the $p$ for some $\varepsilon$. So, we need to sample $\left(\frac{L}{2 \varepsilon}\right)^n$ points, since we need to measure function in $p^n$ points. Doesn’t look scary, but if we’ll take $L = 2, n = 11, \varepsilon = 0.01$, computations on the modern personal computers will take 31,250,000 years.

## Stopping rules

• Argument closeness:
• Function value closeness:
• Closeness to a critical point

But $x_*$ and $f^* = f(x_*)$ are unknown!

Sometimes, we can use the trick:

Note: it’s better to use relative changing of these values, i.e. $\dfrac{\|x_{k+1} - x_k \|_2}{\| x_k \|_2}$.

# Speed of convergence

• Sublinear

where $% $ and $% $

• Linear

where $q \in (0, 1)$ and $% $

• Superlinear

where $q \in (0, 1)$ or $% $, $C_k \to 0$

where $q \in (0, 1)$ and $% $

## Root test

Пусть $\{r_k\}_{k=m}^\infty$ — последовательность неотрицательных чисел, сходящаяся к нулю, и пусть

• Если $0 \leq \alpha \lt 1$, то $\{r_k\}_{k=m}^\infty$ имеет линейную сходимость с константной $\alpha$.
• В частности, если $\alpha = 0$, то $\{r_k\}_{k=m}^\infty$ имеет сверхлинейную сходимость.
• Если $\alpha = 1$, то $\{r_k\}_{k=m}^\infty$ имеет сублинейную сходимость.
• Случай $\alpha \gt 1$ невозможен.

## Ratio test

Пусть $\{r_k\}_{k=m}^\infty$ — последовательность строго положительных чисел, сходящаяся к нулю. Пусть

• Если существует $\alpha$ и при этом $0 \leq \alpha \lt 1$, то $\{r_k\}_{k=m}^\infty$ имеет линейную сходимость с константой $\alpha$
• В частности, если $\alpha = 0$, то $\{r_k\}_{k=m}^\infty$ имеет сверхлинейную сходимость
• Если $\alpha$ не существует, но при этом $q = \lim_{k \to \infty} \sup \dfrac{r_{k+1}}{r_k} \lt 1$, то $\{r_k\}_{k=m}^\infty$ имеет линейную сходимость с константой, не превосходящей $q$.
• Если $\lim_{k \to \infty} \inf \dfrac{r_{k+1}}{r_k} =1$, то $\{r_k\}_{k=m}^\infty$ имеет сублинейную сходимость.
• Ситуация $\lim_{k \to \infty} \inf \dfrac{r_{k+1}}{r_k} \gt 1$ невозможна.
• Во всех остальных случаях (т. е. когда $\lim_{k \to \infty} \inf \dfrac{r_{k+1}}{r_k} \lt 1 \leq \lim_{k \to \infty} \sup \dfrac{r_{k+1}}{r_k}$) нельзя утверждать что-либо конкретное о скорости сходимости $\{r_k\}_{k=m}^\infty$