[置顶]站点公告

本博客现在在主页展示的主要是学习相关内容，吹水的，或者一些日寄之类的琐碎文章放在了本站隐藏专栏里面。

（2023/4/30）

长时间停更了，身上的事情有些琐碎。以后有望在这里开设泛函分析的专栏。哈哈，加油！

（2023/9/20）

恢复更新！

（2023/11）

挖个坑，可以写的东西有： - 22号陆家嘴感受 - 随机漫步的傻瓜（读他的书像是和朋友聊天！） - 日本感受

更新：订阅了obsidian sync，这样我就能在手机上同步博客了！

观看油管技术博主视频的感悟

这位博主对“成功”的定义很有趣：成功即是拥有选择权。你不必为了某些人而“不得不”去做一些事情，你拥有说不的权利。虽然这位博主把人的价值和人生规划比作经商的想法让我很反感（我觉得是非常狭隘）

日寄的前言

距离本博客网站建站已经有两年半之久了。回忆当时的自己，在疫情和学业（还有很多其他东西）的n重打击下倍感迷茫，时常感到思绪万千且想法非常凌乱。我总结当初建站的动机差不多有以下几点：

• 我当时极度迷茫，需要以文字的形式整理思绪。
• 搭建一个博客网站很酷！这是一件非常个性化的事！
• 我有一种分享欲，抑或是“被注视”的感觉——即你这些想法光写给自己看我总觉得差点什么；而进入大学后圈子愈来愈杂，导致我在以往社交媒体上逐渐失去了分享欲。写博客便成了一个不错的手段，把自己的想法给比较好的朋友看（或者是有缘的陌生人）。
• 这种”他者的注视“仿佛对我有种督促的作用：比如说我在总结学习类内容的时候就会非常认真。 最近翻看早期的文字，一些草稿上的内容都非常有趣，让我不禁感叹：啊，原来我当年的心理状态是这样的啊，还会写出这样的文字。可见，忠实地记录下自己的感受（别让宝贵的内容溜走！）是一件挺有意义的事情。

如今经过了一年多的漫长停更，我又回到了这里，希望开启并维护我的《日寄》系列！ 对于如今的又一次启程，我是满怀期待的：我可以专心经营属于自己的世界，在这里畅所欲言了！ 作为日寄的前言，我想在这里记录一下我最新的动机，我为什么想做这样一个长期的规划呢？（持续更新中）

• 最近无意中了解到Lex Fridman其人，深感震撼。此人既是AI行业牛人，又因为自己的能力足够强大，能够利用Podcast这样的形式来拓宽认知边界，促进思想碰撞。他的视频尤具启发性，其一天由下面的安排构成：
  • 两段四小时的“深度工作”（Deep Work）。在这总计八小时的深度工作期间，他会切断所有干扰，包括手机、社交媒体和音乐。唯一允许的中断是喝水、喝咖啡和上厕所。
  • “浅度工作”与播客制作（Shallow Work）。他会专门留出时间处理那些认知要求不高的事务，播客的后期制作就被归于此类。
  • 严格的体育锻炼。他每天会跑10公里上下，不仅如此还有15分钟的高强度自重训练（每分钟5个俯卧撑5个引体向上，而我现在都无法做五个标准引体向上！）。
  • 阅读与学习：每天他会保证至少2小时的阅读时间，其中1小时阅读科学论文，另1小时阅读文学作品（虚构或非虚构类，尤其是历史与文学读物）。 这实在是令人钦佩不已（虽然有些“过于”追求极致，但不妨碍给我带来启示）。在这个信息高度碎片化的当今，我们每天都在面临着各种各样的信息，而其中“噪声”其实占据了上风（我们总是很难意识到，自己其实长久以来很难形成属于自己的、相对正确的判断！）。换言之，我们每天真正在学到“正儿八经”的知识或者在探索性与创造性的工作上，有效的时间是不多的。因此花费固定的时间隔绝外部噪声而专注于自己这一点非常重要。体育锻炼层面，我看到了Lex之后，再也不想把“工作学习忙”当作自己不锻炼的借口；我完全可以在开小差的时候去做15个俯卧撑，这很难吗？正因如此，写日寄就可以鞭策自己写下今天到底干了哪些“实在”的事，从而起到督促的作用。
