概要
最优化问题的一般形式:
$$ \begin{aligned} \min_{x} \quad & f(x) \\ \text{s.t.} \quad & g_i(x) \leq 0, \quad i = 1, 2, \ldots, m \\ & h_j(x) = 0, \quad j = 1, 2, \ldots, p \end{aligned} $$稀疏优化
考虑线性方程组 $Ax = b$, 优化函数 $\min_{x \in R^n} {\Vert x \Vert}_0, {\Vert x \Vert}_1, {\Vert x \Vert}_2$, 分别指代 $x$ 的非零元个数, $l_1, l_2$ 范数. LASSO(least absolute shrinkage and selection operator) 问题:
$$ \min_{x \in \mathbb{R}^n} \mu {\Vert x \Vert}_1 + \frac{1}{2} {\Vert Ax - b \Vert}_2^2 $$低秩矩阵优化
考虑矩阵 $M$, 希望 $X$ 在描述 $M$ 有效特征元素的同时, 尽可能保证 $X$ 的低秩性质. 低秩矩阵问题:
$$ \min_{X \in \mathbb{R}^{m \times n}} \text{rank}(X) \quad \text{s.t.} \quad X_{ij} = M_{ij}, \quad (i, j) \in \Omega $$核范数 ${\Vert X \Vert}_*$ 为所有奇异值的和. 也有二次罚函数的形式:
$$ \min_{X \in \mathbb{R}^{m \times n}} \mu {\Vert X \Vert}_* + \frac{1}{2} \sum_{(i,j)\in \Omega} (X_{ij} - M_{ij})^2 $$对于低秩情形, $X=LR^T$, 其中 $L \in \mathbb{R}^{m \times r}, R \in \mathbb{R}^{n \times r}$, $r \ll m,n$ 为秩. 优化问题可写为:
$$ \min_{L,R} \alpha {\Vert L \Vert}^2_F + \beta {\Vert R \Vert}^2_F + \frac{1}{2} \sum_{(i,j)\in \Omega} ([LR^T]_{ij} - M_{ij})^2 $$引入正则化系数 $\alpha, \beta$ 来消除 $L,R$ 在常数缩放下的不确定性.
深度学习
机器学习的问题通常形如
$$ \min_{x \in W} \frac{1}{N} \sum_{i=1}^N \ell(f(a_i, x), b_i) + \lambda R(x) $$基本概念
定义
设 $f: \mathbb{R}^n \mapsto \mathbb{R}$, $x \in \mathbb{R}^n$ 的可行区域为 $S$. 若存在一个邻域 $N(x)$, 使得 $\forall x \in N(x) \cap S$, 有 $f(x^\ast) \leq f(x)$, 则称 $x^\ast$ 为 $f$ 的局部极小点. 若 $\forall x \in S$, 有 $f(x^\ast) \leq f(x)$, 则称 $x^\ast$ 为 $f$ 的全局极小点.
大多数的问题是不能显式求解的, 通常要使用迭代算法.
定义
称算法是 Q-线性收敛 的, 若对充分大的 $k$ 有
$$ \frac{{\Vert x_{k+1} - x^\ast \Vert}}{{\Vert x_k - x^\ast \Vert}} \le a, \quad a \in (0, 1) $$称算法是 Q-超线性收敛 的, 若对充分大的 $k$ 有
$$ \lim_{k \to \infty} \frac{{\Vert x_{k+1} - x^\ast \Vert}}{{\Vert x_k - x^\ast \Vert}} = 0 $$称算法是 Q-次线性收敛 的, 若对充分大的 $k$ 有
$$ \lim_{k \to \infty} \frac{{\Vert x_{k+1} - x^\ast \Vert}}{{\Vert x_k - x^\ast \Vert}} = 1 $$称算法是 Q-二次收敛 的, 若对充分大的 $k$ 有
$$ \frac{{\Vert x_{k+1} - x^\ast \Vert}}{{\Vert x_k - x^\ast \Vert^2}} \le a, \quad a > 0 $$定义
设 $x_k$ 是迭代算法产生的序列且收敛到 $x^\ast$, 如果存在 Q-线性收敛于 $0$ 的非负序列 $t_k$, 且
$$ \Vert x_k - x^\ast \Vert \le t_k $$则称 $x_k$ 是 R-线性收敛 的.
一般来说, 收敛准则可以是
$$ \frac{f(x_k) - f^\ast}{\max\left\{\left|f^\ast \right|, 1\right\}} \le \varepsilon $$也可以是
$$ \nabla f(x_k) \le \varepsilon $$如果有约束要求, 还要同时考虑到约束违反度. 对于实际的计算机算法, 会设计适当的停机准则, 例如
$$ \frac{{\Vert x_{k+1} - x_k \Vert}}{\max\left\{\Vert x_k \Vert, 1\right\}} \le \varepsilon $$