Optimization

- 2 mins

Life is NP hard.

Rate of Convergence

We say ${x_{k}}$ converges to $x^{\ast}$ if and only if

$$\lim_{k \rightarrow \infty} {\parallel x_{k} - x^{\ast} \parallel}= 0$$

Converge Sublinearly

$$\lim_{k \rightarrow \infty} \frac{\parallel x_{k+1} - x^{\ast} \parallel}{\parallel x_{k} - x^{\ast} \parallel} = a$$

and $a \in (0,1)$ then the ${x_{k}}$ is said to converge sublinearly.

Toy Example

$x_{k} = 2^{-k}$$x_{k} = 2^{-k}$ is monotonically decreasing and the minimum is $x^{\ast} = 0$

hence we can derive

$$\lim_{k \rightarrow \infty} \frac{\parallel x_{k+1} - x^{\ast} \parallel}{\parallel x_{k} - x^{\ast} \parallel} = \lim_{k \rightarrow \infty} \frac{2^{-(k+1)}}{2^{-k}} = \frac{1}{2}$$

By the definition,$x_{k} = 2^{-k}$ converges sublinearly.

Converge Superlinearly

$$\lim_{k \rightarrow \infty} \frac{\parallel x_{k+1} - x^{\ast} \parallel}{\parallel x_{k} - x^{\ast} \parallel} = 0$$

then the ${x_{k}}$ is said to converge superlinearly.

Toy Example

$x_{k} = k^{-k}$ is monotonically decreasing, it is trivial if we convert it into $x_{k} = k^{-k} = e^{ln(k^{-k})} = e^{-klnk}$,the minimum is

$$x^{\ast} = \lim_{k \rightarrow \infty} k^{k} =\lim_{k \rightarrow \infty} e^{ln(k^{-k})} =\lim_{k \rightarrow \infty} e^{-klnk} = 0$$

Therefore

$$\lim_{k \rightarrow \infty} \frac{\parallel x_{k+1} - x^{\ast} \parallel}{\parallel x_{k} - x^{\ast} \parallel} = \lim_{k \rightarrow \infty} \frac{(k+1)^{-(k+1)}}{k^{-k}} = \lim_{k \rightarrow \infty} \frac{(k+1)^{-k}}{(k)^{-k}(k+1)} $$
$$= \lim_{k \rightarrow \infty} \frac{1}{k+1}(\frac{k+1}{k})^{-k} = \lim_{k \rightarrow \infty} \frac{1}{k+1}(\frac{1}{k} + 1)^{-k} = \lim_{k \rightarrow \infty} \frac{1}{(k+1)}\frac{1}{e} = 0$$

By the definition,$x_{k} = k^{-k}$ converges superlinearly.

Converge with order q

$$\lim_{k \rightarrow \infty} \frac{\parallel x_{k+1} - x^{\ast} \parallel}{\parallel x_{k} - x^{\ast} \parallel ^{q} = a$$

for any $a$ as a constant, then the ${x_{k}}$ is said to converge with order q.

Toy Example

Given that $x_{k} = a^{2^{k}}, 0 < a < 1$ is monotonically decreasing, its minimum is $x^{\ast} = 0$

Therefore,

$$\lim_{k \rightarrow \infty} \frac{\parallel x_{k+1} - x^{\ast} \parallel}{\parallel x_{k} - x^{\ast} \parallel^{2}} = \lim_{k \rightarrow \infty} \frac{a^{2^{k+1}}}{(a^{2^{k}})^{2}} = \lim_{k \rightarrow \infty} \frac{a^{2^{k+1}}}{a^{2^{k}\ast 2}} = \lim_{k \rightarrow \infty} \frac{a^{2^{k+1}}}{a^{2^{k+1}}} = 1$$

By the definition,$x_{k} = a^{2^{k}}, 0 < a < 1$ converges with order q.

Ying Zhang

Ying Zhang

A statistician who gets lost in analysis.

comments powered by Disqus
rss facebook twitter github youtube mail spotify instagram linkedin google google-plus pinterest medium vimeo stackoverflow reddit quora