betway必威体育我们先来介绍上图 (epigraph) 的概念. 6 凸优化理论 考虑定义域为某子集 X ? n+

当前位置:betway必威体育 > betway必威体育 > betway必威体育我们先来介绍上图 (epigraph) 的概念. 6 凸优化理论 考虑定义域为某子集 X ? n+
作者: betway必威体育|来源: http://www.enjoyhs.com|栏目:betway必威体育

文章关键词:betway必威体育,凸子集

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

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!