第 1章凸分析的基本概念
凸集和凸函数在优化模型中非常有用，是一种便于分析和算法设计的内涵丰富的结构 .这个结构的主体可以归结为几条基本性质 .例如，每个闭的凸集合都可以被支撑该集合的超平面所描述；凸集边界上的每个点都可以通过该集合的相对内点集来逼近，以及包含于闭凸集的每条半直线当被平移到该集合中的任意一个点发出的时候仍然包含于该集合.不过，尽管有这些好的性质，凸集及其分析并非完全没有理论和应用上难以处理的异常和例外情况 .例如，不同于仿射的紧集，像线性变换和向量和这样的某些基本运算并不保持闭凸集的闭性不变 .这会使得某些优化问题的处理，包括最优解的存在性和对偶性，变得复杂起来 .因此，有必要认真对待凸集的理论和应用的学习 .第 1章的目标是建立凸集学习的基础，特别是要强调与优化有关的问题 .1.1凸集与凸函数本章将介绍凸集合与凸函数相关的基本概念，这些内容将贯穿本书所有的后续章节 .附录 A列举了本书将用到的线性代数和实分析的定义、符号和性质.首先我们给出凸集合的定义如下 见图 1.1.1.定义 1.1.1 .n的子集 C被称为凸集，如果其满足x 1 . y C, . x, y C, . [0, 1]依惯例我们认为空集是凸的 .通常根据问题的背景，我们可容易地判定某特定凸集是否为非空 .然而多数情况下，我们会尽量说明集合是否为非空，从而降低模糊性 .命题 1.1.1给出了一些保持集合凸性不变的集合变换.命题 1.1.1 a任意多个凸集 {Ci | i I}的交集 iI Ci是凸集.图 1.1.1凸集的定义 .凸集中任意两点的连线线段都包含在集合内部，因此左图中的集合是凸集，而右图中的不是 .b任意两个凸集 C1与 C2的向量和 C1 C2是凸集.c对任意凸集 C和标量 ，集合 C是凸集 .另外，如 1, 2为正标量，则以下集合是凸的，1 2C = 1C 2C.d凸集的闭包 closure与内点集 interior是凸集.
e凸集在仿射函数下的象和原象是凸集.
证明证明的思路是直接利用凸集的定义 .在 a中，我们在交集 iI Ci中任取两点 x，y.由于每个 Ci都是凸集，x和 y间的线段被每个 Ci所包含,因而也属于它们的交集.类似地在 b中，任取 C1 C2中的两点，可以用 x1 x2和 y1 y2表示，其中 x1,y1 C1且 x2,y2 C2.对任意 [0, 1]有如下关系x1 x2 1 . y1 y2= x1 1 . y1 x2 1 . y2.由于 C1和 C2分别是凸集，上式右侧中两个小括号代表的向量分别属于 C1和 C2，而它们的向量和属于 C1 C2.因此根据定义 C1 C2是凸集.对 c的证明留给读者作为练习.对 e可用类似 b的方法来证明.为证明 d，考虑某凸集合 C，以及 C的闭包中任取的两点 x与 y.根据闭包的性质可得，在 C中存在序列 {xk}. C和 {yk}. C分别收敛到 x与 y，即 xk x且 yk y.对任意 [0, 1]，我们构造一收敛到 x 1 . y的序列 {xk 1 . ykd，由于 C是凸集，则该序列被包含在 C内.我们可得到 x 1 . y属于 C的闭包，因此凸集 C的闭包也是凸集 .类似地，在 C的内点集中任取两点 x与 y并构造分别以 x，y为中心且半径 r足够小的开球，使得它们都被包含在 C内.对任意 [0, 1]，构造以 x 1 . y为中心 r为半径的开球 .则该球内的任意点都可表示为 C中向量 x z和 y z的凸组合 x z 1 . y z，其中 IzI r.因此该开球属于 C，即凸组合 x z 1 . y z属于 C的内点集 .因此集合 C的内点都可表示为内点的凸组合 x 1 . y，即 C的内点集是凸集.口几个特殊的凸集我们现在来介绍常用的特殊凸集 .超平面 hyperplane是由一个线性等式定义的集合，形式为 {x | a;x = b}，其中 a为非零向量而 b为标量 .半空间 half space是由一个线性不等式定义的集合，可写为 {x | a;x《 b}，其中 a为非零向量而 b为标量 .易验证超平面和半空间都是凸闭集 .多面体 polyhedral是有限个半空间的非空交集，可写为如下形式{x | a;j x《 bj,j =1, ,r},其中 a1, ,ar和 b1, ,br分别为 n中的一组向量和一组标量 .作为有限个半空间的交集，多面体也是凸闭集 [见命题 1.1.1a].称集合 C为锥体 cone如果对所有 x C和常数 0都满足 x C.通常锥体并不一定是凸集，也不一定包含原点，但任何非空锥体的闭包必然包含原点 见图 1.1.2.多面体锥 polyhedral cone是可写作如下形式的集合C = {x | a;jx《 0,j =1, ,r},其中 a1, ,ar为 n中的一组向量 .线性代数中介绍的子空间则是多面体锥的一种特例，同时多面体锥则是多面体的一种特例 .1.1.1凸函数现在我们给出实值凸函数的定义 见图 1.1.3.n定义 1.1.2令 C为 的凸集，则称函数 f : C 为凸函数 convex图 1.1.2凸锥体和非凸锥体 .图 a和 b中的锥体是凸集，而 c中的锥体由两条过原点的直线组成，是非凸的 .图 a中的锥体是多面体 .图 b中的锥体不包含原点 .图 1.1.3凸函数 f : C 贤的定义 .任意两个函数点的线性插值 fx 1 . fy大于或等于实际的函数值 fx 1 . y叫，其中 可在 [0, 1]中任意取值 .function如果fx 1 . y《 fx 1 . fy, . x, y C, . [0, 1] 1.1注意在我们的定义中，定义域 C为凸集是函数 f : C 为凸函数的先决条件.因此当称某函数为凸函数时，通常默认其定义域为凸集 .现在我们介绍凸函数的几种拓展定义 .函数 f : C 被称为严格凸函数 strictly convex，如果其满足式 1.1且不等式处处被严格满足，即式 1.1对所有满足 x y的向量 x, y C及所有 0, 1都取不等号 .=函数 f : C 被称为凹的 concave如果 .f为凸函数，注意先决条件是 C为凸集.一个凸函数的典型例子是仿射函数 a.ne function，这类函数形如 fx= a;x b，其中 a n而 b ；其凸性可用凸函数的定义直接验证 .n另一个典型例子是范数函数 II.对任意 x, y 及 [0, 1]，通过三角形不等式我们可得到Ix 1 . yI《 IxI I1 . yI = IxI 1 . IyI,因此 II是凸函数.令 f : C 为任一函数，而 为标量，则集合 {x C | fx《 }与集合 {x C | fx }被称为 f的水平集 level sets.如果 f是凸函数，则其水平集都为凸集 .为验证这一事实，我们观察到如果两点 x, y C满足 fx《 且 fy《 ，由于 C是凸集，则任意 [0, 1]都使得 x 1 . y C.由于 f又是凸函数，我们可推出fx 1 . y《 fx 1 . fy《 ,即函数的水平集 {x C | fx《 }是凸集 .类似地可证出如 f为凸函数，则其水平集 {x C | fx }亦为凸集 .值得注意的是，由函数水平集是凸集并不能推出函数是凸函数；例如，函数 fx= J|x|的所有水平集为凸集，但 f并非凸函数.扩充实值凸函数为便捷起见，我们往往希望所考虑的凸函数定义在整个 n空间上 而非仅仅定义在某一凸子集上 并且处处取有限实值，因为从数学的角度讲这类函数更简单 .然而在很多优化问题和对偶问题的实际情况中，某些操作常使对象函数取到无限值，从而失去良好的性质 .例如下列函数fx = sup fix,iI其中 I为一个无限序数集合，即使 fi都是实函数， f仍可能在某些点取值 ；另一例子则为，实函数的共轭函数常常会在某些点取到无限值 见1.6节.此外，我们还会遇到一些凸函数 f仅仅定义在某凸子集上，却无法将其拓展为全空间上的实凸函数 [例如，函数 f : 0, 可定义为 fx=1x便无法拓展 ].在这种情况下，相对于把 f局限在 C上，更方便的做法是把定义域拓展到整个 n空间并允许 f在某些点取值无限.基于上述原因，我们将引入扩充实值 extended real-valued函数的概念，即定义在全空间 n上且可在一些点上取值 .或 的函数 .为了刻画这样的函数，我们先来介绍上图 epigraph的概念.n考虑定义域为某子集 X . 的函数 f : X [., ]，则其上图是 n 1的子集，定义如下epif= {x, w | x X, w ,fx《 wd.函数 f的有效定义域 e.ective domain则定义为如下集合domf= {x X | fx d 见图 1.1.4.我们易得出 domf= {x |存在 w 使得x, w epifd,n即 domf为 epif在 自变量 x的空间 上的投影 .如果把 f的定义域限制为其有效定义域，函数的上图不变 .类似地，如果扩展 f的定义域到n并对任意 x X定义函数值为 fx= ，新函数的上图和有效定义域亦不变.图 1.1.4扩充实值的凸函数和非凸函数，及其分别的上图和有效定义域 .有两种特殊情况我们必须首先排除在外，即当 f处处为 的情况 [当且仅当 epif为空 ]，以及当函数在某些点取值 .的情况 [当且仅当 epif包含竖直直线 ].如果存在 x X使得 fx 且对任意 x X满足 fx .，我们称 f为真的 proper，反之我们则称函数 f为非真的 improper.简而言之，函数 f为真当且仅当其上图为非空且不包含任何竖直直线.我们试图为扩充实值函数定义凸性，传统对实凸函数的定义方法会遇到这样的困难，若 f既能取值 .也能取值 ，则插值项 fx 1 .fy变成了不可求和的 . 该情况仅在 f非真时发生，但是这种函数却在证明和其他分析中常常出现，因此我们并不希望事先排除它们的存在 ，引入上图的概念恰可有效地回避这个难题，其引申出的凸函数定义如下 .n定义 1.1.3令 C为 的凸子集，则扩充实值函数 f : C [., ]为凸函数当 epif是 n 1的凸子集.依定义 1.1.3我们容易证出，凸函数 f的有效定义域 domf，水平集 {x C | fx《 d和 {x C | fx d都是凸集，其中 可取任意标量值.更进一步，如果 f处处满足 fx 或处处满足 fx .，则fx 1 . y《 fx 1 . fy, . x, y C, . [0, 1], 1.2因此针对扩充实值函数的定义 1.1.3和之前针对实凸函数的定义 1.1.2是一致的.我们已建立了扩充实值函数的凸性与其上图的凸性的等价关系，因而很多针对凸集的结论都可应用于凸函数 如证明函数的凸性等 .反向也是可行的，我们可以用分析凸函数的方法来分析集合的相关性质，如对集合nnX . 可定义其示性函数 indicator function : ., ]为 0, x X,x | X=,其他.具体道来，一集合为凸集当且仅当其示性函数为凸函数，而且集合非空当且仅当其示性函数为真.凸函数 f : C ., ]被称为严格凸函数 strictly convex，如果不等式 1.2对任意满足 x = y的 x, y domf及任意 0, 1都严格成立，即取不等号 .函数 f : C [., ]被称为凹函数当函数 .f: C [., ]为凸函数，其中 C为凸子集.有时我们会遇到定义域 C非凸的函数，但是若限制定义域为 C的凸子集，得到的新函数是凸函数 .我们对这种特例给出如下的严格定义.定义 1.1.4令 C和 X为 n维欧氏空间 n的子集，其中 C为 X的非空凸子集，即 C . X.则称扩充实值函数 f : X [., ]为在 C上的凸函数 convex over C，如果把 f的定义域限制在 C后得到的新函数是凸的，也即，函数 f.: C [., ]是凸函数，其中对所有 x C函数值 f.定义为 f.x= fx.当把扩充实值真凸函数的定义域替换为其有效定义域，原函数就变成了实凸函数 .这样一来，对新函数可直接应用针对实凸函数的结论和性质，同时也避免了涉及 的运算 .因此，即使不引入扩充实值函数 ,我们依然可以推导出几乎所有凸函数的理论 .反之，我们也可以把扩充实值函数当作规范，在其框架下推演凸函数的理论， Rockafellar [Roc70]使用的就是这种规范.后续章节中我们将采用更灵活的方式，根据具体背景决定考虑采用实值函数或是扩充实值函数，以方便分析具体的问题 .1.1.2函数的闭性与半连续性如果某个函数 f : X [., ]的上图是闭集，我们称 f为闭函数 .闭性与经典的下半连续性的概念有关 .回顾一下，函数 f是在向量 x X处下半连续的，如果fx《 lim inf fxkk对于每个满足 xk x的点列 {xk}. X成立 .我们称 f是下半连续的 lower semicontinuous，如果它在定义域 X的每一点 x处都是下半连续的.我们称 f是上半连续的 upper semicountinous，如果 .f是下半连续的.这些定义与针对实函数的相应定义是一致的 [参见定义 A.2.4c].以下命题将函数的闭性、下半连续性和函数水平集的闭性联系起来 .见图 1.1.5.图 1.1.5函数上图和它的水平集关系的示意图 .易见水平集 {x | fx . }经过平移后等同于 epif和 切片 {x, | x贤 n}的交集 .这表明 epif为闭当且仅当所有的水平集为闭 .命题 1.1.2对于函数 f : n [., ]，以下各款等价：i水平集 V = {x | fx《 d对每个标量 均为闭.
ii函数 f为下半连续的.
iii集合 epif为闭.
证明如果 fx= 对所有 x成立，那么结果是平凡的，显然成立 .n我们假定 fx 对至少一个 x 成立 .这样 epif就是非空的，且 f至少有一个非空的水平集.先来证明 i蕴含 ii.假定水平集 V对于每个标量 都是闭的.反设fx lim inf fxkk对某个 x和收敛到 x的点列 {xk}成立，并且令 为满足fx lim inf fxkk的标量 .那么必存在子列 {xk}K使得 fxk《 对所有 k K成立 .于是 {xk}K . V成立 .由于 V是闭的， x必然也属于 V，于是 fx《 ，从而导出矛盾.n下面证明 ii蕴含 iii.假定 f在 上为下半连续，并令 x, w为点列{xk,wkd . epif的极限 .于是我们有 fxk《 wk，进而令 k ，由 f在 x处的下半连续性，我们得到fx《 lim inf fxk《 wk于是，x, w epif，故 epif为闭.最后证明 iii蕴含 i.假定 epif为闭，且令 {xk}为点列，它收敛到某个 x且属于对应于某个标量 的水平集 V .于是 xk, epif对于所有的 k成立，并且 xk, x, ，因而由于 epif为闭，我们有 x, epif.故 x属于 V .这意味着这个集合是闭的.口在大部分推导中，我们倾向于采用闭性的概念，而较少用到下半连续性.其中的一个原因是，不同于闭性，下半连续性是一个与定义域有关的性质.例如，由 0,x 0, 1;fx=, x 0, 1.定义的函数 f : ., ]既不是闭的也不是下半连续的；但如果把它的定义域限制到 0, 1上，就变成为下半连续 .另一方面，如果函数 f : X [., ]具有闭的有效定义域 domf且在每个 x domf处均为下半连续，那么 f必然是闭的 .我们把这个结论叙述为一个命题.其证明可以据命题 1.1.2证明 ii蕴含 iii的过程给出.命题 1.1.3令 f : X [., ]为一函数 .如果它的有效定义域 domf是闭的，且 f在每个 x domf处均是下半连续的，那么函数 f是闭的.举例来说，集合 X的示性函数为闭当且仅当 X是闭的 当的部分可以根据上述命题得出，而仅当的部分可以用上图的定义导出 .更一般地，如果 fX是形如 fx,x X fX x= ,其他的函数，其中 f : n 为连续函数，那么可以证明 fX是闭的当且仅当 X是闭的.最后需要指出非真的闭凸函数非常特殊：它不能在任何点上取有限值，因此它具有如下形式 .,x domf,fx=, x domf.n为明白其中的原因，让我们来考虑非真的闭凸函数 f : [., ]，并假定存在着某个 x使得 fx为有限 .令 x满足 fx= . 这样的点必然存在，因为 f是非真的并且 f不恒等于 .因为 f是凸的，可知每个点k . 11xk = x x, . k =1, 2, kk 都满足 fxk= .，同时有 xk x.因为 f是闭的，这意味着 fx= .，从而导出矛盾.总之，非真的闭凸函数在任何点都不能取有限值 .
1.1.3凸函数的运算我们可以通过几种途径来验证函数的凸性 .像仿射函数 a.ine func-tions和范数 模,norms这样的一些常见函数是凸的 .多面体函数 poly-hedral function是一类重要的凸函数，根据定义是真凸函数，且其上图是多面体 polyhedral set.从已知的凸函数出发，可以通过保持凸性的运算来生成其他凸函数.保持凸性的主要运算如下：a与线性变换做复合运算.
b与非负标量相加或相乘.
|
購物車/收銀台(0) | 在線留言板
| 付款方式
| 運費計算
| 聯絡我們
| 幫助中心 |
加入書簽
HOME
新書上架
