Strong convexity and implications
在讨论无约束凸优化问题(1)的时候，我们会假设
是一个凸二次可微的函数。考虑一个起始点
，记%20%5Cleq%20f(x%5E%7B(0)%7D)%5Cright%5C%7D%5Ctag%7B0%7D)
显然
是一个闭集。此外，我们设%3Df(x%5E*))
为最优值。
有时候，我们还会给目标函数加上两个更强的条件。
简而言之，在闭集上，
的Heisen矩阵的特征值有下确界
。如果这个条件被满足，由Taylor展开：%3Df(x)%2B%5Cnabla%20f(x)%5E%7BT%7D(y-x)%2B%5Cfrac%7B1%7D%7B2%7D(y-x)%5E%7BT%7D%20%5Cnabla%5E%7B2%7D%20f(z)(y-x)%20%5Ctag%7B1%7D)
其中
是线段![[x,y]](https://math.jianshu.com/math?formula=%5Bx%2Cy%5D)
上的一点。
继而，我们有：
%20%5Cgeq%20f(x)%2B%5Cnabla%20f(x)%5E%7BT%7D(y-x)%2B%5Cfrac%7Bm%7D%7B2%7D%5C%7Cy-x%5C%7C_%7B2%7D%5E%7B2%7D%5Ctag%7B2%7D)
这给出了函数的一个更好的下界。
另一个条件，在闭集上，的Heisen矩阵的特征值有上确界
（因为闭集，保证了上确界存在）。通过式(1)，我们可以得到类似式(2)的结论：%20%5Cleq%20f(x)%2B%5Cnabla%20f(x)%5E%7BT%7D(y-x)%2B%5Cfrac%7BM%7D%7B2%7D%5C%7Cy-x%5C%7C_%7B2%7D%5E%7B2%7D%5Ctag%7B3%7D)
这其实就给出了函数的一个上界。
综合这两个条件：%20%5Cpreceq%20M%20I%20%5Cquad%20%2C%5Cforall%20x%20%5Cin%20S%20%5Ctag%7B4%7D)
接下来我们来推导，加上这两个条件，有什么用。
注意到(2)式的右边是一个关于
的凸函数，在
时最小，从而：
上式说明，当
模长很小很小的时候，)
跟最优值
的距离也很小很小。虽然这个结论看起来很显然，但是我们从数学的角度证明了它！%5C%7C_%7B2%7D%20%5Cleq(2%20m%20%5Cepsilon)%5E%7B1%20%2F%202%7D%20%5CLongrightarrow%20f(x)-p%5E%7B%5Cstar%7D%20%5Cleq%20%5Cepsilon%5Ctag%7B5%7D)
利用(5)式，我们可以通过梯度的模长，来控制与最优解之间的距离。
类似的推导能得到更强的结论：
对于第二种情况：
%20%5Cpreceq%20M%20I%20%5CRightarrow%20p%5E%7B%5Cstar%7D%20%5Cleq%20f(x)-%5Cfrac%7B1%7D%7B2%20M%7D%5C%7C%5Cnabla%20f(x)%5C%7C_%7B2%7D%5E%7B2%7D%5Ctag%7B6%7D)
总结一下，在一个闭集上，理想情况下，凸函数的Heisen矩阵的特征值是“可控的”，我们从数学上推导出当某处的梯度模长很接近0的时候，其实离最优解和最优值不远了，这个“接近”的程度可以由估计式给出。尽管大部分时候我们没有办法确定
和，但是只要梯度足够小，还是可以保证非常接近最优解的。
