最优化算法期末复习

2-1: 一维无约束优化 ($\min f(x), x \in \mathbb{R}$)

分类	方法
无导数信息	黄金分割法, 斐波那契法
一阶可导	二分法, 割线法
二阶可导	牛顿法

1. 单峰函数

在定义域区间有唯一局部极小点。

性质： $[a_0, b_0]$ 上的单峰函数在区间上任取两点 $a_1, b_1$ 且 $a_1 < b_1$：

• 若 $f(a_1) \ge f(b_1)$，则极小值 $x^* \in [a_1, b_0]$
• 若 $f(a_1) < f(b_1)$，则极小值 $x^* \in [a_0, b_1]$
• 证明：反证法。

2. 方法一：等比例压缩法

设 $a_1 = a_0 + p(b_0 - a_0)$，$b_1 = b_0 - p(b_0 - a_0)$，其中 $p < \frac{1}{2}$。 $[a_0, b_1]$ 和 $[a_1, b_0]$ 都是原来的 $1-p$ 倍。 $N$ 次迭代：总压缩比 $(1-p)^N$，调用 $f(x)$ 次数 $2N$。

优化：令 $1-p = p + (1-p) \cdot p$，解得 $p = \frac{3 \pm \sqrt{5}}{2}$。 为了使上一次计算的点能被重复使用，取 $p = \frac{3 - \sqrt{5}}{2} \approx 0.382$。

3. 方法二：黄金分割法

即 $p = 0.382$ 的等比例压缩法。 $N$ 次迭代：总压缩比 $(0.618)^N$，调用 $f(x)$ 次数 $N+1$。

4. 方法三：斐波那契法

给定迭代次数，允许 $\rho$ 动态改变使得 $N$ 次迭代后的压缩比最小。 满足 $\rho_{k+1} = 1 - \frac{\rho_k}{1-\rho_k}$，其中 $0 \le \rho_k \le \frac{1}{2}$。

最优解满足 $\rho_k = 1 - \frac{F_{N+1-k}}{F_{N+2-k}}$，其中 $F_{-1}=0, F_0=1$。 最优压缩比为 $\frac{1}{F_{N+1}}$。

注意：由于第 $N$ 次迭代 $\rho_N = \frac{1}{2}$ 时两个点会重叠，实际操作需在第 $N$ 次迭代的比例上加一个小的扰动量 $\varepsilon$。 总结：虽然斐波那契法能获得更优的压缩比，但黄金分割法更简单易行，且当 $N \to +\infty$ 时，二者拥有相同的压缩比。

二、二分法

要求 $f(x)$ 是连续可微的。 $x^{(0)} = \frac{a_0 + b_0}{2}$

• 若 $f'(x^{(0)}) > 0 \to [a_0, x^{(0)}]$
• 若 $f'(x^{(0)}) < 0 \to [x^{(0)}, b_0]$ 压缩比 $(\frac{1}{2})^N$，优于黄金分割和斐波那契法。

三、如何确定初始迭代范围 (Bracket Minimum 算法)

1. 随机确定初始区间 $[a, b]$，通过交换 $a, b$ 使 $f(a) > f(b)$。
2. 考虑点 $b+s$：
   • 如果 $f(b+s) > f(b)$，返回 $[a, b+s]$
   • 如果 $f(b+s) < f(b)$，返回 $[b, b+s]$，并继续搜索 $s$ 初始值一般为 $1 \times 10^{-2}$，通过 $s \times k$ 扩展，$k$ 通常为 2。没有局部极小值的函数无法被包围，会导致算法失败。

2-2: 一维无约束优化 (牛顿法、割线法、二次拟合法)

分类	方法
一阶可导	割线法 $\to$ 多维拟牛顿法
二阶可导	牛顿法 $\to$ 多维牛顿法

一、牛顿法

从 $x^0$ 出发，迭代 $x^k$ 直至 $f'(x) \approx 0$。 由 Taylor 公式近似 $q(x) = f(x^k) + f'(x^k)(x - x^k) + \frac{1}{2} f''(x^k)(x - x^k)^2$，令 $q'(x) = 0$。 迭代公式：$x^{k+1} = x^k - \frac{f'(x^k)}{f''(x^k)}$。

• 当 $f''(x) > 0$ 时收敛；$f''(x) < 0$ 时牛顿法可能失效。
• 可用 $|x^{k+1} - x^k| < \varepsilon$ 作为停机条件。
• 牛顿法也可用于求解 $g(x) = f'(x) = 0$。

二、割线法

用一阶导数近似二阶导数： $f''(x^k) \approx \frac{f'(x^k) - f'(x^{k-1})}{x^k - x^{k-1}}$ 迭代公式：$x^{k+1} = x^k - \frac{x^k - x^{k-1}}{f'(x^k) - f'(x^{k-1})} f'(x^k)$。

三、二次拟合搜索 (无需计算一阶导数)

通过三个点 $(x^k, f(x^k)), (x^{k-1}, f(x^{k-1})), (x^{k-2}, f(x^{k-2}))$ 拟合二次函数。 实际计算极小点只需计算 $-\frac{b}{2a} \to -\frac{\det(X_2)}{2\det(X_1)}$。

补充：正定矩阵

1. 正定：$\forall x \in \mathbb{R}^n, x \neq 0, x^T Q x > 0$
2. 半正定：$\forall x \in \mathbb{R}^n, x \neq 0, x^T Q x \ge 0$

• 正定 $\leftrightarrow$ 所有特征值为正 / 所有顺序主子式为正。
• 半正定 $\leftrightarrow$ 所有特征值为非负。

$\nabla f(x) = \begin{bmatrix} \frac{\partial f(x)}{\partial x_1} \\ \vdots \\ \frac{\partial f(x)}{\partial x_n} \end{bmatrix}$ 为 $f(x)$ 在 $x$ 处的梯度，读作 Nabla，记作 $g$。

常数 gradient: $c \in \mathbb{R}^n, \nabla c = 0$

$c, x \in \mathbb{R}^n, f(x) = c^T x, \nabla f(x) = c$

$x \in \mathbb{R}^n, f(x) = x^T x, \nabla f(x) = 2x$

$A$ 是 $n$ 阶对称矩阵, $f(x) = x^T A x, \nabla f(x) = 2Ax$

$A$ 为对称矩阵, $f(x) = \frac{1}{2} x^T A x + b^T x + c, \nabla f(x) = Ax + b$

1. Jacobi 矩阵

$f: \mathbb{R}^n \to \mathbb{R}^m$, $f(x) = \begin{bmatrix} f_1(x) \\ \vdots \\ f_m(x) \end{bmatrix}$ 且 $f_1(x), \dots, f_m(x)$ 可微，那么 $Df(x)$ 为其 Jacobi Matrix：

$Df(x) = \begin{bmatrix} \frac{\partial f_1(x)}{\partial x_1} & \dots & \frac{\partial f_1(x)}{\partial x_n} \\ \vdots & & \vdots \\ \frac{\partial f_m(x)}{\partial x_1} & \dots & \frac{\partial f_m(x)}{\partial x_n} \end{bmatrix} \Rightarrow f(x) \text{ 在 } x \text{ 处的导数, 记为 } Df(x) / J(x)$

★ $Df(x) = \nabla f(x)^T$ ($m=1$)

2. 多维函数求导的链式法则

$h(t) = g(x(t)) \quad (g(x) = g(x_1, x_2, \dots, x_n), x_i = x_i(t_1, t_2, \dots, t_m))$

$\nabla h(t) = D x(t)^T \nabla g(x(t))$

其中 $x(t): \mathbb{R}^m \to \mathbb{R}^n$, $g(t): \mathbb{R}^n \to \mathbb{R}^1$。

推导: $Dh(t) = Dg(x) Dx(t)$ $\nabla h(t)^T = \nabla g(x)^T Dx(t)$ $\nabla h(t) = Dx(t)^T \nabla g(x)$

3. 梯度的性质

① 沿 $g$ 方向函数具有最大增长率。 设 $\|d\|=1$，则单位向量的方向导数为： $\begin{aligned}\frac{\partial f(x)}{\partial d} &= \frac{d(f(x+ad))}{da} \\ &= \lim_{a \to 0} \frac{f(x+ad) - f(x)}{a} \\ &= \lim_{a \to 0} \frac{a \nabla f(x)^T d + o(d)}{a} \\ &= \nabla f(x)^T d\end{aligned}$

② $\forall$ 经过 $x_0$ 的水平集 $f(x) = f(x_0)$，$x_0$ 处的切向量与 $\nabla f(x_0)$ 正交。

