凸性

https://zh.d2l.ai/chapter_optimization/convexity.html

Typo:
凸性的 11.2.4. 小结 第一项应为:

  • 凸集的交集是凸的,并集不是。
2 Likes


下面的公式是如何推导出来的,有详细步骤吗,多谢了!

4 Likes

image
想问问这个公式是如何推导的呢?

性质1,应该是局部最小值就是全局最小值吧,翻译有误

1 Like

我来证明一下11.2.2,请指教 :blush:

$\forall x_0, x_1, 且x_1 \geq x_0$,其函数值对应$f(x_0), f(x_1)$,
将这两个点连接起来所形成的的线段对应的直线定为$line(x)$

简单来讲,若上面这两点连成的线段,每个点都在同一横坐标原函数的值的上方,那么就为凸函数;反之,则为非凸函数。

易得,若为凸函数,$\forall x \in [x_0, x_1], f(x)\leq line(x)$成立。

$$
\begin{align}
line(x)=y=\frac{f(x_1)-f(x_0)}{x_1-x_0}x+b, \
b=f(x_0)-\frac{f(x_1)-f(x_0)}{x_1-x_0} \cdot x_0,\
line(x)=y=\frac{f(x_1)-f(x_0)}{x_1-x_0}x+f(x_0)-\frac{f(x_1)-f(x_0)}{x_1-x_0} \cdot x_0 \
= \frac{f(x_1)-f(x_0)}{x_1-x_0}(x-x_0) + f(x_0)
\end{align}
$$

$\forall x \in [x_0, x_1], \frac{x - x_0}{x_1-x_0} \in [0, 1]$,
那么$\lambda$ 可表示为$\frac{x - x_0}{x_1-x_0}$,
那么$line(x)=\lambda(f(x_1)-f(x_0)) + f(x_0)$

将下式进行变形。
$$
\begin{align}
\lambda f(x_1)+ (1-\lambda)f(x_0) - f(\lambda x_1 + (1-\lambda)x_0) \
= \lambda (f(x_1)-f(x_0)) + f(x_0) - f(\lambda (x_1-x_0) + x_0) \
= line(x) - f(x)
\end{align}
$$

易得,如果$f(x)$为凸函数且线段$line(x)$图像在$f(x)$之上,
$$\lambda f(x_1)+ (1-\lambda)f(x_0) - f(\lambda x_1 + (1-\lambda)x_0) = line(x) - f(x) \geq 0$$

因此原式$\lambda f(x) + (1-\lambda) f(x’) \geq f(\lambda x + (1-\lambda) x’).$成立。