adydio
文章27
标签8
分类1
机器学习与组合优化

机器学习与组合优化

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 状态编码

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

Tensor Feature Description
obj_cos_sim Cosine similarity with objective.
bias Bias value, normalized with constraint coefficients.
is_tight Tightness indicator in LP solution.
dualsol_val Dual solution value, normalized.
age LP age, normalized with total number of LPs.
coef Constraint coefficient, normalized per constraint.
type Type (binary, integer, impl. integer, continuous) as a one-hot encoding.
coef Objective coefficient, normalized.
has_lb Lower bound indicator.
has_ub Upper bound indicator.
sol_is_at_lb Solution value equals lower bound.
sol_is_at_ub Solution value equals upper bound.
sol_frac Solution value fractionality.
basis_status Simplex basis status (lower, basic, upper, zero) as a one-hot encoding.
reduced_cost Reduced cost, normalized.
age LP age, normalized.
sol_val Solution value.
inc_val Value in incumbent.
avg_inc_val Average value in incumbents.
4.3 branching 规则的参数化

网络结构如下:

泛函分析

泛函分析

Functional Analysis

占坑,泛函分析复习笔记,内容大概有:

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

Ciarlet 相关有趣的内容整理(期中前)

易混淆的点:

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

补充例子与结论

强调(1.3里面常用结论)

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

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

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

的一组基,对于扩充的实数,定义映射

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

定理为可分的空间,则存在的有限维子空间的可数有限族满足:

证明 由稠密性,设,满足

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

那么,满足所有条件。

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

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

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

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

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

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

中稠密,时不稠密。

强调(有限维的情况)

  • 任意两个范数等价;

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

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

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

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

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

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

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

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

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

证明 选取基展开,证明

定理(投影映射相关)

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

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

定理(正交补相关)

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

  • 的闭子空间;
  • 如果是闭的,

定理(空间中的表示定理)

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

例子(空间中不是闭的子空间)

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

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

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

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

Ciarlet 相关有趣的内容整理(期中后)

未完待续...

随便寄1

随便寄1

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

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),我们学的是非负函数列+几乎处处收敛,这里的条件是,其形式是: