非线性与凸优化
线性规划的世界里，最优解一定在顶点上，算法只要沿着边走。一旦目标或约束弯了，这个保证就没了：可能有很多个局部最优，也可能只有一个但特别难走到。这一页想把"凸"这个词讲清楚——它不是一个技术细节，而是决定你能不能相信手里那个解的分水岭。
LAB 01
梯度下降轨迹
在等高线图上画出迭代轨迹，学习率太大太小都看得见
问题
机器学习训练的本质就是"沿着坡往下走"。可步子迈多大？迈小了走不到头，迈大了在山谷两壁之间来回弹。这一台把轨迹画在等高线上，让学习率的作用变成看得见的东西。
模型
梯度下降及其收敛条件。
xk+1 = xk − η ∇f(xk)； 二次型时收敛要求 η < 2/L， 最优 η = 2/(L+μ)
L 是梯度的利普希茨常数（最大曲率），μ 是强凸参数（最小曲率）。收敛速度由条件数 κ = L/μ 决定，误差按 ((κ−1)/(κ+1))k 衰减——这就是"病态问题"走之字形的数学原因。最后的 f 值—
最后的 |∇f|—
状态—
降到 10⁻⁶ 需要几步—
先别动别的，只把学习率往右推。会依次看到三种典型行为：太小时轨迹爬得很慢，还没到底就用完了步数；合适时一条平滑的曲线直奔谷底；再大一点开始来回震荡（沿着陡的那个方向反复越过谷底）；再大就直接发散。这三段的分界线不是玄学：对二次函数，梯度下降收敛的充要条件是学习率小于 2/L，L 是最大的曲率（Hessian 的最大特征值）。接着把条件数从 1 拉到 60。等高线从圆变成细长的椭圆，轨迹立刻变成锯齿形——因为负梯度方向并不指向最小点，它垂直于等高线，而细长椭圆的等高线法向严重偏离圆心方向。这就是"病态"的几何含义，也是动量、预条件、二阶方法存在的理由。想看教科书上那种斜着来回弹的锯齿，就把地形换成"旋转的病态二次"——椭圆的长轴一旦不与坐标轴对齐，负梯度偏离圆心的方向就一目了然了。再看动量。条件数 30 时，动量 0 需要 184 步才降到 10⁻⁶，动量 0.5 只要 82 步；但调到 0.9 反而回升到 88 步——动量太大自己会带来新的震荡，它不是越大越好。最后换到 Rosenbrock 香蕉谷：把步数拉满 400，普通梯度下降也只是沿着谷底慢慢蹭。这条谷的曲率比在 100:1 以上，它正是当年拟牛顿方法被造出来要对付的例子。
LAB 02
凸与非凸
同一个算法在两种地形上的命运对比
问题
同一个算法，在凸地形上保证找到全局最优，在非凸地形上只能保证找到"某个"局部最优。而"我的问题是不是凸的"这件事，决定了你该期待什么样的保证。
模型
凸性的定义与它带来的保证。
f 凸 ⟺ f(λx + (1−λ)y) ≤ λf(x) + (1−λ)f(y) ∀λ∈[0,1]
二阶判据：∇²f ⪰ 0（半正定）
凸问题的局部最优就是全局最优，而且有可验证的最优性证书（KKT）。非凸问题没有这个保证——深度学习之所以还能用，靠的是高维里鞍点远多于坏的局部极小这一经验事实，不是定理。二阶判据：∇²f ⪰ 0（半正定）
一共收敛到几个不同的点—
有几条轨迹落到全局最优—
最好的终点值—
最差的终点值—
凸函数上，所有起点最后都走到同一个地方——这就是凸的全部好处。换成 Himmelblau：四个谷一样深，都是全局最优，但从哪个起点会掉进哪一个谷，画出来是一张边界极其破碎的图，这些区域叫吸引域。再换成 Rastrigin：几乎每个起点都卡在自己旁边那个小坑里，落到全局最优的比例通常只有百分之几。这时候"我跑了梯度下降，收敛了"这句话完全不能说明解是好的。非凸问题的正确做法不是相信一次运行，而是承认随机性：多起点重启、模拟退火、群体算法，本质上都是在花计算量买"跳出当前吸引域"的机会。把起点网格从 3 拉到 14，看那个读数：命中全局最优的轨迹从 1 条涨到 4 条，而比例反而从 11% 掉到 2%。这说明多起点买到的是"至少有一条命中"的机会，单位算力的命中率并没有提高。二维里撒 196 个点还能撞上；维度一高，要把空间盖住所需的点数按指数增长，多起点很快就不够用了。
LAB 03
拉格朗日乘子
约束曲线与等高线相切的那一刻，就是乘子的几何含义
问题
"在约束曲线上找最值"——最优点有一个漂亮的几何特征：目标的等高线和约束曲线在那里相切。拉格朗日乘子把这个几何观察变成了一组可以直接解的方程。
模型
拉格朗日函数与一阶条件。
L(x, λ) = f(x) − λ g(x)； ∇f = λ ∇g， g(x) = 0
∇f 与 ∇g 平行，正是"相切"的代数写法。λ 不只是辅助变量，它就是影子价格：约束 g(x) = c 里的 c 变一点，最优值的变化率恰好是 λ（包络定理）。当前点的 f—
∇f 与 ∇g 的夹角—
λ = |∇f| / |∇g|（同向为正）—
离最近的驻点还差多少度—
拖动 θ，盯住两支箭头。绝大多数位置上，∇f（目标上升最快的方向）和 ∇g（约束的法向）是斜着的；只要它们不平行，就说明沿着约束曲线还能再走一点让 f 变大或变小。只有当两支箭头共线（夹角 0° 或 180°）时，沿曲线的移动才不再改变 f——那就是约束极值点，也正是 ∇f = λ∇g 这个式子的全部含义。换句话说，拉格朗日乘子法不是一个技巧，它就是"目标等高线与约束曲线相切"的代数写法。而 λ 的大小同样有意义：它是把约束放松一点点时目标值的变化率，和线性规划里的影子价格是同一个东西。把 f 换成 x·y 再拖一圈：这次会看到四个驻点，两个极大两个极小——拉格朗日条件只给驻点，不区分极大极小，也不排除鞍点。
LAB 04
KKT 条件
带不等式约束时，哪些约束「起作用」
问题
不等式约束比等式约束麻烦：有的约束在最优点上"顶住了"，有的则完全没起作用。事先并不知道是哪些。KKT 条件用一个巧妙的互补关系把这两种情况统一处理。
模型
KKT 条件（凸问题下是充要的）。
∇f = Σi λi ∇gi + Σj νj ∇hj； gi(x) ≤ 0， λi ≥ 0， λi gi(x) = 0
最后一条是互补松弛：要么约束顶住了（gi = 0），要么它的乘子是 0（没起作用）。这正好对应线性规划里"闲置资源影子价格为零"。凸问题满足 Slater 条件时 KKT 充分必要。最优点—
起作用的约束—
乘子 μ₁ / μ₂ / μ₃ / μ₄—
互补松弛 μᵢ·gᵢ = 0 的检验—
把目标中心拖回可行域内部，所有乘子立刻全变成 0。这就是互补松弛：约束没顶住你，它对应的乘子就必须是 0；乘子不为 0，就说明那条约束正卡着你，而且卡得越狠乘子越大。这一条把不等式约束的"有和没有"变成了可以计算的等式，也是 KKT 条件里最容易被当成公式背下来、其实最直观的一条。默认位置 (3.2, 2.8) 上①②同时起作用，最优点卡在顶点 (1.667, 1.333)，乘子是 2.98 和 0.04；把中心拖到 (5, 5)，②就松开了，只剩①，最优点滑回边上的 (1.5, 1.5)，乘子变成 7 和 0。顶点那一刻，−∇f 正好落在两条约束法向张成的锥里——图上那两支虚线箭头围成的区域就是这个锥。注意 μ₂ = 0.04 这种"几乎为零"的情形：它说明中心再挪一点点，②就会从起作用变成不起作用，这类退化点是数值求解器最容易出问题的地方。KKT 是必要条件；只有问题是凸的时候它才同时是充分条件。这里目标是二次的、约束是线性的，属于凸问题，所以解出来的就是真最优。
这一页想说的
这一页只讲了一件事：凸性决定了你手里那个"收敛了"的解值不值得相信。问题是凸的，局部最优就是全局最优，KKT 条件既必要又充分，算法跑完你可以直接汇报结论；问题非凸，你汇报的就只能是"在这些起点下找到的最好解"，并且应该同时报出你试了多少个起点。建模时值得花时间做的一件事，是想办法把问题写成凸的——换变量、放松、取对数、改用凸的代理目标，这些改写带来的收益通常远大于换一个更强的求解器。