• 日寄的意义还在于记录零碎的想法以避免遗忘（我其实遗忘了很多东西！）。现在的我时常会有一些新的想法，它们琐碎无序，但有的却十分有价值。
• 探索与利用。人的行为往往受限于其视野。因此接触多元化的信息（如阅读、适量的社交媒体、社交与出行等）非常有必要（甚至是至关重要！这或许属于人生自我规划的一部分，倘若“探索”的太少，人生就会被限制在很狭窄的圈套里！），但又不能喧宾夺主（我短期内只能专注于特定的事情）。写日寄可以记下自己探索的历程，这无疑是很有趣的。在这里我便沿用“二八定律”：八成精力专注于现有的短期目标；剩余二成可以用在各种形式的探索。
• 有些事情规划要趁早。这句话仿佛已经成为了陈腐的家长的说辞，但是，我们不得不培养一种前瞻性。有一些事情如果没有在年轻的时候去做，会引起我本能的恐慌。这些事情（我会不断更新）大概如下：
  • 理财。理财的意识和起点当然是越早越好，这件事情需要自己的意识和前期不断的积累。
  • 梦想。换言之我很想分清楚“我想做的事”和“我为了生计需要做的事”的界限。对于学术活动，我愈发觉得这一点属于后者，因为我不想让我的人生被一个某某高校教授、某某大厂员工、某某学校PhD如此种种头衔所绑定。在我看来，这些头衔统统都只说明了”我仿佛可以在社会上立足生存“，但哪些事情能为”我能成为我“这件事情贡献厚度？目前看来我的学术活动苍白无力（我始终怀疑自己做的科研里面的”真正的“创新成分和其价值），学术激情十分有限。那些”真正属于我“的部分，我不能放弃对这个事物的追寻；哪怕我始终得不到答案。东亚盛产那些“为了找到一份工作，在一个既定路线上取得所谓成功”的人，这些人往往会在三四十岁的时候面临着中年危机或者存在主义危机，然后人生再无变化，从此走向一成不变的结局，这一点让我十分恐惧！我某一刻起意识到了自己过去二十年受到教育的落后和局限（我甚至一段时间还奉其为圭臬！），那之后我就时刻提醒自己，在自己“探索”的部分，去寻找属于自己的东西，时刻警惕由于自己认知的惯性（被环境潜移默化的惰性，自由思想的反面）而导致的某种“被规训”。
  • 健康和饮食的规划。我最近接触到的信息，包括在家人不断的提醒下我意识到饮食习惯的重要性。至少在我习惯性一天两餐外加健身之后，能看到明显的体态改善和精力充足。尤其是Lex等一些人提倡的生酮饮食习惯（如缩短进餐窗口，适当使用补剂，少吃精致碳水等等），很具启发性。
  • 未完待续...
• 日寄似乎是一个很好的宣泄情绪，发疯和倒垃圾的地方！

ML4CO

[1]组合优化和分支定界的背景：pdf

[2]GNN做branching的经典文章：pdf

[3,4]GNN在线性优化/组合优化问题上表达能力和逼近能力的理论基础：pdf pdf

[5]通用近似定理：pdf

[1]要点梳理

1 Introduction

分支定界法递归地将解空间以搜索树的形式划分，然后计算松弛问题的解，再对不能达到比现有解更优的子树进行剪枝。这个反复迭代的过程需要进行顺序决策（sequential decision making），如节点选择（node selection），即选择下一个做子问题拆解的结点；以及变量选择（variable selection），选择对于哪个变量进行划分子树。这种决策过程通常服从一系列由专家设计的硬编码的（hard-coded）（1）启发式规则。这些规则的目的是最小化在一组代表性MILP实例上的平均解决时间。但是在很多语境下经常需要反复求解一系列相似度的组合优化问题，这些问题可能与通常用来评估分支定界算法的实例集合有显著差异（2）。因此，使用统计学习方法是具有吸引力的；然而这面临着一些挑战。