③ $d \in \mathbb{R}^n (d \neq 0)$, $x \in \Omega$, $\exists a_0 > 0$, $a \in [0, a_0]$, $x + ad \in \Omega$，$d$ 为 $x$ 处的可行方向。对于约束集的内点 $x$，任意方向均为可行方向。

4. Hessian Matrix

$\nabla^2 f(x) = \begin{bmatrix} \frac{\partial^2 f(x)}{\partial x_1^2} & \frac{\partial^2 f(x)}{\partial x_2 \partial x_1} & \cdots & \frac{\partial^2 f}{\partial x_n \partial x_1} \\ \vdots & \ddots & & \vdots \\ \frac{\partial^2 f(x)}{\partial x_1 \partial x_n} & \cdots & \cdots & \frac{\partial^2 f(x)}{\partial x_n^2} \end{bmatrix} \rightarrow F(x) / D^2 f(x)$ 二阶导连续，对称 Matrix。

5. 多维 Taylor

$f^{(n)}(x) \rightarrow \nabla^{(n)} f(x)^T \Delta$

4-1: 多维无约束优化

一、Linear Regression

令 $\hat{w} = (w, b) \in R^{l+1}$, $y = (y_1, y_2, \dots, y_m)$ $X = \begin{pmatrix} x_{11} & x_{12} & \cdots & x_{1l} & 1 \\ \vdots & \vdots & & \vdots & \vdots \\ x_{m1} & x_{m2} & \cdots & x_{ml} & 1 \end{pmatrix} = \begin{pmatrix} x_1^T & 1 \\ \vdots & \vdots \\ x_m^T & 1 \end{pmatrix}$ 最小二乘问题从 $\min_{(w, b) \in R^{l+1}} \sum_{i=1}^m (w^T x_i + b - y_i)^2$ 转化为 $\min_{\hat{w} \in R^{l+1}} ||X\hat{w} - y||_2^2$。

$L_1$ 范数正则项: $\min_{\hat{w} \in R^{l+1}} ||X\hat{w} - y||_2^2 + \mu ||\hat{w}||_1 \rightarrow \text{LASSO模型}$

二、Ridge Regression

$\min_{\hat{w} \in R^{l+1}} ||X\hat{w} - y||_2^2 + \mu ||\hat{w}||_2^2 \rightarrow \text{合理设置 } \mu \text{ 值可使目标函数变成严格凸函数}$

分析: 一个函数是凸函数 $\iff$ Hessian Matrix 半正定。 $J_1(\hat{w}) = (X\hat{w} - y)^T (X\hat{w} - y)$ $H_1 = \nabla^2 J_1(\hat{w}) = 2X^T X$ (半正定矩阵，若行列满秩则为正定 Matrix)。

$J_2(\hat{w}) = \mu \hat{w}^T \hat{w}$ $H_2 = \nabla^2 J_2(\hat{w}) = 2\mu I$ 若 $\mu \ge 0$, 则 $H_2$ 也呈半正定。两个凸函数的和仍为凸函数。

三. 无约束优化的最优性条件

1. FONC (一阶必要条件): 设 $f: \mathbb{R}^n \to \mathbb{R}$ 一阶连续可微，如果 $x^*$ 是局部最小点，则 $\nabla f(x^*) = 0$。驻点（平稳点）包括极大值、极小值和鞍点。
2. SONC (二阶必要条件): 设 $f: \mathbb{R}^n \to \mathbb{R}$ 二阶连续可微，$\nabla f(x^*) = 0$ 且 $\nabla^2 f(x^*)$ 半正定。
3. SOSC (二阶充分条件): $\nabla f(x^*) = 0$ 且 $\nabla^2 f(x^*)$ 正定。
4. 无约束凸函数 FONC $\to$ 全局极小点。

4-2: 多维无约束优化 - 下降法

一、下降方向: $f(x^k + \alpha d) = f(x^k) + \alpha \nabla f(x^k)^T d < f(x^k)$，其中 $\nabla f(x^k)^T d < 0$，$d$ 是 $f$ 在 $x^k$ 的下降方向。

下降算法

• 梯度下降法 (一阶)
• 共轭梯度法 (一阶)
• 牛顿下降法 (二阶)
• 拟牛顿法 (二阶)

步长因子 $\alpha_k$ 的确定：

• $\alpha_k$ 太小，收敛太慢；$\alpha_k$ 太大，可能产生锯齿状的函数曲线。
• 步长衰减因子：$\alpha_k = \alpha_0 \gamma^{k-1}, \gamma \in (0, 1]$
• 精确/近似线搜索：令 $\phi_k(\alpha) = f(x^k + \alpha p^k)$，则 $\alpha_k = \underset{\alpha \ge 0}{\text{argmin}} \phi_k(\alpha)$

二、精确线搜索

$\min_{\alpha \ge 0} f(x^k + \alpha d^k)$ 性质：方向正交，即 $\nabla f(x^{k+1})^T d^k = 0$（驻点），意味着 $\nabla f(x^{k+1}) \perp d^k$。

三、近似线搜索

1. 步长 $\alpha$ 的充分下降条件 (Armijo 条件)：选择合适 $\alpha$ 满足 $f(x^{k+1}) \le f(x^k) + \alpha \beta \nabla f(x^k)^T d$ 其中 $\beta \in (0, 1)$ (如 $1 \times 10^{-4}$)。

   • $\beta = 0$：选择一个 $\alpha$ 使得 $f(x^{k+1})$ 变小即可。
   • $\beta = 1$：$f(x^{k+1})$ 至少要小于 $f(x)$ 在 $x^k$ 处的一阶 Taylor 近似。

2. 充分下降条件不够精细，可能导致算法过早收敛，引入曲率条件： $\nabla f(x^{k+1})^T d_k \ge \sigma \nabla f(x^k)^T d_k \quad (0 < \beta < \sigma < 1)$ 防止了 $\alpha$ 太小导致收敛过慢。若 $\alpha$ 太小，$\nabla f(x^{k+1})^T d_k$ 仍会非常负，意味着有很大的下降空间没有利用。

   强曲率条件：$|\nabla f(x^{k+1})^T d_k| \le -\sigma \nabla f(x^k)^T d_k$ 防止了 $\alpha$ 太大导致过大下降。

   • Wolfe 条件：Armijo + 曲率条件
   • 强 Wolfe 条件：Armijo + 强曲率条件

   停机准则： $\begin{cases} \|\nabla f(x^k)\| < \varepsilon \\ k > k_{max} \\ |f(x^{k+1}) - f(x^k)| < \varepsilon \\ \frac{|f(x^{k+1}) - f(x^k)|}{|f(x^k)|} < \varepsilon \end{cases}$

重要结论：二次型优化

形如 $f(x) = \frac{1}{2}x^T Q x + b^T x + c$ 的二次型，其梯度为 $\nabla f(x) = Q^T x + b = g$。 通过求导 $\nabla \varphi(\alpha_k) = 0$ 可得最优步长： $\alpha_k = \frac{g^T g}{g^T Q g}$

四、共轭梯度法

① 一阶方法；② 对于 $n$ 维二次凸优化问题，能够在 $n$ 步之内得到结果。

1. 何为共轭？ 设 $Q \in \mathbb{R}^{n \times n}$ 且 $Q = Q^T$，对于方向 $d^{(1)}, \dots, d^{(m)}$，如果对于所有 $i \neq j$，都有 $d^{(i)^T} Q d^{(j)} = 0$，则这些方向关于 $Q$ 是共轭的。

   • 共轭不保证正交，但可保证线性无关。
   • $n$ 维空间中相互共轭的非零向量不超过 $n$ 个。

2. 共轭性的优势 由于 $\{d^0, d^1, \dots, d^n\}$ 线性无关，构成 $R^n$ 空间的基。沿着共轭方向 $d^k$ 迭代，每一步找到的最优步长不会破坏前一步在 $d^{k-1}$ 上已经找到的最优性。理论上不超过 $n$ 次迭代就能精确找到二次函数的全局最优解。

3. 计算过程 $\min_x f(x) = \frac{1}{2}x^T Qx - b^T x + c, \quad x^{k+1} = x^k + \alpha_k d_k$

   • ① $d_0 = -g_0 = -(Ax_0 - b)$
   • ② 精确线搜索：$\alpha_k = \frac{-g_k^T d_k}{d_k^T Q d_k}$
   • ③ $x_{k+1} = x_k + \alpha_k d_k$
   • ④ $g_{k+1} = Ax_{k+1} - b$
   • ⑤ 计算共轭系数 $\beta_k = \frac{g_{k+1}^T Q d_k}{d_k^T Q d_k}$
   • ⑥ 更新下降方向：$d_{k+1} = -g_{k+1} + \beta_k d_k$

4. 实际应用时的变体

   • ① $\alpha_k$ 变为近似线搜索。
   • ② 非线性 CG 法使 $\beta_k$ 的计算与 $Q$ 无关。

