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

  数学 数值计算 最优化    浏览次数: 3378
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回答

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

证明LogLoss是凸函数   1回答

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

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

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

对函数进行log变换后,它的凹凸性会变吗?   1回答

怎么理解roc convex hull?   2回答

一个凸函数加上L2正则项之后,它还凸的吗?   1回答

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

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

对于小批量随机剃度下降法(mini-batch SGD),如何选择每批样本的数量?   1回答



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

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

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

我们谢绝答非所问。

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

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