半小时梳理凸优化ppt课件.ppt

《半小时梳理凸优化ppt课件.ppt》由会员分享，可在线阅读，更多相关《半小时梳理凸优化ppt课件.ppt（49页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、凸优化初步 七月算法 邹博 2015年3月31日1经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用主要内容o凸集基本概念n凸集保凸运算n分割超平面n支撑超平面o凸函数基本概念n上境图nJensen不等式n凸函数保凸运算o凸优化一般提法n对偶函数n鞍点解释n用对偶求解最小二乘问题n强对偶KKT条件22经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用思考凸集和凸函数oy=x2是凸函数，函数图像上位于y=x2上方的区域构成凸集。n凸函数图

2、像的上方区域，一定是凸集；n一个函数图像的上方区域为凸集，则该函数是凸函数。n稍后给出上述表述的形式化定义。o因此，学习凸优化，考察凸函数，先从凸集及其性质开始。33经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用凸集o集合C内任意两点间的线段均在集合C内，则称集合C为凸集。44经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用凸集55经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者

3、购买商品的价款或接受服务的费用超平面和半空间o超平面hyperplaneo半空间halfspace66经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用超平面和半空间77经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用多面体o多面体有限个半空间和超平面的交集。o仿射集(如超平面、直线)、射线、线段、半空间都是多面体。o多面体是凸集。o此外：有界的多面体有时称作多胞形(polytope)。n注：该定义略混乱，不同文献的含义不同。88经营

4、者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用多面体99经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用保持凸性的运算o集合交运算n思考：如何证明？(提示：根据定义)o仿射变换n函数f=Ax+b的形式，称函数是仿射的：即线性函数加常数的形式o透视变换o投射变换(线性分式变换)1010经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用集合交运算：半空间的交1

5、111经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用仿射变换o仿射变换n伸缩、平移、投影o若f是仿射变换，n若S为凸集，则f(S)为凸集；n若f(S)为凸集，则S为凸集。1212经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用透视变换o透视函数对向量进行伸缩(规范化)，使得最后一维的分量为1并舍弃之。o透视的直观意义n小孔成像1313经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费

6、者购买商品的价款或接受服务的费用透视变换的保凸性o凸集的透视变换仍然是凸集。o思考：反过来，若某集合的透视变换是凸集，这个集合一定是凸集吗？1414经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用投射函数(线性分式函数)o投射函数是透视函数和仿射函数的复合。og为仿射函数：o定义f为线性分式函数o若c=0,d0，则f即为普通的仿射函数。1515经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用分割超平面o设C和D为两不相交的凸集，则存

7、在超平面P，P可以将C和D分离。o注意上式中可以取等号：n所以：逆命题：“若两个凸集C和D的分割超平面存在，C和D不相交”为假命题。n加强条件：若两个凸集至少有一个是开集，那么当且仅当存在分割超平面，它们不相交。1616经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用分割超平面1717经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用分割超平面的构造o两个集合的距离，定义为两个集合间元素的最短距离。o做集合C和集合D最短线段的垂直平分

8、线。1818经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用支撑超平面o设集合C，x0为C边界上的点。若存在a0，满足对任意xC，都有 成立，则称超平面 为集合C在点x0处的支撑超平面。o凸集边界上任意一点，均存在支撑超平面。o反之，若一个闭的非中空（内部点不为空）集合，在边界上的任意一点存在支撑超平面，则该集合为凸集。1919经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用思考o如何定义两个集合的“最优”分割超平面？n找到集合“边

9、界”上的若干点，以这些点为“基础”计算超平面的方向；以两个集合边界上的这些点的平均作为超平面的“截距”n支持向量：support vectoro若两个集合有部分相交，如何定义超平面，使得两个集合“尽量”分开？n注：上述“集合”不一定是凸集，可能是由若干离散点组成。若一组集合为(x,1)，另一组集合为(x,2)，则为机器学习中的分类问题。2020经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用凸函数o若函数f的定义域domf为凸集，且满足2121经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到

10、的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用一阶可微o若f一阶可微，则函数f为凸函数当前仅当f的定义域domf为凸集，且2222经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用进一步的思考o结合凸函数图像和支撑超平面理解该问题o对于凸函数，其一阶Taylor近似本质上是该函数的全局下估计。o反之，如果一个函数的一阶Taylor近似总是起全局下估计，则该函数是凸函数。o该不等式说明从一个函数的局部信息，可以得到一定程度的全局信息。2323经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔

11、偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用二阶可微o若函数f二阶可微，则函数f为凸函数当前仅当dom为凸集，且o若f是一元函数，上式表示二阶导大于等于0o若f是多元函数，上式表示二阶导Hessian矩阵半正定。2424经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用凸函数举例2525经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用上境图o函数f的图像定义为：o函数f的上境图(epigraph)定义为：262

12、6经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用凸函数与凸集o一个函数是凸函数，当且仅当其上境图是凸集。n思考：如何证明？(提示：定义)o进一步，一个函数是凹函数，当且仅当其亚图(hypograph)是凸集。2727经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用Jensen不等式：若f是凸函数o基本Jensen不等式o若o则o若o则2828经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金

13、额为消费者购买商品的价款或接受服务的费用 Jensen不等式是几乎所有不等式的基础o利用f(E(x)E(f(x)，(f是凸函数)，证明下式D0o利用y=-logx是凸函数，证明：n提示：任取a,b0，=0.5带入基本Jensen不等式2929经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用保持函数凸性的算子o凸函数的非负加权和o凸函数与仿射函数的复合o凸函数的逐点最大值、逐点上确界3030经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的

14、费用凸函数的逐点最大值of1,f2均为凸函数，定义函数f：o则函数f为凸函数。3131经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用思考o逐点上确界和上境图的关系n一系列函数逐点上确界函数对应着这些函数上境图的交集。n直观例子oOxy平面上随意画N条直线(直线是凸的虽然直线也是凹的)，在每个x处取这些直线的最大的点，则构成的新函数是凸函数；o同时：N条直线逐点求下界，是凹函数；o在Lagrange对偶函数中会用到该结论。3232经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔

15、偿的金额为消费者购买商品的价款或接受服务的费用凸优化o优化问题的基本形式3333经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用优化问题的基本形式o优化问题的域o可行点(解)(feasible)nxD，且满足约束条件o可行域(可解集)n所有可行点的集合o最优化值o最优化解3434经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用凸优化问题的基本形式ofi(x)(0i m)为凸函数，hj(x)(1i p)为仿射函数o凸优化问题的重要性质

16、n可行域为凸集n局部最优解即为全局最优解3535经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用对偶问题o一般优化问题的Lagrange乘子法oLagrange函数n对固定的x，Lagrange函数L(x,v)为关于和v的仿射函数3636经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用Lagrange对偶函数(dual function)oLagrange对偶函数o若没有下确界，定义：o根据定义，显然有：对0，v，若原优化问题有最优

17、值p*，则o进一步：Lagrange对偶函数为凹函数。3737经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用左侧为原函数，右侧为对偶函数3838经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用鞍点解释o为表述方便，假设没有等式约束，只考虑不等式约束，结论可方便的扩展到等式约束。o假设x0不可行，即存在某些i，使得fi(x)0。则选择 ，对于其他乘子，o假设x0可行，则有fi(x)0,(i=1,2,.,m),选择o有：3939经营者

18、提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用鞍点：最优点o而原问题是：o从而，原问题的本质为：o而对偶问题，是求对偶函数的最大值，即：o而：4040经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用证明：o对于任意的(x,y)domf4141经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用线性方程的最小二乘问题o原问题oLagrange函数oLagrang

19、e对偶函数n对L求x的偏导，带入L，得到gn对g求v的偏导，求g的极大值，作为原问题的最小值4242经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用求L的对偶函数4343经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用求对偶函数的极大值4444经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用极小值点o极小值：o极小值点的结论，和通过线性回归计算得到的结

20、论是完全一致的。n线性回归问题具有强对偶性。4545经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用强对偶条件o若要对偶函数的最大值即为原问题的最小值，考察需要满足的条件：4646经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用Karush-Kuhn-Tucker(KKT)条件4747经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用参考文献oConvex Optimization,Stephen Boyd,Lieven Vandenberghe,Cambridge University Press,2004n中译本：王书宁，许鋆，黄晓霖 译，凸优化，清华大学出版社，2013o同济大学数学教研室 主编，高等数学，高等教育出版社，1996o同济大学数学系 编，工程数学线性代数(第五版)，高等教育出版社，2007484849