• 编码MILP B&B决策过程的状态并不容易，尤其是因为搜索树和整数线性规划都可能具有可变的结构和大小；

• 如何构建一个模型架构，以便产生可以至少泛化到类似实例，理想情况下还能泛化到训练期间未见过的更大实例的规则，这一点也不清楚。

文章提出用图卷积网络（GCNN）来解决上面的问题。文章专注于变量选择问题，也就是分支问题（branching problem），这一问题是B&B范式的核心，但从理论上来说仍未被充分理解。文章采用模仿学习策略来快速近似强分支（strong branching），这是一种高质量但成本高昂的分支规则。

虽然上述想法不算新颖，文章基于此有两点主要贡献：

• 将branching策略编码到GCNN中，这使得能够利用MILP问题的自然二分图表示，从而减少手动特征工程的工作量；
• 使用行为克隆和交叉熵损失来近似强分支决策，这比预测强分支得分或排名更为简单。

文章在四类NP难题上评估了上述方法，包括集合覆盖、组合拍卖、有容量的设施定位和最大独立集问题。结果表明，文章选择的模型、状态编码和训练程序导致的策略在传统分支规则上有显著的改进，并且能够很好地泛化到比训练中使用的更大的实例。

1.理解为这些规则是预先设定并固定在算法中的，而不是在运行时动态生成或学习的；

2.暂时理解为泛化性能不佳，只能在一些相似的问题上，strong branching才有效。

3 Background

3.2 分支规则

到目前为止，一致性的分支策略结果表明，在所有 B&B 树中选择最小树是有力的分支。它通过在每个可能的分支点运行强分支来实现，这个分支计算每个候选变量在解决问题的预期贡献，并为每个候选变量选择最好的下界。然而，强分支不幸地需要为每个候选变量解决两个线性规划（LP），而在每个节点上运行强分支在实践中是不现实的，现代 B&B 求解器转而依赖于混合分支，它通过在仅在求解过程的开始计算强分支得分然后逐渐借还到更简单的启发式方法如：冲突得分（conflict score）或伪成本（pseudo-cost）或两者的人工组合。

3.3 马尔可夫决策过程公式化

B&B 过程中做出的连续决策可以被同化为马尔可夫决策过程。考虑一个求解器作为环境，分支器（brancher）作为代理。在第 个决策中，求解器处于一个状态 ，该状态包括了 B&B 树的所有过去分支决策，到目前为止找到的最佳整数解，每个节点的 LP 解，当前关注的叶节点以及其他任何求解器统计信息（例如，调用了多少次每个原始启发式算法）。然后分支器从当前关注的节点的所有分数变量 中选择一个变量 ，根据一个策略 。然后求解器扩展 B&B 树，解决两个孩子 LP 松弛，运行任何内部启发式，如果合适就剪枝树，并最终选择下一个要分割的叶节点。我们随后处于一个新状态 ，并且分支器再次被调用来做出下一个分支决策。这个过程如下图所示。

作为马尔可夫决策过程，B&B 是 episodic 的，其中每个 episode 相当于解决一个 MILP 实例。初始状态对应于在一组兴趣中采样的实例，而最终状态标志着优化过程的结束。轨迹 的概率取决于分支策略 和求解器的其余组件，因此可以表示为：

注：原文这里的公式可以简化。其推导见这里

我的疑问

• 文章只针对进行学习，但是具体是怎么得到的我还不清楚。换言之选取了后，具体怎么划分子问题？这应该超出了“branching”的范畴。

4 Methodology

由于B&B变量选择问题可以被表述为马尔可夫决策过程，因此训练策略的自然方式是强化学习。然而，这种方法遇到了许多问题。值得注意的是，由于episode length与性能成正比，而随机初始化的策略表现不佳，标准的强化学习算法在训练初期通常非常慢，以至于总训练时间过长。此外，一旦选择了与实例对应的初始状态，剩余的过程就是实例特定的，所以马尔可夫决策过程往往非常庞大。在这项工作中，我们选择直接从一个专家分枝规则中学习，这种方法通常被称为模仿学习。

4.1 模仿学习

