2 赋范线性空间与凸集 .docx

1、第2章 赋范线性空间与凸集2.1 赋范线性空间2.2 凸集2.3 一些重要例子2.4 保持凸性的运算2.5 分离超平面和支撑超平面2.1 赋范线性空间2.1.1 赋范线性空间2.1.2 开集和闭集2.1.3 上确界和下确界2.1.4 序列收敛和完备性2.1.5 紧性2.1.6 Banach 空间 2.1.1 赋范线性空间l 线性空间(linear space)/向量空间(vector space)n 指定义加法和标量乘法的非空集合 加法(addition)， 标量乘法 ，n ，满足：1. (交换律)2. (结合律)3.4.5. (结合律)6，7对，8l 线性空间在加法和标量乘法下是闭的(clo

2、sed)。l 线性空间的元素称为向量(vector)。例2.1 一些线性空间 维实向量空间或维欧氏空间：所有维实向量的集合 所有实数序列的集合， 所有多项式的集合。l 消费集(例1.1)和生产可能性集(例1.2)本身不是线性空间。l 但它们都是线性空间的子集，并且都从其母空间中继续了许多线性特征。例2.2 (总需求和总供给) l 个消费者，每个消费者购买消费组合l 总需求(aggregate demand)n 其中对每种商品，对它的总需求n 其中是消费者对商品的需求。l 个厂商，每个厂商的净产出向量为l 总供给(aggregate suppley)l 均衡要求总需求等于总供给，即n 意味着:或

3、者:l 范数(norm)n 实值函数称为范数，满足：1. 非负性(positivity)：2. 严格非负性(strict positivity)：3. 齐次性(homogeneity)：4. 三角不等式(triangle inequality)：n 范数用来衡量向量的大小，符号表明范数是实数集上绝对值的推广。l 度量(metric) n 符合距离函数的要求n 即对，满足：1. 非负性(positivity)：2. 严格非负性(strict positivity)：3. 对称性(symmetry)：4. 三角不等式(triangle inequality)：l 集合加上其度量称为度量空间(met

4、ric space)，表示为。例2.3 范数的一些例子l 上的绝对值l 欧几里德（Euclidean）或范数 Cauchy-Schwarz不等式：，。l 绝对值之和或范数l Chebyshev范数或范数l 上述三个范数都属于范数的特例，其中。n 范数；欧几里德范数l例2.4生产计划的“大小 ” 的测量l 赋范线性空间(normed linear space)n 定义在范数之上的线性空间l 本书涉及的三类赋范线性空间n 维实向量空间n 阶实矩阵空间n 上的有界、连续的实值函数空间u ， 处的函数值为u 在处的函数值为例2.5 (空间)一生的消费路径选择问题l 一种商品，表示期时对该商品的消费量l

5、 设消费者是长生不老的l 消费者计划l 消费集，它是一个线性空间l 每期消费受资源限制：。l 结合范数，它成为赋范线性空间。l 在这一范数中，任意消费计划的规模是任一时期最大的计划消费的绝对值l 子空间(subspace)n ，称为的子空间，n 每个赋范线性空间都有两个平凡子空间：和。例2.6 的子空间l 原点l 所有经过原点的直线l 所有经过原点的平面l 本身例2.7 次数小于的多项式 设表示所有次数小于的多项式，由于加法和标量乘法不会提高多项式的次数，因此，集合是所有多项式的集合的子空间。l 非空集合，跨度：l 设是子空间的子集，如果中没有真子集具有跨度这一性质，则称是子空间的基(base

6、)。n 基的元素是线性无关的n 除外，子空间通常有很多不同的基。n 若有一个由有限个元素组成的基，则所有基都有相同数目的非零元素，这一数目称为子空间的维(dimension)。n 若子空间没有有限基，则它是无限维的。例2.8 的标准基l 单位向量的集合称为的标准基。l 每一向量都有唯一表达式：l 是具有许多可能的基的维空间l 任意个线性无关的维向量的跨度形成的维子空间。2.1.2 开集、闭集和紧集l 开球(open ball)例2.9 中的单位球l 单位球(unit ball)n 欧几里德或范数：圆形n 范数：正方形n 范数，单位球是菱形的l 是的邻域包含的开球，称为的内点(interior

7、point)l 内部(interior) 中所有内点的集合l 是开的(open) l 是闭的(closed) 是开的。例2.10 开球是开集图2.4 开球是开集l 中的开集和闭集具有如下事实：n 任意个开集的并是开集，有限个开集的交是开集。n 任意个闭集的交是闭集，有限个闭集的并是闭集。l 边界点(boundary point)n 是的边界点的每个邻域既包含中的点也包含中的点n 边界(boundary)是所有边界点的集合图2.5 中的内点和边界点l 闭包(closure)n 开n 闭。例2.10 (闭球)闭球是闭集。例 2.11 (单位球面)单位球的边界是，称为单位球面(unit sphere

8、)。中单位球面是，它是集合的边界。例2.13 效率生产l 生产计划是有效率的(efficient)不存在可行计划，l -有效率的生产计划的集合Effl 的每个内点都是非效率的ln 通常是的真子集2.1.5 上确界和下确界l ，是的上界(upper bound)，l 的上界的集合n (此时称无上界)n 整个(仅当时)n 闭的无界区间l 上确界(supremumin)n 集合的最小上界；n 向上无界，则取，而n 当时，称取得(或达到)上确界。l ，是的下界(upper bound)，。l 下确界(infimum)n 集合的最大下界；n 向上无界，则取，而n 当，称取得(或达到)上确界。2.1.4