A. HS 公式： $\beta_k = \frac{g_{k+1}^T (g_{k+1} - g_k)}{d_k^T (g_{k+1} - g_k)}$

B. PR 公式： $\beta_k = \frac{g_{k+1}^T (g_{k+1} - g_k)}{g_k^T g_k}$

C. FR 公式： $\beta_k = \frac{g_{k+1}^T g_{k+1}}{g_k^T g_k}$

↑ 首先 $g_{k+1}^T dk = 0$, $g_k^T dk_{k-1} = 0$

$dk = -g_k + \beta_{k-1} dk_{k-1}$

由共轭 $\Rightarrow dk^T \alpha_{dk} dk_j = 0$ ($j \neq k$)

$g_{k+1} = \alpha x_{k+1} - b$ $= \alpha (x_k + \alpha_k dk) - b$ $= \alpha x_k - b + \alpha_k \alpha_{dk} dk = g_k + \alpha_k \alpha_{dk} dk$

$dk_{k-1}^T g_{k+1} = \underbrace{dk_{k-1}^T g_k}_{=0} + \underbrace{\alpha_k \alpha_{dk} dk_{k-1}^T dk}_{=0}$

4-4: 无约束高维优化 → 牛顿法

令 $g(x^{(k)}) = \nabla f(x^{(k)})$, $F(x^{(k)}) = \nabla^2 f(x^{(k)})$

一、牛顿法的思想

令 $q(x) = f(x^{(k)}) + (x - x^{(k)})^T \nabla f(x^{(k)}) + \frac{1}{2} (x - x^{(k)})^T \nabla^2 f(x^{(k)}) (x - x^{(k)})$

利用 $q(x)$ 在 $x^{(k)}$ 近似 $f(x)$ → 找 $q(x)$ 极小点 → $\nabla q(x) = g(x^{(k)}) + F(x^{(k)}) (x - x^{(k)}) = 0$

若 $F(x^{(k)}) > 0$, $q(x)$ 极小点为 $x^{(k)} - F(x^{(k)})^{-1} g(x^{(k)})$

二、注意

1. 计算 $F(x^{(k)}) d^{(k)} = -g(x^{(k)})$ 需要求解 $n$ 维非齐次方程组
2. 牛顿法可用于求解 $g(x) = 0$

三、牛顿法缺点

1. 基于二次近似，可能发散
2. 在 $x^{(k)}$ 处 $F(x^{(k)})$ 非正定，$d^{(k)}$ 非下降方向
3. $x^{(k)}$ 处 $F(x^{(k)})$ 奇异，无法求解 $F(x^{(k)}) d^{(k)} = -g(x^{(k)})$
4. Hessian Matrix 计算量太大 ⇒ 拟牛顿法

四、修正牛顿法

1. 定理: $F(x^{(k)}) > 0$, $g^{(k)} = \nabla f(x^{(k)}) \neq 0$, $d^{(k)} = -F(x^{(k)})^{-1} g^{(k)}$ 是一个下降方向

2. 解决 $f(x^{(k)} + d^{(k)}) > f(x^{(k)}) \rightarrow$ 设置步长 $\rightarrow$ 阻尼牛顿法

3. $F(x^{(k)})$ 不正定 $\rightarrow$ Levenberg-Marquardt 修正 $\rightarrow x^{(k+1)} = x^{(k)} - (F(x^{(k)}) + \mu_k I)^{-1} g^{(k)}$ $\rightarrow \mu_k$ 足够大可保证正定

4. 定理: 若 $F(x^{(k)}) + \mu_k I$ 正定, 则 $[F(x^{(k)}) + \mu_k I]^{-1} g^{(k)}$ 也是一个下降方向

   • $\mu_k \to 0$, 接近牛顿法
   • $\mu_k \to \infty$, 表现出步长较小的梯度方法的特征. 实际可先选择较小的 $\mu_k$, 逐渐增大直至出现下降特性.

5. $F(x^{(k)})$ 奇异: 这一步换成最速梯度下降法.

由于 $\underbrace{z^{(k)} z^{(k)T}}_{\text{外积}} = \text{rank} \left( \begin{bmatrix} z_1^{(k)} \\ \vdots \\ z_n^{(k)} \end{bmatrix} [z_1^{(k)} \dots z_n^{(k)}] \right) = 1$

→ 如果 $H_k$ 对称, 则 $H_{k+1}$ 对称

秩 1 修正法步骤: ① 任选一个对称正定矩阵 $H_0$ (一般为 $I$) ② 若 $g^{(k)} = 0$, 停止, 否则 $d^{(k)} = -H_k g^{(k)}$ ③ 计算 $\alpha_k = \arg \min_{\alpha \ge 0} f(x^{(k)} + \alpha d^{(k)}), x^{(k+1)} = x^{(k)} + \alpha_k d^{(k)}$ ④ 计算: $\Delta x^{(k)} = \alpha_k d^{(k)} = x^{(k+1)} - x^{(k)}$ $\Delta g^{(k)} = g^{(k+1)} - g^{(k)}$ $\star H_{k+1} = H_k + \frac{(\Delta x^{(k)} - H_k \Delta g^{(k)}) (\Delta x^{(k)} - H_k \Delta g^{(k)})^T}{\Delta g^{(k)T} (\Delta x^{(k)} - H_k \Delta g^{(k)})}$

推导: 由 $H_{k+1} \Delta g^{(k)} = \Delta x^{(k)}$ 即 $(H_k + \alpha_k z^{(k)} z^{(k)T}) \Delta g^{(k)} = \Delta x^{(k)}$ $\alpha_k z^{(k)} z^{(k)T} \Delta g^{(k)} = \Delta x^{(k)} - H_k \Delta g^{(k)}$

性质: ① $H_1, \dots, H_k$ 满足拟牛顿条件 ② $H_k$ 一定是对称 Matrix ($H_1 = I$ 对称, $\alpha_k z^{(k)} z^{(k)T}$ 对称) ③ 秩 1 法也是一种共轭方向法, 具有和共轭法相同的收敛速度

$f(x_1, x_2) = x_1^2 + \frac{1}{2}x_2^2 + 3 = \frac{1}{2} [x_1, x_2] \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + 3$

$Q = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix}, x^{(0)} = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, H_0 = I$

$\nabla f(x) = Q^T x + b = Q^T x$

$g^{(0)} = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix} = \begin{bmatrix} 2 \\ 2 \end{bmatrix} \Rightarrow d^{(0)} = -g^{(0)} = \begin{bmatrix} -2 \\ -2 \end{bmatrix}$

$\alpha_k = \underset{\alpha \ge 0}{\text{argmin}} f(x^{(0)} + \alpha d^{(0)})$ $\Rightarrow \varphi(\alpha) = (x^{(0)} + \alpha d^{(0)})^T Q (x^{(0)} + \alpha d^{(0)}) + c$ $= x^{(0)T} Q x^{(0)} + 2\alpha d^{(0)T} Q d^{(0)} + x^{(0)T} Q \alpha d^{(0)} + \alpha d^{(0)T} Q x^{(0)}$ $\nabla \varphi(\alpha) = 2\alpha \cdot d^{(0)T} Q d^{(0)} + d^{(0)T} Q^T x^{(0)} + d^{(0)T} Q x^{(0)} = 0$

$x_0 = \begin{bmatrix} 1 \\ 2 \end{bmatrix}, d_0 = \begin{bmatrix} -2 \\ -2 \end{bmatrix}$ $2\alpha \cdot [-2, -2] \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} -2 \\ -2 \end{bmatrix} + 2 \cdot [-2, -2] \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} 1 \\ 2 \end{bmatrix}$ $[-4, -2] \begin{bmatrix} -2 \\ -2 \end{bmatrix} = 8 + 4 = 12, [-4, -2] \begin{bmatrix} 1 \\ 2 \end{bmatrix} = -8$ $\alpha = \frac{2}{3} \text{ ☆}$

$x_1 = \begin{bmatrix} 1 \\ 2 \end{bmatrix} + \frac{2}{3} \begin{bmatrix} -2 \\ -2 \end{bmatrix} = [-\frac{1}{3}, \frac{2}{3}]^T$

$\Delta x^0 = x_1 - x_0 = [-\frac{4}{3}, -\frac{4}{3}]^T$

$\Delta g^0 = g^1 - g^0 = \begin{bmatrix} 2 & 0 \\ 0 & 1 \end{bmatrix} \begin{bmatrix} -\frac{1}{3} \\ \frac{2}{3} \end{bmatrix} - \begin{bmatrix} 2 \\ 2 \end{bmatrix} = \begin{bmatrix} -\frac{2}{3} \\ \frac{2}{3} \end{bmatrix} - \begin{bmatrix} 2 \\ 2 \end{bmatrix} = \begin{bmatrix} -\frac{8}{3} \\ -\frac{4}{3} \end{bmatrix}, H_0 = I$

