Run this notebook online: or Colab:

# 11.2. 凸性¶

## 11.2.1. 定义¶

### 11.2.1.1. 凸集¶

(11.2.1)$\lambda a + (1-\lambda) b \in \mathcal{X} \text{ 当 } a, b \in \mathcal{X}.$

.. _fig_pacman:

.. _fig_convex_intersect:

.. _fig_nonconvex:

### 11.2.1.2. 凸函数¶

(11.2.2)$\lambda f(x) + (1-\lambda) f(x') \geq f(\lambda x + (1-\lambda) x').$

%load ../utils/djl-imports
%load ../utils/plot-utils
%load ../utils/Functions.java

import ai.djl.ndarray.*;

import tech.tablesaw.plotly.traces.ScatterTrace;
import tech.tablesaw.plotly.components.Axis.Spikes;

// ScatterTrace.builder() does not support float[],
// so we must convert to a double array first
public double[] floatToDoubleArray(float[] x) {
double[] ret = new double[x.length];
for (int i = 0; i < x.length; i++) {
ret[i] = x[i];
}
return ret;
}

public Figure plotLineAndSegment(float[] x, float[] y, float[] segment, Function<Float, Float> func,
int width, int height) {
ScatterTrace trace = ScatterTrace.builder(floatToDoubleArray(x), floatToDoubleArray(y))
.mode(ScatterTrace.Mode.LINE)
.build();

ScatterTrace trace2 = ScatterTrace.builder(floatToDoubleArray(segment),
new double[]{func.apply(segment[0]),
func.apply(segment[1])})
.mode(ScatterTrace.Mode.LINE)
.build();

Layout layout = Layout.builder()
.height(height)
.width(width)
.showLegend(false)
.build();

return new Figure(layout, trace, trace2);
}

Function<Float, Float> f = x -> 0.5f * x * x; // 凸函数
Function<Float, Float> g = x -> (float)Math.cos(Math.PI * x); // 非凸函数
Function<Float, Float> h = x -> (float)Math.exp(0.5f * x); // 凸函数

NDManager manager = NDManager.newBaseManager();

NDArray X = manager.arange(-2f, 2f, 0.01f);
float[] x = X.toFloatArray();
float[] segment = new float[]{-1.5f, 1f};

float[] fx = Functions.callFunc(x, f);
float[] gx = Functions.callFunc(x, g);
float[] hx = Functions.callFunc(x, h);

display(plotLineAndSegment(x, fx, segment, f, 350, 300));
display(plotLineAndSegment(x, gx, segment, g, 350, 300));
display(plotLineAndSegment(x, hx, segment, h, 350, 300));

9e1dd18c-51d6-4314-8302-b8117cc27f26


### 11.2.1.3. 詹森不等式¶

(11.2.3)$\sum_i \alpha_i f(x_i) \geq f\left(\sum_i \alpha_i x_i\right) \text{ and } E_X[f(X)] \geq f\left(E_X[X]\right),$

(11.2.4)$E_{Y \sim P(Y)}[-\log P(X \mid Y)] \geq -\log P(X),$

## 11.2.2. 性质¶

### 11.2.2.1. 局部极小值是全局极小值¶

(11.2.5)\begin{split}\begin{aligned} f(\lambda x^{\ast} + (1-\lambda) x') &\leq \lambda f(x^{\ast}) + (1-\lambda) f(x') \\ &< \lambda f(x^{\ast}) + (1-\lambda) f(x^{\ast}) \\ &= f(x^{\ast}), \\ \end{aligned}\end{split}

Function<Float, Float> f = x -> (x - 1) * (x - 1) * (x + 1);

float[] fx = Functions.callFunc(x, f);
plotLineAndSegment(x, fx, segment, f, 400, 350);


### 11.2.2.2. 水平集的凸函数¶

(11.2.6)$\mathcal{S}_b := \{x | x \in \mathcal{X} \text{ and } f(x) \leq b\}$

(11.2.7)$f(\lambda x + (1-\lambda) x') \leq \lambda f(x) + (1-\lambda) f(x') \leq b.$

### 11.2.2.3. 凸性和二阶导数¶

(11.2.8)$\frac{1}{2} f(x + \epsilon) + \frac{1}{2} f(x - \epsilon) \geq f\left(\frac{x + \epsilon}{2} + \frac{x - \epsilon}{2}\right) = f(x).$

(11.2.9)$f''(x) = \lim_{\epsilon \to 0} \frac{f(x+\epsilon) + f(x - \epsilon) - 2f(x)}{\epsilon^2} \geq 0.$

(11.2.10)$f'(\alpha) = \frac{f(x) - f(a)}{x-a} \text{ 且 } f'(\beta) = \frac{f(b) - f(x)}{b-x}.$

(11.2.11)$\frac{x-a}{b-a}f(b) + \frac{b-x}{b-a}f(a) \geq f(x).$

(11.2.12)$\lambda f(b) + (1-\lambda)f(a) \geq f((1-\lambda)a + \lambda b),$

(11.2.13)$g(z) \stackrel{\mathrm{def}}{=} f(z \mathbf{x} + (1-z) \mathbf{y}) \text{ where } z \in [0,1]$