9、序列收敛和完备性l 中的序列(sequence) 或l 或，。n 称为的极限点(limit point)或极限(limit)l 序列收敛极限惟一图2.6 序列收敛l 柯西序列(Cauchy sequence)n 极限点的候选点不易得时，一般采用柯西准则。n 为柯西序列，。n 每个收敛的序列都是柯西序列。l 有界(bounded)直径有限，即。l 柯西序列有界，这意味着，每个收敛序列都有界。l 在一些度量空间中，柯西序列不会收敛于空间中的元素。为此，我们有：l 定义2.4 (完备度量空间) 如果集合中的每个柯西序列都收敛于中的一个元素，则称度量空间()是完备的(complete)。l 基本事实

10、具有度量的实数集是一个完备的度量空间。l 子序列(subsequence) n 给定序列，设有一个严格递增函数，它将每个正整数分配给一个正整数，则序列称为的子序列(subsequence)。l 紧度量空间n 度量空间是紧的(compact)中的每个序列都有收敛子序列n 紧集闭而有界2.1.4 Banach 空间l Banach空间完备的赋范线性空间l 是典型的有限维赋范线性空间l 定理2.2 有限维赋范线性空间的性质：(1) 它是完备的；(2) 定义于其上的所有范数都是等价的；(3) 子集是紧集，当且仅当它是闭而有界的。2.2 凸集2.2.1 仿射集2.2.2 凸集2.2.3 凸锥2.2.1

11、仿射集l ，形为的点形成经过和的直线。n 对应于n 对应于n 对应于和之间的线段。ln 是基点(对应于)和用缩放的方向(由指向)之和。n 给出了点所在的从到的部分路径。图2.7 直线和线段l 是仿射的(affine)，l 形为的点称为点的仿射组合(affine combination)，其中。l 仿射集包含它的点的每一种仿射组合，即如果是仿射集，则也在中l 仿射集可表示为子空间加上偏移量(offset) ：，l 是仿射集是的子空间。例2.13 线性方程组的解集l 线性方程组的解集是仿射集，其中矩阵，向量。证明：设，即，则对，有这意味着仿射组合也在中。l 与仿射集相联系的子空间是的零空间，即。l

12、 反命题也成立：每个仿射集都可表示为线性方程组的解集。l 仿射包(affine hull)n 中的点的所有仿射组合的集合n 仿射包是包含的最小仿射集：如果为任意满足的仿射集，则。2.2.2 凸集l 集合是凸的(convex)，l 每个仿射集都是凸的凸集 非凸集 非凸集图2.8 中的凸集与非凸集l 形为的点称为点的凸组合(convex combination)，其中，n 注意，仿射组合没有这一非负性要求n 集合是凸的它包含其元素的所有凸组合。n 凸组合可以视为点的混合或加权平均(mixture or weighted average)，其中是的权重。例2.14 (消费集) 消费集指所有可行消费组

13、合的集合(例1.1)。如果和是两种消费组合，它们加权平均是另一消费组合。消费集是的凸子集。例2.15 ( 投入要求集) l 投入要求集为，和是生产的两种不同方式。l 问题：能否将两种生产过程联合起来，并且仍生产，？l 为凸集，则答案为是。l 生产者理论一般假设是凸集，此时，称技术是凸的。l 的凸包(convex hull )l 凸包是包含的最小凸集(a)(b)图2.9 中的凸包2.2.3 凸锥l 集合为锥(cone)，有。l 是凸锥(convex cone)既是锥又是凸集，即，图2.10 凸锥l 形为的点称为点的锥组合(conic combination)，其中l 集合是凸锥包含其元素的所有锥

