摘要:
这篇文章主要用例子来阐述什么叫凸函数以及如何证明.
我们的目标是证明函数
\[ f(x)=max\{x_1,...,x_n\} \]
是凸函数.
回顾凸函数的定义. 一个函数\(f:\mathbb{R}^n \to \mathbb{R}\)满足如下条件可以被称为凸函数:
\(dom(f)\)是凸集, 对于任意的\(x,y \in dom(f)\)和\(0 \leq \theta \leq 1\), 有:
\[ f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y) \].
证明
对于函数 \(f(x)=max\{x_1,...,x_n\}\)的定义域是\(\mathbb{R}^n\), 这是一个仿射集, 所以也是凸集.
对于任意的\(x,y \in dom(f)\)和\(0 \leq \theta \leq 1\), 可以求得:
\[ \begin{align} &z = \theta x + (1-\theta)y= \theta x_1+(1-\theta)y_1,\theta x_2+(1-\theta)y_2,...,\theta x_n+(1-\theta)y_n \\ & 令: max\{z\}= z_m= \theta x_m + (1-\theta)y_m \\ & 所以:f(\theta x + (1-\theta)y)=\theta x_m + (1-\theta)y_m \end{align} \]
假设\(max(x)=x_i, max(y)=y_j\), 则有:
\[ \begin{align} \theta f(x) + (1-\theta)f(y)=&\theta max\{x_1,x_2,...,x_n\} +(1-\theta)max\{y_1,y_2,...,y_n\} \\ =& \theta x_i+ (1-\theta) y_j \\ 因为:& x_m \leq x_i ,y_m \leq y_j \\ 并且:& 0 \leq \theta \leq 1 \to 0 \leq (1-\theta) \leq 1 \\ 所以:& \theta x_m \leq \theta x_i ; (1-\theta) y_m \leq (1-\theta)y_j \\ 最终得到:&\theta x_m + (1-\theta) y_m \leq \theta x_i + (1-\theta)y_j \\ 即:& f(\theta x + (1-\theta)y) \leq \theta f(x) + (1-\theta)f(y) \end{align} \]
所以目标函数是凸函数.