数学知识准备 在本章，我们提供本书相关章节使用的基本定义和重要结果。我们还提供了一些参 考文献，读者可以据此查找更多细节内容或证明。本章的主题包括：概率论，线性代 数，线性规划，数学分析，以及计算复杂性。在这里，我们仅提供重要定义和结果；对 于严格的技术细节，读者需要查询章末列出的参考文献。 33.1概率论 一个概率模型是一个三元组（Q，F，P），其中 ·Ω是实验的结果集，称为样本空间。 ·FC2在补运算下是闭的，在可列并之下也是闭的，而且F包含；F称为Ω上 的。代数，F的元素称为事件。 ·P：F→[0，1]是一个概率映射，它满足 （a）P（O)=O≤P（A)≤P（Ω)=1，AEF。 （b）（可列可加性）：给定Ω的可列无限多个不相交的子集A（i=1，2，）， P（AUAU.·.)=P（A）+P（A)+… 上面的两个性质也称为概率公理。随机变量X是一个映射X：Q→R使得概率P{X≤x)， VrER有明确定义而且能够计算。 随机变量X的累积分布函数是一个映射Fx：R→[0，1]，它的定义为 Fx（x)=P{X<x} 累积分布函数是单调非增的，是右连续的，而且满足

limFx（x）=0 limFx（x)=1 给定随机变量，若它的值域为至多可列的，则称其为离散随机变量；给定随机变 量，若它的累积分布函数为连续的，则称其为连续随机变量。显然，连续随机变量的值 域是不可列无限的。 如果X是一个值域为{1，2，）的离散随机变量，我们将它的概率质量函数定 义为 P{X=i}，i=1,2，… 容易证明>P{X=i}=1。如果X是一个连续随机变量，那么我们将它的概率密度函 数（若存在）定义为 fx(x)=dFx(x). 容易证明 fx（x）dx=1 给定两个事件E和F，若 第 ENF=O 章 则称E和F互不包含（或说，互斥），这意味着 数学知识准备 P(EUF)=P(E)+P(F) 若事件E的发生概率不取决于事件F的发生概率，则称E和F独立。在这种情形下， 可以证明，事件E和F的独立性等价于： P(E∩F)=P(E)P(F) 若E，E2，，E是互不相交的事件，使得EUE2U·UE=Q而且P（E）>O，Vi， 则对于任何事件FEF，都有 F(F)=∑ P(F|E;)P(E) i=1 贝叶斯法则是条件概率的一个重要结果，它表明对于任意两个事件E，FEF，使得 P(E)>0与P(F)>0，则 P (E|F)=P(F|E)P (E) P(F) P（E）称为先验概率，P（EF）称为后验概率；P（FE)P（E）表示F提供给E的 支撑。 贝叶斯法则的一个简单推广是推广到当E，E2，"，E互斥使得U=E=Ω而且

P（E）>0，Vi时。在这种情形下，对于i=1，，n，我们有： P(F|E)P(E) P(E|F)= ∑P(F|E;)P(E) 假设我们有一个随机向量X，X2，，X。将随机变量X定义为： P{X=（s1，·,Sn）}=P{X=S1;·;X=sn} 这称为联合概率分布。如果X1，X2，，X是相互独立的，那么V（s，，Sn），我 们有： P{X=（s1，·"，Sn）}=P{X=s1}···P{X=sn} 概率P（X；=s:}称为边缘概率。另外，假设X，"，X是互相独立的随机变量，我们 可以利用概率质量函数定义下列联合分布： ·P{X=x}P{X2=x2}； ·P{X=x1}P{X2=x2}P{X=x3}； ·P{X=x1}···P{X=xn}。 33.2线性代数 我们在这里提供几个重要概念。为了简单起见，我们没有定义向量空间。更多细节 可参考书籍[1，2]。 假设V={，U2，}是一个向量集，I={1，2，…}是V的指标集。若存在不 全为零的实数入：（iI）使得 =x iEI 则我们说向量x可以表示为V中向量的线性组合（linearcombination）。 给定向量集，如果其中的每个向量都可以表示为V中向量的线性组合，则将该向 量集称为V的张成集，记为span(V)。 口线性相关与线性无关 给定有限向量集V={，2，，），如果存在不全为零的实数入（i∈I）使得 ZAu;=0 iEI 则称V线性相关。若V不是线性相关的，则称其线性无关或线性独立。 例33.1集合{（1，0，0)，（0，1，0)，（0，0，1））是线性无关的。集合 （（5，0，0)，（0，1，0），（0，0，10）}是线性无关的。集合{（1，0，0），（0，1，0）， (1，1，0)}是线性相关的。集合{(1，0，0)，（0，1，0)，（5，6，0)}也是线性相关的。口