先跑expert程序得到专家的决策组合，利用交叉熵损失：

4.2 状态编码

的编码。考虑携带特征的二部图含义列举如下：

4.3 branching 规则的参数化

网络结构如下：

Functional Analysis

占坑，泛函分析复习笔记，内容大概有：

• 到2.2章节除了1.5章所有作业题解答以及部分未布置的题；
  • faMidNotes.pdf 部分笔记，剩余习题有的不在范围内，选择性重做一遍。
• 部分定理手动证明；
• 往届期中真题自己的解答；（不正式写了）

Ciarlet 相关有趣的内容整理（期中前）

易混淆的点：

• 是指的所有线性包（即 有限 线性组合）的并；
• 基要满足两点：
  • 向量族的元线性无关，即对于任意有限子集各元素线性无关；
  • 对于任何 ，都存在有限子族 ，被子族里面的向量线性表示。
  • 注意：任意向量空间均存在基（引理），且基的基数唯一确定。

补充例子与结论

强调（1.3里面常用结论）

• 中任意有界集为列紧集；
• 列紧空间的任意（闭）子集都是（自）列紧集；
• 列紧空间必是完备空间；
• 完全有界的度量空间可分。

定理 任何有限维空间均是可分的。

要证明这个定理，首先有：有限维空间的范数相互等价，于是换一个范数证明可分。

设为的一组基，对于扩充的实数，定义映射：

则有为上的范数，且空间是可分的，取坐标为有理数的点即可。

定理 设为可分的空间，则存在的有限维子空间的可数有限族满足：

证明 由稠密性，设，满足

首先可以假设对任何。此时递推地定义向量族为：

那么，满足所有条件。

定理 任意向量空间均可赋范。

证明 取的基，对任意给定向量，唯一地存在有限子族，被子族里面的向量线性表示。 此即 ，那么下面映射就是上的一个范数:

定理 赋范空间，可有内积给出满足平行四边形法则。并且满足平行四边形法则时，是内积。

定理 是可分的。时不可分。

证明 不妨证的情况，时构造稠密子集如下： 时，考虑为中所有以组成的数列集合，则，且是不可列的。设是中任意稠密子集，任给，存在，故映射为单射，不可列，从而不可分。

定理 为中的开子集，上紧支集连续函数在中稠密。是可分空间，时不可分。

在中稠密，时不稠密。

强调（有限维的情况）

• 任意两个范数等价；

• 任何有限维赋范空间可分；

• 对于有限维赋范空间中的子集，紧等价于有界闭；

• 空间的有限维子空间在中闭；

• 空间是有限维的等价于的单位球面列紧。

证明第三条：对于，由于紧蕴含有界闭只需反过来证明自列紧。取的基，有界推得各个系数有界，故找到了收敛的子列，这证明了自列紧。

定理 为任意向量空间，则在上存在不等价的范数。

证明 取的基​，那么下面映射就是上的范数:

这时取一个中的可数子族，不妨设为，令，得到。

定理 为赋范空间且 是有限维的，则由 到 的任何线性算子均是连续的。

证明 选取基展开，证明。

定理（投影映射相关）

是内积空间中的非空闭凸子集。为投影映射，代表的是关于的最佳逼近元。

• 为连续映射，常数为1。
• 为线性的充要条件是是的子空间，此时的算子范数为1。

定理（正交补相关）

是内积空间中的非空子集。

• 是的闭子空间；
• ；
• 如果是闭的，。

定理（空间中的表示定理）

为上的空间，对任意给定的，存在唯一的向量，使得而且。

例子（空间中不是闭的子空间）

在希尔伯特空间中构造一个不是闭集的子空间的经典例子是考虑无限维空间中的有限维子空间。

以序列空间 为例，这是所有平方可和的复数序列构成的空间。一个元素 满足 。在这个空间中，我们可以考虑子空间 由所有最终变为零的序列构成，也就是说，对于 中的每个序列 ，存在一个整数 使得所有 的 。

