凸集、凸函数与凸规划

凸优化数学基础笔记六凸集、凸函数与凸规划现有最优化方法对一般函数只能找到局部最优解判断有无极值点以及它是否为全局最优解要用到函数凸性概念。一般在现实优化问题上我们一般把优化问题变成凸优化问题因为凸优化凸优化Convex OPtimization是数学优化中的一个重要分支研究的是在凸集上极小值的问题。下面首先介绍凸集。从直观上看凸集是这样一些点的集合它的内部没有“洞”hole边界不向内凹。凸集的基本特征是其上任取两点所联成线段上的点依然属于这个集合。在数学上就是采用这种描述方法给凸集下定义的。首先给出凸组合的概念在给出凸集和凸函数的定义并简单讨论凸函数判定方法。1.凸 集Convex Set​Definition 6.1凸组合定义设X1,X2,⋯,Xl1,2,⋯, 是Rn 中的l个已知点。若对于某个点X∈Rn∈ 存在常数α1,α2,⋯,αl≥01,2,⋯,≥0且∑li1αi1∑11 使得X∑li1αiXi∑1则称X 是X1,X2,⋯,Xl1,2,⋯, 的凸组合。若 α1,α2,⋯,αl01,2,⋯,0 且∑li1αi1∑11则称X是X1,X2,⋯,Xl1,2,⋯, 的严格凸组合。​ 考虑两点X11和X22的凸组合Xα1X1α2X21122 其中α1,α2≥01,2≥0 且α1α21121。把 α21−α121−1 代入X 的凸组合中得到XX2α1(X1−X2)21(1−2) 其中α∈[0,1]∈[0,1]。由解析几何知识可知当 α11从0变到1时点X 由点X22 出发沿X1−X21−2 的方向移动到X11 。由此可知X11和X22 所有严格凸组合的集合是不含X11和X22 两端点的线段。​Definition 6.2 凸集的定义设集合C⊆Rn⊆。如果对于任意两点X1,X2∈C1,2∈ 它们的任意两点X1,X2∈C1,2∈ 它们的任意凸组合仍然属于C 则称集合C 为凸集。特别地规定空集是凸集。​Definition 6.3 (半空间的定义)设a∈Rn∈ 且 a≠0,b∈R1≠0,∈1 则集合{X|aTX≥b,X∈Rn}{|≥,∈} 称为Rn 中的一个半空间。​ 容易地验证空间Rn、半空间、超平面、直线、点、球都是凸集。​定理 6.1任意一组凸集的交集仍然是凸集。​证 明设C∩i∈ICi∩∈ ,其中I是{Ci}{} 的下标集Ci 都是凸集。任取X1,X2∈C1,2∈ , 则对于任意i∈I∈ 都有X1,X2∈Ci1,2∈。任取α1,α2∈[0,1]1,2∈[0,1] 且α1α21121因为Ci 是凸集有 α1X1α2X2∈Ci1122∈。于是α1X1α2X2∈∩i∈ICiC1122∈∩∈即C 是凸集。2.凸函数Convex Function​Definition 6.4 凸函数的定义设f:C⊆Rn→R1:⊆→1 , 其中C 为凸集。若对于任意两点X1,X2∈C1,2∈ 和任意一对满足α1α21121 的数α1,α2∈[0,1]1,2∈[0,1] 都有 f(α1X1α2X2)≤α1f(X1)α2f(X2)(1122)≤1(1)2(2) 则称f 为定义在C 上的凸函数。若对于任意一对满足α1α21121的数α1,α2∈(0,1)1,2∈(0,1) 都有f(α1X1α2X2)α1f(X1)α2f(X2)(1)(1)(1122)1(1)2(2)则称f为定义在凸集C上严格凸函数。​Definition 6.5若函数g(X)−f(X)()−()在凸集C 上是严格凸函数则称f是定义在凸集C 上的严格凹函数。​定理 6.2设f:C⊂Rn→R1:⊂→1其中C为非空凸集。若f是凸函数则对于任意实数β, 水平集Dβ{X|f(X)≤β,X∈C}{|()≤,∈} 是凸集。​证 明若Dβ是空集则Dβ 是凸集。以下设Dβ 非空任取X11 ,X2∈Dβ2∈ , 则f(X1)≤β,f(X2)≤β(1)≤,(2)≤ 。设α1,α2∈[0,1]1,2∈[0,1] ,且α1α21121 根据f的凸性必有f(α1X1α2X2)≤α1f(X1)α2f(X2)≤α1βα2ββ(2)(2)(1122)≤1(1)2(2)≤12即 α1X1α2X2∈Dβ1122∈ ,所以 Dβ 是凸集。3.判断凸函数的方法​ 判定一个函数是否为凸函数一般来说比较困难但函数可微时有如下几个定理可供使用。​定理 6.3设f:C⊆Rn→R1:⊆→1 是可微函数其中C 为凸集则f为凸函数的充要条件是∀X1,X2∈C∀1,2∈, 都有f(X2)≥f(X1)∇f(X1)T(X2−X1)(3)(3)(2)≥(1)∇(1)(2−1)​f为严格凸函数的充要条件是∀X1,X2∈C∀1,2∈,且X1≠X21≠2,都有f(X2)f(X1)∇f(X1)T(X2−X1)(4)(4)(2)(1)∇(1)(2−1)证 明1必要性证明已知f是C上的凸函数证明式3。由凸函数定义可知对满足α1α21121 的任意正数α1,α2∈[0,1]1,2∈[0,1]都有f(α1X1α2X2)≤α1f(X1)α2f(X2)(5)(5)(1122)≤1(1)2(2)令α2t2则α11−t11−代入上式中整理得到f(X1t(X2−X1))−f(X1)t≤f(X2)−f(X1)(6)(6)(1(2−1))−(1)≤(2)−(1)令 t→0→0 ,由f的可微性利用一阶Taylor展开式方向导数定义及式6可得∇f(X1)T(X2−X1)≤f(X2)−f(X1)(7)(7)∇(1)(2−1)≤(2)−(1)必要性得证充分性证明任取一对正数α1,α2∈[0,1]1,2∈[0,1] ,且α1α21121考虑点 Xα1X1α2X21122 根据充分性假设应有f(X1)≥f(X)∇f(X)T(X1−X)f(X2)≥f(X)∇f(X)T(X2−X)(8)(8)(1)≥()∇()(1−)(2)≥()∇()(2−)两式分别乘以α11 和α22 后相加得到α1f(X1)α2f(X2)≥f(X)∇f(X)T(α1X1α2X2−X)f(α1X1α2X2)(9)(9)1(1)2(2)≥()∇()(1122−)(1122)由凸函数定义可知f 是C上的凸函数。​ 2命题2充分性可仿照命题1的充分性证得​ 必要性因为严格凸函数本身是凸函数所以∀X1,X2∈C∀1,2∈ ,且X1≠X21≠2 都有f(X2)≥f(X1)∇f(X1)T(X2−X1)(10)(10)(2)≥(1)∇(1)(2−1)以下证明式中只能取号假设存在X1,X2∈C1,2∈ 且X1≠X21≠2 ,满足f(X2)f(X1)∇f(X1)T(X2−X1)(11)(11)(2)(1)∇(1)(2−1)取X12X112X2121122 ,由f 的严格凸性有f(X3)12f(X1)12f(X2)(12)(12)(3)12(1)12(2)把式11代入式12中经整理得f(X3)f(X1)∇f(X1)T(X3−X1)(13)(13)(3)(1)∇(1)(3−1)根据本定理1部分结论得知此时与f的凸性相矛盾。​定 理 6.4设f:C⊆Rn→R1:⊆→1 是二次可微函数C 为非空开凸集则f为C上为凸函数的充要条件是 f(X)() 的Hessian矩阵∇2f(X)∇2() 在凸集C 处处半正定即∇2f(X)⪰0∇2()⪰0 。​定 理6.5设f:C⊆Rn→R1:⊆→1 是二次可微函数C 为非空凸集。若Hessian矩阵∇2f(X)∇2() 在凸集C 上到处正定则 f在C 上为严格凸函数。​ 需要注意该定理的逆命题不真。​ 例如 f(x)x4()4 在R11 上为严格凸函数但是它的Hessian矩阵∇2f(x)12x2∇2()122在点x00 处是半正定的。4.凸规划 Convex Programing​ 凸规划是数学优化中的一个重要概念指目标函数损失函数为凸函数、可行域为凸集的优化问题具有许多的优化性质例如局部最优解就是全局最优解且对偶理论成熟。广泛应用于机器学习信号处理金融工程等领域。Definition 6.6 凸规划问题设f:C⊆Rn→R1:⊆→1 其中 C 是非空凸集合 f 为凸函数则形式如下minf(X)s.t.X∈C(14)(14)min()..∈的优化问题为凸规划问题。更进一步设将可行域的凸集可写为如下形式C{X|gi(X)≥0,i1,⋯,l;hj(X)0,j1,⋯,m,X∈Rn}(15)(15){|()≥0,1,⋯,;ℎ()0,1,⋯,,∈}若g1,g2,⋯,gl1,2,⋯, 都是Rn 上的凸函数h1,h2,⋯,hmℎ1,ℎ2,⋯,ℎ 都是Rn上的线性函数则容易验证C是凸集 。事实上因为−g1,−g2,−gl−1,−2,−都是凸函数根据定理6.2集合Ci{X|−g(X)i≤0,X∈Rn}(i1,2,⋯,l){|−()≤0,∈}(1,2,⋯,) 也都是凸集。此外超平面Pj{X|hj(X)0,X∈Rn}(j1,⋯,m){|ℎ()0,∈}(1,⋯,) 也都是凸集。显然C是C1,⋯,Cl,P1,⋯,Pm1,⋯,,1,⋯, 的交集也是凸集。于是这种情况下凸规划问题又可表示成如下形式minf(X)s.t.{gi(X)≥0,i1,2,⋯,lhj(X)0,j1,2,⋯,m(16)(16)min()..{()≥0,1,2,⋯,ℎ()0,1,2,⋯,如下定理指明凸规划的一个重要性质。​定 理6.6设X∗∗ 是凸规划问题的局部极小值若f是凸函数则X∗∗ 是凸规划问题的局部极小值点若f是严格凸函数则X∗∗ 是凸规划问题的唯一全局极小值点。证 明1使用反证法。假设X∗∗ 不是全局极小值点则必存在Z∈C∈ 使得 f(Z)f(X)()() 。对应Z 与X∗∗ 的任意凸组合Xα1Zα2X∗12∗,其中α1,α2∈(0,1)1,2∈(0,1) 且α1α21121根据f的凸性有f(X)f(α1Zα2X∗)≤α1f(Z)α2f(X∗)α1f(X∗)α2f(X∗)f(X∗)(17)(17)()(12∗)≤1()2(∗)1(∗)2(∗)(∗)由此看到当α1010充分小时X充分接近X∗∗ 注意到此时也有f(X)f(X∗)()(∗)而这与X∗∗ 是局部极小值点相矛盾因此X∗∗ 必是全局极小值。​ (2) 假设X∗∗ 不是唯一全局的极小值点必存在X′∈C′∈ 但X′≠X∗′≠∗使得f(X′)f(X∗)(′)(∗)。考虑中点X12(X′X∗)∈C12(′∗)∈ 。由于 f的严格的凸性有f(X)f(12(X∗X′))12(f(X∗)f(X′))f(X∗)(18)(18)()(12(∗′))12((∗)(′))(∗)此式与X∗∗ 为全局极小值点相矛盾。这就证明了唯一性。​ 由上面的推导可知凸规划有如下优秀的重要性质局部最优即全局最优凸规划的任一局部极小值点都是全局极小值点最优解集为凸集若存在最优解则所有最优解构成一个凸集可微情况下的最优性条件若f可微则x∗∗为全局最优解的情况下的充要条件