计算科学 - 凸最小化问题的收敛率和复杂度 - 吾爱随笔录

计算科学优化凸优化复杂

2021-12-14 23:27:57

在Yurii Nesterov 的 Introductory Lectures on Convex Optimization中，描述了最小化问题的分析复杂度的收敛速度和相应的上限：

min f (x), x \in R^{n}

$\min f(x),\quad x \in \mathbb R^n$

迭代 $k$ 的误差由 $r_k=||x_k-x^*||$ 其中 $x_k$ 处的近似解，x 是真实解。二次率：。 $k$ $x^*$ $r_{k+1} \leq c r_k^2$

相应的复杂度估计取决于所需精度的双对数： $\ln\ln\frac{1}{\epsilon}$ 。为什么会这样？

1个回答

与第 36 页上的前两个案例不同，案例 3“二次率”在上有一个界限，它取决于而不是。 $r_{k+1}$ $r_{k}$ $k$

我们有

$r_{k+1} \le cr_{k}^{2}$

$r_{k+1} \le c(cr_{k-1}^{2})^{2}$

$r_{k+1} \le c(c(cr_{k-2}^{2})^{2})^{2}$

$\vdots$

$r_{k+1} \le c^{2^{k}-1} r_{0}^{2^{k+1}}$

展开这一点，您可以看到需要次迭代才能使降至小于。 $O(\log \log 1/\epsilon)$ $r$ $\epsilon$

其它你可能感兴趣的问题