夜雨聆风学习资料网

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 ✿

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料