3 优化

凸集和凸函数

凸集

给定集合 $C \subseteq \mathbb{R}^n$ 。若 $\forall x, y \in C$ 满足

$$\forall t \in[0,1], t x+(1-t) y \in C$$

那么集合 $C$ 为凸集。

凸函数

给定一个函数 $f:\mathbb{R}^n→\mathbb{R}$，如果 domain(f) 是凸集，且任意 $x,y\in domain(f),$

$$\forall t \in[0,1], f(t x+(1-t) y) \leq t f(x)+(1-t) f(y)$$

那么函数 $f$ 是凸函数。

凸函数例子：

• 指数函数 $\exp (a x)$

• 负对数函数 $-\log (x)$

• 反射函数 $\boldsymbol{a}^{\top} \boldsymbol{x}+b$
• 二次函数 $x^{\top} A \boldsymbol{x}+2 \boldsymbol{b}^{\top} \boldsymbol{x}+c \quad(A$ 半正定 $)$
• 范数 $\|x\|_p=\sqrt[p]{\sum_i\left|x_i\right|^p}$
• 最大函数 $f(x)=\max \left\{x_1, \cdots, x_n\right\}$
• Softplus $\log (1+\exp (x))$
• LogSumExp $\log \left(\sum_i \exp \left(x_i\right)\right)$
• LogDeterminant $-\log \operatorname{det}(X)$ 在半正定矩阵定义域上

一阶条件

假设函数 $f$ 可微，那么 $f$ 是凸函数当且仅当 $∀ x,y∈dom(f)$， $$ f(y)≥f(x)+∇f(x)^⊤ (y-x) $$ 即 —— 函数在切线上方。

二阶条件

假设函数 $f$ 二阶可微，那么 $f$ 是凸函数当且仅当 $∀ x∈dom(f)$， $$ ∇^2 f(x)≽0 $$ 即 —— 海森矩阵半正定。

优化问题

优化问题

$$\begin{array}{cl} & \min _x f(x) \\ \text { s.t. } & g_i(x) \leq 0, i=1,2, \ldots, m \\ & h_j(x)=0, j=1,2, \cdots, n \end{array}$$

这里的 $s.t.$ 是 subject to，意为 “在……的约束下”。

凸优化问题

$$\begin{gathered} \min _x f(\boldsymbol{x}) \\ \text { s.t. } g_i(\boldsymbol{x}) \leq 0, i=1,2, \ldots, m \\ \boldsymbol{a}_i^{\top} \boldsymbol{x}=b, j=1,2, \cdots, n \end{gathered}$$

其中 $f(\boldsymbol{x}), g_i(\boldsymbol{x})$ 是凸函数。

• 凸优化中，局部最优等价于全局最优。假设函数 $f$ 可微凸函数，那么 $x$ 是 $f$ 的全局最优当且仅当 $∇f(\mathbf{x})=0$。

无约束优化：梯度下降

目标： $\min _x f(x)$

$$\begin{aligned} &\text { while }\left\|\nabla f\left(x_t\right)\right\|>\delta \text { do } \\ &\quad \boldsymbol{x}_{t+1} \leftarrow \boldsymbol{x}_t-\alpha \nabla f\left(\boldsymbol{x}_t\right) \\ &\text { end while } \end{aligned}$$

有约束优化：KKT条件（拉格朗日乘子法）

$$\begin{array}{cc} & \min _{\boldsymbol{x}} f(\boldsymbol{x}) \\ \text { s.t. } & g_i(\boldsymbol{x}) \leq 0, i=1,2, \ldots, m \\ & h_j(\boldsymbol{x})=0, j=1,2, \cdots, n \end{array}$$

引入拉格朗日函数：

$$L(\boldsymbol{x}, \boldsymbol{u}, \boldsymbol{v})=f(\boldsymbol{x})+\sum_i u_i g_i(\boldsymbol{x})+\sum_j v_j h_j(\boldsymbol{x})$$

其中 $u_i \geq 0$。

最优解的必要条件：KKT条件

$$\begin{gathered} \boldsymbol{\nabla}_{\mathbf{x}} L(\boldsymbol{x}, \boldsymbol{u}, \boldsymbol{v})=\mathbf{0} \\ g_i(\boldsymbol{x}) \leq 0 \\ h_j(\boldsymbol{x})=0 \\ \mu_i \geq 0 \\ \mu_i g_i(\boldsymbol{x})=0 \end{gathered}$$