$H_1 = H_0 + \frac{(\Delta x^{(0)} - H_0 \Delta g^{(0)}) (\Delta x^{(0)} - H_0 \Delta g^{(0)})^T}{g^{(0)T} (\Delta x^{(0)} - H_0 \Delta g^{(0)})} = \begin{bmatrix} \frac{1}{6} & 0 \\ 0 & \frac{1}{6} \end{bmatrix}$

$\Delta^1 = H_1 \Delta g^{(0)} = \begin{bmatrix} \frac{1}{3} & -\frac{2}{3} \end{bmatrix}^T$

注意： 秩1修正法并不一定能满足下降性质，对于二次型问题也不一定下降。 → 当 $g^{(k)T} (\Delta x^{(k)} - H_k \Delta g^{(k)}) < 0$ 时，$H_k$ 不一定正定。

6. DFP算法 (秩2修正法)

$H_{k+1} = H_k + \alpha_k z_1^{(k)} z_1^{(k)T} + \beta_k z_2^{(k)} z_2^{(k)T}$

如何确定 $\alpha_k z_1^{(k)} z_1^{(k)T}$ 和 $\beta_k z_2^{(k)} z_2^{(k)T}$？

$\Delta g^{(k)} = g^{(k+1)} - g^{(k)}, \quad \Delta x^{(k)} = x^{(k+1)} - x^{(k)}$

$H_{k+1} \Delta g^{(k)} = \Delta x^{(k)} \rightarrow (H_k + \alpha_k z_1^{(k)} z_1^{(k)T} + \beta_k z_2^{(k)} z_2^{(k)T}) \Delta g^{(k)} = \Delta x^{(k)}$

$\Rightarrow \underbrace{\alpha_k z_1^{(k)} z_1^{(k)T} \Delta g^{(k)}}_{\textcircled{1}} + \underbrace{\beta_k z_2^{(k)} z_2^{(k)T} \Delta g^{(k)}}_{\textcircled{2}} = \underbrace{\Delta x^{(k)}}_{\textcircled{a}} - \underbrace{H_k \Delta g^{(k)}}_{\textcircled{b}} \rightarrow \text{假设 } \textcircled{1} = \textcircled{a}, \textcircled{2} = \textcircled{b}$

由于 $z_1^{(k)T} \Delta g^{(k)}$ 和 $z_2^{(k)T} \Delta g^{(k)}$ 是标量，那么可假设存在 $\theta_1, \theta_2$：

$z_1^{(k)} = \theta_1 \Delta x^{(k)}, \quad z_2^{(k)} = \theta_2 H_k \Delta g^{(k)}$

代回可得：$\alpha_k \theta_1^2 (\Delta x^{(k)T} \Delta g^{(k)}) \Delta x^{(k)} = \Delta x^{(k)}$

$\alpha_k \theta_1^2 = \frac{1}{\Delta x^{(k)T} \Delta g^{(k)}}$

同理可得：$\beta_k \theta_2^2 = \frac{1}{(H_k \Delta g^{(k)})^T \Delta g^{(k)}}$

我们要找到的是 $\alpha_k z_1^{(k)} z_1^{(k)T}$ 和 $\beta_k z_2^{(k)} z_2^{(k)T}$：

$H_{k+1} = H_k + \frac{\Delta x^{(k)} \Delta x^{(k)T}}{\Delta x^{(k)T} \Delta g^{(k)}} - \frac{(H_k \Delta g^{(k)}) (H_k \Delta g^{(k)})^T}{(H_k \Delta g^{(k)})^T \Delta g^{(k)}}$

○ DFP 能够修正秩 1 法中不定的问题。

示例

$f(x) = \frac{1}{2} x^T \begin{bmatrix} 4 & 2 \\ 2 & 2 \end{bmatrix} x - x^T \begin{bmatrix} 1 \\ 1 \end{bmatrix}, x \in \mathbb{R}^2, x^{(0)} = [0, 0]^T, H_0 = I$

$f(x) = \frac{1}{2} x^T Q x - x^T b$ $\nabla f(x) = Q x - b = \begin{bmatrix} 4 & 2 \\ 2 & 2 \end{bmatrix} x - \begin{bmatrix} 1 \\ 1 \end{bmatrix} = \begin{bmatrix} -1 \\ -1 \end{bmatrix} = g^{(0)}$ (注：此处原文计算结果与矩阵乘法逻辑略有差异，保留原文数值)

$d^{(0)} = -H_0 g^{(0)} = \begin{bmatrix} 1 \\ 1 \end{bmatrix}$ $\alpha_0 = \underset{\alpha > 0}{\operatorname{argmin}} f(x^{(0)} + \alpha d^{(0)}) = - \frac{g^{(0)T} d^{(0)}}{d^{(0)T} Q d^{(0)}} = 1$ $x^{(1)} = x^{(0)} + \alpha_0 d^{(0)} = [1, 1]^T, \Delta x^{(0)} = [1, 1]^T$ $\Delta g^{(0)} = g^{(1)} - g^{(0)}$

$H_1 = H_0 + \frac{\Delta x^{(0)} \Delta x^{(0)T}}{\Delta x^{(0)T} Q \Delta x^{(0)}} - \frac{(H_0 \Delta g^{(0)}) (H_0 \Delta g^{(0)})^T}{(H_0 \Delta g^{(0)})^T Q \Delta g^{(0)}} = \begin{bmatrix} \frac{1}{2} & -\frac{1}{2} \\ -\frac{1}{2} & \frac{3}{2} \end{bmatrix}$

$d^{(1)} = -H_1 g^{(1)}, \alpha_1 = - \frac{g^{(1)T} d^{(1)}}{d^{(1)T} Q d^{(1)}}$ $x^{(2)} = x^{(1)} + \alpha_1 d^{(1)} = \begin{bmatrix} -1 \\ \frac{3}{2} \end{bmatrix}^T$

7. BFGS算法

DFP满足了 $H_k > 0$ 以及拟牛顿条件，但规模较大时 $H_k$ 会接近奇异矩阵 $\Rightarrow$ BFGS

$H_{k+1} = H_k + \left( 1 + \frac{\Delta g^{(k)T} H_k \Delta g^{(k)}}{\Delta x^{(k)T} \Delta g^{(k)}} \right) \frac{\Delta x^{(k)} \Delta x^{(k)T}}{\Delta x^{(k)T} \Delta g^{(k)}} - \frac{\Delta x^{(k)} \Delta g^{(k)T} H_k + H_k \Delta g^{(k)} \Delta x^{(k)T}}{\Delta x^{(k)T} \Delta g^{(k)}}$

小结

• 牛顿法计算 Hessian Matrix $F(x^{(k)})$ 开销太大 $\rightarrow$ 拟牛顿法用 $H_k$ 拟合 $F^{-1}(x^{(k)})$
• $H_k \Delta g^{(k)} = \Delta x^{(k)}$
• 秩1修正：$H_{k+1} = H_k + \frac{(\Delta x^{(k)} - H_k \Delta g^{(k)}) (\Delta x^{(k)} - H_k \Delta g^{(k)})^T}{\Delta g^{(k)T} (\Delta x^{(k)} - H_k \Delta g^{(k)})}$
• $\Delta g^{(k)T} (\Delta x^{(k)} - H_k \Delta g^{(k)}) < 0$ 可能无法保证 $H_{k+1}$ 正定 $\rightarrow$ DFP算法

$H_{k+1} = H_k + \frac{\Delta x^{(k)} \Delta x^{(k)T}}{\Delta x^{(k)T} \Delta g^{(k)}} - \frac{(H_k \Delta g^{(k)}) (H_k \Delta g^{(k)})^T}{\Delta g^{(k)T} H_k \Delta g^{(k)}} \rightarrow$ 规模较大 $H_{k+1}$ 可能奇异 $\rightarrow$ BFGS算法

2. SVM

要求找出 $w, b$，使得所有数据点的最小间隔最大化： $\max_{w, b} \left\{ \min_{i} \left[ \frac{y^{(i)} (w^T x^{(i)} + b)}{\|w\|} \right] \right\}$ → 几何间隔尺度不变，函数间隔尺度可变。

$\min \frac{1}{2} \|w\|^2$ s.t. $y_i (w^T x_i + b) \ge 1, \quad i = 1, 2, \dots, m$