14、组合。例2.16 (凸技术)技术的典型假设是：(1)加法：; (2)规模报酬不变：对加法要求生产过程是独立的。同时，通常的假定意味着生产可能性集是一个凸锥。对技术来说，凸性的要求比较严格。l 集合的锥包(conic hull)l 锥包是包含的最小凸锥图2-8 锥包 2.3 一些重要例子2.3.1 超平面与半空间2.3.2 欧几里德球、赋范球和赋范锥2.3.3 多面体l 凸集的一些简单的例子n 空集、任意单点集以及整个空间是的仿射子集，从而是的凸子集。n 任意直线都是仿射集，如果它经过，那么它是子空间，因而凸锥。n 线段是凸集，但不是仿射集，除非它缩减为一点。n 形为的射线是凸集，但不是仿射集。

15、如果基点，则它是凸锥。n 任意子空间都是仿射集和凸锥(因而是凸集)。2.3.1 超平面与半空间l 超平面(hyperplane)n ，。n 线性方程组的解集，从而是仿射集。n 法向量(normal vector)为的超平面，常数决定着超平面和原点之间的偏移：其中是超平面上的任意点：lnn 超平面由偏移加上与法向量正交的所有向量组成图2.12 中的超平面例2.18 竞争性厂商的净收入函数是包含常数利润为的生产计划的超平面，有时称为等利润线(isoprofit lines)l (闭)半空间(halfspace) 其中n 半空间是凸集，但不是仿射集。图2.14 中的半空间l 半空间的另一表示： ，

16、n 解释：半空间由加上与(外向法)向量的夹角成钝角或直角的任意向量组成图2.15 由决定的半空间l 半空间的边界为超平面l 开半空间(open halfspace)为半空间的内部2.3.2 欧几里德球、赋范球和赋范锥l 欧几里德球(Euclidean ball)，简称球：其中，是中心，标量为半径。l 欧几里德球的另一表达式l 欧几里德球是凸集l 赋范球(norm ball)是凸集2.3.3 多面体l 多面体(polyhedron) n 多面体是有限个半空间和超平面的交集n 仿射集(如子空间、超平面、直线等)、射线、线段和半空间都是多面体。n 多面体是凸集图2.13 多面体l 多面体的简单表达

17、其中，2.4 保持凸性的运算2.4.1 交2.4.2 仿射函数2.4.1 交l 两个凸集之交是凸集l 任意凸集之交是凸集l 子空间、仿射集和凸锥在任意个交下也是闭的。 n 如：多面体是半空间和超平面(它们都是凸集)之交，因而是凸集。2.4.2 仿射函数l 函数是仿射的(affine)，其中l 集合是凸的，是仿射的是凸的。l 是仿射的是凸的。l 例子n 缩放(scaling)和移动(translation)u 集合是凸的，集合和是凸的其中， l 两个集合的和l 和是凸的是凸的l 和是凸的笛卡尔乘积(Cartesian product)是凸的l 集合在函数下的像是例2.20 (多面体) 多面体P

18、可表示为和原点的笛卡尔乘积在仿射函数下的逆像2.5 分离超平面和支撑超平面2.5.1 分离超平面定理2.5.2 支撑超平面2.5.1 分离超平面定理l 分离超平面定理(separating hyperplane theorem)凸集，；，l 超平面称为和的分离超平面(separating hyperplane)。图2.17 分离超平面l 一种特殊情形时的证明设集合和的(欧几里德)距离为正数，且达到最小距离：定义：我们将证明仿射函数在在非正，而在上非负，即超平面分离和。这一超平面与和之间的线段垂直，并且经过其中心，如图2.18。图2.18 分离超平面的构造先证明在上非负，关于在上非正的证明相似。

19、假设存在点，满足： (2.4)则可表示为：式(2.4)意味着。于是，因此对一些很小的，我们有也即，点比更靠近。由于是凸集并且包含和，因此，。但这是不可能的，因为被假设为中最靠近的点。2.5.2 支撑超平面l 设，。，则超平面称为在点的支撑超平面(supporting hyperplane)。l 几何解释：超平面与相切于点，并且半空间包含。如图2.20。图2.20 超平面在点处支撑l 支撑超平面定理(supporting hyperplane theorem)对任意非空凸集和任意边界点，在点处存在的支撑超平面。n 如果的内部非空，通过对集合和应用分离超平面定理，结果立即可得n 如果的内部为空，则必然位于维数小于的仿射集上，并且任意包含仿射集的超平面包含和，从而为(平凡)支撑超平面。l 正规化(normalization)n 超平面n 正规化u 选择，或者u 对某些79