特征值如何塑造椭圆?
转动特征方向、拉大特征值比,再拖动点 x。观察等高线、梯度方向与函数值。
为可拖动的点; 是旋转矩阵。图中主椭圆满足 ,虚线为特征方向。
梯度箭头只表示方向,长度已缩放。主椭圆为 f(x)=1/2。
想一想沿哪一个特征方向移动相同距离,函数值变化更大?
MATH6015 · 交互例子
原有实验与参数链接保留在这里。
课程章节与教材顺序不同。以下索引连接主要模型及其教学特例;各例卡注明原始出处、变量维数和适用条件。
把向量、矩阵与微积分,连接到优化问题的语言。
转动特征方向、拉大特征值比,再拖动点 x。观察等高线、梯度方向与函数值。
为可拖动的点; 是旋转矩阵。图中主椭圆满足 ,虚线为特征方向。
梯度箭头只表示方向,长度已缩放。主椭圆为 f(x)=1/2。
想一想沿哪一个特征方向移动相同距离,函数值变化更大?
改变 p,观察单位球从菱形变为圆,再逐渐接近正方形。拖动点 x,比较它是否落在单位球内。
为可拖动的点;单位球为 。选择 时使用第二个公式。
灰色圆是欧氏单位圆,作为固定参照;p=∞ 时为正方形。
想一想同一个向量,为什么在不同范数下会有不同长度?
拖动向量 a、b,分解 b 在 a 上的投影和垂直余量。
是可拖动的向量, 是 到 的正交投影。
绿色分量与橙色余量正交。a=0 时投影到零子空间,但夹角不定义。
想一想Cauchy–Schwarz 不等式何时取等号?零向量的夹角应如何处理?
改变展开点与位移,比较指数函数、切线和二次近似。
原函数 , 为展开点,试探点为 。两条模型都使用同一展开点的导数。
误差比较针对当前位移;Taylor 的局部精度不保证远处模型同样准确。
想一想位移缩小时,两个近似的误差按什么数量级下降?
调整对角元与耦合项,观察等高线和最小特征值跨过零。
,控制项是 与 。此判据利用 ;一般矩阵还需完整的半正定条件。
两个特征值都为正:原点是唯一全局极小点。
想一想半正定为什么不保证唯一极小点?
调节缩放和剪切,沿单位圆移动输入点,观察输出椭圆。
是缩放, 是剪切;输入 在单位圆上,输出为 。
灰色单位圆经 A 映射为紫色椭圆;半轴来自 AAᵀ 的特征值平方根。
想一想椭圆半轴为什么对应奇异值,而不是一般矩阵的特征值?
拖动线性目标向量 z,切换范数球并改变半径,寻找最优接触点。
拖动的是目标向量 ,优化变量为球内的 。 的对偶分别为 。
优化变量是范数球内的 x,拖动的是目标向量 z。z=0 时全部球内点都最优;平直边上也可能出现多解。
想一想为什么 ℓ₁ 与 ℓ∞ 互为对偶,而欧氏范数自对偶?
识别凸集、凸函数与凸优化模型,理解局部与全局的联系。
拖动 A、B,或者切换为带缺口的集合。改变 t,追踪线段上的点 z(t)。
、 是两个可拖动端点, 是凸组合。只有两端点都在集合内时,这次检验才有效。
当前采样点均在集合内;有限次试验不能证明任意集合全局凸。
想一想发现一条越出集合的线段足以否定凸性;检查一条线段能否证明凸性?
改变两个端点和混合比例,比较“先混合再求值”与“先求值再混合”。
这是凸函数应满足的不等式,。图中显示的差值为右侧减左侧;单组端点不代表全局结论。
蓝色为函数,橙色为弦;差值的正负只反映当前端点和比例。
想一想换成 log(x) 或双阱函数后,弦与图像的关系怎样改变?
拖动 (x,t) 检查上图成员关系;切换到 log-sum-exp 并调节温度。
可选择 或 ,其中 。平滑最大值满足 。
上图包含曲线及其上方。log-sum-exp 对 |x| 的逼近误差介于 0 与 τ log 2 之间。
想一想温度趋于零时,平滑函数与 |x| 的距离怎样变化?
拖动 (x,t),观察透视函数的次水平集 x²≤ct。
这里 和 都是标量, 是图中的可拖动点。它是 的透视函数。
紫色区域是次水平集在图框中的部分;t 保持严格为正。
想一想固定 t 的截面与固定 x 的截面分别是什么曲线?
调节支撑线斜率 y 和试探点 x,查看 Fenchel–Young 间隙。
二次情形 给出 ;指数情形在 给出 。橙线为 。
橙线为斜率 y 的最紧仿射下界。指数函数此处只选 y>0;y<0 时共轭为 +∞。
想一想为什么最优接触点满足 f′(x)=y?指数函数的共轭定义域是什么?
旋转目标方向并移动切割约束,观察线性目标的接触面。
多边形模式取 , 为图示固定多边形;正交象限模式取 。
最优顶点并列时,连接它们的边也最优;把切割右端降到 −3 以下可构造不可行问题。
想一想什么方向会使整条边都是最优解?
拖动无约束极小点 c,改变曲率比,观察三角形上的二次规划解。
是优化变量, 是可拖动的无约束极小点,。
检查内部驻点及每条边上的一维极小点,得到精确的二维 QP 解。
想一想活动约束变化时,解路径是否一定光滑?
调节正系数和乘积要求,对比原变量与对数变量中的同一个问题。
所有系数 ,、。精确解为 、。
正变量经对数变换后,乘法约束变为半空间;目标变为凸的 log-sum-exp。
想一想取对数为何需要严格正变量?
固定一个相关系数,优化另外两个的线性组合;可行集来自相关矩阵半正定约束。
是固定相关系数,。优化变量为 、,可行条件等价于 。
固定 |ρ₁₂|<1 后,可行集是椭圆;边界对应奇异但仍半正定的 3×3 相关矩阵。
想一想相关系数各自落在 [−1,1],足以保证矩阵半正定吗?
改变相关性和收益下界,观察两资产组合的风险–收益曲线与可行性。
两资产的抽象均值为 ,标准差为 ,相关系数由滑块指定; 是权重。
两资产抽象模型:均值 (1,1.8),标准差 (1,0.6),权重非负且和为 1;紫线包括全部允许的组合。
想一想为什么收益要求超过所有资产均值时,非负组合会不可行?
从最小二乘出发,比较误差度量与正则化的建模作用。
移动一个观测值,同时比较最小二乘、绝对值损失与 Huber 损失的最优拟合。
优化变量是直线斜率 和截距 ; 是观测。Huber 使用教材损失的 倍等比例参数化,极小点不变。
所有直线都重新求解;Huber 使用 IRLS,当前梯度残差 2.87e-12。
想一想异常点不断增大时,哪条直线最敏感?Huber 阈值控制了什么?
在一个病态的线性模型中,调整观测噪声和正则化强度。轨迹展示 λ 变化时的正则化解。
,真值为 ,观测 。;彩色点为当前解,星号为真值。
曲线是 λ 从 10⁻⁵ 到 10 的解路径;正则化引入偏差,不能保证每个 λ 都更接近真值。
想一想λ 增大为何压缩解的范数?压缩后的解一定更接近真值吗?
拖动未正则化的解,改变特征相关性和 λ,观察折线状稀疏解路径。
, 是未正则化解。此正定二次损失可写成平方最小二乘形式,对应教材稀疏描述模型的二维特例。
路径覆盖 λ∈[0,3]。使用收敛的坐标下降求解相关特征问题,不把一次软阈值误当成最优解。
想一想相关特征出现时,简单地逐坐标软阈值为何不再给出完整解?
移动一个异常观测,求解最小最大绝对残差的拟合直线和误差带。
是观测,优化变量为斜率 、截距 和最大残差 。红点表示达到最大绝对残差的活动观测。
将 L∞ 拟合写成 3 变量 LP,枚举基本可行解;误差带包含全部观测。
想一想最优解处为什么常出现多个同样大的正负残差?
调节测量系数和观测,比较最小 ℓ₁ 解与最小 ℓ₂ 解的几何接触。
同一欠定方程的两种最小范数解。 且 时, 最优解不唯一。
蓝线是欠定测量方程。并列时仅标出一个 ℓ₁ 最优端点,不能推断所有最优解都同样稀疏。
想一想两个测量系数绝对值相等时,ℓ₁ 解为什么可能不唯一?
调节噪声和 TV 强度,观察分段常数信号的恢复;同时显示求解的原始–对偶间隙。
是待恢复的整段信号, 是带噪观测,。这是高维信号以一维曲线显示的教材模型,不把它称为二维优化问题。
采用盒约束对偶问题的投影梯度法求解,显式报告对偶间隙。
想一想TV 为什么倾向于产生平台,而不是光滑波浪?
改变二阶差分惩罚和噪声,比较数据、平滑估计与生成信号。
, 是二阶差分。
解 (I+λD₂ᵀD₂)x=y;二阶差分的零空间是离散仿射信号。
想一想惩罚趋大时,为什么估计更接近直线,而不一定趋近零?
在相同病态模型上,比较忽略矩阵误差、随机误差平均和 Frobenius 球最坏误差。
,。随机模型假设矩阵元素的误差独立且方差为 ;最坏模型假设 。
随机模型假设 ΔA 各元素独立、零均值、方差 σ²;最坏模型假设 ‖ΔA‖F≤ρ,二者不能把参数直接等同。
想一想随机方差与最坏扰动半径是同一个假设吗?
选择下降方向与步长,比较梯度法、线搜索和 Newton 法。
教材式 (9.20)。拖动共同初始点,对比梯度、二次范数最速下降和 Newton;轨迹与误差同步播放,也可以展开一次线搜索。
所有方法优化同一个原函数,并共享可拖动的 。回溯接受条件为 ,失败则 ;教材默认 。精确线搜索在整个 上数值求解。
实心小圆为实际迭代点,线段为两次迭代之间的步。误差用稳定恒等式计算;≤10⁻³⁰ 画在底线。精确搜索为正射线上的数值求根,内层计算也计数。二次范数球为 dᵀPd≤1(Newton 用当前 Hessian),ℓ₁ 球为 ‖d‖₁≤1;方向箭头另行缩放。
| 方法 | 实际 k | f(xᵏ) − p* | ‖∇f(xᵏ)‖₂ | 到达本点的 t | f / ∇f / H 调用 | 状态 |
|---|---|---|---|---|---|---|
| 梯度 · 回溯 | 50 | 6.63e-20 | 9.33e-10 | 0.11765 | 319 / 51 / 0 | 达到梯度阈值 |
| 梯度 · 精确搜索 | 20 | 3.94e-20 | 8.88e-10 | 0.33959 | 21 / 961 / 0 | 达到梯度阈值 |
| 最速下降 · P₁ | 28 | 3.06e-20 | 8.40e-10 | 1 | 32 / 29 / 0 | 达到梯度阈值 |
| 最速下降 · P₂ | 80 | 6.63e-9 | 2.16e-4 | 0.343 | 319 / 81 / 0 | 达到 80 步上限 |
| Newton · 回溯 | 6 | 1.56e-23 | 1.51e-11 | 1 | 7 / 7 / 6 | 达到梯度阈值 |
统一起点默认取 (−1, 1),用于同场比较;教材没有明示所有图的数值起点。P₁=diag(2,8),P₂=diag(8,2)。调用数是算法轨迹截至当前步的请求次数,三类请求代价不同,不代表运行时间。
梯度方向 d=−g;二次范数方向 d=−P⁻¹g;Newton 方向 d=−H⁻¹g;ℓ₁ 最速下降只更新 |gᵢ| 最大的坐标。所有回溯均使用真实方向导数 gᵀd。
想一想P₁ 与 P₂ 为什么带来相反的效果?Newton 什么时候接受全步,其误差曲线又在什么时候开始加速弯折?
共享同一个多边形和起点,比较原坐标、缩放坐标下的梯度法与 Newton。切换解析中心后,可将同一组约束带入内点法实验。
是图中原坐标的迭代点; 是 的第 行。 对应式 (9.21) 的形式, 求解析中心。此处 是课程自选缩放,不复用原书式 (9.22) 的参数化。所有方法用真实方向导数做 Armijo 回溯。
式 (9.21) 的二维教学实例,原书使用 100 维数据。缩放取 x=diag(γ,1)y;四法共享实际 x₀,Newton 映回 x 后应重合。请求起点若在外部,则沿原点射线收缩到严格内部。 收敛图中 ≤10⁻¹⁴ 的值显示在底线,表格保留实际值。
| 方法 | k | 完整 x | f(x) | 梯度范数 | 原始残差 | 最小松弛 | 到达步长 | 试探数 | 状态 |
|---|---|---|---|---|---|---|---|---|---|
| 梯度法 | 45 | -1.0029, -0.32786 | -3.61937 | 7.40e-9 | 0 | 0.9971 | 1 | 45 | 已收敛 |
| 缩放坐标梯度法 | 100 | -1.0029, -0.32786 | -3.61937 | 5.59e-7 | 0 | 0.9971 | 0.0625 | 486 | 达到迭代上限 |
| Newton | 5 | -1.0029, -0.32786 | -3.61937 | 2.50e-13 | 0 | 0.9971 | 1 | 5 | 已收敛 |
| 缩放坐标 Newton | 5 | -1.0029, -0.32786 | -3.61937 | 2.50e-13 | 0 | 0.9971 | 1 | 5 | 已收敛 |
当前进度已结束时,显示最后一次实际更新。
| 步长 | 在定义域内 | 试探目标值 | 线搜索残差 | 判定 |
|---|---|---|---|---|
| 1 | 是 | -3.61937 | — | 接受 |
六个法向量依次为 (1,0)、(0,1)、(−1,0)、(0,−1)、(0.8,0.6)、(−0.6,0.8)。
b = (2, 1.5, 2, 1.5, 1.45, 1.6);c = (0.819, -0.574);实际内部起点 = (0.7, -0.6)。
想一想把 x₁ 的尺度放大后,哪两条映回 x 空间的轨迹仍然重合?靠近边界时,为什么试探步会被拒绝?
固定一个正定二次型,比较固定步长梯度下降、精确线搜索与 Newton 的迭代。
是迭代点; 的特征值为 与 。固定 GD 使用 ;Newton 使用完整 Hessian 和全步。
视窗由各方法的完整有限轨迹共同确定,不随当前迭代步跳动;发散/溢出的后续点不会投影回图框。
想一想为什么梯度法可能走锯齿,而全步 Newton 在这个问题上只需一步?
从负的初始点出发,对比全步 Newton 和带 Armijo 回溯的 Newton。拖动迭代步查看两个当前位置。
这里 ,唯一极小点为 。全步取 ,阻尼步由 Armijo 回溯选择。曲线显示相对目标差的 ;此函数没有全局有界 Hessian。
目标值最小为 0;≤10⁻¹⁶ 的相对目标差画在底线。起点为 0 时已经最优。
想一想局部二次模型准确,是否意味着远离解时也能放心取全步?
改变起点和回溯参数,直接比较一维搜索曲线与充分下降直线。
,、。绘制左侧的实际函数值与右侧的充分下降界。
从 t=1 开始乘 β,直到蓝色目标值不高于橙色充分下降界;图框可能截去过大的候选目标。
想一想“下降了”与“满足充分下降”有什么区别?
在相同二次型上,用 ℓ₂、ℓ₁ 和 ℓ∞ 范数选择方向,再做精确线搜索。
。方向的正比例缩放不影响精确线搜索后的点;并列最大梯度分量时, 方向选其中一个。
三种方向均配精确线搜索;不同范数定义不同的单位步长集合。
想一想为什么 ℓ₁ 最速下降每次只更新一个坐标?
改变条件数,逐步观察共轭方向与最优点,同时检查方向的 Q-正交性。
、,目标为 。二维有限步结论针对精确算术下的线性 CG;此方法来自课程补充。
仅对 SPD 二次型使用线性 CG;精确算术中至多二维两步结束。Q-共轭内积:-2.87e-10
想一想线性 CG 的有限步结论为什么不能直接套到一般非线性目标?
改变正起点,比较原函数、二次模型、全步和保守阻尼步。
,,,。减量给出局部模型信息,不能直接当作实际目标差。
f(x)=x−log x−1,x>0;全步可越出定义域,t=1/(1+λ) 则保留严格可行性。
想一想当全步离开定义域时,1/(1+λ) 阻尼能做什么?
比较原坐标 GD 和对角预条件 GD;二者都解同一个二次问题。
原 Hessian 为 。预条件后使用 ;原坐标 GD 使用 。
原 Hessian 条件数 159,缩放后 5.67;图中迭代始终用原变量表示。
想一想为什么改变算法使用的度量不等于改变最优解?
Newton 法为什么在二次型上一步到解,在非线性问题上却可能需要阻尼?
打开本章完整讲义 ↗连接等式约束、对偶下界、敏感性与互补松弛。
三变量、一条资源约束。左图是 (x₁,x₂) 投影;表格保留完整三维点。三种方法分别满足各自的起点要求,最终寻找同一个解。
图中显示 投影, 在表格中完整显示; 表示逐分量倒数。对偶问题为最大化 ,要求 。可行起点方法将请求点按比例缩放到 。
三变量教学实例。投影位于三角形内,不代表完整点满足 Ax=b;请结合原始残差与 x₃ 判断。三法使用各自合法的起点,不声称同一初始点。视窗包含所选方法的完整轨迹;切换方法开关可聚焦比较。 收敛图中 ≤10⁻¹⁴ 的值显示在底线,表格保留实际值。
| 方法 | k | 完整 x | f(x) | KKT 残差 | 原始残差 | 对偶残差 | 到达步长 | 试探数 | 状态 |
|---|---|---|---|---|---|---|---|---|---|
| 可行起点 Newton | 5 | 1, 0.83333, 0.71429 | 0.518794 | 1.61e-10 | 0 | 1.61e-10 | 1 | 5 | 已收敛 |
| 不可行起点 Newton | 5 | 1, 0.83333, 0.71429 | 0.518794 | 6.93e-10 | 4.44e-16 | 6.93e-10 | 1 | 5 | 已收敛 |
| 对偶 Newton | 5 | 1, 0.83333, 0.71429 | 0.518794 | 5.53e-13 | 5.53e-13 | 0 | 1 | 5 | 已收敛 |
当前进度已结束时,显示最后一次实际更新。
| 步长 | 在定义域内 | 试探目标值 | 线搜索残差 | 判定 |
|---|---|---|---|---|
| 1 | 是 | 0.518794 | 1.61e-10 | 接受 |
变量为三个正分量 x=(x₁,x₂,x₃),A=(1,ω,1.4)。可行方法将请求起点按比例缩放到 Ax=b;不可行方法保留请求起点。 对偶方法从指定乘子出发,恢复的 x 中途不必满足 Ax=b。
可行 Newton 对原始目标做 Armijo 回溯;不可行 Newton 对 KKT 残差做回溯;对偶 Newton 对负对偶函数做 Armijo 回溯。对偶下界为 −q(ν);只有原始点可行时,f(x)+q(ν) 才作为原始–对偶间隙;显示时以原始残差小于 10⁻⁹ 判为数值可行,舍入造成的负零截为 0。
想一想一次全 Newton 步如何消除等式残差?对偶 Newton 恢复的 x 在迭代中一定可行吗?
拖动点 c,旋转或平移约束直线。观察最优点、垂线与拉格朗日乘子的变化。
是单位法向量, 是可拖动点。乘子 ;最优值对 的导数为 。
圆心为 c;最小的接触圆在约束直线处相切。
想一想约束右端 b 微小变化时,最优目标值怎样变化?
改变起点或约束右端,逐步观察位置、等式残差与对偶残差。回溯以 KKT 残差范数为依据。
;对偶残差为 ,原始残差为 。最优解为 。
曲线使用残差回溯;全步可一次消除仿射等式残差,阻尼步则未必。
想一想为什么阻尼步可能仍不满足等式?何时会落到可行直线上?
旋转等式约束并改变曲率,比较可行参数 z 与原空间里的点。
,,所以 。,。
x=b a+zN,a 与 N 是单位正交向量;任意 z 都满足等式约束。
想一想降维后的 Hessian 为什么是 NᵀHN?
调节约束右端和非负乘子,观察凹的对偶函数、最优值与对偶间隙。
对偶问题为 。原始解 ,最优乘子 。
q(λ)=λb−λ²/4,λ≥0。原问题严格可行,强对偶成立;b≤0 时最优乘子为零。
想一想非最优乘子能给出有效下界吗?什么时候间隙为零?
移动上界 b,比较最优值曲线、切线和乘子;观察约束从活动变为非活动。
是约束上界, 是无约束最优点。此特例值函数可微;一般问题在不可微处应讨论支撑线或次梯度。
p*(b)=½ max(c−b,0)²,切线斜率等于 −λ*;b≥c 后约束非活动。
想一想为什么乘子为零时,小幅放宽约束不再降低最优值?
改变总预算与一个通道的噪声底,观察公共水位、零分配通道和乘子。
表示噪声底, 是分配功率, 为公共水位。总功率 将教材的单位预算作参数化。
xᵢ=max(0,水位−aᵢ),满足非负约束与总预算;高于水位的通道分配为零。
想一想为什么劣质通道可能完全不获得功率?
移动两个弹簧的自然位置并调整刚度;约束禁止两个滑块的次序交换。
两自然位置为 ,两刚度为 。驻点条件为 、,乘子解释为接触力。
约束 x₁≤x₂;上下错开仅为绘图。非接触时 λ=0,接触时间隙 x₂−x₁=0,并满足弹力平衡。
想一想为什么没有接触时力为零,而有接触力时位置间隙必须为零?
用障碍函数处理不等式约束,沿中心路径接近最优解。
与“对数障碍”共用六个半空间。旋转目标方向、移动斜边或拖动起点,比较两种方法的实际步、目标差、互补量和对偶残差。
障碍法逐步增大 ;原始–对偶法每步取 ,在该次线搜索中固定 ,并保持 。本例 。 在对偶可行时才是真实间隙;图中的实际目标差由多边形顶点求得的 独立计算。
二维 LP 教学实例,不冒充原书 50 维基准。灰虚线为数值中心路径。两法都从同一严格内部点开始;sᵀλ 只有在对偶可行时才等于原始–对偶间隙。障碍法的外层参数不计作额外 Newton 步。目标平行于边时,最优解可能不唯一,绿色边段表示最优面。 收敛图中 ≤10⁻¹⁴ 的值显示在底线,表格保留实际值。
| 方法 | k | 完整 x | f(x) | KKT 残差 | 原始残差 | 对偶残差 | 互补量 | 障碍外层 / t | 到达步长 | 试探数 | 状态 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 障碍法 | 49 | -2, 0.5 | -1.92509 | 2.45e-7 | 0 | 9.56e-9 | 6.00e-7 | 8 / 1.00e+7 | 1 | 90 | 已收敛 |
| 原始–对偶内点法 | 11 | -2, 0.5 | -1.92509 | 5.23e-8 | 0 | 4.25e-14 | 1.28e-7 | — | 0.99 | 14 | 已收敛 |
当前进度已结束时,显示最后一次实际更新。该步障碍参数 t=1.00e+7。
| 步长 | 在定义域内 | 试探目标值 | 线搜索残差 | 判定 |
|---|---|---|---|---|
| 1 | 是 | -1.93e+7 | — | 接受 |
六个法向量依次为 (1,0)、(0,1)、(−1,0)、(0,−1)、(0.8,0.6)、(−0.6,0.8)。
b = (2, 1.5, 2, 1.5, 1.45, 1.6);c = (0.819, -0.574);实际内部起点 = (0.7, -0.6)。
想一想障碍法的外层参数更新为什么带来阶段变化?互补量很小时,是否还需要检查对偶可行性?
改变障碍参数 t,观察内部点沿中心路径移动;旋转目标方向,看看最优顶点如何切换。
定义域为 、、;。,三个不等式给出中心点的目标差上界 。
紫线为 t∈[0.1,1000] 的中心路径;当前点始终严格位于三角形内部。
想一想为什么 t 越大,中心点越接近边界?3/t 在这里衡量什么?
改变原问题右端 b,再压低公共松弛 s。观察放松后的三角形何时缩成一点、何时消失。
原约束为 、、。此特例 ; 时只有可行点 ,没有严格内部。
灰线表示原约束;紫线表示公共松弛后的约束。s
想一想s*<0、s*=0 与 s*>0,分别说明原问题什么性质?
在区间约束内调节线性目标和障碍权重,拖动试探点读取目标值。
是标量优化变量, 是线性目标系数,。目标在两个端点都趋向 。
端点的目标为 +∞,不画成有限数值;增加 t 相当于减弱原目标中的障碍系数 1/t。
想一想障碍为何把极小点留在严格内部?
调整 μ 和目标中心 a,在 x–λ 平面追踪驻点直线与双曲线的交点。
控制互补扰动。严格可行的原变量和对偶变量满足 。
紫线为 xλ=μ,蓝线为驻点条件 x−a−λ=0;这里的原始–对偶间隙精确等于 μ。
想一想μ→0 时,是 x 还是 λ 走向零?
移动多面体的一条边,比较对数障碍解析中心和 Chebyshev 中心。
,约束为图中矩形的四条边及一条可移动切割直线。对比的 Chebyshev 中心优化最小边界距离,而非松弛量乘积。
解析中心最大化所有松弛量的乘积;其位置依赖不等式表示,不能等同于最大内切圆圆心。
想一想同一集合的冗余不等式会不会改变解析中心?
增大不确定半径,观察鲁棒可行域收缩;显示当前最坏系数对应的支撑线。
,,。此二阶锥模型来自教材鲁棒 LP;图中采用低维边界求解,未声称运行通用 SOCP 求解器。
灰色三角形为名义可行域;紫色满足 aᵀx+σ‖x‖₂≤2,红线由最坏扰动 a+σx/‖x‖₂ 产生。
想一想欧氏球不确定性为什么产生一个二阶锥约束?
从严格正的松弛和乘子出发,逐步解 Newton 系统;可选原变量可行或不可行的初始点。
目标为 ,约束 、,并引入松弛 与乘子 。每步最多走到边界距离的 。
联立驻点、Ax+s=b 和扰动互补方程;步长同时保持 s、λ 严格为正。原变量尚不可行时,替代间隙不能冒充有效原始–对偶目标界。
想一想为什么只看目标值下降不足以判定内点迭代成功?
障碍子问题需要解得多精确?为什么不直接把障碍参数推到极限?
打开本章完整讲义 ↗把估计、检测与实验设计写成优化问题。
取值为 −1、0、1 的三点分布,已知均值 μ。改变均值约束,观察概率分量、可行集和三种 Newton 方法;对应习题 10.15 的小规模教学实例。
对应随机变量取值 的概率。第一条约束归一化,第二条指定均值;使用自然对数。对偶 Newton 最小化 ,其恢复点 在中途不必满足归一化或均值约束。只有原始可行时才将 解释为间隙。
三点分布是习题 10.15 的小规模教学实例。彩色轨迹使用 (p₁,p₃) 投影;投影落在三角形内不代表完整点已经满足概率约束。视窗包含所选方法的完整轨迹;切换方法开关可聚焦比较。 收敛图中 ≤10⁻¹⁴ 的值显示在底线,表格保留实际值。
| 方法 | k | 完整 p | f(x) | KKT 残差 | 原始残差 | 对偶残差 | 到达步长 | 试探数 | 状态 |
|---|---|---|---|---|---|---|---|---|---|
| 可行起点 Newton | 3 | 0.21624, 0.31752, 0.46624 | -1.05117 | 8.28e-15 | 0 | 8.28e-15 | 1 | 3 | 已收敛 |
| 不可行起点 Newton | 3 | 0.21624, 0.31752, 0.46624 | -1.05117 | 6.37e-15 | 0 | 6.37e-15 | 1 | 3 | 已收敛 |
| 对偶 Newton | 4 | 0.21624, 0.31752, 0.46624 | -1.05117 | 1.04e-11 | 1.04e-11 | 0 | 1 | 4 | 已收敛 |
当前进度已结束时,显示最后一次实际更新。
| 步长 | 在定义域内 | 试探目标值 | 线搜索残差 | 判定 |
|---|---|---|---|---|
| 1 | 是 | -1.05117 | 8.28e-15 | 接受 |
变量为三个正分量 p=(p₁,p₂,p₃)。可行时其和为 1,且 p₃−p₁=μ。请求点先确保分量为正;可行方法再保持 p₂ 并满足均值。 对偶方法从指定乘子出发,恢复的 x 中途不必满足 Ax=b。
可行 Newton 对原始目标做 Armijo 回溯;不可行 Newton 对 KKT 残差做回溯;对偶 Newton 对负对偶函数做 Armijo 回溯。对偶下界为 −q(ν);只有原始点可行时,f(x)+q(ν) 才作为原始–对偶间隙;显示时以原始残差小于 10⁻⁹ 判为数值可行,舍入造成的负零截为 0。
想一想均值趋近端点时,概率怎样集中?为什么对偶方法在中途恢复的正分量,尚不能直接当作概率分布?
改变样本量、成功比例与对称 Beta 先验。拖动概率 p,读取负对数似然,并比较 ML 与 MAP。
为样本数, 为按成功比例取整后的成功次数。先验为 ,;,。
不相容的边界概率给出 +∞,不画成有限值。a=1 为均匀先验;全成功/全失败时允许 ML 位于边界。
想一想全部观测都失败时,ML 会怎样?先验如何改变边界解?
在 t=−1、0、1 三个观测位置间分配权重。观察信息矩阵与参数空间中单位信息椭圆的面积。
候选位置为 , 且 。D-optimal 最大化 ;图中为 ,不标作某一置信概率。
在线性高斯噪声方差为 1 的模型下解释信息矩阵。当前三个位置中,等分两个端点最大化行列式。
想一想为什么只在一个位置观测,无法同时识别直线的截距和斜率?
移动两类样本间隔、翻转一个标签或调节正则化,重新拟合概率曲线。
优化变量为 ,。此处 ,避免完全可分数据的无正则 MLE 参数发散。
使用正 λ 惩罚两个系数,使演示始终有有限唯一解;概率模型实时通过阻尼 Newton 重新拟合。
想一想完全可分的数据为什么可能没有有限的未正则化极大似然估计?
给三个可能取值指定均值,在约束下最大化熵;观察指数族分布如何倾斜。
三个结果为 ,, 由均值约束确定。熵使用自然对数,并约定 。
pᵢ∝exp(βtᵢ),β 通过均值方程求解。均值 0 时为均匀分布;使用自然对数。
想一想为什么均值接近端点时,熵越来越小?
改变样本相关性和尺度,在单位精度与最优精度之间插值,查看似然差。
为两维样本协方差, 为精度矩阵,均值固定为零。图中候选为 ,。
假设均值已知为 0、样本协方差正定;最优精度为 S⁻¹。图中椭圆表示单位二次型,不指定置信水平。
想一想为什么对精度矩阵凸,不代表对协方差矩阵也具有同样形式?
调整两种正态分布的间隔和误报率要求,查看最优阈值与 ROC 曲线。
, 是标准正态分布函数。规则为 时拒绝 ,并令误报率为 。
δ>0 时似然比单调,最优规则为 x>阈值;δ=0 时两假设相同,检出率等于误报率。
想一想两分布重合时,ROC 为什么退化为对角线?
在五点支撑上穷举基本可行分布,最大化尾部概率;比较只依赖方差的 Cantelli 界。
已知支撑 ,优化变量为五个概率。对比的一般 Cantelli 界为 ,其中 。
已知 E[X]=0、E[X²]=指定方差,并限制支撑 {−2,−1,0,1,2}。枚举至多三个非零概率的基本可行解;不是所有实值分布的精确界。
想一想额外知道支撑集,为什么可能得到更紧的概率上界?
从投影、距离与椭球,到分类、布局和选址。
拖动点 y,切换闭凸集合的形状。观察最近点 x*,以及法向为 y−x* 的支撑直线。
是可拖动的点, 是其欧氏投影。外部点给出 ,对所有 成立。
绿色直线支撑集合,将外部点与集合分开。
想一想把 y 拖到集合内部后,投影和分离直线分别会发生什么?
旋转并移动一条切割约束,观察可行域、最大内切圆与圆心的变化。
矩形被额外半空间 截取。显示一个最大内切圆;最优圆心不一定唯一。
每个候选圆都检查全部半空间约束;退化多面体的最大半径可能为 0。
想一想为什么“圆完全在半空间内”能够写成一个线性不等式?
拖动第二个圆盘并调节半径,观察最近点对和居中的分离直线。
本例 为两个闭圆盘。第二个圆心可拖动;距离为零时,严格分离不成立。
距离为 max(0,圆心距离−两半径之和);相切或相交时不绘制严格分离线。
想一想圆盘相切与相交时,严格分离结论有什么区别?
移动一对对称异常点,改变误分类惩罚,重新求解软间隔线性分类器。
数据成对为 与 。由对称性可取最优截距为零;。这是教材软间隔模型的对称教学特例。
样本成 ± 对称对,因此可取最优截距 0;枚举分段二次目标的驻点、折线驻点和交点。虚线为功能间隔 ±1。
想一想为什么增大 C 不一定让所有样本都满足间隔要求?
拖动三角形顶点,同时观察最小面积外接椭圆与最大面积内接椭圆。
是非共线的三角形顶点; 为最小面积外接椭圆形状矩阵, 为最大面积内接椭圆形状矩阵。
采用非退化三角形的 Steiner 椭圆精确公式;面积比 4 是该特例的性质,不能推广到任意点集或多面体。
想一想为什么两椭圆在三角形特例中共心,半轴恰好相差两倍?
拖动一个需求点并调节其权重,比较总距离最小点与加权重心。
是需求位置, 是权重, 是设施位置。橙色重心 则最小化加权平方距离和。
使用处理重合点的修正 Weiszfeld 迭代。加权重心最小化平方距离之和,几何中位数最小化距离之和。
想一想一个需求点权重很大时,最优设施会不会直接落在该点?
拖动右侧锚点,改变两个自由节点之间的连接强度,重新求解布局。
是固定锚点, 可拖动; 是两个自由节点,共四个标量优化变量。锚定条件消除了整体平移不唯一性。
每个坐标解相同的加权图 Laplacian 方程;这里的弹簧自然长度为零。
想一想连接强度增大时,两个自由节点为什么会靠拢?
从频谱视角看梯度法,进一步研究动量、加速与大步长。
让 GD、Heavy-ball 和 Nesterov 从同一点出发。改变动量系数,逐步观察过冲和收敛。
上式为 Heavy-ball。此例把相同 给 HB 与 NAG;NAG 在外推点求梯度。参数不标作两者的理论最优值。
视窗由各方法的完整有限轨迹共同确定,不随当前迭代步跳动;发散/溢出的后续点不会投影回图框。
想一想同样的步长与动量,为什么两种加速方法会走出不同轨迹?
点击或拖动迭代进度,观察 Silver 的长步与随后的误差变化,再与固定步长 GD 对比。
是 中因子 的次数。默认倍率为 ;改变倍率是实验变体。光滑凸保证针对完整块末端,不保证逐步下降。
橙色为当前步;大步出现在编号含较多因子 2 的位置。
想一想为什么要看完整的 2ᵐ−1 步块,而不是要求每一步都下降?
调节输入 z 与 λ,观察绝对值函数的近端解和软阈值映射。
是输入, 是标量优化变量;。此处近端步长吸收到 中。
这是标量近端子问题的精确解;与一般相关设计矩阵下的完整 Lasso 解有区别。
想一想阈值区间为什么恰好把小坐标映射到零?
用次梯度法最小化 |x|,对比当前值和历史最好值,切换步长衰减方式。
在非零点取 ,在零点取 。这是 EE364b 的额外教学补充,不属于 Boyd–Vandenberghe 主教材的方法覆盖范围。
在 x=0 处选择次梯度 0。固定步长通常在折点两侧振荡,但某些起点和步长恰好有限步到零。
想一想历史最好值下降,是否意味着当前迭代也单调下降?
使用可复现的零均值随机梯度噪声,对比样本轨迹与精确期望误差。
, 独立取 。每步使用一次样本梯度;常步长下 。
f(x)=x²/2,随机梯度 x+ε,ε 独立取 ±σ。期望曲线由二阶矩递推精确计算,未用单条样本冒充期望。
想一想固定步长的误差地板由步长和噪声方差怎样决定?
一步目标值上升,是否意味着长期收敛一定更差?
打开本章完整讲义 ↗