又由于优化问题为 $\max \gamma \min_i$，令 $\hat{\gamma}_{\min} = \min_i [y^{(i)} (w^T x^{(i)} + b)]$： $\max \gamma \min_i = \max \frac{\hat{\gamma}_{\min}}{\|w\|}, \text{ 令 } k = \frac{1}{\hat{\gamma}_{\min}} \rightarrow \hat{\gamma}_{\min}' = 1 \rightarrow \gamma_{\min} = \max \frac{1}{\|w\|_{(\text{new})}}$ $\rightarrow \min \|w\| \rightarrow \min \frac{1}{2} \|w\|^2$ $y^{(i)} (w^T x^{(i)} + b) = 1$

3. 异常点处理

→ 软间隔： $y_i (w^T x_i + b) \ge 1 - \xi_i, \xi_i \ge 0$ $\min \frac{1}{2} \|w\|^2 + C \sum_{i=1}^{m} \xi_i$ s.t. $y_i (w^T x_i + b) \ge 1 - \xi_i, \forall i = 1, 2, \dots, m$ $\xi_i \ge 0, \forall i = 1, 2, \dots, m$

4. 非线性分类

→ 将点映射到一个新空间，使得新空间的线性分类=原空间分类 → 核技巧。

---

5.2: 有约束问题最优性条件 $\Rightarrow$ 一阶条件 (拉格朗日和 KKT 条件)

一、约束优化一阶必要条件 $\Rightarrow$ 含等式约束

1. 仅含等式约束：$\min f(x)$ s.t. $h_i(x) = 0, i = 1, 2, \dots, m$ 其中 $x \in \mathbb{R}^n, f: \mathbb{R}^n \to \mathbb{R}, h_i: \mathbb{R}^n \to \mathbb{R}$ 连续可微，$m \le n$。

2. 拉格朗日定理：$n = 2, m = 1$，一阶等式约束问题的最优性条件： 设 $x^*$ 是 $f: \mathbb{R}^2 \to \mathbb{R}$ 的极小值，s.t. $h(x^*) = 0, h: \mathbb{R}^2 \to \mathbb{R}$ 且 $\nabla h(x^*) \neq 0$，则存在标量 $\lambda^*$ 满足 $\nabla f(x^*) + \lambda^* \nabla h(x^*) = 0$（$\lambda^*$ 为拉格朗日乘子）。

   推广至 $m$ 个 ($m \le n$) 约束的问题： ① 正则点：对于满足 $h_1(x^*) = 0, \dots, h_m(x^*) = 0$ 的点 $x^* \in \mathbb{R}^n$，若 $\nabla h_1(x^*), \dots, \nabla h_m(x^*)$ 是线性无关的，那么称 $x^*$ 是该约束的一个正则点。 $Dh(x^*) = \begin{bmatrix} \nabla h_1(x^*)^T \\ \vdots \\ \nabla h_m(x^*)^T \end{bmatrix}$ 为 $h(x)$ 在 $x^*$ 处的 Jacobi Matrix。若 $x^*$ 是正则点，$Dh(x)$ 满秩。

$m$ 个约束，$n$ 个变量的拉格朗日定理（必要条件）

$\min f(x)$ $\text{s.t. } h(x)=0, \quad h: \mathbb{R}^n \to \mathbb{R}^m \text{ 且 } m \le n, \quad x \in \mathbb{R}^n$ 若 $x^*$ 是优化问题的极小值且 $x^*$ 是正则点，那么一定存在 $\lambda^* \in \mathbb{R}^m$ 使得： $\nabla f(x^*) + \lambda_1^* \nabla h_1(x^*) + \dots + \lambda_m^* \nabla h_m(x^*) = 0$ $\text{或 } \nabla f(x^*) + Dh(x^*)^T \lambda = 0$ ★ 若 $x^*$ 是极小值和正则点，那么 $f$ 在 $x^*$ 的梯度可表示成 $\nabla h_i(x^*)$ 的线性组合。

