ARTICLE · 1400427
【神奇小习题】最优性理论(上)
✿ L I L A C ✿最优性理论习题(上)
这组题不是很简单,每道都要借另一门课的工具。
题目是读刘浩洋、户将、李勇锋、文再文《最优化:建模、算法与理论》第 5 章 5.1–5.3 节时整理的:5.1 问最优解在不在,5.2 和 5.3 问最优解长什么样(光滑与非光滑两种)。
每题两问。热身是课内的基础小问;难题从书中的一个证明步骤出发,换到泛函分析、PDE、概率论或线性代数的场景里,看哪一步还成立、哪一步要改。标“口试”的适合当面问,标“笔试”的需要动笔。
每道难题配了三条提示,统一放在文末,按顺序一条比一条直接。先自己想,卡住了再往下翻,一次只看一条。
✿ 5.1 最优化问题解的存在性✿
♪ 1. Weierstrass 定理推广到自反 Banach 空间
联系:泛函分析 | 口试
热身 写出问题 的 Weierstrass 定理,即解的存在性条件。
难题 上面的定理要求 。请充分利用本科泛函分析,把它推广到 的情形,其中 是自反 Banach 空间。
♪ 2. Dirichlet 原理与 Weierstrass 的反例
联系:PDE、变分法 | 口试
热身时,强制吗?最小值点满足什么方程?
难题 设 是有界开集,。证明 Dirichlet 能量
在 上有唯一最小值点,且它是 的弱解。
再解释 Weierstrass 本人给出的反例:,,,为什么取不到最小值?
给 Dirichlet 原理挑错的,正是这一节定理冠名的 Weierstrass。
✿ 5.2 无约束可微问题的最优性理论✿
♪ 3. 变分法的 Euler–Lagrange 方程
联系:变分法、实分析 | 笔试
热身 设 是子空间,可微,是 在仿射集 上的局部极小点。仿照一阶必要条件的证明,证明 。
难题 设 在 上 ,在 上极小化
设 是按范数的局部极小点。**不假设**,证明关于是的,并且满足 Euler–Lagrange 方程
为什么不能照搬书上“取 ”那一步?
♪ 4. 无穷维的二阶充分条件
联系:泛函分析、变分法 | 口试
热身 二阶充分条件的证明用到了 。为什么 就能保证这一点?给一个不用谱分解的证明。
难题 在 Hilbert 空间 上:
(a) 构造一个 上的光滑函数 ,使 ,对所有 成立,但 不是局部极小点。
(b) 书上的证明在哪一步失效?把二阶充分条件改成在 Hilbert 空间里成立的版本。
(c) 你构造的 限制在每条过 的直线上,是不是严格局部极小点?有限维里有没有类似的现象?
口试时只问 (b),当场构造 (a) 的例子时间不够。
♪ 5. Rayleigh 商:球面上的二阶条件
联系:线性代数、微分几何 | 口试
热身 二阶必要条件的证明沿直线 做 Taylor 展开。改沿一条曲线,,,写出的和。在无约束问题的稳定点处,曲线的弯曲会影响结论吗?
难题是 阶实对称矩阵,考虑球面上的问题 。
(a) 用球面上的曲线代替直线,推导一阶和二阶必要条件,并证明:局部极小点恰是 的单位特征向量,所以局部极小都是全局极小。
(b) 有人说“二阶条件是 在切空间(tangent space)上半正定”。错在哪里?多出来的那一项是什么?
这就是 5.5 节约束问题的二阶条件里出现 Lagrange 函数 Hesse 矩阵的原因。
♪ 6. 山路引理
联系:拓扑、常微分方程、变分法 | 笔试
热身 设 有两个严格局部极小点 $a<b$。证明 $(a,b)$="" 内有局部极大点。<="" p="">
难题 设 强制,有两个不同的严格局部极小点 。证明 还有第三个稳定点。它一定是局部极大点吗?
♪ 7. 梯度下降几乎不会停在鞍点
联系:动力系统、测度论 | 笔试
学完梯度类算法再回来看更合适。
热身,对称非奇异,且有负特征值。步长 的梯度下降 ,从哪些初值出发会收敛到鞍点 ?这个集合的 Lebesgue 测度是多少?
难题 设 ,是 -Lipschitz 的,是严格鞍点(,),。证明:使梯度下降收敛到 的初值集合是 Lebesgue 零测集。
5.2 节的二阶必要条件因此不只是理论:随机初始化的一阶方法,自动“看见”了 Hesse 矩阵的负特征值。
✿ 5.3 无约束不可微问题的最优性理论✿
♪ 8. 带 惩罚的 Dirichlet 问题
联系:PDE、实分析 | 笔试
热身 设 。证明 的解是 当且仅当 。这个阈值为什么与 无关?
难题 设 是有界开集,,。在 上极小化
(a) 书中复合问题一阶条件的证明,搬到 上还成立吗?逐步检查。
(b) 证明:是最小值点当且仅当 。
♪ 9. 中位数与分位数
联系:概率论、实分析、统计 | 笔试
热身 给定数据 $a_1<a_2<\cdots<a_n$,用 $0\in\partial="" f(x^*)$="" 求="" $f(x)="\sum_{i=1}^n\lvert" x-a_i\rvert$="" 的全部最小值点。$n$="" 为奇数和偶数时有什么不同?<="" p="">
难题 设随机变量 满足 ,分布函数为 。
(a) 证明 是有限凸函数,且
由此说明 的最小值点恰是 的中位数(median)。
(b) 把 换成 ,,最小值点是什么?
(c) 最小值点一定存在吗?一定唯一吗?用 5.1 节的语言回答。
♪ 10. LASSO 的解什么时候唯一
联系:线性代数、统计 | 笔试
热身 LASSO 的目标 什么时候严格凸?且 $m<n$ 时,5.1="" 节的唯一性定理还能用吗?<="" p="">
难题 设 $m
(a) 证明 LASSO 的所有解有相同的 和相同的 。
(b) 记 (由 (a),它与解的选取无关),。证明每个解的支撑都含于 ;若 的列子矩阵 列满秩,则解唯一。
(c) 举一个解不唯一的例子。
实际算出来的解往往是唯一的。目标函数对 不严格凸,唯一性从哪里来,正是这道题想回答的。
♪ 11. 障碍问题:从变分不等式到互补条件
联系:PDE | 笔试
热身 设 非空闭凸,可微且凸。取为的示性函数,用复合问题的结论证明:当且仅当对所有成立。
难题 设 是有界光滑区域,障碍函数在上,。在上极小化。
(a) 证明最小值点存在唯一,并写出它满足的变分不等式。
(b) 假设解足够光滑,推出互补系统
这和 5.5 节的 KKT 条件怎样对应?
♪ 12. 近似点梯度法是压缩映射
联系:数值分析、泛函分析中的不动点定理 | 笔试
热身 用本节的一阶条件计算 。
难题 设 ,(),适当闭凸,$0<t<2 l$。证明<="" p="">
是压缩映射,压缩系数 ,并由此证明近似点梯度法线性收敛到 的唯一最小值点。取多少时 最小?
✿ 提示✿
翻到这里之前,不妨再想五分钟。
1. Weierstrass 定理推广到自反 Banach 空间
提示 1 请回忆 Weierstrass 定理的证明。哪一步用到了有限维? 提示 2 试着回忆 Bolzano–Weierstrass 定理著名的 Banach 空间版本(Eberlein–Šmulian 定理)。 提示 3 收敛换成弱收敛后,“闭”也要跟着换。回忆 Mazur 定理:范数闭的凸集是弱闭的。
2. Dirichlet 原理与 Weierstrass 的反例
提示 1 热身就是有限维的 Dirichlet 原理。无穷维里扮演 的是哪个不等式?(Poincaré 不等式。) 提示 2 是 Hilbert 空间,可以直接用第 1 题。 提示 3 弱解来自一阶条件 。
3. 变分法的 Euler–Lagrange 方程
提示 1 请回忆一阶必要条件的证明:先对每个方向得到方向导数 ,正负方向一起用得到等式,最后取 。这里允许走的方向 是什么? 提示 2 记 ,,。分部积分把一阶条件写成 。取遍允许的方向时,取遍什么集合? 提示 3 请回忆热身:梯度不在允许的方向里,就取它在这个子空间上的投影。试着回忆变分法里的 du Bois-Reymond 引理。
4. 无穷维的二阶充分条件
提示 1 请回忆热身:来自连续函数在单位球面上取到最小值。哪个假设在无穷维里没了? 提示 2 试着回忆泛函分析:无穷维赋范空间的单位球面不紧(Riesz 引理)。让 随 趋于零。 提示 3 再加一个负的四次项,例如 ,让它在 方向上很快“压过”二次项。
5. Rayleigh 商:球面上的二阶条件
提示 1 请回忆二阶必要条件的证明。直线 离开了球面,换成大圆 (,)。 提示 2 请回忆热身:比沿直线多出一项 。它在无约束问题里消失,这里为什么不消失? 提示 3 试着回忆线性代数里的 Rayleigh 商:,等号何时成立?不同特征值的特征向量正交。
6. 山路引理
提示 1 请回忆热身的证明:最大值在区间内部取到。高维里没有“区间”,把它换成所有连接 的路径,考虑山路值 。 提示 2 先证 :严格局部极小点外面套一个小球面,每条路径都要穿过它。 提示 3 再反证 是临界值。试着回忆常微分方程里的梯度流:若水平 附近没有稳定点,就沿负梯度方向把一条“几乎最优”的路径整体往下推。
7. 梯度下降几乎不会停在鞍点
提示 1 请回忆热身:按 的特征向量分解初值,哪些分量被放大? 提示 2 把一步迭代看成映射 。证明 时 是 微分同胚(Jacobi 矩阵可逆,且 是单射)。 提示 3 试着回忆动力系统里的(中心)稳定流形定理,并注意 有大于 的特征值。
8. 带 惩罚的 Dirichlet 问题
提示 1 请回忆复合问题 一阶条件的证明:用了线段 、的凸性、沿线段的导数。哪一步用到了 ? 提示 2 请回忆热身:处光滑部分的导数是 。条件变成 对所有 成立。 提示 3 试着回忆实分析:,且 在 中稠密。
9. 中位数与分位数
提示 1 请回忆热身:有限和用的是和法则。期望是“无穷和”,和法则不能直接搬,要回到次梯度的定义。 提示 2 一元凸函数的次微分是 。差商 的绝对值不超过 ,试着回忆实分析里的控制收敛定理。 提示 3 请回忆 5.1:强制性给出存在性,唯一性要严格凸或强拟凸。在什么样的区间上是仿射的?
10. LASSO 的解什么时候唯一
提示 1 请回忆 5.1 唯一性定理的证明:两个最小值点取中点。对 不严格凸,对 呢? 提示 2 请回忆 LASSO 的最优性条件:时 等于多少? 提示 3 试着回忆线性代数:的解什么时候唯一?例子可以从两列相同的 里找。
11. 障碍问题:从变分不等式到互补条件
提示 1 请回忆热身:示性函数的次微分是法锥。 提示 2 存在唯一性请回忆第 2 题(Dirichlet 原理),只需检查 是 中的非空闭凸集。 提示 3 在变分不等式中取 (光滑紧支)得到一个不等号;在接触集外的开集 里取 得到等号。
12. 近似点梯度法是压缩映射
提示 1 请回忆复合问题的不动点刻画:的不动点恰是 的稳定点。 提示 2 是梯度步和 的复合,分别估计 Lipschitz 常数。那一半请回忆次微分的单调性:。 提示 3 试着回忆泛函分析里的 Banach 不动点定理(压缩映射原理)。
祝大家做题愉快!
✿ 今天也是好日子 · LILAC ✿














































