尽管 是 的一个线性子空间，它不是闭的。这是因为可以构造一个序列的序列（也就是一个序列的极限），这个极限在 中，但不在 中。例如，考虑序列 其中 是一个序列，它的前 个元素是 ，之后的元素都是零。每个 都在 中，但它们的极限是序列 ，这个极限在 中但不在 中，因为没有一个点使得序列之后的所有元素都是零。

因此， 是 中的一个不闭子空间的例子。

Ciarlet 相关有趣的内容整理（期中后）

未完待续...

好久没更新博客了！正好参加一个读书笔记二课活动，就随便写了点，水一篇博客先。这几天看看能不能整理一些手写或者电子版泛函分析笔寄。下面是原文。

19岁才开始读哲学入门书籍，我确实来晚了一些。我是带着问题来寻找答案的。

古希腊哲学的伊壁鸠鲁学派对我影响比较大，或者说感触比较深。

首先我比较认同的是他的“快乐主义”思想。伊壁鸠鲁学派认为快乐是生活的最高目标和最终目的，他们强调通过避免痛苦和追求愉悦来实现生活的最大幸福。而有的后人将这一点与享乐主义和纵欲联系起来。恰恰相反，伊壁鸠鲁主张的是一种”克制“的快乐。所谓乐趣非常广泛，而他认为自我的欲望需要加以克制，平和的心境可以帮助我们忍受痛苦。给我的感觉就是不过度放纵，也遵循自己内心”快乐“的标尺，这样追求快乐我觉得很聪明。

我想起我的一个朋友访问科大时给我提出的主张。他也是一个对自己很忠诚的人；他只做自己感觉快乐的事情。但是有很多人不一样的是他将快乐分了好几类。有些诸如打游戏等带来的短期”快乐“，也有更为长久没那么激烈的”享受“，比如研究物理，抑或是沉浸于音乐、艺术当中。这就好比伊壁鸠鲁提出的，在我们考量一个行动是否有乐趣时，必须同时斟酌它可能带来的副作用。这好像也很符合我这些年的心境：只要避免过度狂喜，自然不会有悲哀造次。我这个同学就看的很通透，他自然把各种乐趣分了层级。这不意味着我们放弃追求所谓低级乐趣，各种乐趣都是生活的一部分，不过基于理性，我们可以了解到真正厚重的乐趣的源泉，更可能来自于情感与精神层面（如知识、艺术和爱情等）。

关于如何能达到这种长久的快乐，伊壁鸠鲁列了四种方法：理解力使我们摆脱烦扰我们的偏见，摆脱空洞的幻想和愿望。它教给我们真正的生活艺术。自我克制以其对待快乐和痛苦的正确态度使我们免受伤害。勇敢则以蔑视死亡和痛苦同样使我们免受伤害；对惩罚的畏惧决不能扰乱我们内心的平安，这要归功于正义。此之谓：“神不足惧，死不足忧，祸苦易忍，福乐易求。”我对此觉得有一定道理，至少我坚定自己要更深刻的认识自己和外在，能在复杂的环境下做到足够的清醒。

一些哲学思想的诞生离不开那个时代。伊壁鸠鲁学派诞生的时代正值希腊城邦之间的冲突和战争频繁的时期，包括著名的伯罗奔尼撒战争。这些战争给希腊社会带来了巨大的破坏和不稳定。在伊壁鸠鲁学派出现之前，苏格拉底、柏拉图和亚里士多德的哲学思想已经在希腊占据主导地位。而对比我自己，显然在大学浑浑噩噩的自己心境早已混乱许久。面对复杂的社会，繁重的学业我也一度怀疑自己缘何行走至此。很幸运能（迟来的）阅读哲学书籍，虽然只是蜻蜓点水泛泛而读，但我能感到灵魂被悄然解放。我很久以来在脑海里描摹自己理想的心境，而伊壁鸠鲁给了我，至少是现在的我一个答案：“幸福就是肉体的无痛苦，灵魂的无纷扰。”对于伊壁鸠鲁学说其他的方面如无神论、德谟克利特原子论我的兴趣属实不大，这一次的读书笔记遂停止于此。

实分析补充练习与补充知识点

6.30