口秩 向量集V的秩（rank），是V的最大线性无关子集的基数（cardinality），即该最大 线性无关子集所含向量的个数。 基 令V是一个向量集，B是V的一个有限线性无关子集。若 BU{x}是线性相关的，VxEV\B 则称B是一个最大线性无关集。 V的基（basis）是V的一个最大线性无关子集。可以证明，每个向量空间 VCR”都有基，而且如果B是V的一个基，那么span（V）=span（B）。另外，如果B 和B’是V的两个基，那么|B|=|B|=rank（V)。集合B的基数（cardinality）称为V 的维数。 33.3 线性规划与对偶 一个线性规划（linearprogram，LP）包含 ·一组变量x1，x2，，∈R； ·一个线性目标函数 数学知识准备 其中c1，C2，，C∈R是已知实数（称为权重）； ·一组线性约束，变量的加权和必须满足这些约束。 规范型（canonicalform）或称对称型的线性规划如下所示（以最小化为例）*： min cc s.t.Ar≥b x≥0 其中c=[c……cn]，x=[x·…xn]T，A=[aj]mXn，b=[bbm]T。 标准型（standardform）的线性规划如下所示： min cx s.t.Ax=b x0 下面是线性规划典型的最大化问题的版本： *式中min是minimize（最小化）的缩写；s.t.是subjectto（受约束于）的缩写。由于这样的表达在中文书籍 中已很常见，因此我们保留了这样的写法而不再翻译成中文。一—译者注

maxcc s.t.Ax<b x≥0 不含目标函数的线性规划，称为可行性问题。满足约束条件的向量x=（x"x）称为可行 解。使得目标函数达到最优值的可行解x，称为最优解，通常记为向量x*=（x，""，x）”。 给定一个线性规划，它的所有可行解组成的集合对应着n维空间中的一个凸多面 体。线性约束条件对应着n维空间的超平面。 由于目标函数是线性的，可行空间的任何局部最优解也是全局最优解。而且，它至 少存在着一个最优解，这样的最优解位于凸多面体的某个（些）顶点上。 在求线性规划问题时，单纯形算法比较著名，它的做法如下。单纯形算法从凸多面体 的某个顶点处出发，移动到使目标函数值有所改进的相邻顶点（有所改进，在最小化问题 中是指目标函数值变小，在最大化问题中是指目标函数值变大），迭代下去，直至找到最 优点。单纯形算法的最坏情形一时间复杂度，关于变量和约束条件的个数成指数增长。 线性规划的另外一种求解方法，称为内点法。这种方法考察多面体的内部区域而不 是顶点。伴随最坏情形一一时间复杂度的内点法，也已经被发展出来。 口线性规划中的对偶 例33.2首先我们考察一个对称型线性规划问题 min6x+8x2-10x s.t.3x+x2-x3≥4 5.x+2x2-7x≥7 x1,x2x≥0 这个线性规划的对偶问题为 max4w+7w s.t.3w+5w<6 +2w<8 -w-7w≤-10 <m 在下面的讨论中，我们将推广这个例子。口 给定 c=c···cn]；x=x··x]T A=[ajmxn；b=[b··.bm]T w=[w.wm] 对称型线性规划的原问题为 mincx s.t.Ax≥b x≥0

