iLovEing
commented
1 year ago 先前知识: 约束优化问题求解
此章节讲解SVM中，带约束优化问题的求解，纯数学内容。
1. 写出原问题
考虑一个带不等式约束的优化问题：
----- 公式(a)
2. 使用拉格朗日乘子法求解约束优化问题
使用拉格朗日乘子法，将原问题写成无约束形式。
引入拉格朗日函数：
----- 公式(b)
则原问题可以写为一下无约束形式：
----- 公式(c)
补充说明1：嵌套优化问题的理解 这里关于 $min$ , $max$ 两层嵌套优化问题的含义可以这样理解：假设固定某个 $x$ ，则遍历 $λ$ ， $η$ 寻找 $L$ 的最大值作为该 $x$ 的函数值，而最终的结果是遍历所有 $x$ ，寻找所有 $x$ 下函数值的最小值作为最终解。
补充说明2：公式(c)和公式(a)同解 考虑原问题的两个约束：
- $n_{j}$为等式约束，对拉格朗日函数 $L(x, λ, η)$ 求导即满足；
- $m{i}$为不等式约束，考虑两种情况： a. 如果 $x$ 不满足约束 $m{i}$ ，即 $m{i}(x) > 0$ ，观察拉格朗日函数，由于 $λ{i} > 0$ ，则 $\maxλ{L(x, λ, η)}$ 值为正无穷； b. 如果 $x$ 满足约束 $m{i}$ ，同理， $\max_λ{L(x, λ, η)}$ 值小于正无穷。
由a. b. 易推断：
$\min_x{\max_λ{L}} = min_x{\{+\infty (when: m_i > 0), L(when: m_i \le 0)\}} = min_x{\{L(when: mi \le 0)\}}$ 即公式(c)的解隐式地满足 $m{i} \le 0$故：公式(c)和公式(a)同解
3. 转化为对偶问题
3.1 先写出原问题的对偶形式，其实就是将 $min$ 和 $max$ 对调：
----- 公式(d)
3.2 弱对偶性与强对偶性
这一节主要讨论原问题和对偶问题解的关系（这里的解指的是满足条件下拉格朗日函数 $L$ 的值）。
-
弱对偶性：对偶问题的解小于等于原问题，天然拥有，即 $\max_{λ, η}{\min_x L(x, λ, η)} \le \minx{\max{λ, η} L(x, λ, η)} $ 证明： 显然有： $\minx{L} \le L \le \max{λ, η}L$ $\therefore \max_{λ, η}{\min_x{L}} \le L \le \minx{\max{λ, η}L}$ 即，在小的值里面取最大的，肯定小于等于 大的值里面取最小的。
-
强对偶性：对偶问题的解等于原问题，当优化问题满足某些条件时拥有强对偶性。这里直接写结论，凸优化问题，满足slater条件时拥有强对偶性，原问题和对偶问题同解。
补充说明3：对偶问题的几何理解 简化原问题，考虑一维不等式约束问题： $\min_x{f(x)}, s.t. m(x) \le 0$ , 其中 $x$ 定义域为 $D$ 拉格朗日函数： $L(x, λ) = f(x) + λ m(x)$ 原问题的无约束形式： $\min_x{\max_λ{L(x, λ)}}, s.t. λ \ge 0$ 对偶问题： $\max_λ{\min_x{L(x, λ)}}, s.t. λ \ge 0$ 定义：
- $\tilde{p}$ 是原问题的解， $\tilde{d}$ 是对偶问题的解
- $u=m(x)$ ， $t=f(x)$
- 区域 $G = \{(u, t) | x \propto D\}$
则有：
- $\tilde{p} = inf\{t | (u, t) \propto D, u \le 0\} $
- $\tilde{d} = \max_λ{\min_x{L(x, λ)}} := \max_λ{g(λ)}, 其中： g(λ) = inf\{t+λu | (u, t) \propto G, λ \ge 0\}$
如图，在图上表示区域G，注意G可以非凸，其中阴影部分为约束条件 $u \le 0$，可以看出：
- $\tilde{p}$ 是满足 $u \le 0$ 下， $t$ 能取到的最小值
- 当固定 $λ$ 时， $g(λ)$ 是直线 $t + λu = a$ 和 $t$ 轴交点，又 $(u, t) \propto G$ ，且斜率 $-λ$ 小于0，故 $g(λ)$ 与 $G$ 相切时，取到下确界。现在，考虑 $λ$ 可变，要取到最大的 $g(λ)$ ，当且仅当 $t + λu = a$ 同时和 A、B相切，此时 $\tilde{d}$ 为 $g(λ)$ 和 竖轴交点。可以直观地看出 $\tilde{d} \le \tilde{p}$ 。
补充说明4：slater条件 在补充说明3中，如果G是凸的，可以直观地感觉到 $\tilde{d} \= \tilde{p}$ 可以成立
数学上，凸函数不是强对偶的充分条件，还需要满足一些其他条件，比如slater条件： $\exists \hat{x} \propto relint-D， s.t. \forall i=1, 2, ..., M， m_i(\hat(x)) < 0$ 放松的slater：若 $M$ 中有 $k$ 个仿射函数，则不需要校验这 $k$ 个条件（ $m_i(\hat(x)) < 0， i=1,...,k$ ）
3.3 KKT条件
如果一个凸优化问题满足强对偶性，则可以引出KKT条件，借助KKT条件求解问题。
-
先写出原问题和对偶问题 拉格朗日函数： $L(x, λ, η)$ 原问题（无约束）： $\min_x{\max_λ{L(x, λ, η)}}, s.t. λ \ge 0$ 对偶问题： $\max_λ{\min_x{L(x, λ, η)}}, s.t. λ \ge 0$ 定义： $\tilde{p}$ 为原问题的解，在 $\tilde{x}$ 处取得； $\tilde{d}$ 为对偶问题的解，在 $\tilde{λ}, \tilde{η}$ 处取得。
-
KKT条件
- 可行性条件（由定义的约束直接得出）:
- $m_i(\tilde{x}) \le 0$
- $n_j(\tilde{x}) = 0$
- $\tilde{λ} \ge 0$
- 互补松弛条件： $\tilde{λ}_i m_i = 0$
- 梯度为0： $\frac{\partial L}{\partial x} |_{x=\tilde{x}} = 0$
- 可行性条件（由定义的约束直接得出）:
-
KKT条件证明 显然有：
----- 公式(e)
观察式e的两个不等号，当优化问题满足强对偶性时，不等号取等：
- 第一个不等号取等：梯度为0条件 $\frac{\partial L}{\partial x} |_{x=\tilde{x}} = 0$
- 第二个不等号取等：互补松弛条件： $\tilde{λ}_i m_i = 0$ 至此，KKT条件的2、3证毕。
补充说明5：关于引入对偶问题求解优化问题 主要目的是，如果优化问题满足强对偶性，则可以使用KKT条件，降低问题求解复杂度（或使问题从不可解变为可解？） 这一章的整体逻辑是：凸优化+slater条件 -> 强对偶性（原问题和对偶问题同解） -> KKT条件
公式latex附录 (a): \left{\begin{matrix}\min_x{f(x)}, x\propto R^P \s.t. m_i(x) \le 0, i=1, 2...M \s.t. nj(x) = 0, j=1, 2...N\end{matrix}\right. (b): L(x,\lambda,\eta) = f(x) + \sum{i}^{M}\lambda_i mi + \sum{j}^{N}\eta_j m_j，x\propto R^P (c): \left{\begin{matrix} \minx{\max{\lambda,\eta} L(x,\lambda,\eta)} \ s.t. \lambda{i} \ge 0\end{matrix}\right. (d): \left{\begin{matrix} \max{\lambda,\eta}{\minx L(x,\lambda,\eta)} \ s.t. \lambda{i} \ge 0\end{matrix}\right. (e): \tilde{d} = \max_{\lambda, \eta}{\min_x{L(x, \lambda, \eta)}} = \minx{L(x, \tilde{\lambda}, \tilde{\eta})} {\color{Red} \le} L(\tilde{x}, \tilde{\lambda}, \tilde{\eta}) = f(\tilde{x}) + \sum{i}^{M}\tilde{\lambda}_i m_i + 0 {\color{Red} \le} f(\tilde{x}) = \tilde{p}
support vector machine -- 支持向量机
写在最前
个人理解，SVM最亮眼的几个点：
SVM基本思路
大纲