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 相关有趣的内容整理(期中后)

未完待续...

实分析练习题

实分析练习题

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

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(积分号下求导)

是定义在上的函数,作为的函数在上可积,作为的函数在上可微。若存在使得: 那么有如下成立: 证明:当足够小的时候,由微分中值定理有: 再利用DCT,得到:

补充6 可积函数与连续函数的关系

  • 上的可积函数可以被紧支连续函数逼近。任给,存在紧支连续函数和函数满足。换言之,存在上的紧支连续函数列地并且几乎处处收敛于

  • 平均连续性:

  • 上的可积函数可以被紧支阶梯函数逼近,即存在上的紧支阶梯函数列地并且几乎处处收敛于

补充7 重积分与累次积分

Fubini定理和Tonelli定理部分在周民强上已经过了一遍了,就不在这里写了

7.3

补充8 不定积分的微分

引理2,令,(当),那么有: 证明思路:表达式写开,用Tonelli定理再加上平均连续性即得。

Lebesgue微分定理(一维版本),令,则

证明:

step1,几乎处处可微,这是因为为两个单增函数的差,故几乎处处可微。

step2,因为几乎处处可微,对于,可假设其几乎处处收敛到上的可测函数上,又由引理2,意义下收敛于,故只需要证明

step3,证明(不等式即Fatou引理): 定理对于也是成立的,将定理应用在上的可测集上立刻得到上几乎处处的点都是Lebesgue密度点。下面证明一个有用的推论:

推论上局部可积,则几乎每个点属于的Lebesgue集。

证明:将Lebesgue微分定理应用于函数,则对于每个有理数,存在测度为零的集合,只要就有: ,则,且对所有,存在使得。我们有:

补充9 绝对连续函数

,则,且

定义 对于定义在上的实值函数,若对任意,存在使得只要且区间内部不交就有 则称绝对连续(AC)。绝对连续函数具有以下性质:

  • AC函数是一致连续且有界变差的;
  • 如果上几乎处处可微,并且上的可积函数。
  • 微积分基本定理成立;
  • 如果,那么对于任意中的零测集
  • 如果中的可测集,那么可测;
  • 满足以下条件,
    • 如果,则

绝对连续函数有着强于有界变差函数的结论:

定理 如果,则几乎处处存在。此外,若几乎处处为零,则为常数。

暂时更新到这里,剩下的时间要回顾stein上的习题,再就泡在周民强里面了。晚上争取把chap2的习题全都过一遍。

实分析想法寄录

实分析想法寄录

考虑下面的问题:

给定区间上的一个具有正测度的类集合的补集记为。对于上的特征函数,考虑上点处的导数,这是否为0?

这一点由于微分定理是显然的,因为测度为正,故在地有。但是换一个角度来看,这一点或许还没有那么直观。

选定一个,考察小区间这个区间内部取0或1,如果,那么随着中取1的部分的(测度)占比趋于零。而在缩小的取值之时,无论怎么缩小,中总是会包含无数个取值为1的闭区间,又怎么证明这些闭区间的测度之和与的比值趋于0呢?这是一个很复杂的问题,因为在附近的行为很怪异。加上类集合的选取本身就多种多样,如果没有微分定理,单纯用极限理论来看待处的微分的话,确实复杂。这也让我体会到了微分定理的深刻性,对于这样棘手的问题会有如此优雅的结论。当时我转念一想,对于处均不可微,而零测,从而仍是地为0的,导不出矛盾。这就引发了我对微分定理深究的兴趣,藉此机会我们从可积函数出发,梳理一下勒贝格积分与微分理论。

积分理论

  • 积分的定义

引理 对于支撑在有限测度集合上的有界函数(BF),为任何以为界的简单函数序列,且对,那么有

  1. 存在;
  2. ,那么

这样,定义BF函数的积分为

而对于非负函数,去掉BF的条件后,其积分定义为,其中

对于一般的函数,其积分定义为。当是我们说可积。

定理(有界收敛定理) 为一串以为界,支撑在有限测度集合的可测函数序列,且,则可测、有界、支撑在上,且 总结来说就是有界BF函数+几乎处处收敛推得可积+积分值收敛。