3. 拉格朗日乘子法：通过求解拉格朗日条件方程组找到极值点： $\left\{ \begin{array}{l} \nabla f(x^*) + \lambda_1^* \nabla h_1(x^*) + \dots + \lambda_m^* \nabla h_m(x^*) = 0 \\ h_i(x) = 0, \quad i = 1, 2, \dots, m \end{array} \right.$ 正则性是拉格朗日定理成立的必要条件。

逻辑： $\left\{ \begin{array}{l} \text{正则性} \rightarrow \text{拉格朗日定理} \\ \text{拉格朗日定理} \rightarrow \text{拉格朗日乘子法} \rightarrow \text{候选点} \end{array} \right.$ 需要验证。Tip: 矩阵正定 $\Rightarrow$ 满秩 $\Leftrightarrow$ 可逆。

---

二、约束优化问题一阶必要条件 $\rightarrow$ 一般约束问题

1. KKT条件：形如 $\min f(x)$ s.t. $h_i(x) = 0, i = 1, \dots, m$ $g_j(x) \le 0, j = 1, \dots, p$ $x \in \mathbb{R}^n, f, h_i, g_j$ 均可微。

   定义正则点：

   • 起作用的约束：$g_j(x^*) = 0$
   • 不起作用的约束：$g_j(x^*) < 0$
   • 正则点：设 $x^*$ 满足 $h(x^*) = 0, g(x^*) \le 0$。设 $J(x^*)$ 为 $x^*$ 处起作用的不等式约束下标集 $J(x^*) = \{j: g_j(x^*) = 0\}$。如果 $\nabla h_i(x^*), \nabla g_j(x^*), 1 \le i \le m, j \in J(x^*)$ 是线性无关的，则 $x^*$ 是正则点。

2. KKT定理：设 $f, h_i, g_j$ 一阶连续可微，$x^*$ 是正则点且局部极小点，那么必然存在 $\lambda_1^*, \dots, \lambda_m^* \in \mathbb{R}$ 和 $\mu_1^*, \dots, \mu_p^* \in \mathbb{R}$，使得以下成立： ① $\mu_1^*, \dots, \mu_p^* \ge 0$ ② $\nabla f(x^*) + \sum_{i=1}^m \lambda_i^* \nabla h_i(x^*) + \sum_{j=1}^p \mu_j^* \nabla g_j(x^*) = 0$ ③ $\mu_j^* g_j(x^*) = 0, \forall j$ （互补松弛条件）

Observation:

① 每个等式约束 $\to \lambda$，不等式 $\to \mu$ ② $g_j(x^*) < 0 \to \mu_j^* = 0$

求解条件： ① $\mu^* \ge 0$ ② $\nabla f(x^*) + \nabla h(x^*)^T \lambda + \nabla g(x^*)^T \mu^* = 0$ ③ $\mu^* \perp g(x^*) = 0$ ④ $h(x^*) = 0$ ⑤ $g(x^*) \le 0$

非标准型KKT：$\max f(x) \rightarrow \min -f(x) \rightarrow -\nabla f(x^*)$。

② $g(x) \ge 0 \rightarrow -g(x) \le 0 \rightarrow \nabla f(x^*) + D h(x^*)^T \lambda^* - D g(x^*)^T \mu^* = 0$

三、拉格朗日函数

$L(x, \lambda, \mu) = f(x) + \sum_{i=1}^{m} \lambda_i h_i(x) + \sum_{j=1}^{p} \mu_j g_j(x)$

或 $f(x) + \lambda^T h(x) + \mu^T g(x)$

$x \in \mathbb{R}^n, \lambda \in \mathbb{R}^m, \mu \in \mathbb{R}^p$

• $\lambda$ 和 $\mu \rightarrow$ 拉格朗日乘子
• KKT条件 $\rightarrow$ ① $\mu_1^*, \dots, \mu_p^* \ge 0$ ② $\nabla_x L(x^*, \lambda^*, \mu^*) = 0$ ③ $\mu_1^* g_1(x^*) = 0, \dots, \mu_p^* g_p(x^*) = 0$ ④ $\nabla_{\lambda_i} L(x^*, \lambda^*, \mu^*) = 0$ ⑤ $\nabla_{\mu_i} L(x^*, \lambda^*, \mu^*) \le 0$

四、拉格朗日对偶

1. 拉格朗日对偶函数: $d(\lambda, \mu) = \inf_{x \in \mathbb{R}^n} L(x, \lambda, \mu) = \inf_{x \in \mathbb{R}^n} \left( f(x) + \sum_{i=1}^{m} \lambda_i h_i(x) + \sum_{j=1}^{p} \mu_j g_j(x) \right)$ ☆ $\inf \to$ 下确界 = $\min(\cdot)$

2. 弱对偶定理: 设 $p^*$ 为原优化问题最小值, $d(\lambda, \mu)$ 为拉格朗日对偶函数, 则 $\forall \lambda, \forall \mu \ge 0$ $p^* \ge d(\lambda, \mu)$

3. 对偶问题: $d^* = \max d(\lambda, \mu)$, $d^*$ 是原问题的下界 $(\lambda, \mu) \Rightarrow$ 对偶变量 ☆ $d(\lambda, \mu)$ 是关于 $\lambda, \mu$ 的凸函数 $\Rightarrow$ 无论原问题是否是凸优化, 它的对偶问题都是凸优化

证明凸优化: ① 凸函数: 二阶 (Hessian 半正定)、一阶 ($f(\theta x_1 + (1-\theta)x_2) \le \theta f(x_1) + (1-\theta)f(x_2)$) ② 可行集是凸集 (不等式凸函数, 等式是仿射函数) $x_1, x_2 \in D, \forall \theta \in [0, 1], \theta x_1 + (1-\theta)x_2 \in D$

---

5-3: 约束问题的求解算法

$\begin{array}{ll} \min f(x) & x \in \mathbb{R}^n, f: \mathbb{R}^n \to \mathbb{R} \\ \text{s.t. } h(x) = 0 & h: \mathbb{R}^n \to \mathbb{R}^m \\ & g(x) \le 0 \quad g: \mathbb{R}^n \to \mathbb{R}^p, m \le n \end{array}$

一、算法概览

• 投影法 (线性等式约束)
• 罚函数法 / 外点法 (等式不等式约束)
• 内点法 / 障碍函数法 (不等式约束)

二、投影法 (适用于线性等式约束)

1. 思想: 若迭代中 $x_{k+1}$ 跑出了可行域 $\Omega$, 就用一个投影算子 $\Pi(x)$ 拉回 $\Omega$ 内最近的点
2. 公式: $\min f(x) \quad \text{s.t. } Ax = b$ $P = I_n - A^T (AA^T)^{-1} A$ $x_{k+1} = x_k - \alpha_k \underbrace{P \nabla f(x_k)}_{\text{梯度投影方向}}$
3. 性质: ① $P = P^T$ 且 $P = P^2$ ② 只要 $x_0$ 满足 $Ax_0 = b$, 后续都满足 ③ 投影 $\nabla f$ 方向是目标函数下降方向

三、罚函数法 / 外点法

1. 思想: 将约束问题 $\to$ 无约束问题, 构造包含惩罚项 $\gamma P(x)$ 的新函数 $Q(x, \gamma)$
2. 迭代:
   • ① 惩罚因子 $\gamma$: 初始取较小值 ($\gamma=1$), $\uparrow \gamma \to \infty$
   • ② 轨迹: 迭代点通常在可行域外部, 惩罚 $\uparrow \to$ 逐渐逼近可行域边界 $\to$ 外点法
3. 常见罚函数:
   • ① 绝对值: $\sum |h_i(x)| + \sum \max(0, g_j(x)) \to$ 不可微
   • ② Courant-Beltrami 罚函数: $P(x) = \sum_{i=1}^{m} [h_i(x)]^2 + \sum_{j=1}^{p} [\max(0, g_j(x))]^2$
4. 优缺点:
   • ① 初始点可任取 $\checkmark$
   • ② 中间结果不可行, $\gamma$ 很大时计算困难 $\times$

四、内点法 / 障碍函数法

1. 思想: 在可行域边界设置 barrier, 靠近边界函数值 $\to \infty$

2. 障碍函数:

   • ① Log barrier: $P(x) = -\sum_{i=1}^{p} \ln(-g_i(x))$
   • ② Power barrier: $\sum_{i=1}^{p} \frac{1}{(-g_i(x))^t} \quad (t > 0)$

3. 迭代:

   • ① $\gamma$ 从某个正数开始 $\to 0$ (惩罚函数相反)
   • ② 必须严格在可行域内部

4. 罚函数 vs. 障碍函数:

   • ① 外部逼近 vs. 内部逼近
   • ② 内点法可随时停机
   • ③ 罚函数二阶导数边界可能不存在

---

6-1: 线性规划案例

一、定义

LP (Linear Programming) 是指约束和目标函数都是线性优化问题，形如：

$\begin{aligned} \min & \quad C^T x \\ \text{s.t. } & Ax \ge b \\ & x \ge 0 \end{aligned} \rightarrow \begin{cases} \text{① 目标函数是线性函数} \\ \text{② 约束是线性等式和不等式} \end{cases}$

特点：

• ① 有很强的建模能力，广泛应用
• ② 具备高效求解公式
• ③ 是基本的优化问题

二、建模技巧：最小化最大值

$\begin{aligned} \min \max_{i=1 \dots n} c_i x_i \\ \text{s.t. } Ax = b \end{aligned} \rightarrow \begin{aligned} \min & \quad t \\ \text{s.t. } & c_i x_i \le t \quad \forall i=1 \dots n \\ & Ax = b \end{aligned}$

最大化最小值同理： $\begin{aligned} \max \min c_i x_i & \rightarrow \min -\min c_i x_i \\ \text{s.t. } c_i x_i \ge t & \Rightarrow -c_i x_i \le -t \end{aligned}$

三、绝对值目标函数

$\min \sum_{i=1}^{n} c_i |x_i| \implies \begin{aligned} & \min \sum_{i=1}^{n} c_i z_i \\ & \text{s.t. } Ax = b \\ & -z_i \le x_i \le z_i, z_i \ge 0, \forall i = \{1, \dots, n\} \end{aligned}$

四、绝对值约束条件

$\begin{aligned} & \min c^T x \\ & \text{s.t. } |a^T x| \le c \implies -c \le a^T x \le c \\ & \phantom{\text{s.t. } |a^T x| \le c} \implies -a^T x \le c \\ & \phantom{\phantom{\text{s.t. } |a^T x| \le c} \implies} a^T x \le c \end{aligned}$

$\begin{aligned} & \text{s.t. } |a^T x| \ge c \implies a^T x \ge c \\ & \phantom{\text{s.t. } |a^T x| \ge c \implies} -a^T x \ge c \end{aligned}$ ☆ 不可转化，除 $c=0$ 以外，无可行解

五、回归分析中的 LP

$\min \|Ax - b\|_2^2$ (最小二乘函数), $x \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}$

• 最小 $L_1$ 范数模型：$\|x\|_1 = \sum_{i=1}^{n} |x_i|$
• 最小 $L_{\infty}$ 范数模型：$\|x\|_{\infty} = \max \{|x_1|, \dots, |x_n|\}$

1. $L_1$ 线性数据拟合: $\min \|Ax-b\|_1 \Rightarrow \min |y_1| + \dots + |y_n|$

$\begin{aligned} & \star \text{ s.t. } Ax-b=y \\ \Rightarrow & \min z_1 + \dots + z_n \\ & \text{s.t. } Ax-b=y \\ & -z_i \le y_i \le z_i, \forall i \in \{1, \dots, n\} \end{aligned}$

2. $L_\infty$ 线性数据拟合: $\min \|Ax-b\|_\infty \Rightarrow \min \max \{t_1, \dots, t_n\}$

$\begin{aligned} & \text{s.t. } Ax-b=y \\ & -t_i \le y_i \le t_i, \forall i \in \{1, \dots, n\} \\ \Rightarrow & \min t \\ & \text{s.t. } Ax-b=y \\ & -t_i \le y_i \le t_i, \forall i \in \{1, \dots, n\} \\ & t_i \le t, \forall i \in \{1, \dots, n\} \end{aligned}$

• 建模时, $L_1$ 拟合更抗异常值 • $L_\infty$ 拟合能保证最大偏差最小

$\begin{aligned} \Rightarrow & \min t \\ & -\|t\|_1 \le Ax-b \le \|t\|_1 \end{aligned}$

3. 线性分类: $\max \delta$

$\text{s.t. } y(p_i) \ge ax(p_i) + b + \delta$ $y(q_i) \le ax(q_i) + b - \delta$

$p_1, p_2, \dots, p_m$ 和 $q_1, q_2, \dots, q_n$ 分别为上下两个点集

6-2: 线性规划基础

一. 图解法

可解只有2个变量的LP问题, 但无法求解至少3个变量的LP。 由观察, 一个LP问题可能：

序号	情况
①	有一个最优解
②	无界, 无最优解
③	有无穷个最优解
④	没有可行解

求解历史: 单纯形法 $\to$ 拟单纯形法 $\to$ 内点法

二. LP求解

1. LP标准型: $\min c^T x$ s.t. $Ax = b$ (等式约束, 左边线性函数, 右边常数) $x \ge 0$ (变量全部 $\ge 0$) 其中 $c \in \mathbb{R}^n, A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m$

2. 松弛变量的引入: 将不等式约束转化为等式约束 $a_{i1}x_1 + \dots + a_{in}x_n \le b_i \Leftrightarrow a_{i1}x_1 + \dots + a_{in}x_n + y_i = b_i, \quad y_i \ge 0$

3. 基础概念

   • Basis (基): 从 $A$ 中挑出的线性无关的 $m$ 列构成的矩阵 $\Rightarrow$ 基矩阵 $B$。剩下 $n-m$ 列组成的矩阵 $\Rightarrow$ 非基矩阵 $D$。 $\Rightarrow Ax=b \Rightarrow [B, D]x=b \Rightarrow [B, D] \begin{bmatrix} x_B \\ x_D \end{bmatrix} = b \Rightarrow Bx_B + Dx_D = b$ 其中 $x_B$ 为基变量, $x_D$ 为非基变量。
   • 基本解 (Basic Solution): 把所有 $x_D$ 设为 0 然后求解方程。 $Bx_B = b$, 由 $B$ 满秩 (可逆), $x_B = B^{-1}b$, $x_0 = [x_B, x_D]^T = [B^{-1}b, 0]^T$ 即为基本解。 注意: 基本解对应直线交点, 但不一定满足 $x \ge 0$。
   • 基本可行解 (BFS): 若 $x_B$ 的每一个分量都 $\ge 0$, 则称其为基本可行解。

4. 几何意义和核心定理

   • 极点: 线性规划的可行域是一个凸多面体。基本可行解 $\longleftrightarrow$ 凸多面体的顶点 $\longleftrightarrow$ 极点。
   • 核心定理: (1) 存在性: 若线性规划有可行解, 就一定有基本可行解。 (2) 最优性: 若线性规划有最优解, 那么一定有一个基本可行解是最优解。 单纯形法逻辑: 在各个基本可行解之间跳跃, 直到找到最好的点。

6.3: 单纯形法

1. 核心逻辑: ① 判断当前解是否最优。 ② 寻找下一个方向 (进基): 若不是最优, 找一条让目标下降最快的边。 ③ 确定步长 (出基): 沿着边走到下个顶点为止, 不可离开可行域。

2. 判定最优性: 设当前解 $x^0 = \begin{bmatrix} B^{-1}b \\ 0 \end{bmatrix}$, 目标函数 $f(x) = c^T x_0 + (c_D^T - c_B^T B^{-1}D)x_D'$。 如果 $c_D^T - c_B^T B^{-1}D \ge 0$ 成立, 由于 $x_D' \ge 0$, 可行解 $x_0$ 具有最优性。

3. 转换到下一个基本可行解 (Pivot 操作): ① 将第 $p$ 行除以 $a_{p, q}$。 ② 将第 $q$ 列除第 $p$ 行以外的元素均置 0。 ③ 更新 $b_i' = b_i - \frac{b_p}{a_{pq}} a_{iq}$。

• $a_{pq}$: 主元，$q$ 列：进基列，$p$ 行：出基行。
• $x_q$: 进基变量，$x_p$: 出基变量。

$b_p' = \frac{b_p}{a_{pq}} \ge 0, \quad a_{pq} > 0$

$\forall i \neq p, b_i' = b_i - \frac{b_p}{a_{pq}} a_{iq} \ge 0 \quad \begin{cases} a_{iq} \le 0 \quad \checkmark \\ a_{iq} > 0 \rightarrow \frac{b_i}{a_{iq}} \ge \frac{b_p}{a_{pq}} \star \end{cases}$

我们可将 $x_q$ 系数列变为单位阵的一列并替换原单位阵 $x_p$ 系数列，并保持可行解不变（行初等变换）。

如何保证 $x^0$ 更优？

判别数 $\sigma = c^T - c_B^T B^{-1} A = [c_B^T, c_D^T] - c_B^T B^{-1} [B, D] = [0, c_D^T - c_B^T B^{-1} D]^T$

• $\forall q \in \{m+1, n\}, \sigma_q \ge 0 \Rightarrow x^0$ 是最优解。
• $\exists q \in \{m+1, n\}, \sigma_q < 0$:
  • 第 $q$ 列存在 $a_{iq} > 0 \to$ 用第 $q$ 列作进基。
  • 第 $q$ 列不存在 $a_{iq} > 0 \to$ 问题无界 ($\min = -\infty$)。

如何将一个线性规划转化为等价的标准型？

总结：循环利用以下规则，直到原线性规划成为标准型。

1. $\max c^T x \Rightarrow \min -c^T x$
2. 约束不满足左端线性函数，右端常数 $\to$ 左右两端移项为目标格式。
3. $a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n \le b_i \Rightarrow$ 引入松弛变量 $y_i$，将不等式替换为 $a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n + y_i = b_i$，加入约束 $y_i \ge 0$。
4. $a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n \ge b_i \Rightarrow$ 引入松弛变量 $y_i$，将不等式替换为 $a_{i1}x_1 + a_{i2}x_2 + \dots + a_{in}x_n - y_i = b_i$，加入约束 $y_i \ge 0$。
5. $x_i$ 无正负约束 $\to$ 引入变量 $u$ 和 $v$，将 $x_i$ 替换为 $u - v$，加入约束 $u \ge 0, v \ge 0$。

单纯形法步骤

→ 贪心法则，可能导致循环。

a) 先选第 $q$ 列: $q = \arg \min_j \{ \sigma_j \mid \sigma_j < 0 \}$ b) 再选第 $p$ 行: $p = \arg \min_i \{ \frac{b_i}{\Delta_{iq}} : \Delta_{iq} > 0 \}$，如果 $p$ 不存在，停止运算 $\to$ 问题无界。 c) 以 $\Delta_{pq}$ 为主元做行初等变换 (换基运算):

