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

  数学 数值计算 最优化    浏览次数: 2151
7

为什么?

 

雕牌   2017-03-11 14:31



   2个回答 
14

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

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

我们可以用反证法来证明。已知$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)$必定为最小值。

高代兄   2017-03-18 10:17

1

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

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


sasa   2017-10-14 08:15



  相关主题

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

证明LogLoss是凸函数   1回答

逻辑回归的Log Loss是凸函数吗?   1回答

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

怎么理解roc convex hull?   2回答

凸优化中的仿射是什么意思   1回答

两个凸函数相加,还是凸函数吗?   4回答

随机平均梯度法(Stochasitc Average Gradient)和随机梯度下降(SGD)有什么区别   3回答

用SGD时陷入局部最优解的解决方法   3回答

梯度上升算法是什么?   2回答

随机梯度下降(sgd)的收敛问题   2回答

Adam优化算法   1回答



回答问题时需要注意什么?

我们谢绝在回答前讲“生动”的故事。

我们谢绝“这么简单,你自己想”、“书上有的,你认真看”这类的回答;如果你认为对方的提问方式或者内容不妥,你可以直接忽略该问题,不用进行任何作答,甚至可以对该问题投反对票。

我们谢绝答非所问。

我们谢绝自己不会、硬要回答。

我们感激每一个用户在编写答案时的努力与付出!