定理(法图引理) 为一串非负的可测函数,且,则 这是一个很反直觉的结果,这个结论的证明也相当巧妙。简言之就是选取了,而构造了,这样不仅有,还始终有,这样就得证了。直觉似乎告诉我们几乎处处收敛于,积分也会足够靠近,然而我们最终得到的却是这样一个不等式。trick或许在于的定义。如果是BF函数一切等号都能取到,然而不是BF函数的时候,根据上面的定义才诞生了这个不等式。

推论 是一个非负可测函数,为一串满足的函数列,且,则 相应地单调收敛定理是更弱的推论。一个有用的推论是,无穷非负可测函数项级数的积分可以逐项积分。

可积函数的重要性质

  1. ,存在有限测度集使得

  1. (绝对连续性)存在使得只要,就有

第一个结论,令,其中是以原点位中心半径为的球。由单调收敛定理即证。第二个结论,我们思路差不多,但是构造的是截断函数,由单调收敛定理仍有。后面将写为,前者由收敛性控制,后者由截断函数的上界控制。

控制收敛定理 为可测函数序列,且,其中可积,那么

微分理论

为了证明勒贝格微分定理,我们先引入哈代-李特尔伍德极大函数。

定义(哈代-李特尔伍德极大函数) 对于上的可积函数,定义其极大函数: 极大函数具有以下性质:

  1. 可测;

  2. 几乎处处有限;

  3. (弱型不等式)对所有,满足:

此外还有性质如:

  • 若对于上的可积函数不几乎处处为0,那么对某个和所有,有,从而有不可积。

(3)的形式比切比雪夫不等式弱。切比雪夫不等式说的是,对于非负可测函数 这个不等式放缩其实很松。将挪过去,等号左边代表的是高为,宽为大于的部分,这一部分面积显然被包围。(1)很好证明,只需注意到集合是开集;而(2)是(3)的直接推论,下面着手证明(3)。在证明之前还需要证明重要的:

覆盖引理中的有限开球簇,则存在不相交子集使得

定理的证明是构造性的。我们先选出最大的球,将半径扩大为原有3倍之后变为,所有的与相交的球都会被完全涵盖在之内。去掉这些被完全包含的球,重复这种操作即构造成立。下面证明弱型不等式。

(3)的证明:

要证明。对于每一个$x E_B_x使_{B_x}|f(y)|y>$,此即

取定的一个紧子集,选取的有限子覆盖$={B_1,,B_n} B_{i_1},,B_{i_k}$。则有如下不等式成立:

命题得到了证明。下面着手证明勒贝格微分定理。

微分定理上可积,那么对有: 仅需证明对每个,集合 测度为0。由于紧支撑连续函数在中稠密,对于任何,存在紧支撑连续函数使得。对与连续函数式显然成立。我们可以将写为: 两边同时取上极限并且利用三角不等式得到: 再定义: 则由切比雪夫不等式和弱型估计得到: 显然有包含关系,选取与足够靠近的即证。

remark:对于局部可积函数,上述结论仍然成立。

其他定义及结论:

定义(勒贝格密度点) 是可测集,定义为的勒贝格密度点,若: 则几乎每个的勒贝格密度点;几乎每个不是的勒贝格密度点。

定义(勒贝格集) 上局部可积,则的勒贝格集由所有满足: 组成。并且的连续点属于勒贝格集。并且有定理:若上局部可积,则几乎每个点属于勒贝格集。

实分析chap2,3其他结论

可积函数空间

定理 向量空间在它的度量下是完备的。

推论 柯西列存在几乎处处收敛子列。

定理 以下函数簇在中稠密:

  • 简单函数(有限测度可测集的特征函数的有限线性组合)
  • 阶梯函数(cube的特征函数的有限线性组合)
  • 紧支撑连续函数

平移不变性 为可积函数,定义。则 这是紧支撑连续函数在中稠密的推论。

定理

假定可积,则:

  1. 截面上可积;
  2. 上可积;

此外,还满足等式: 作为一个应用,有如下的结论:

定理 假定非负可测,则对,有:

  1. 截面上可测;
  2. 上可测;
  3. 在扩充的意义下,满足等式:

上的可测子集,将定理应用到上,得到如下的:

推论上的可测子集,且:

关于集合的可测性的若干命题
  1. 上的可测子集,且,则可测。
  2. ,则
  3. 均为可测集,那么

引理1 上的可测函数,那么定义上可测。

引理2 上的非负函数,且令,则:

  • 上可测当且仅当上可测。
  • 上可测,则:

定理 上的可测函数,则上可测。