(11.2.14)\begin{split}\begin{aligned} &g(\lambda a + (1-\lambda) b)\\ =&f\left(\left(\lambda a + (1-\lambda) b\right)\mathbf{x} + \left(1-\lambda a - (1-\lambda) b\right)\mathbf{y} \right)\\ =&f\left(\lambda \left(a \mathbf{x} + (1-a) \mathbf{y}\right) + (1-\lambda) \left(b \mathbf{x} + (1-b) \mathbf{y}\right) \right)\\ \leq& \lambda f\left(a \mathbf{x} + (1-a) \mathbf{y}\right) + (1-\lambda) f\left(b \mathbf{x} + (1-b) \mathbf{y}\right) \\ =& \lambda g(a) + (1-\lambda) g(b). \end{aligned}\end{split}

(11.2.15)\begin{split}\begin{aligned} &f(\lambda \mathbf{x} + (1-\lambda) \mathbf{y})\\ =&g(\lambda \cdot 1 + (1-\lambda) \cdot 0)\\ \leq& \lambda g(1) + (1-\lambda) g(0) \\ =& \lambda f(\mathbf{x}) + (1-\lambda) g(\mathbf{y}). \end{aligned}\end{split}

## 11.2.3. 约束¶

(11.2.16)\begin{split}\begin{aligned} \mathop{\mathrm{minimize~}}_{\mathbf{x}} & f(\mathbf{x}) \\ \text{ subject to } & c_i(\mathbf{x}) \leq 0 \text{ for all } i \in \{1, \ldots, N\}. \end{aligned}\end{split}

### 11.2.3.1. 拉格朗日函数¶

(11.2.17)$L(\mathbf{x}, \alpha_1, \ldots, \alpha_n) = f(\mathbf{x}) + \sum_{i=1}^n \alpha_i c_i(\mathbf{x}) \text{ where } \alpha_i \geq 0.$

### 11.2.3.3. 投影¶

(11.2.18)$\mathbf{g} \leftarrow \mathbf{g} \cdot \mathrm{min}(1, \theta/\|\mathbf{g}\|).$

(11.2.19)$\mathrm{Proj}_\mathcal{X}(\mathbf{x}) = \mathop{\mathrm{argmin}}_{\mathbf{x}' \in \mathcal{X}} \|\mathbf{x} - \mathbf{x}'\|.$

.. _fig_projections:

## 11.2.4. 小结¶

• 凸集的交点是凸的，并集不是。

• 根据詹森不等式，“一个多变量凸函数的总期望值”大于或等于“用每个变量的期望值计算这个函数的总值“。

• 一个二次可微函数是凸函数，当且仅当其Hessian（二阶导数矩阵）是半正定的。

• 凸约束可以通过拉格朗日函数来添加。在实践中，只需在目标函数中加上一个惩罚就可以了。

• 投影映射到凸集中最接近原始点的点。

## 11.2.5. 练习¶

1. 假设我们想要通过绘制集合内点之间的所有直线并检查这些直线是否包含来验证集合的凸性。 i.证明只检查边界上的点是充分的。 ii.证明只检查集合的顶点是充分的。

2. $$p$$-范数表示半径为:math:r的球，证明$$\mathcal{B}_p[r] := \{\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \text{ and } \|\mathbf{x}\|_p \leq r\}$$$$\mathcal{B}_p[r]$$对于所有$$p \geq 1$$是凸的。

3. 已知凸函数$$f$$$$g$$表明$$\mathrm{max}(f, g)$$也是凸函数。证明$$\mathrm{min}(f, g)$$是非凸的。

4. 证明Softmax函数的规范化是凸的，即$$f(x) = \log \sum_i \exp(x_i)$$的凸性。

5. 证明线性子空间$$\mathcal{X} = {\mathbf{X} | \mathbf{W} \mathbf{X} = \mathbf{b}}$$是凸集。

6. 证明在线性子空间$$\mathbf{b} = \mathbf{0}$$的情况下，对于矩阵$$\mathbf{M}$$的投影$$\mathrm {Proj} \mathcal{X}$$可以写成$$\mathbf{M} \mathbf{X}$$

7. 证明对于凸二次可微函数$$f$$，对于$$\xi \in [0, \epsilon]$$，我们可以写成$$f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(x + \xi)$$

8. 给定一个向量$$\mathbf{w} \in \mathbb{R}^d$$$$|\mathbf{w}| 1 > 1$$计算在$$L_1$$单位球上的投影。 i.作为中间步骤，写出惩罚目标$$|\mathbf{w} - \mathbf{w}'|_2^2 + \lambda |\mathbf{w}'|_1$$，计算给定$$\lambda > 0$$的解。 ii.你能无须反复试错就找到$$\lambda$$的“正确”值吗？

9. 给定一个凸集$$\mathcal{X}$$和两个向量$$\mathbf{X}$$$$\mathbf{y}$$证明了投影不会增加距离，即$$\|\mathbf{x} - \mathbf{y}\| \geq \|\mathrm{Proj}_\mathcal{X}(\mathbf{x}) - \mathrm{Proj}_\mathcal{X}(\mathbf{y})\|$$