凸优化中局部最优解就是全局最优解吗?

  数学 数值计算 最优化    浏览次数:22042        分享
8

为什么?

 

雕牌   2017-03-11 14:31



   2个回答 
16

是的,对于凸优化来说,局部最优就是全局最优,换句话说,极小值就是最小值。

至于为什么?这个就是数学证明了,这个要用到凸函数、凸集的定义

我们可以用反证法来证明。已知$x_0$是个局部最优点,假设在全集$S$上存在一个点$x_*$,使得

$$f(x_*) < f(x_0).$$

因为$f(x)$是凸函数,所以对于任意的$t$

$$f(tx_*+(1-t)x_0)\leq tf(x_*) + (1-t)f(x_0)$$

注意,这个$t$是$0$到$1$之间的任意值,所以$t$可以非常接近$0$,此时$(tx_*+(1-t)x_0)$这个点就可以无限接近$x_0$,但是函数在这个点的值又比$f(x_0)$小,所以$f(x_0)$不可能是局部最小值。故假设矛盾,因此不存在这样的$x_*$。$f(x_0)$必定为最小值。

SofaSofa数据科学社区DS面试题库 DS面经

高代兄   2017-03-18 10:17

1

是的,这是凸优化极好的一个性质。

找到局部最优也就找到了全局最优。这让很多类梯度下降的优化算法有了大展拳脚的空间。


SofaSofa数据科学社区DS面试题库 DS面经

sasa   2017-10-14 08:15



  相关讨论

非凸的目标函数还可以用随机梯度下降吗?

牛顿法是凸优化算法还是全局优化算法?

什么样的优化问题算是凸优化?

如果极小值就是最小值,那么这个函数就是凸函数吗?

凸优化问题一定存在最优解吗?

凸函数、凸集分别是什么意思?

线性回归的目标函数是凸函数吗?

怎么判断一个损失函数的凹凸性?

利用牛顿法求一个凸函数的最小值有可能出现发散的情况么?

凸函数有鞍点吗?

  随便看看

为什么样本方差是除以n-1

机器学习中的奥卡姆剃刀原理是什么意思

dropout rate一般设置多大?

怎么理解库克距离(Cook's distance)?

推荐系统里的ALS是什么意思?