它的对偶问题为 maxwb s.t.wA<c wo 标准型线性规划的原问题为 mincx s.t.Ax=b x≥0 它的对偶问题为 maxwb s.t.wA≤c w不受限制 上面的线性规划形式出现在矩阵博弈的最大最小化问题以及最小最大化问题中（第 9章）。容易证明，给定原问题，则它的对偶问题的对偶是这个原问题本身。下面列出 关于对偶的一些重要结果，我们要用到这些结论。 口弱对偶定理 如果原问题是一个最大化问题，那么任何可行原解的值小于或等于任何可行对偶解 第 的值。如果原问题是一个最小化问题，那么任何可行原解的值大于或等于任何可行对偶 章 解的值。 数学知识准备 口强对偶定理 给定原问题和它的对偶问题，如果其中一个问题有最优解，那么另外一个问题也有 最优解，而且它们最优解的值相同。注意，这是我们证明最小最大定理时用到的重要 结果。 口基本对偶定理 给定原问题和它的对偶问题，下列论断恰有一个为真。 （1）两个问题都有最优解（比如x和w），而且cx*=w*b。 （2）其中一个问题有无界目标函数值，在这种情形下，另外一个问题必定不可行。 （3）两个问题都不可行。 33.4数学分析 口度量空间 一个度量空间（V，d）包含一个集合V和一个映射d：V×V→R，使得Vx，y，

xEV，下列各项成立。 (1)d(x，y）≥0; （2）d（x，y)=0当且仅当x=y； (3)d（x，y)=d（y，x); (4)d(x，z)<d（x，y)+d（y，z)。 映射d称为一个度量（metric）或距离（distance）函数。注意，上面的条件（1） 可从其他三个条件推出。 开球 d(x，y)<r}。 开集 度量空间（V，d）中的开集X是V的一个子集，使得我们在每个xEX点上都能 找到一个开球，而且该开球包含于X。 有界集 给定度量空间（V，d）及其一个子集X，如果X完全包含于某个中心在0且半径 为有限的开球内，则X是有界的。 闭集 列收敛到X中的点。也就是说，对于X中的所有序列{xk〉使得对于某个x∈V，xk→ x，则xEX。值得注意的是，集合X为闭的当且仅当它的补X°=V\X是一个开集。 紧集 给定度量空间（V，d）及其一个子集X，如果X中的每个点序列都有收敛子序列， 则称X是紧的。一个重要结果是，如果度量空间为R”（在欧几里得度量下），那么X 为紧的当且仅当X为闭且有界的。 例33.3（紧集）闭区间[0，1]是紧的。集合[0，00），（0，1)，（0，1]，[0，1)， （一，）都不是紧的。注意，集合[0，∞）和（一，）都是闭的，但都不是有界 的。R的任何有限子集都是紧的。口 口一个有用的结果 令XCR”，令f:X→R是一个连续函数。于是，紧集在f下的像（image）也是 紧的。 口魏尔斯特拉斯（Weierstrass）定理 令XCR”，以及f：X→R是一个连续函数。如果X是紧的，那么f在X中有最大

值和最小值。 口凸理论 凸组合 给定x1，，m∈R”，若存在数入1，，入m∈R使得 （1）入≥0，i=1，，m， (2)∑入；=1， （3）y= Zaici, =1 则称点y∈R”为x1，，m的一个凸组合（convexcombination）。 凸集 给定集合XCR”，如果X内的任何两点的凸组合也在X内，则称X是凸的。这个 定义立即意味着含有两个或多个元素的有限集不可能是凸集。在直觉上，如果X内的 任意两点连成的直线段完全包含在X内，则X是凸集。 例33.4（凸集）单点集总是凸的。区间（0，1)，（0，1]，[0，1)，[0，1]都是 凸的。集合X={x∈R²：Ilx<1}是凸的。集合X={x∈R²：|x=1}不是凸的。口 凹函数与凸函数 令XCR”是一个凸集。函数f：X→R是凹的当且仅当Vx，yEX以及V入∈ (0，1)， 第 f[ax+(1-x)y]≥入f(x)+(1-x)f(y) 章 f是凸的当且仅当Vx，yEX以及V入∈（0，1)， 数学知 f[ax+(1-a）y]<af（x)+(1-x）f(y) 识 凸函数和凹函数的另外一种定义方法如下。 准备 若XCR”是一个凸集，f：X→R是一个函数，定义 subf={（x,y):x∈X,y∈R,f(x)≥y} epif={（x,y):xEX,yER,f（x)<y} 若subf为凸，则f为凹；若epif为凸，则f为凸。 例33.5（凸函数与凹函数）函数f（x）=x²（其中x∈R）不是凸的，也不是凹 的。函数f2（x）=ax十b（其中x∈R”，α，b∈R）既是凸的又是凹的。给定由 f3（x）=x定义的函数f3：R+→R（其中R+是所有正实数组成的集合），当0<α<1 时，f3是凹的；当α>1时，f3是凸的。当α=1时，f3既是凹的又是凸的。口 关于凸理论的一些结果 假设XCR”是一个凸集。则： （1）函数f：X→R是凹的当且仅当函数一f是凸的。 （2）令f：X→R是凹的或凸的。若X是一个开集，则函数f在X上连续。若X不 是开集，则函数f在X内部连续。