设定义在上的函数满足$|f(x)-f(y)|e^{|x|+|y|}|x-y| Em(E)=0m(f(E))=0$。

不妨设为有界集，因为对每个，可令，这样就有，再由即得结论。

对于有界零测集，设。任给，存在开集，且。对使用开集结构定理，任意构成区间满足，故，这便证明了。

设是上的连续函数，是上的实值可测函数，则是上的可测函数。

上可测函数列满足，且依测度收敛到0，证明。

是上的正值可积函数，是一列可测子集，且有，证明。

设存在一列，那么足够大时。选取的子列使得在第项上的积分值小于。简便起见，这个子列仍记为。定义，作为Fatou-Lebesgue定理的直接推论，其测度。我们有： 这推出在上几乎处处为零，与题设矛盾。

7.1

补充上面的定理证明：

补充1 Fatou-Lebesgue定理

对于给定的度量空间 ，假设是一系列定义在其上的实值可测函数。如果存在一个勒贝格可积函数在上以绝对值控制该序列，即对于所有自然数，都满足，那么： 证明：所有的 以及 的下限和上限序列在绝对值上被 控制，因此它们是可测的，并且是可积的。第一个不等式是通过将非负函数 应用于Fatou引理，并利用Lebesgue积分的线性性得到的。最后一个不等式是反向Fatou引理。这里的Fatou引理比我们学的要强一些（周民强4.2例题4），我们学的是非负函数列+几乎处处收敛，这里的条件是，其形式是： 总的来说，就是Fatou引理加上的控制，就能得到Fatou-Lebesgue定理！

补充2 各种收敛性

考试可能涉及到各种收敛性，这里做出一定总结：

• 几乎处处收敛

引理1 若，那么对任意，有 证明：的上极限集合必然不是收敛点，那么，再由递降集合测度的极限性质，得到： Egorov定理 为几乎处处有限，定义在有限测度集合上的可测函数列。若，则对，存在，使得在上一致收敛于。

证明我看过一遍了，要用到上面的引理。取定之后，先把分解为，每一个对应使得 从而构造 进一步说明在上一致收敛于。

注意

1. 条件不可去掉，否则考虑上的特征函数。
2. 在下，近一致收敛于几乎处处收敛等价，二者都能推出依测度收敛。

• 依概率收敛

定理 为几乎处处有限，定义在有限测度集合上的可测函数列。若，且几乎处处有限，则依测度收敛于。

由上述引理1立即得证。

Riesz定理 依测度收敛序列存在几乎处处收敛子列。

补充3 Lusin定理

Lusin定理描述了可测函数和连续函数的关系。其叙述如下：

是定义在的几乎处处有限可测函数，任给，存在闭集使得是上的连续函数。

首先我们需要知道，对于可测函数，存在简单紧支函数列使得并且逐点收敛。特别地若有界，该收敛是一致的。利用这一点重要性质，从简单函数出发可得Lusin定理。Lusin定理有若干推论：

推论1 是定义在的几乎处处有限可测函数，任给，存在上的连续函数满足： 若，上述的可取为紧支的。

推论2 是定义在的几乎处处有限可测函数，则存在上的连续函数列满足：

7.2

设，证明。

证明：等价于证明级数在上几乎处处收敛即可。我们用积分说明该级数在上几乎有限： 第一步是因为为非负可测函数列，可以逐项积分。上面的式子说明在上几乎处处有限，故在时上几乎处处收敛于0。

补充4 基本换元

对，，有： 证明思路：先证明对简单函数成立，再用简单函数逼近可测函数。

补充5 控制收敛定理相关

首先，DCT证明了更强的收敛。简单的记忆就是：控制函数+几乎处处收敛，极限符号可以挪到里面去。DCT有一些应用，为了强化理解，下面列举并证明两个有用的推论：

推论1（逐项积分）

不同于非负可测函数列的逐项积分定理，这里的表述是：

设，若有，那么函数项级数在上几乎处处收敛，且且 证明：为非负可测函数列，故可以逐项积分。即： 从而且几乎处处有限。命，则。而在上几乎处处有即被可积函数控制。由DCT立得： 推论2（积分号下求导）