[置顶]站点公告
本博客现在在主页展示的主要是学习相关内容,吹水的,或者一些日寄之类的琐碎文章放在了本站隐藏专栏里面。
(2023/4/30)
长时间停更了,身上的事情有些琐碎。以后有望在这里开设泛函分析的专栏。哈哈,加油!
(2023/9/20)
恢复更新!
(2023/11)
本博客现在在主页展示的主要是学习相关内容,吹水的,或者一些日寄之类的琐碎文章放在了本站隐藏专栏里面。
(2023/4/30)
长时间停更了,身上的事情有些琐碎。以后有望在这里开设泛函分析的专栏。哈哈,加油!
(2023/9/20)
恢复更新!
(2023/11)
[1]组合优化和分支定界的背景:pdf
[2]GNN做branching的经典文章:pdf
[3,4]GNN在线性优化/组合优化问题上表达能力和逼近能力的理论基础:pdf pdf
[5]通用近似定理:pdf
分支定界法递归地将解空间以搜索树的形式划分,然后计算松弛问题的解,再对不能达到比现有解更优的子树进行剪枝。这个反复迭代的过程需要进行顺序决策(sequential decision making),如节点选择(node selection),即选择下一个做子问题拆解的结点;以及变量选择(variable selection),选择对于哪个变量进行划分子树。这种决策过程通常服从一系列由专家设计的硬编码的(hard-coded)(1)启发式规则。这些规则的目的是最小化在一组代表性MILP实例上的平均解决时间。但是在很多语境下经常需要反复求解一系列相似度的组合优化问题,这些问题可能与通常用来评估分支定界算法的实例集合有显著差异(2)。因此,使用统计学习方法是具有吸引力的;然而这面临着一些挑战。
编码MILP B&B决策过程的状态并不容易,尤其是因为搜索树和整数线性规划都可能具有可变的结构和大小;
如何构建一个模型架构,以便产生可以至少泛化到类似实例,理想情况下还能泛化到训练期间未见过的更大实例的规则,这一点也不清楚。
文章提出用图卷积网络(GCNN)来解决上面的问题。文章专注于变量选择问题,也就是分支问题(branching problem),这一问题是B&B范式的核心,但从理论上来说仍未被充分理解。文章采用模仿学习策略来快速近似强分支(strong branching),这是一种高质量但成本高昂的分支规则。
虽然上述想法不算新颖,文章基于此有两点主要贡献:
文章在四类NP难题上评估了上述方法,包括集合覆盖、组合拍卖、有容量的设施定位和最大独立集问题。结果表明,文章选择的模型、状态编码和训练程序导致的策略在传统分支规则上有显著的改进,并且能够很好地泛化到比训练中使用的更大的实例。
1.理解为这些规则是预先设定并固定在算法中的,而不是在运行时动态生成或学习的;
2.暂时理解为泛化性能不佳,只能在一些相似的问题上,strong branching才有效。
到目前为止,一致性的分支策略结果表明,在所有 B&B 树中选择最小树是有力的分支。它通过在每个可能的分支点运行强分支来实现,这个分支计算每个候选变量在解决问题的预期贡献,并为每个候选变量选择最好的下界。然而,强分支不幸地需要为每个候选变量解决两个线性规划(LP),而在每个节点上运行强分支在实践中是不现实的,现代 B&B 求解器转而依赖于混合分支,它通过在仅在求解过程的开始计算强分支得分然后逐渐借还到更简单的启发式方法如:冲突得分(conflict score)或伪成本(pseudo-cost)或两者的人工组合。
B&B 过程中做出的连续决策可以被同化为马尔可夫决策过程。考虑一个求解器作为环境,分支器(brancher)作为代理。在第
作为马尔可夫决策过程,B&B 是 episodic 的,其中每个 episode 相当于解决一个 MILP 实例。初始状态对应于在一组兴趣中采样的实例,而最终状态标志着优化过程的结束。轨迹
注:原文这里的公式可以简化。其推导见这里
我的疑问
- 文章只针对
进行学习,但是 具体是怎么得到的我还不清楚。换言之选取了 后,具体怎么划分子问题?这应该超出了“branching”的范畴。
由于B&B变量选择问题可以被表述为马尔可夫决策过程,因此训练策略的自然方式是强化学习。然而,这种方法遇到了许多问题。值得注意的是,由于episode length与性能成正比,而随机初始化的策略表现不佳,标准的强化学习算法在训练初期通常非常慢,以至于总训练时间过长。此外,一旦选择了与实例对应的初始状态,剩余的过程就是实例特定的,所以马尔可夫决策过程往往非常庞大。在这项工作中,我们选择直接从一个专家分枝规则中学习,这种方法通常被称为模仿学习。
先跑expert程序得到专家的决策组合
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. |
网络结构如下:
占坑,泛函分析复习笔记,内容大概有:
强调(1.3里面常用结论)
中任意有界集为列紧集; - 列紧空间的任意(闭)子集都是(自)列紧集;
- 列紧空间必是完备空间;
- 完全有界的度量空间可分。
定理 任何有限维
要证明这个定理,首先有:有限维
设
则有
定理 设
证明 由稠密性,设
首先可以假设对任何
那么,
定理 任意向量空间均可赋范。
证明 取
定理 赋范空间
定理
证明 不妨证
定理
强调(有限维的情况)
任意两个范数等价;
任何有限维赋范空间可分;
对于有限维赋范空间中的子集,紧等价于有界闭;
空间 的有限维子空间在 中闭;
空间 是有限维的等价于 的单位球面列紧。 证明第三条:对于
,由于紧蕴含有界闭只需反过来证明 自列紧。取 的 基 ,有界推得各个系数有界,故找到了收敛的子列,这证明了自列紧。
定理
证明 取
这时取一个
定理
证明 选取基展开,证明
定理(投影映射相关)
定理(正交补相关)
定理(
例子(
在希尔伯特空间
以序列空间
尽管
因此,
未完待续...
好久没更新博客了!正好参加一个读书笔记二课活动,就随便写了点,水一篇博客先。这几天看看能不能整理一些手写或者电子版泛函分析笔寄。下面是原文。
19岁才开始读哲学入门书籍,我确实来晚了一些。我是带着问题来寻找答案的。
古希腊哲学的伊壁鸠鲁学派对我影响比较大,或者说感触比较深。
首先我比较认同的是他的“快乐主义”思想。伊壁鸠鲁学派认为快乐是生活的最高目标和最终目的,他们强调通过避免痛苦和追求愉悦来实现生活的最大幸福。而有的后人将这一点与享乐主义和纵欲联系起来。恰恰相反,伊壁鸠鲁主张的是一种”克制“的快乐。所谓乐趣非常广泛,而他认为自我的欲望需要加以克制,平和的心境可以帮助我们忍受痛苦。给我的感觉就是不过度放纵,也遵循自己内心”快乐“的标尺,这样追求快乐我觉得很聪明。
我想起我的一个朋友访问科大时给我提出的主张。他也是一个对自己很忠诚的人;他只做自己感觉快乐的事情。但是有很多人不一样的是他将快乐分了好几类。有些诸如打游戏等带来的短期”快乐“,也有更为长久没那么激烈的”享受“,比如研究物理,抑或是沉浸于音乐、艺术当中。这就好比伊壁鸠鲁提出的,在我们考量一个行动是否有乐趣时,必须同时斟酌它可能带来的副作用。这好像也很符合我这些年的心境:只要避免过度狂喜,自然不会有悲哀造次。我这个同学就看的很通透,他自然把各种乐趣分了层级。这不意味着我们放弃追求所谓低级乐趣,各种乐趣都是生活的一部分,不过基于理性,我们可以了解到真正厚重的乐趣的源泉,更可能来自于情感与精神层面(如知识、艺术和爱情等)。
关于如何能达到这种长久的快乐,伊壁鸠鲁列了四种方法:理解力使我们摆脱烦扰我们的偏见,摆脱空洞的幻想和愿望。它教给我们真正的生活艺术。自我克制以其对待快乐和痛苦的正确态度使我们免受伤害。勇敢则以蔑视死亡和痛苦同样使我们免受伤害;对惩罚的畏惧决不能扰乱我们内心的平安,这要归功于正义。此之谓:“神不足惧,死不足忧,祸苦易忍,福乐易求。”我对此觉得有一定道理,至少我坚定自己要更深刻的认识自己和外在,能在复杂的环境下做到足够的清醒。
一些哲学思想的诞生离不开那个时代。伊壁鸠鲁学派诞生的时代正值希腊城邦之间的冲突和战争频繁的时期,包括著名的伯罗奔尼撒战争。这些战争给希腊社会带来了巨大的破坏和不稳定。在伊壁鸠鲁学派出现之前,苏格拉底、柏拉图和亚里士多德的哲学思想已经在希腊占据主导地位。而对比我自己,显然在大学浑浑噩噩的自己心境早已混乱许久。面对复杂的社会,繁重的学业我也一度怀疑自己缘何行走至此。很幸运能(迟来的)阅读哲学书籍,虽然只是蜻蜓点水泛泛而读,但我能感到灵魂被悄然解放。我很久以来在脑海里描摹自己理想的心境,而伊壁鸠鲁给了我,至少是现在的我一个答案:“幸福就是肉体的无痛苦,灵魂的无纷扰。”对于伊壁鸠鲁学说其他的方面如无神论、德谟克利特原子论我的兴趣属实不大,这一次的读书笔记遂停止于此。
设定义在
上的函数 满足$|f(x)-f(y)|e^{|x|+|y|}|x-y| E 。 若 m(E)=0 且 m(f(E))=0$。 , 证 明
不妨设
对于有界零测集
设
是 上的连续函数, 是 上的实值可测函数,则 是 上的可测函数。
上可测函数列 满足 ,且 依测度收敛到0,证明 。
是 上的正值可积函数, 是一列可测子集,且有 ,证明 。
设存在一列
补充上面的定理证明:
对于给定的度量空间
考试可能涉及到各种收敛性,这里做出一定总结:
引理1 若
证明我看过一遍了,要用到上面的引理。取定
注意
定理
由上述引理1立即得证。
Riesz定理 依测度收敛序列存在几乎处处收敛子列。
Lusin定理描述了可测函数和连续函数的关系。其叙述如下:
首先我们需要知道,对于可测函数
推论1
推论2
设
,证明 。
证明:等价于证明级数
对
首先,DCT证明了更强的
推论1(逐项积分)
不同于非负可测函数列的逐项积分定理,这里的表述是:
设
平均连续性:
Fubini定理和Tonelli定理部分在周民强上已经过了一遍了,就不在这里写了
引理2 设
Lebesgue微分定理(一维版本) 设
证明:
step1,
step2,因为
step3,证明
推论 若
证明:将Lebesgue微分定理应用于函数
, ,则 ,且 。
定义 对于定义在
绝对连续函数有着强于有界变差函数的结论:
定理 如果
暂时更新到这里,剩下的时间要回顾stein上的习题,再就泡在周民强里面了。晚上争取把chap2的习题全都过一遍。
考虑下面的问题:
给定区间
上的一个具有正测度的类 集合 , 的补集记为 。对于 上的特征函数 ,考虑 在 上点处的导数,这是否 为0?
这一点由于
选定一个
引理 对于支撑在有限测度集合
这样,定义BF函数
而对于非负函数
对于一般的函数
定理(有界收敛定理)
定理(法图引理)
推论
可积函数的重要性质
第一个结论,令
控制收敛定理
为了证明勒贝格微分定理,我们先引入哈代-李特尔伍德极大函数。
定义(哈代-李特尔伍德极大函数) 对于
(弱型不等式)对所有
此外还有性质如:
(3)的形式比切比雪夫不等式弱。切比雪夫不等式说的是,对于非负可测函数
定理的证明是构造性的。我们先选出最大的球
(3)的证明:
要证明
取定
命题得到了证明。下面着手证明勒贝格微分定理。
remark:对于局部可积函数,上述结论仍然成立。
其他定义及结论:
定义(勒贝格密度点)
定义(勒贝格集)
定理 向量空间
推论
定理 以下函数簇在
平移不变性
假定
此外,还满足等式:
推论 对
引理1
引理2
定理
引理 若
第三原理:每个收敛序列接近于一直收敛序列。
定理(
第二原理:每个可测函数接近于连续函数。
定理(
定义 对于定义在
绝对连续函数有着强于有界变差函数的结论:
定理 如果
新概念cp谁懂啊谁懂啊 Kreisler x Rachmaninov 磕
这个小网站的功能便是把很长的地址转化为一个短地址,起到方便转发的作用。
所用到的技术栈:Python+Flask+html+MySQL。
实例:输入一长串地址如下
点击生成,得到的输出如下:
点击短链接立刻成功转到长链接对应的页面。
这个作业是一个典型的Flask
框架,我也采用的是经典的布局:
app.py
是主程序,里面是获取长链接页面和生成短链接页面的相关代码,通过GET和POST的方法实现前后端的联系;config.py
是Flask
项目的配置文件,主要是数据库的连接信息;models.py
是自己撰写的类,里面设计了url在数据库中的表单形式,此外还设计了两个获取数据的方法;exts.py
专门用来存放SQLAlchemy
的实例,这样做的原因见下文。index.html
是基于bootstrap的app页面,简洁美观。大致的思路便是通过将网页的序号(在数据库里的序号)通过62进制函数形成一一对应并且缩短长度,再在本网页设置重定向即可。运作流程可以概括为:用户输入长链接->数据库存储长链接并且生成序号->(点击短链接时)通过短链接后缀找到序号,找到数据库中对应的长链接->跳转。
models.py
from exts import db
class URLModel(db.Model):
#数据表信息设置
= "urls"
__tablename__ id = db.Column(db.Integer, nullable=False, autoincrement=True, primary_key=True)
= db.Column(db.String(1000), nullable=False)
url #通过id找到对应url
def find_url(self, id):
= URLModel.query.filter(URLModel.id == id).first().url
url return url
#获取当前最后一个数据(即刚刚存储的数据)的id
def find_id(self):
return URLModel.query.order_by(URLModel.id.desc()).first().id
这个类先设计了url在数据库中的表单形式:id是url对应的序号,为整型变量,是整个table的主键并且有自增;url为字符串变量,存放用户输入的长url。Flask-SQLAlchemy
提供一个名为 Model 的类,用于作为声明模型时的 declarative 基类。在这之后我设计了两个简单的方法,分别用数据库的语句查询到相应的信息,从而简化了主程序的代码。find_url
通过输入id返回对应的url,find_id
的作用是查询数据表最后一行对应的id。这个类的设计至关重要,因为主程序绝大多数功能都要调用这个类。
(这个问题到现在还没解决)Python的虚拟环境问题。这个app分别在pycharm terminal跑和在进入虚拟环境的cmd上跑,用的包位置不一样。后面就统一在terminal里面跑得了。
(最坑爹的bug)
The current Flask app is not registered with this 'SQLAlchemy' instance.
为了解决这个报错,我先改变了代码的结构,新增了exts.py
专门用来存放SQLAlchemy
的实例,这样比较符合Flask
的文件规范,也可以有效防止同时构建多个实例导致报错。然而报错仍然存在。搞了好几个小时才发现app.py
中的初始化语句app = Flask(__name__)
写了两遍!系统会觉得我创建了重复的实例就报错了。
(各种小bug)
bases.py
而我一开始下载的是bases
。正确的语句是pip3 install bases.py
。(难点)其实每个模块单独来看真的不难,对我来说最难的部分就是这个项目技术栈之间的联系,比如说Flask
和MySQL
的联系;app与网页的联系;表单和数据库的联系等等。这往往是最容易出bug的地方。