期末速成：最优化方法考点总览

Views: --
#速成

这篇不是把整门课再抄一遍，而是把考场上真正需要调动的知识压成一条主线：先判断问题结构，再写条件或选算法，最后检查条件是否真的成立。遇到不会的题，也尽量靠这条主线拿到过程分。

一张路线图

题型第一反应核心工具
线性规划计算化标准形、找初始基单纯形表、比值检验
LP 对偶与灵敏度统一原问题方向弱/强对偶、互补松弛、B−1B^{-1}
凸性证明先判定义域和可行域凸组合、Hessian、上图集
无约束极值先解一阶条件，再看二阶梯度、Hessian
约束极值写成统一不等式方向可行方向、Fritz John、KKT
Lagrange 对偶先写 LL，再对 xx 取下确界对偶函数、弱/强对偶
迭代算法明确方向和步长各怎么来下降方向、一维搜索、停止准则
证明收敛找下降性、紧性和闭映射极限点、Zangwill 框架

线性规划：单纯形法必须会写的骨架

把问题化为

min⁡cTx,Ax=b,x≥0.\min c^T x,\qquad Ax=b,\qquad x\ge 0.

选基矩阵 BB 后，基本解与目标函数写成

xB=B−1b−B−1NxN,x_B=B^{-1}b-B^{-1}Nx_N, z=cBTB−1b+(cNT−cBTB−1N)xN.z=c_B^TB^{-1}b+ \left(c_N^T-c_B^TB^{-1}N\right)x_N.

本课程的最小化表常用检验数

σj=zj−cj=cBTB−1Aj−cj.\sigma_j=z_j-c_j=c_B^TB^{-1}A_j-c_j.

当前基最优的判据是所有非基变量满足 σj≤0\sigma_j\le 0。若某个 σj>0\sigma_j>0，让它进基；再用正主元列做最小比值检验，决定谁出基。

考场固定步骤：

  1. 统一约束为等式并保证右端非负。
  2. 找单位阵基；找不到就用大 MM 法或两阶段法。
  3. 写清进基变量、比值和出基变量。
  4. 做行变换，直到满足最优性条件。
  5. 从基变量列读解，同时写目标值。

三个异常必须能辨认：主元列没有正元素表示无界；比值检验出现并列可能退化；人工变量最终仍为正表示原问题不可行。

LP 对偶与互补松弛

最容易记的一组是

min⁡cTxs.t.Ax≥b, x≥0⟺max⁡bTys.t.ATy≤c, y≥0.\begin{aligned} \min\quad &c^Tx\\ \text{s.t.}\quad &Ax\ge b,\ x\ge0 \end{aligned} \Longleftrightarrow \begin{aligned} \max\quad &b^Ty\\ \text{s.t.}\quad &A^Ty\le c,\ y\ge0. \end{aligned}

其他方向不要死背，先把约束乘 −1-1 化到这组形式。弱对偶给出

bTy≤cTx,b^Ty\le c^Tx,

强对偶说明双方存在有限最优解时最优值相等。互补松弛是算题最快的工具：

yi(Ax−b)i=0,xj(c−ATy)j=0.y_i(Ax-b)_i=0, \qquad x_j(c-A^Ty)_j=0.

一句话理解：一边的变量为正，另一边对应的松弛就必须为零。

灵敏度分析只围绕两件事：

B−1b≥0（原可行）,cBTB−1A−cT≤0（对偶可行）.B^{-1}b\ge0\quad\text{（原可行）}, \qquad c_B^TB^{-1}A-c^T\le0\quad\text{（对偶可行）}.

改 bb 先看第一式；改 cc 先看第二式。原可行破坏而对偶可行时用对偶单纯形；反过来用原始单纯形。

凸性：定义、判据和结论不要混

集合 CC 凸，指任意 x,y∈Cx,y\in C 和 θ∈[0,1]\theta\in[0,1] 都有

θx+(1−θ)y∈C.\theta x+(1-\theta)y\in C.

函数 ff 在凸集上凸，指

f(θx+(1−θ)y)≤θf(x)+(1−θ)f(y).f(\theta x+(1-\theta)y) \le \theta f(x)+(1-\theta)f(y).

二阶可微时，∇2f(x)⪰0\nabla^2f(x)\succeq0 可判凸，∇2f(x)≻0\nabla^2f(x)\succ0 可判严格凸。注意：严格凸保证最优解至多一个；凸函数的一阶驻点是全局最优点；但“唯一最优点”不能反推严格凸。

凸规划中，只要约束资格成立，KKT 条件通常既必要又充分；一般非凸问题里，KKT 只是一阶必要条件，不能直接宣布全局最优。

无约束最优性条件

若 x∗x^* 是可微函数的内点局部极小点，则

∇f(x∗)=0.\nabla f(x^*)=0.

在驻点处：

  • ∇2f(x∗)≻0\nabla^2f(x^*)\succ0：严格局部极小；
  • ∇2f(x∗)≺0\nabla^2f(x^*)\prec0：严格局部极大；
  • Hessian 不定：鞍点；
  • 半正定：二阶条件不给结论，要回到定义或看更高阶项。

方向 dd 是下降方向的局部判据为

∇f(x)Td<0.\nabla f(x)^Td<0.

欧氏范数下的最速下降方向是 −∇f(x)-\nabla f(x)。

约束最优性条件：统一符号后再写 KKT

采用本课程常见形式

min⁡f(x),gi(x)≥0,hj(x)=0.\min f(x),\qquad g_i(x)\ge0,\qquad h_j(x)=0.

Lagrange 函数取

L(x,μ,λ)=f(x)−∑iμigi(x)+∑jλjhj(x),μi≥0.L(x,\mu,\lambda) =f(x)-\sum_i\mu_i g_i(x)+\sum_j\lambda_jh_j(x), \qquad \mu_i\ge0.

KKT 四件套：

{∇xL(x∗,μ∗,λ∗)=0,gi(x∗)≥0, hj(x∗)=0,μi∗≥0,μi∗gi(x∗)=0.\begin{cases} \nabla_xL(x^*,\mu^*,\lambda^*)=0,\\ g_i(x^*)\ge0,\ h_j(x^*)=0,\\ \mu_i^*\ge0,\\ \mu_i^*g_i(x^*)=0. \end{cases}

答题时先列活动约束，再求乘子，最后逐项检查乘子符号与互补条件。约束资格不明时，先写 Fritz John：目标函数前还有乘子 μ0≥0\mu_0\ge0，且全部乘子不能同时为零；只有能证明 μ0>0\mu_0>0 时才能归一化成 KKT。

Lagrange 对偶

对原问题先写

q(μ,λ)=inf⁡x∈DL(x,μ,λ),q(\mu,\lambda)=\inf_{x\in D}L(x,\mu,\lambda),

再写对偶问题

max⁡μ≥0,λq(μ,λ).\max_{\mu\ge0,\lambda}q(\mu,\lambda).

qq 永远是凹函数，即使原问题不凸。对任何原可行点和对偶可行乘子，都有 q≤fq\le f；所以对偶给原最小化问题提供下界。凸问题满足 Slater 条件时通常强对偶成立。

一维搜索和主要无约束算法

统一迭代式：

x(k+1)=x(k)+αkd(k).x^{(k+1)}=x^{(k)}+\alpha_kd^{(k)}.

精确一维搜索首先解的是

αk∈arg⁡min⁡α∈Ikϕ(α),ϕ(α)=f(x(k)+αd(k)),\alpha_k\in\arg\min_{\alpha\in\mathcal I_k} \phi(\alpha), \qquad \phi(\alpha)=f(x^{(k)}+\alpha d^{(k)}),

其中 Ik\mathcal I_k 是允许的步长区间。只有当最小值由有限的区间内点 αk\alpha_k 取得，且 ϕ\phi 在该点可微时，才可用必要条件

ϕ′(αk)=0.\phi'(\alpha_k)=0.

若最优步长落在区间端点、目标沿方向无下界，或有限极小解不存在，都不能直接套导数等于零。在上述内点可微条件下，才有重要正交关系

∇f(x(k+1))Td(k)=0.\nabla f(x^{(k+1)})^Td^{(k)}=0.
方法方向关键提醒
最速下降dk=−gkd_k=-g_k稳但在狭长谷地中锯齿
Newtondk=−Hk−1gkd_k=-H_k^{-1}g_kHk≻0H_k\succ0 才保证下降
共轭梯度dk+1=−gk+1+βkdkd_{k+1}=-g_{k+1}+\beta_kd_k正定二次型至多 nn 步精确终止
DFP用割线条件更新 Hk≈∇2f−1H_k\approx\nabla^2f^{-1}要检查 skTyk>0s_k^Ty_k>0
Powell只用函数值并更新方向组适合无导数问题

DFP 逆 Hessian 更新公式：

Hk+1=Hk+skskTskTyk−HkykykTHkykTHkyk,H_{k+1}=H_k+ \frac{s_ks_k^T}{s_k^Ty_k} -\frac{H_ky_ky_k^TH_k}{y_k^TH_ky_k},

其中 sk=xk+1−xks_k=x_{k+1}-x_k，yk=gk+1−gky_k=g_{k+1}-g_k。

可行方向法

线性约束 Ax≥b,Ex=eAx\ge b, Ex=e 下，设当前活动不等式矩阵为 AIA_I。可行方向满足

AId≥0,Ed=0,A_Id\ge0,\qquad Ed=0,

下降还要求 ∇f(x)Td<0\nabla f(x)^Td<0。Zoutendijk 法把“寻找一个尽量好的可行下降方向”写成线性规划，若最优下降量为零，则到达一阶驻点。

等式约束 Ax=bAx=b 可消去基变量：

xB=B−1b−B−1NxN.x_B=B^{-1}b-B^{-1}Nx_N.

既约梯度为

rN=∇Nf−(B−1N)T∇Bf.r_N=\nabla_Nf-(B^{-1}N)^T\nabla_Bf.

取 dN=−rNd_N=-r_N，再令 dB=−B−1NdNd_B=-B^{-1}Nd_N，就自动满足 Ad=0Ad=0；若 rN≠0r_N\ne0，还有 ∇fTd=−∥rN∥2<0\nabla f^Td=-\lVert r_N\rVert^2<0。

最后十分钟检查清单

  1. 目标是 min 还是 max？不等号方向统一了吗？
  2. 单纯形表的检验数约定是哪一种？全文保持一致了吗？
  3. 候选解真的可行吗？活动约束找全了吗？
  4. KKT 乘子符号与 Lagrange 函数符号匹配吗？
  5. 二阶条件是充分、必要，还是无法判断？
  6. Newton 方向真的是下降方向吗？精确一维搜索是否存在有限最小值？
  7. 最终答案有没有写变量顺序、目标值和参数范围端点？

这门课最常见的丢分不是不会算，而是套对了公式却漏了前提。每写一个结论，都顺手问一句“它为什么在这道题里能用”，答案会稳很多。

评论