• 第 $p$ 行第 $j$ 个元素 $\Delta_{pj}' = \frac{\Delta_{pj}}{\Delta_{pq}}, b_p' = \frac{b_p}{\Delta_{pq}}$
• 第 $i$ 行 ($i \neq p$), $\Delta_{ij}' = \Delta_{ij} - \frac{\Delta_{pj}}{\Delta_{pq}} \Delta_{iq}, b_i' = b_i - \frac{b_p}{\Delta_{pq}} \Delta_{iq}$

Bland 法则

• 进基 $q$ 选满足 $\sigma_j < 0$ 序号最小的。
• $p$ 选择不变，若多行比例相同选序号小的。
• 最后一行 $\sigma_j' = \sigma_j - \frac{\Delta_{pj}}{\Delta_{pq}} \sigma_q, z' = z - (\frac{b_p}{\Delta_{pq}} \sigma_q)$

二阶段单纯形法: 处理不易从标准型中找到一个单位矩阵 $I_m$ 的情况。 问题：为了利用单纯形法，如何找到一个初始的基础可行解？

• 枚举
• 二阶段法

6-4: 线性规划对偶

一、如何快速构造一个 LP 的对偶？

$\begin{array}{ll} \min & c^T x \\ \text{s.t.} & Ax = b \\ & x \ge 0 \end{array} \xrightarrow{\text{拉格朗日对偶}} \begin{array}{ll} \max & \lambda^T b \\ \text{s.t.} & \lambda^T A \le c^T \end{array}$

$\begin{array}{ll} \min & c^T x \\ \text{s.t.} & Ax \ge b \\ & x \ge 0 \end{array} \xrightarrow{\text{对偶}} \begin{array}{ll} \max & \lambda^T b \\ \text{s.t.} & \lambda^T A \le c^T \\ & \lambda \ge 0 \end{array}$

→ LP 中对偶的对偶就是原问题。

二、对偶问题构造

对称型 P: $\min c^T x, \text{s.t. } Ax \ge b, x \ge 0$ D: $\max \lambda^T b, \text{s.t. } A^T \lambda \le c, \lambda \ge 0$

非对称型 (标准型) P: $\min c^T x, \text{s.t. } Ax = b, x \ge 0$ D: $\max \lambda^T b, \text{s.t. } A^T \lambda \le c$

$= (8 - \lambda_1 - 3\lambda_2)x_1 + (6 - 2\lambda_1 - \lambda_2)x_2 + (3 - \lambda_2 - \lambda_3)x_3 + (6 - \lambda_1 - \lambda_2 - \lambda_3)x_4 + 3\lambda_1 + 6\lambda_2 + 2\lambda_3$

注意

用 $\nabla_L x = 0 \Rightarrow$ 对 $x$ 施加约束 $\mu^T x \ge 0$ (KKT) 用 $\nabla_L \lambda \ge 0 \Rightarrow$ 没对 $\lambda$ 施加约束