拟凹与拟凸 令XCR”是一个凸集，f：X→R是一个函数。函数f在aER点的上轮廓集（up- percontourset）的定义为 Us(a)={xEX:f(x)≥a} f在aER点的下轮廓集（lowercontourset）的定义为 Lf(a)={xEX:f（x)≤a} 给定函数f：X→R，若U（a）对于所有aER都为凸，则称函数f为拟凹的（qua- si-concave)，若Lr（a）对于所有a∈R都为凸，则称f为拟凸的（quasi-convex）。 拟凹和拟凸函数的另外一种定义方式如下。 给定函数f：X→R，则f在X上为拟凹的当且仅当Vx，yEX以及V入E（0，1)， f[Ax+(1-x）y]≥min(f(x),f(y)) f在X上为拟凸的当且仅当Vx，yEX以及V入∈（0，1)， f[Ax+(1-x）y]＜max(f（x),f（y)) 立即可以注意，每个凸函数都是拟凸的，每个凹函数都是拟凹的。 例33.6（拟凹函数与拟凸函数）函数f（x）=x²在R上是拟凸的也是拟凹的，但 它在R上既不是凸的也不是凹的。注意，上轮廓集与下轮廓集都是凸的，因此，这个函 博 数既是拟凸的也是拟凹的。另外，对于任何一对点x和x2，这个函数在介于x和c2 弈论与 之间的点上的函数值，介于min（f（xi），f（x2））和max（f(x1），f(x2））之间，因此 与机 该函数既是拟凸的也是拟凹的。任何非减函数f：R→R都是拟凸的，也是拟凹的，但 它未必为凸，也未必为凹。口 制 设计 33.5计算复杂类 P,NP与NPC NP完全性（NP-completeness）这个概念是在决策问题的架构内研究的。我们关 注的大多数问题通常是最优化问题。为了使用NP完全性，我们必须将最优化问题视为 决策问题。 例33.7考虑SPATH问题。即给定一个无权重、无方向的图G=（V，E）以及两 个顶点u，vEV，请找到u和之间的最短路径。SPATH问题通常由一个特定的图以 及此图的两个顶点组成。与最优化问题SPATH相关的决策问题PATH是：给定图G= （V，E）及其两个顶点u，u∈V，以及一个非负整数k，那么u和之间存在着长度 至多为k的路径吗？决策问题PATH仅是将原最优化问题转变为决策问题的一种方 法。口 如果给定的最优化问题比较简单，那么与它相关的决策问题也比较简单。类似地， 如果有证据表明决策问题比较难，那么与它相关的最优化问题也比较难。

口P类与NP类 给定一种算法，若它的最坏情形复杂性以输入规模（inputsize）的多项式函数为 界，则称该算法的复杂性为多项式有界的。这里常用的基准模型为确定型图灵机。P是 由所有那些可以由确定型图灵机在多项式时间内解决的问题组成的集合。 NP代表可由非确定型图灵机在多项式时间内解决的决策问题类。非确定型图灵机 在每一步都能做出正确猜测，而且比确定型图灵机更快地逼近解。NP的一个等价定义 是：NP是所有那些可在多项式时间内验证解的决策问题组成的集合。更具体地说，给 定问题的一个备选解（称其为资格），你可以（用确定型图灵机）在多项式时间内验证 决策问题的答案为YES或NO。 显然，PCNP。然而，NP=P吗？答案未知。这是当前计算机科学中最著名的 待解决问题。 口问题的可归约性 假设我们有一个用于求解问题Y的算法。给定问题X，假设存在函数T，当我们输 人r时得到T（x），而T（x）是Y的一个输人，使得X在x上的正确答案为YES当且 仅当Y在T（x）上的正确答案为YES。于是，通过使用函数T以及用于求Y的算法， 我们得到了用于求X的算法。如果函数T可（用确定型图灵机）在多项式有界时间内 计算，我们就说X能多项式归约到Y，记为 第 X≤PY 章 如果X≤pY，这意味着Y的求解难度至少与X的一样。也就是说，X不比Y难求解。 数 学知 显然， 识 X≤PY且YEP→XEP 准 备 NP-hard问题以及NP-complete问题 给定决策问题Y，若X≤pY，VXENP，则称Y为NIP-hard问题。给定NP-hard 问题Y，若YENP，则称Y为NP-complete问题。由所有NP-complete问题组成的 集合，记为NPC。 注释大致地说，一个NP-hard问题至少与NP中的任何问题一样难。另外，如 果该问题属于NP，那么它称为一个NP-complete问题。 注释为了证明给定决策问题Y是NP-complete的，只要我们找到决策问题X∈ NPC使得X≤pY而且YENP就足够了。 注释如果能够证明NPC中的任何一个问题也是P中的问题，那么NP=P。 注释NPC的另外一种刻画方法是，它是由所有下述决策问题Y组成的集合 YENP使得X≤pY，其中X是任一NP-complete问题。 NP-complete问题举例 对于下面列举的这些常见问题，它们的决策问题版本都是NP-complete的。

（1）3-SAT（每个句子中恰好含有三个变量的布尔表达式）； （2）背包问题； （3）旅行商问题； （4）顶点覆盖问题； （5）图形染色问题； （6）斯坦纳（Steiner）树问题； （7）加权集合打包（setpacking）问题； （8）加权集合覆盖（setcovering）问题。 33.6小结与参考文献 在本章，我们提供了概率论、线性代数、线性规划、数学分析以及计算复杂性中的 重要定义和结果。尽管这些定义和结果方便参考，但我们建议读者查阅这些领域的学术 教科书。在这里我们仅提供少数几本： ●概率论[3]； ●线性代数[1,2]； ●线性规划[4]； ●数学分析[5]； ·计算复杂性[6,7]。 以下教科书也是很好的参考文献：Vohra[8]，Sundaram[9]，Mas-Colell，Whin- ston，andGreen[1o]。这些书也提供了很多数学知识。 口参考文献 [1]Kenneth M.Hoffman and Ray Kunze.LinearAlgebra.Prentice Hall,Second Edition,1971. [2]Gilbert Strang.Introduction to Linear Algebra.Wellesley-CambridgePub- lishers,FourthEdition,2009. [3]SheldonMRoss.AFirst CourseinProbability.Pearson,EighthEdition,2010. [4]VasekChvatal.LinearProgramming.W.H.Freeman& Company,1983. [5]Walter Rudin.PrinciplesofMathematicalAnalysis.McGraw-Hill Interna tional Edition,Third Edition,1976. [6]MichaelR.GareyandDavidS.Johnson.Computers andIntractability:A GuidetotheTheoryofNP-Completeness.W.H.Freeman and Company,1979. [7]Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,and Clifford Stein Introduction toAlgorithms.TheMITPress andMcGraw-Hill,ThirdEdition,2009. [8]RakeshVohra.Aduanced Mathematical Economics.Cambridge University Press, 2009.

[9]RangarajanK.Sundaram.AFirst CourseinOptimizationTheory.Cambridge UniversityPress,1996. [10]Andreu Mas-Colell,Michael D.Whinston,and Jerry R.Green.Microeco- nomicTheory.OxfordUniversityPress,1995.* 第3章数学知识准备 *书后的索引请登录中国人民大学出版社网站www.crup.com.cn/jingji下载并查阅。