有界变差函数
  • 单调有界函数、处处可微且导数有界的函数均为有界变差函数。
  • 上的实值函数是有界变差的当且仅当是两个有界的递增函数之差。
  • 若函数上是有界变差的,则几乎处处可微。

引理递增且连续,则几乎处处存在,进而可测、非负,且

李特尔伍德三大原理

第三原理:每个收敛序列接近于一直收敛序列。

定理( 是定义在有限测度集合上的可测函数序列并且在上几乎处处收敛于。给定,能找到对应的闭集,使得且在一致收敛于

第二原理:每个可测函数接近于连续函数。

定理( 在有限测度集合上可测且取有限值。给定,能找到对应的闭集,使得且在上连续。

绝对连续函数

定义 对于定义在上的实值函数,若对任意,存在使得只要且区间内部不交就有 则称绝对连续(AC)。绝对连续函数具有以下性质:

  • AC函数是一致连续且有界变差的;
  • 可积,,则绝对连续,这是积分的绝对连续性保证的。
  • 如果,那么对于任意中的零测集
  • 如果中的可测集,那么可测;
  • 满足以下条件,
    • 如果,则

绝对连续函数有着强于有界变差函数的结论:

定理 如果,则几乎处处存在。此外,若几乎处处为零,则为常数。

实分析

实分析

复分析资料

复分析资料

数理统计

数理统计

随机过程

随机过程

数学分析复习

数学分析复习

数学分析复习(已完结,最后更新2/24)

Chapter 16.1:度量空间与连续函数

内积空间,满足对称性,双线性性与正定性.

赋范空间,满足正定性,齐性和三角不等式.

定义内积诱导的范数.有极化恒等式.

定义范数诱导的度量,满足正定性,对称性和三角不等式.

完备度量空间:每个柯西列都收敛.

上的范数:.

连续函数的范数:对于.

矩阵范数:对于.

命题.

常见的完备度量空间:.

注意:有限维赋范线性空间都是完备的,赋范线性空间里,完备等价于闭。

Chapter 16.2:度量空间的拓扑

紧致:度量空间的子集是紧致的,是指的任一点列的所有极限点均属于.

结论

  1. 非空开集是开球的并集,反之也成立.
  2. 是度量空间的一个度量子空间.子集的开集存在的开集使得.若的开集,那么子集的开集的开集.
  3. 度量空间的一个子集是闭集当且仅当它的余集是开集.
  4. 完备度量空间的一个子集是完备的当且仅当它是的闭子集.
  5. 紧致性完备性.反之不一定成立,如.
  6. 紧致性每一个开覆盖有有限子覆盖有界闭.
  7. 任意紧致度量空间存在至多可数稠密子集.

Chapter 16.3:度量空间上的连续函数

定义(连续函数) 以下是连续的三个等价形式:

  1. ,对任意,存在,当时,.
  2. 中任意收敛点列 ,中点列收敛.
  3. 中任意开子集的原像的开子集.

压缩映射是压缩映射,指存在常数使得.

是压缩映射,则存在唯一的满足.

定义(一致连续) 是一致连续的,是指对任意,存在,对任意,当时,.

定义(连通):度量空间连通是指,不存在两个不交的非空开集满足.

定义(弧连通):度量空间弧连通是指,存在连接其中任意两点的曲线.即,存在连续映射(曲线).

定理

  1. 定义在紧度量空间上的连续函数一致连续.(证明:Heine-Borel性质,在每个小开球里面误差小于,这样的开球形成的开覆盖是有限的)
  2. 紧致集合在连续函数下的像是紧致集合.(考察点列)
  3. 的子集连通当且仅当它是一个区间.
  4. 是连续满射,连通(弧连通)连通(弧连通).
  5. 弧连通空间是连通空间.
  6. 的开子集,若它是连通集合,则它是弧连通集合.
  7. 的非空开集,,则为闭集.(考察上的点列,可以证明点列的极限也属于

Chapter 17:映射的微分

Chapter 18:积分

MAB3Ch17.pdf

线性代数复习

线性代数复习

线性代数复习(已完结,最后更新2/23)

Chapter 6:线性变换

定理 线性变换可对角化存在的一组特征向量构成的一组基.

定理 复方阵可对角化的最小多项式没有重根.

主要思路,首先是由各个特征子空间的和是直和,构造多项式之间是互素的,因此可以写出裴蜀定理,在裴蜀等式中代入线性变换同时作用于,然后说明.

定理 矩阵为任意正整数,有: 思路:取子空间.定义线性映射.而的核空间维数分别为不等式的左边和右边,而即得证.

定理 复数域上的任何阶方阵相似于上三角形矩阵,且的对角元为的全体特征值.

定理 任意矩阵的特征多项式都是的零化多项式.

思路均为归纳法.

定理(牛顿公式)和整数其中,中取个相乘后累加,.

Chapter 7:标准形

定理(根子空间分解)维复线性空间的线性变换个不同特征值为,特征多项式为.则属于特征值的全体根向量和共同组成,且维数为,称为属于特征值的根子空间,记为.且有关系.

思路:设,令作用于上得到.再由互素,利用裴蜀定理代入即可.

此外,设属于特征值次根向量,那么线性无关,并且构成的一组基.

定义(循环子空间) 是数域上的线性空间上的线性变换,且.则中包含的全体不变子空间的交仍然是包含不变子空间,因此是包含的最小 不变子空间.由中一个向量生成的不变子空间称为循环子空间,,且的一组基,其中相对于的最小多项式的次数.

下的矩阵是:

且有. 特征多项式等于最小多项式,这是这类矩阵的特征.

定理(多项式矩阵相关)

  1. 复数域上的矩阵相抵具有相同的秩和初等因子组.
  2. 是对角元不全为零的对角阵,则的初等因子组是的初等因子组共同组成的集合.
  3. 上相似特征方阵上相抵.
  4. 上的循环变换在任意一组基下的矩阵为单纯方阵(特征多项式等于最小多项式的方阵).
  5. 是数域且,那么上相似上相似.

Chapter 8:二次型

定理

  1. 是数域上的阶对称方阵,则 上存在阶可逆方阵使得是对角矩阵.
  2. 实对称方阵正定存在阶实可逆方阵使得.
  3. 与正定(或半正定)实矩阵相合的矩阵仍然正定(或半正定).

定理(不等式)

阶实可逆方阵,有: 等号成立的充要条件是的列向量两两正交.

Chapter 9:内积

定义(有限维实线性空间的内积) 任取的一组基,任取阶实对称方阵下的坐标为,则定义.

定理(柯西不等式) .

定理(三角不等式) 为欧式空间,,有.

定理 同一个内积在两组基下的度量矩阵相合,即:的过渡矩阵.

定理 任意实方阵都可以正交相似为准上三角阵,对角元为所有实特征值和成对复特征值构成的正交方阵.

例子 可以相似成正交方阵可以相似成正交方阵.

右推左,

推论 对任意实对称方阵,存在可逆上三角矩阵,使得.

思路:将原来的基做正交化,即正交矩阵.

定理(QR分解) 阶实可逆方阵,则存在正交矩阵和对角元都大于零的上三角矩阵,使得.

欧式空间的内积 满足双线性,对称性和正定性.

酉空间的内积 满足共轭双线性,共轭对称性和正定性.

定理

  1. 类似于欧式空间,对任意共轭对称方阵,存在可逆上三角矩阵,使得.
  2. 类似于欧式空间,酉空间两组标准正交基之间的过渡矩阵满足.这种称为酉方阵.
  3. 任一复方阵酉相似于上三角形矩阵.
  4. 与规范方阵酉相似的方阵仍然是规范方阵.
  5. 复方阵是规范方阵酉相似于对角矩阵.
  6. 酉方阵的逆,乘积和与其酉相似的方阵仍是酉方阵.
  7. 与Hermite方阵酉相似、共轭相合的矩阵仍为Hermite方阵.
  8. 是酉方阵酉相似于,且.
  9. 是Hermite方阵酉相似于,且.正定的全部特征值为正实数.
  10. 酉方阵、Hermite方阵和复规范方阵属于不同特征值的特征向量互相正交.

定理(不等式) 阶复方阵,有,等号成立当且仅当是规范方阵.

思路:将酉相似于上三角阵.

定理(奇异值分解) 阶复矩阵,存在阶酉方阵阶酉方阵使得,其中的全部非零特征值的算术平方根.

定理(矩阵的极分解) 阶复方阵,可以分解为半正定Hermite方阵 和一个酉方阵 的乘积,且唯一确定.

其他结论(期中考试以前)

证明利用初等变换即可。