最后一个式子表明只有 $\mu_i=0$ 或者 $g_i(x)=0$。

取一个简单的示例做解释：

令 $L(x,\mu)=f(x)+\sum_i\mu_ig_i(x)$，因为 $\mu g(x)\le0$，所以 $\displaystyle\max_\mu L(x,\mu)=f(x)$（1）。

所以目标函数变为（称之为 $x\mu$ 问题）

$$\min _x f(x)=\min _x \max _\mu L(x, \mu)$$

如果对等号右边那一项交换顺序（称之为 $\mu x$ 问题）

$$\begin{aligned} \max _\mu \min _x L(x, \mu)&=\max _\mu\left[\min _x f(x)+\min _x \mu g(x)\right]（按定义展开）\\&=\max _\mu \min _x f(x)+\max _\mu \min _x \mu g(x)（分配算子，这一步可略）\\&=\min _x f(x)+\max _\mu \min _x \mu g(x)（第一项不受\mu约束） \end{aligned}$$

然后我们观察

$$\left.\begin{array}{c} \mu_k \geq 0 \\ g_k(x) \leq 0 \end{array}\right\}=>\min _x \mu g(x)=\left\{\begin{array}{cc} 0 & \text { if } \mu=0 \text { or } g(x)=0 \\ -\infty & \text { if } \mu>0 \text { and } g(x)<0 \end{array}\right.$$

说明

$$\max _\mu \min _x \mu g(x)=0 \text { 此时 } \mu=0 \text { or } g(x)=0 （2）$$

就是说

$$\max _\mu \min _x L(x, \mu)=\min _x f(x)+\max _\mu \min _x \mu g(x)=\min _x f(x)（3）$$

这说明 $\min _x \max _\mu L(x, \mu)=\max _\mu \min _x L(x, \mu)$，两个算子可以交换顺序

$$\left.\begin{array}{c} L(x, \mu)=f(x)+\sum_{k=1}^q \mu_k g_k(x) \\ \mu_k \geq 0 \\ g_k(x) \leq 0 \end{array}\right\}=>\min _x \max _\mu L(x, \mu)=\max _\mu \min _x L(x, \mu)=\min _x f(x)$$

这就说明如果满足条件（2），互为对偶的两个问题 $x\mu,\mu x$ 的解和 $\min_x f(x)$ 是相同的。

设这个最优解是 $\xi$，则 $x=\xi$ 时 $\mu=0$ 或 $g(\xi)=0$。带入（1）中，有

$$\max_\mu L(\xi,\mu)=f(\xi)$$

又由（3）得【注意到 $f(\xi)=\min_xf(x)$】

$$\max _\mu \min _x L(x, \mu)=f(\xi)$$

所以

$$L(\xi,\mu)=\min_xL(x,\mu)$$

说明 $\xi$ 也是 $L(x,\mu)$ 的极值点，后者在这点的偏 $x$ 导数为 0。

结论就是：

$$\left.\begin{array}{c} L(x, \mu)=f(x)+\sum_{k=1}^q \mu_k g_k(x) \\ \mu_k \geq 0 \\ g_k(x) \leq 0 \end{array}\right\}=>\left\{\begin{array}{c} \min _x \max _\mu L(x, \mu)=\max _\mu \min _x L(x, \mu)=\min _x f(x)=f\left(\xi\right) \\ \mu_k g_k\left(\xi\right)=0 \\ \left.\frac{\partial L(x, \mu)}{\partial x}\right|_{x=\xi}=0 \end{array}\right.$$

KKT 条件总结起来就是：

$$\left.\begin{array}{c} L(x, \lambda, \mu)=f(x)+\sum_{i=1}^n \lambda_i h_i(x)+\sum_{k=1}^q \mu_k g_k(x) \\ \lambda_i \neq 0 \\ h_i(x)=0 \\ \mu_k \geq 0 \\ g_k(x) \leq 0 \end{array}\right\}=>\left\{\begin{array}{c} \min _x \max _\mu L(x, \lambda, \mu)=\max _\mu \min _x L(x, \lambda, \mu)=\min _x f(x)=f\left(\xi\right) \\ \mu_k g_k\left(\xi\right)=0 \\ \left.\frac{\partial L(x, \lambda, \mu)}{\partial x}\right|_{x=\xi}=0 \end{array}\right.$$

注: $x, \lambda, \mu$ 都是向量。

本文阅读量