$\Rightarrow \begin{cases} \lambda_1 + 3\lambda_2 \le 8 \\ 2\lambda_1 + \lambda_2 \le 6 \\ \lambda_2 + \lambda_3 \le 3 \\ \lambda_1 + \lambda_2 + \lambda_3 \le 6 \end{cases} \quad \begin{array}{ll} \max & 3\lambda_1 + 6\lambda_2 + 2\lambda_3 \\ \text{s.t.} & \lambda_1 + 3\lambda_2 \le 8 \\ & 2\lambda_1 + \lambda_2 \le 6 \\ & \lambda_2 + \lambda_3 \le 3 \\ & \lambda_1 + \lambda_2 + \lambda_3 \le 6 \end{array}$

原问题（对偶问题）	对偶问题（原问题）
目标函数 $\max Z$	目标函数 $\min Z$
约束条件：$m$ 个 第 $i$ 个约束类型为 ” $\le$ “ 第 $i$ 个约束类型为 ” $\ge$ “ 第 $i$ 个约束类型为 ”=“	变量数：$m$ 个 第 $i$ 个变量 $\ge 0$ 第 $i$ 个变量 $\le 0$ 第 $i$ 个变量是自由变量
变量数：$n$ 个 第 $j$ 个变量 $\ge 0$ 第 $j$ 个变量 $\le 0$ 第 $j$ 个变量是自由变量	约束条件：$n$ 个 第 $j$ 个约束类型为 ” $\ge$ “ 第 $j$ 个约束类型为 ” $\le$ “ 第 $j$ 个约束类型为 ”=“

三. 三大核心定理

1. 弱对偶定理： 对偶问题的任意目标值 $\le$ 原问题的任意目标值 $P: \min c^T x \rightarrow D: \max \lambda^T A$ 因 $\lambda^T A \le c^T, x \ge 0$ $\lambda^T A x \le c^T x$ 已知 $Ax = b$ $\lambda^T b \le c^T x \star$

2. 强对偶定理： 若原问题有最优解，则对偶问题也有最优解，且 $c^T x^* = \lambda^* b$ 假设原问题有最优解，最优基为 $B$，则最优解可表示为 $x^* = B^{-1}b$ 令 $\lambda^T = C_B^T B^{-1}$，单纯形法判别数 $= C^T - C_B^T B^{-1}A = C^T - \lambda^T A \ge 0$ $\lambda^T A \le C^T$，满足对偶问题约束，是一个可行解 $\lambda^T b = (C_B^T B^{-1})b = C_B^T (B^{-1}b) = C_B^T x^*$ 二者数值相等

3. 互补松弛定理： $x$ 和 $\lambda$ 是最优解的充要条件是 $C^T - \lambda^T A \ge 0$ ① 必要：$x, \lambda$ 是最优解 $\rightarrow C^T x = \lambda^T b$ 由 $Ax = b \rightarrow C^T x = \lambda^T (Ax) \rightarrow C^T x = \lambda^T A x \rightarrow (C^T - \lambda^T A)x = 0$ ② 充分：$(C^T - \lambda^T A)x = 0 \rightarrow C^T x = \lambda^T A x$ 因为 $x$ 是可行解，$Ax = b \rightarrow C^T x = \lambda^T b$ 由弱对偶 $\rightarrow$ 此时 $x$ 和 $\lambda$ 是各自最优解

四. 对偶的经济意义: 影子价格

最优状态下，$Z^* = \lambda^*{}^T b = \sum_{i=1}^{m} \lambda_i^* b_i$ $\frac{\partial Z^*}{\partial b_i} = \lambda_i^* \rightarrow$ 若资源 $b_i$ 变化一点，最优成本 $Z^*$ 会变化多少

结合互补松弛条件: $\lambda_i^* (A_i x^* - b_i) = 0$ A. $A_i x^* - b_i > 0 \rightarrow \lambda_i^* = 0 \rightarrow \frac{\partial Z^*}{\partial b_i} = 0 \rightarrow$ 资源的边际价值为 0 B. $A_i x^* - b_i = 0 \rightarrow \lambda_i^* \text{ 可以 } > 0 \rightarrow \frac{\partial Z^*}{\partial b_i} = \lambda_i^* > 0 \rightarrow b_i$ 是优化瓶颈

7-1: 整数规划 $\to$ 部分或全部变量为整数的规划问题

整数线性规划：目标函数和约束函数是线性函数的整数规划问题

• 0-1 规划：所有变量定义域为 0 或 1
• 纯整数规划：所有变量定义域为整数
• 混合整数规划：变量中同时包含整数和非整数变量

一、主要关注：纯整数规划 $\begin{cases} \min c^T x \\ \text{s.t. } Ax = b \\ x \ge 0 \\ x \in \mathbb{Z}^n \end{cases}$

1. 问题：线性松弛 $\to$ 去掉整数条件 $\to$ 变成普通 LP 为什么不能四舍五入？松弛最优解 $(5.2, 1.8) \to (5, 2) \to$ 可能超出约束 / 不是真实整数最优解 什么时候可以偷懒？$\to$ TU Matrix (完全幺模矩阵) $\to$ 若不等式系数矩阵是 TU Matrix 考虑 IP: $\min c^T x, \text{s.t. } Ax \le b, x \ge 0 \text{ 且 } x \in \mathbb{Z}^n$ ① $A \in \mathbb{R}^{m \times n}$ 的任意子方阵行列式均为 0 或 1 ② $b \in \mathbb{Z}^m$ 则线性松弛解就是整数

TU Matrix 的判定： ① 所有子方阵的行列式（所有非零子式都为 $\pm 1$） ② 充分条件： A. 元素只有 0, 1, -1 B. 每一列至多 2 个非 0 元素 C. 如果一列有 2 个非 0 元素，它们相加为 0

2. 网络流问题：约束

• 容量限制：流经任一条边的流量不超过最大流量
• 流量守恒：流入 = 流出

二. 整数规划如何求解？

1. 割平面法 ① 思路：使用单纯形法对线性松弛问题 LP 求最优解 $\to$ 若最优解是整数，则找到了原问题的最优解 $\to$ 如果 $x$ 至少包含一个非整数元素，添加一个新的约束，使得 $x$ 违反该约束，但是任何可行的整数解却不违反 $\to$ 求解添加约束后的 LP 问题直到发现最优解。 由于一个线性约束对应一个分割平面，所以叫割平面法。

② 举例：$\min c^T x, \text{s.t. } Ax = b, x \ge 0$ 松弛 LP 最优解时单纯形表： $\begin{bmatrix} 1 & 0 & \dots & 0 & d_{1,m+1} & \dots & d_{1,n} & b_1 \\ 0 & 1 & \dots & 0 & \vdots & & \vdots & \vdots \\ \vdots & \vdots & \ddots & \vdots & \vdots & & \vdots & \vdots \\ 0 & 0 & \dots & 1 & d_{m,m+1} & \dots & d_{m,n} & b_m \\ 0 & 0 & \dots & 0 & \sigma_{m+1} & \dots & \sigma_n & z \end{bmatrix}$ $Z = C_B^T x_B + C_D^T x_D$ $\text{s.t. } Ax = b \to Bx_B + Dx_D = b \to B^{-1}Bx_B + B^{-1}Dx_D = B^{-1}b \to Ix_B + (B^{-1}D)x_D = B^{-1}b$

$\to x_B + \underbrace{(B^{-1}D)}_{A} x_D = \underbrace{B^{-1}b}_{b}$

$Z = C_B (b - Ax_D) + C_D x_D$

$= \underbrace{C_B b}_{Z} + \underbrace{(C_D - C_B A)}_{0} x_D$

①

针对第 $i$ 个等式约束，$x_i + \sum_{j=m+1}^{n} a_{ij} x_j = b_i \to x_i + \sum_{j=m+1}^{n} \lfloor a_{ij} \rfloor x_j \le \lfloor b_i \rfloor$

$\to$ 不会排除任何可行解

②

$x_j$ 是整数，$a_{ij}$ 是整数 $\to x_i + \sum_{j=m+1}^{n} a_{ij} x_j \le b_i$

可引入松弛变量：$\sum_{j=m+1}^{n} (a_{ij} - \lfloor a_{ij} \rfloor)x_j - x_{n+i} = b_i - \lfloor b_i \rfloor$ ☆☆☆

(1-②)

$\to$ 即为新的约束。

2. 分支定界法：二分搜索

① 解线性松弛问题 { 是整数解 $\to$ stop 不是 $\to$ next step 比如 $x = (1.5, 2.5)$

② 分支 { $x_1 \le 1 \to$ 加入约束 $\to$ 若有整数解 stop，否则继续分 (得到 $Z_1$) $x_1 \ge 2 \to$ 加入约束 $\to$ 继续分 (得到 $Z_2$)

③ 若 $Z_1$ 是整数解 { $Z_2 \ge Z_1$，剪枝 $Z_2$ $Z_2 < Z_1$ 但不是整数解 $\to$ 继续分支

Linked Notes

No outgoing note links.

Referenced By

No backlinks yet.