这里我来记录我认为的 20 世纪最具代表性的十个重要算法。鉴于已有包括 IEEE Computing in Science & Engineering 2000 及其之后的修改在内的许多更官方或大众的评选，并且其中一部分算法可能已经得到公认，因此我的版本自然也大差不差，但会稍微注重内容的不重叠性和数学性，主要目的还是帮助自己再对一些重要的算法做个回顾。
1 MC#
$$ \int fp \leftrightarrow \mathbb{E}f \leftrightarrow \frac{1}{n}\sum\limits^n_{i=1} f_i \text{ sampling} $$
Variance Control：$\mathbb{E}f(x) = \mathbb{E}(f(x)+c(g(x)-\mathbb{E}g(x)))$，$c^*=-\frac{\text{Cov}(f,g)}{\text{V} (g)}$
Importance Sampling：$\mathbb{E}_Xf(x)=\mathbb{E}_Y\frac{f(y)p(y)}{q(y)}$，$q^*(y)=\frac{\vert f(y)\vert p(y)}{\mathbb{E}_Xf(x)}$（not computable）
2 Simplex#
$$ \begin{aligned} \text{(LP)} & \min\limits_{x\in \mathbb{R}^n} c^\prime x\\ \text{s.t.} & Ax=b,\\ & x\ge 0 \end{aligned} $$
对于 $Ax\le b$ 条件可引入松弛变量 $Ax + s = b$（$b\ge 0$ 则 $s\in \mathbb{R}^m_+$ 可作为初始 $x_N$）。
线性目标函数在凸可行域上一定有顶点为最优解。这些顶点用基变量 $x_B\in \mathbb{R}^m$ 记载（$A \in \mathbb{R}^{m\times n}$，$m<n$），即从 $x$ 下标集 $\{1,\dots,n\}$ 中选取 $m$ 个非零分量，剩余 $n-m$ 个分量为 $0$。$AP=[B, N],\ Px={x_B \brack x_N}$，$x_B = B^{-1}b - B^{-1}Nx_N$。
目标函数 $z=c_B^\prime x_B+c_N^\prime x_N = c_B^\prime B^{-1}b+\bar{c}^\prime x_N$，Reduced Cost $\bar{c}=c_N-N^\prime B^{-1\prime}c_B$。入基变量 by $\max\limits_j \bar{c}_j >0$（Dantzig Rule），沿这一较优方向行走到尽头（另一顶点）时某变量被出基，对应 $x_{i\in B} \ge 0$ 取等。故入基变量值 $x_j^* = \min\limits_i \frac{(B^{-1}b)_i}{(B^{-1}a_j)_i}$，$a_j$ 为 $A$ 第 $j$ 列，此式即挑出出基变量 $i$。Pivot 更新 $x_B$ 和 $B^{-1}$。
最优的充要条件为 $\forall j\in N,\ \bar{c}_j\le 0$。当出现某个 $\bar{c}_j>0$ 而 $B^{-1}a_j\le 0$ 则原问题无界。
对于初始基选取，除了前述自然基（$B=I_m$）情形，可引入人工变量 $u_i\ge 0$ 于每条 $a^\prime x=b$ 或 $a^\prime x\ge b$ 或 $a^\prime x\le b,\ b<0$ 约束（分别变为 $a^\prime x+u=b,\ a^\prime x-s+u=b,\ -a^\prime x-s+u=-b$）。两阶段法 phase 1 将目标改为 $\min \sum\limits_i u_i$，其余 $x,s$ 置 $0$ 跑一遍得到解 $u^*=0$（否则原问题不可行），phase 2 删去人工变量并以此时的基出发。大M法直接修改原目标 $\min c^\prime x+M\sum\limits_i u_i$，$M\gg 1$（太小压不下去，但太大数值不稳定）。
Bland Rule：如果某个顶点退化 $\exists i\in B,\ x_i = 0$，pivot 后目标值将不变（出入 $0$）。取 $\min j \text{ s.t. }\bar{c}_j>0$ 入基，达到 $\min\limits_i \frac{(B^{-1}b)_i}{(B^{-1}a_j)_i}$ 的多个 $i$ 中最小的出基，可以避免循环（有限步停）。
Tableau：
Interior-Point Method：从可行域中间直接前往最优点而不是沿边走（Klee–Minty example 单纯形法需遍历全部顶点即指数复杂度）。
将负梯度 $-c$ 向 $A$ 的零空间投影得到搜索方向 $d_k = -Pc = -(I-A^\prime (AA^\prime )A)^{-1}c$（由此立刻写出最优性条件 $d_k = 0$ 和无界条件 $d_k > 0$，note $c^\prime x_{k+1}=c^\prime x_k-\alpha_k|d_k|^2$ 即充分下降）。同时步长 $\alpha$ 的上限由 $x_{k+1}\ge 0$ 控制，$\alpha_k = \gamma \min\limits_i\{\frac{(x_k)_i}{-(d_k)_i}|(d_k)_i<0\},\ \gamma\in(0,1)$，这里收缩一个因子是因为在靠近边界的地方搜索效率很低（或障碍 $\log x$ 爆炸），保持严格内点。
可以想到使用线性变换 $x=Xy$ 在每步中将迭代点映至较好的内部如 $e=(1,\dots,1)^\prime ,\ X=\text{diag}(x)$，再对 $y$ 移动，写为 $x$ 的式子则为 $d_k = -(I-X_kA^\prime (AX_k^2A^\prime )AX_k)^{-1}X_kc,\ x_{k+1}= x_k + \alpha_kX_kd_k$。算法终止条件为 feasible $d_k\le 0$ 且 $-e^\prime d_k\le \epsilon$ 足够小，即 $d_k \approx 0$ 最优解。
初始点（影响性能）获取上类似于单纯形法，现代求解器有更成熟的方式。
从 Primal-Dual 内点法来推导，框架为凸优化 $\min\limits_x f(x) \text{ s.t. } Ax=b,\ x\in \mathcal{K}$，构造障碍函数 $\phi(x)$ 如 LP 问题中为 $-\sum\limits_i \log x_i$，改为等式约束下最小化 $f+\mu \phi$，中心参数 $\mu$ 有 $x(\mu)\rightarrow x^*,\ \mu \downarrow 0$。这相当于将原问题 KKT 中的 complementary slackness 光滑化 $x_is_i=\mu$，即现 KKT 系统为（$w$ 为对偶问题解） $$ \left\{ \begin{aligned} & Ax = b \\ & A^\prime w + s = -\nabla f(x) = c \\ & x_i s_i = \mu \\ & x>0,\ s>0 \end{aligned}\right. $$ 采用 Newton 步 $\left[\begin{array}{ccc}0 & A & 0 \\ A^T & 0 & I \\ S & 0 & X\end{array}\right]\left[\begin{array}{l}\Delta w \\ \Delta x \\ \Delta s\end{array}\right]=\left[\begin{array}{c}0 \\ 0 \\ \mu e-X S e\end{array}\right]$ 并令 $\mu = 0$ 得到 $\Delta w=\left(A X^2 A^T\right)^{-1} A X^2 c$，$\Delta x=-\left[I-X A^T\left(A X^2 A^T\right)^{-1} A X\right] X c$ 同上面的搜索方向。且 $\mu = \frac{1}{n}e^\prime X_k(c-A^\prime w_k) = \frac{1}{n}e^\prime d_k$，终止条件即 $\mu \le n\epsilon$。
3 Krylov#
一类逐步扩张子空间从而用其中的近似解逼近最优解的方法，适应大型稀疏矩阵问题（矩阵-向量乘积多）。Krylov subspace $\mathcal{K}_n(A,r_0)\triangleq \text{span}\{r_0,Ar_0,\dots,A^{n-1}r_0\}$。近似解可以残差最小化或残差正交化来寻找（对于 CG 两者同一）。
Conjugated Gradient：
除此之外对于 $Ax=b$ 问题，若为对称不定可用 MINRES，非对称可用 GMRES、QMR 等。$Ax=\lambda x$ 问题则可维护 Krylov 子空间中的一组正交基，在其上投影以构建一个小的相似矩阵 $VAV^\prime $ 并求出其特征值和向量（Ritz pair）作为近似。
Arnoldi：
4 FFT#
5 QR#
Schur 定理知 适应稠密矩阵的特征值和向量求解
6 Quick Sort#
7 FMM#
8 Kalman#
9 Vertibi#
作为动态规划的一个代表且广泛应用。
10 RSA#
11 LLL#
12 Quasi Newton#
13 Annealing#
14 SVD#
Golub-Kahan