凸优化学习笔记14：强凸性
为了便于分析优化算法的收敛性，假设优化问题的目标函数为凸函数，二阶可微且具有强凸性。
强凸性：\\\exists m > 0, \forall x \in domf, \nabla^2f(x) \succeq mI \tag {1}
由于函数二阶可微：
\\\forall x,y \in dom f , f(y)\approx f(x) + \nabla^Tf(x)(y-x)+1/2(y-x)^T\nabla^2f(x)(y-x)\tag{2}
结合强凸性有：
\\ \tag{3} f(y)\geq f(x) + \nabla^Tf(x)(y-x)+m/2||(y-x)||_2^2
当给定 x 时，显然上式不等号右边为 y 的凸函数，对其关于 y 求导并令其导数为0：
\\ \nabla f(x) + m(y-x) = 0\\ \Rightarrow y^* = x - 1/m \nabla f(x)\tag{4}
再将 y^* 带入(3)式：\\ \tag{5} f(y)\geq f(x) -\frac{m}{2}\nabla ||f(x)||_2^2
结合（3）,(5)式有：
\\ \tag{6} f(y)\geq f(x) + \nabla^Tf(x)(y-x)+m/2||(y-x)||_2^2 \\ \geq f(x) + \nabla^Tf(x)(y^*-x)+m/2||(y^*-x)||_2^2\\ =f(x) -\frac{m}{2}\nabla ||f(x)||_2^2 根据前面的阐述对任意 y \in domf 均成立，所以：
\\ \tag{7} p^* \geq f(x) -\frac{m}{2}||\nabla f(x)||_2^2\\ f(y) \leq p^* \\ \Rightarrow ||f(x)-p^*||_2 \leq \frac{m}{2} ||\nabla f(x)||_2^2 (7)式说明当梯度很小时，函数值接近最优值。
接下来看看当梯度很小时， x 是否接近最优解。
\\ f(x^*) = p^* \geq f(x) + \nabla^Tf(x)(x^*-x)+m/2||(x^*-x)||_2^2\\ \geq f(x)-|| \nabla f(x)||||x^*-x||+m/2||(x^*-x)||_2^2 f(x) \geq p^*\\ \Rightarrow-|| \nabla f(x)||||x^*-x||+m/2||(x^*-x)||_2^2 <0 \\ \Rightarrow ||x-x^*||_2 \leq 2/m ||\nabla f(x)||_2\tag{8}
综上讨论了海塞矩阵的下界带来的结论，同样我们也可以讨论上界。
\\\exists M > 0, \forall x \in domf, \nabla^2f(x) \preceq MI \tag {9}
同下界分析类似有：
\\p^*\leq f(x) -\frac{M}{2}\nabla ||f(x)||_2^2 \tag{10}
文章被以下专栏收录
