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

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

comments powered by Disqus