半小时梳理凸优化

凸优化初步七月算法邹博2015年3月31日2/50julyedu.com主要内容凸集基本概念凸集保凸运算分割超平面支撑超平面凸函数基本概念上境图Jensen不等式凸函数保凸运算凸优化一般提法对偶函数鞍点解释用对偶求解最小二乘问题强对偶KKT条件3/50julyedu.com思考凸集和凸函数y=x2是凸函数，函数图像上位于y=x2上方的区域构成凸集。凸函数图像的上方区域，一定是凸集；一个函数图像的上方区域为凸集，则该函数是凸函数。稍后给出上述表述的形式化定义。因此，学习凸优化，考察凸函数，先从凸集及其性质开始。4/50julyedu.com凸集集合C内任意两点间的线段均在集合C内，则称集合C为凸集。5/50julyedu.com凸集6/50julyedu.com超平面和半空间超平面hyperplane半空间halfspace7/50julyedu.com超平面和半空间8/50julyedu.com多面体多面体有限个半空间和超平面的交集。仿射集(如超平面、直线)、射线、线段、半空间都是多面体。多面体是凸集。此外：有界的多面体有时称作多胞形(polytope)。注：该定义略混乱，不同文献的含义不同。9/50julyedu.com多面体10/50julyedu.com保持凸性的运算集合交运算思考：如何证明？(提示：根据定义)仿射变换函数f=Ax+b的形式，称函数是仿射的：即线性函数加常数的形式透视变换投射变换(线性分式变换)11/50julyedu.com集合交运算：半空间的交12/50julyedu.com仿射变换仿射变换伸缩、平移、投影若f是仿射变换，若S为凸集，则f(S)为凸集；若f(S)为凸集，则S为凸集。13/50julyedu.com透视变换透视函数对向量进行伸缩(规范化)，使得最后一维的分量为1并舍弃之。透视的直观意义小孔成像14/50julyedu.com透视变换的保凸性凸集的透视变换仍然是凸集。思考：反过来，若某集合的透视变换是凸集，这个集合一定是凸集吗？15/50julyedu.com投射函数(线性分式函数)投射函数是透视函数和仿射函数的复合。g为仿射函数：定义f为线性分式函数若c=0,d0，则f即为普通的仿射函数。16/50julyedu.com分割超平面设C和D为两不相交的凸集，则存在超平面P，P可以将C和D分离。注意上式中可以取等号：所以：逆命题：“若两个凸集C和D的分割超平面存在，C和D不相交”为假命题。加强条件：若两个凸集至少有一个是开集，那么当且仅当存在分割超平面，它们不相交。17/50julyedu.com分割超平面18/50julyedu.com分割超平面的构造两个集合的距离，定义为两个集合间元素的最短距离。做集合C和集合D最短线段的垂直平分线。19/50julyedu.com支撑超平面设集合C，x0为C边界上的点。若存在a≠0，满足对任意x∈C，都有成立，则称超平面为集合C在点x0处的支撑超平面。凸集边界上任意一点，均存在支撑超平面。反之，若一个闭的非中空（内部点不为空）集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。20/50julyedu.com思考如何定义两个集合的“最优”分割超平面？找到集合“边界”上的若干点，以这些点为“基础”计算超平面的方向；以两个集合边界上的这些点的平均作为超平面的“截距”支持向量：supportvector若两个集合有部分相交，如何定义超平面，使得两个集合“尽量”分开？注：上述“集合”不一定是凸集，可能是由若干离散点组成。若一组集合为(x,1)，另一组集合为(x,2)，则为机器学习中的分类问题。21/50julyedu.com凸函数若函数f的定义域domf为凸集，且满足22/50julyedu.com一阶可微若f一阶可微，则函数f为凸函数当前仅当f的定义域domf为凸集，且23/50julyedu.com进一步的思考结合凸函数图像和支撑超平面理解该问题对于凸函数，其一阶Taylor近似本质上是该函数的全局下估计。反之，如果一个函数的一阶Taylor近似总是起全局下估计，则该函数是凸函数。该不等式说明从一个函数的局部信息，可以得到一定程度的全局信息。24/50julyedu.com二阶可微若函数f二阶可微，则函数f为凸函数当前仅当dom为凸集，且若f是一元函数，上式表示二阶导大于等于0若f是多元函数，上式表示二阶导Hessian矩阵半正定。25/50julyedu.com凸函数举例26/50julyedu.com上境图函数f的图像定义为：函数f的上境图(epigraph)定义为：27/50julyedu.com凸函数与凸集一个函数是凸函数，当且仅当其上境图是凸集。思考：如何证明？(提示：定义)进一步，一个函数是凹函数，当且仅当其亚图(hypograph)是凸集。28/50julyedu.comJensen不等式：若f是凸函数基本Jensen不等式若则若则29/50julyedu.comJensen不等式是几乎所有不等式的基础利用f(E(x))≤E(f(x))，(f是凸函数)，证明下式D≥0利用y=-logx是凸函数，证明：提示：任取a,b0，θ=0.5带入基本Jensen不等式0,0,2baabbaxqxpExqxpxpqpDxpxloglog||30/50julyedu.com保持函数凸性的算子凸函数的非负加权和凸函数与仿射函数的复合凸函数的逐点最大值、逐点上确界31/50julyedu.com凸函数的逐点最大值f1,f2均为凸函数，定义函数f：则函数f为凸函数。32/50julyedu.com思考逐点上确界和上境图的关系一系列函数逐点上确界函数对应着这些函数上境图的交集。直观例子Oxy平面上随意画N条直线(直线是凸的——虽然直线也是凹的)，在每个x处取这些直线的最大的点，则构成的新函数是凸函数；同时：N条直线逐点求下界，是凹函数；在Lagrange对偶函数中会用到该结论。33/50julyedu.com凸优化优化问题的基本形式34/50julyedu.com优化问题的基本形式优化问题的域可行点(解)(feasible)x∈D，且满足约束条件可行域(可解集)所有可行点的集合最优化值最优化解35/50julyedu.com凸优化问题的基本形式fi(x)(0≤i≤m)为凸函数，hj(x)(1≤i≤p)为仿射函数凸优化问题的重要性质可行域为凸集局部最优解即为全局最优解36/50julyedu.com对偶问题一般优化问题的Lagrange乘子法Lagrange函数对固定的x，Lagrange函数L(x,λ,v)为关于λ和v的仿射函数37/50julyedu.comLagrange对偶函数(dualfunction)Lagrange对偶函数若没有下确界，定义：根据定义，显然有：对∀λ≥0，∀v，若原优化问题有最优值p*，则进一步：Lagrange对偶函数为凹函数。38/50julyedu.com左侧为原函数，右侧为对偶函数39/50julyedu.com鞍点解释为表述方便，假设没有等式约束，只考虑不等式约束，结论可方便的扩展到等式约束。假设x0不可行，即存在某些i，使得fi(x)0。则选择，对于其他乘子，假设x0可行，则有fi(x)≤0,(i=1,2,...,m),选择有：iotherwisemixfxfxfxfxLimiii,2,1,0sup,sup01000ijj,0mii,,2,1,040/50julyedu.com鞍点：最优点而原问题是：从而，原问题的本质为：而对偶问题，是求对偶函数的最大值，即：而：xfx0inf,supinf0xLx,infsup0xLx,supinf,infsup00xLxLxx41/50julyedu.com证明：对于任意的(x,y)∈domfyxfyxfxyyx,maxmin,minmaxyxfyxfyxfyxfyxfyxfxyyxxyyx,maxmin,minmax,maxmin,min,max,42/50julyedu.com线性方程的最小二乘问题原问题Lagrange函数Lagrange对偶函数对L求x的偏导，带入L，得到g对g求v的偏导，求g的极大值，作为原问题的最小值43/50julyedu.com求L的对偶函数bAxxxxLTT,TTTTAxAxxbAxxxxL2102令gbAAbAAAAbAAAAbAxxxxLTTTTTTTTTTTTTTT412141212121,44/50julyedu.com求对偶函数的极大值bAAgTTT41bAAAxbAAAAbAAAAbAAAAbAAbAAbAAgTTTTTTTTTTTTTTTT1112122202141令45/50julyedu.com极小值点极小值：极小值点的结论，和通过线性回归计算得到的结论是完全一致的。线性回归问题具有强对偶性。bAAAAbbAAAAAAbbAAAbAAAxxTTTTTTTTTTTTT21111minbAAAxTT146/50julyedu.com强对偶条件若要对偶函数的最大值即为原问题的最小值，考察需要满足的条件：47/50julyedu.comKarush-Kuhn-Tucker(KKT)条件48/50julyedu.com参考文献ConvexOptimization,StephenBoyd,LievenVandenberghe,CambridgeUniversityPress,2004中译本：王书宁，许鋆，黄晓霖译，凸优化，清华大学出版社，2013同济大学数学教研室主编，高等数学，高等教育出版社，1996同济大学数学系编，工程数学线性代数(第五版)，高等教育出版社，2007