资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章,最优化问题与凸分析基础,在日常生活中,无论做什么事情,总是有多种方案可供选择,并且可能出现多种不同的结果。我们在做这些事情的时候,总是自觉不自觉的选择一种最优方案,以期达到最优结果。这种追求最优方案以达到最优结果的学科就是最优化。寻求最优方案的方法就是最优化方法。这种方法的理论基础就是最优化理论,而凸分析又是最优化理论的基础之一。,第一页,编辑于星期五:十点 四分。,1.,最优化问题,最优化问题:求一个一元函数或多元函数的极值。,在微积分中,我们曾经接触过一些比较简单的极值问题。下面通过具体例子来看看什么是最优化问题。,第二页,编辑于星期五:十点 四分。,1.1,最优化问题的例子,例,1,对边长为,a,的正方形铁板,在四个角处剪去相等,的正方形以制成方形无盖水槽,问如何剪法使水槽,的容积最大?,解:设剪去的正方形边长为,x,,由题意易知,此问,题的数学模型为,,第三页,编辑于星期五:十点 四分。,配料,每磅配料中的营养含量,钙,蛋白质,纤维,每磅成本(元),石灰石,谷物,大豆粉,0.380 0.00 0.00,0.001 0.09 0.02,0.002 0.50 0.08,0.0164,0.0463,0.1250,例,2.,(混合饲料配合)设每天需要混合饲料的批量为,100,磅,这份饲料必须含:至少,0.8%,而不超过,1.2%,的钙,;,至少,22%,的蛋白质,;,至多,5%,的粗纤维。假定主要配料包括石灰石、谷物、大豆粉。这些配料的主要营养成分如下表所示。试以最低成本确定满足动物所需营养的最优混合饲料。,第四页,编辑于星期五:十点 四分。,解,:,根据前面介绍的建模要素得出此问题的数学模型如下,:,设 是生产,100,磅混合饲料所须的石灰石、谷物、大豆粉的量(磅)。,第五页,编辑于星期五:十点 四分。,1.2,最优化问题的数学模型,一般形式,向量形式,其中,第六页,编辑于星期五:十点 四分。,目标函数,不等式约束,等式约束,称满足所有约束条件的向量 为,可行解,或可行点,,全体可行点的集合称为,可行集,记为,。,若 是连续函数,则 是闭集。,第七页,编辑于星期五:十点 四分。,在可行集中找一点 ,使目标函数 在该点取最小值,即满足:的过程即为最优化的求解过程。,称为问题的,最优点或,最优解,,称为,最优值,。,定义,1,:,整体(全局)最优解:,若 ,对于一切 ,恒有 则称 是最优化问题的整体最优解。,定义,2,:,局部最优解:,若 ,存在某邻域 ,使得对于一切 ,恒有 则称 是最优化问题的局部最优解。其中,严格最优解:,当 ,有 则称 为问题的严格最优解。,第八页,编辑于星期五:十点 四分。,f(X),局部最优解,整体最优解,第九页,编辑于星期五:十点 四分。,1.3,最优化问题的分类,与时间的关系:静态问题,动态问题,是否有约束条件:有约束问题,无约束问题,函数类型:线性规划,非线性规划,第十页,编辑于星期五:十点 四分。,2,、梯度与,Hesse,矩阵,2.1,等值线,二维问题的目标函数 表示三维空间中的,曲面。在空间直角坐标系中,平面与曲面的交线在,平面上的投影曲线为,取不同的值得到不同的投影曲线。每一条投影曲线,对应一个值,所以我们称此投影曲线为目标函数的,等值线,或,等高线,。,第十一页,编辑于星期五:十点 四分。,当常数取不同的值时,重复上面的讨论,在平面上得到一族曲线,等值线,.,等值线的形状完全由曲面的形状所决定;反之,由等高线的形状也可以推测出曲面的形状,第十二页,编辑于星期五:十点 四分。,例,在坐标平面 上画出目标函数,的等值线,解,:,因为当目标函数取常数时,曲线表示是以原点为圆心,半径为的圆因此等值线是一族以原点为圆心的同心圆(如图所示),第十三页,编辑于星期五:十点 四分。,2.2 n,元函数的可微性与梯度,梯度:多元函数 关于 的,一阶导数,第十四页,编辑于星期五:十点 四分。,Hesse,矩阵:多元函数 关于 的二阶偏导数矩阵,第十五页,编辑于星期五:十点 四分。,例:求目标函数,的梯度和,Hesse,矩阵。,解:因为,则,又因为:,故,Hesse,阵为:,第十六页,编辑于星期五:十点 四分。,下面几个公式是今后常用到的:,(,1,),则,(,2,),则,(,单位阵),(,3,),,Q,对称,则,(,4,)若 ,其中,f,:则:,第十七页,编辑于星期五:十点 四分。,3,、多元函数的,Taylor,展开,多元函数,Taylor,展开式在最优化理论中十分重要。,许多方法及其收敛性的证明都是从它出发的。,定理:设 具有二阶连续偏导数。则:,其中 而,0,1,第十八页,编辑于星期五:十点 四分。,多元函数,Taylor,展开其他形式:,第十九页,编辑于星期五:十点 四分。,第二十页,编辑于星期五:十点 四分。,第二十一页,编辑于星期五:十点 四分。,第二十二页,编辑于星期五:十点 四分。,第二十三页,编辑于星期五:十点 四分。,第二十四页,编辑于星期五:十点 四分。,凸集和凸函数在非线性规划的理论中具有重要作用,下面给出凸集和凸函数的一些基本知识。,定义,1,设 ,若对,D,中任意两点 与 ,连接,与 的线段仍属于,D,;换言之,对 ,,D,,,0,1,恒有,+(1-),D,则称,D,为,凸集,。,+(1-),称为 和 的,凸组合,。,n,R,D,),1,(,x,),2,(,x,),1,(,x,),2,(,x,),1,(,x,),2,(,x,a,),1,(,x,a,),2,(,x,a,),1,(,x,a,a,),2,(,x,),1,(,x,),2,(,x,5,、,凸集、凸函数和凸规划,第二十五页,编辑于星期五:十点 四分。,例,规定:欧式空间 是凸集,空集 是凸集,,单点集,x,为凸集,第二十六页,编辑于星期五:十点 四分。,例,:,证明集合,是凸集。其中,,A,为,m,n,矩阵,,b,为,m,维向量。,证明:任取 ,则,所以,,第二十七页,编辑于星期五:十点 四分。,例:给定线性规划 ,,其中 ,,若令 ,则 是凸集。,第二十八页,编辑于星期五:十点 四分。,凸集的性质,有限个凸集的交集仍然是凸集。,设 是凸集,则 是凸集。,设 是凸集,则 是凸集。,凸集的和集仍然是凸集。,设 是凸集,则,是凸集。,推论:设 是凸集,则 也是凸集,,其中 。,第二十九页,编辑于星期五:十点 四分。,定义,3,极点(顶点),:,设,D,是凸集,若,D,中的点,x,不能成为,D,中任何线段上的内点,则称,x,为凸集,D,的极点。,设,D,为凸集,,XD,若,X,不能用,X,(1),D,X,(2),D,两点的,一个凸组合表示为,X=X,(1),+(1-)X,(2),其中,01,,,则称,X,为,D,的一个极点。,定义,2.,凸组合,:设,X,(1),,,X,(2),,,,,X,(k),是,n,维欧式空间中的,k,个点,若存在,1,2,k,满足,0,i,1,(,i=1,2,k),使,X=,1,X,(1),+,2,X,(2),+,k,X,(k),,,则称,X,为,X,(1),,,X,(2),,,,,X,(k),的凸组合。,第三十页,编辑于星期五:十点 四分。,多边形的,顶点,是,凸集的,极点(顶点),。,圆周上的点都是,凸集的,极点(顶点),。,第三十一页,编辑于星期五:十点 四分。,定义,4,设,D,为,R,中非空凸集,若对 ,,D,,,(0,1),恒有,n,),1,(,x,),2,(,x,a,f,+(1-)+(1-),f,(*),),1,(,x,a,),2,(,x,a,),(,),1,(,x,f,a,a,),(,),2,(,x,则称 为,D,上的凸函数;进一步,若 时,,(*),式仅,成立。,),(,x,f,x,f(x),第三十六页,编辑于星期五:十点 四分。,证明:必要性,即,由,Taylor,公式,令 得,第三十七页,编辑于星期五:十点 四分。,设 则,充分性,令,即,所以,同理,第三十八页,编辑于星期五:十点 四分。,定理,3,(二阶条件):,设,D,是,R,中非空开凸集,是定义在,D,上的二次可微函数,则 是,凸函数,的充要条件为对,x,D,0,即,Hesse,矩阵,半正定,。,n,),(,x,f,),(,x,f,),(,2,x,f,),(,2,x,f,若,x,D,0,,即,Hesse,矩阵,正定,,则 为,严格凸函数,。,),(,2,x,f,),(,x,f,第三十九页,编辑于星期五:十点 四分。,证明:必要性,所以,由,Taylor,公式,令 得,因为 为开集。,由一阶条件,所以,由,p,的任意性,半正定。,第四十页,编辑于星期五:十点 四分。,充分性,其中,因为 半正定,故 为凸函数。,所以,严格凸函数?,第四十一页,编辑于星期五:十点 四分。,充分性,其中,因为 正定,,故 为严格凸函数。,所以,第四十二页,编辑于星期五:十点 四分。,例:判断下列函数的凹凸性。,(,1,),(,2,),解,:,第四十三页,编辑于星期五:十点 四分。,若规划,=,=,=,l,j,h,m,i,g,t,s,f,j,i,2,1,0,),(,2,1,0,),(,.,.,),(,min,x,x,x,中,和,-,为凸函数,是线性函数,则上述问题为凸规划。,),(,x,f,),(,x,i,g,),(,x,i,h,定义,6:,凸规划,设,D,为凸集,是定义在,D,上的凸函数,则称规划问题 为凸规划。,第四十四页,编辑于星期五:十点 四分。,例:线性规划 是凸规划。,第四十五页,编辑于星期五:十点 四分。,例:数学规划,易知,与,都是凸函数,所以该规划是凸规划。,第四十六页,编辑于星期五:十点 四分。,对于一般的规划(,P,),其局部最优解不一定是全局最优解,其可行集也未必是凸集。但若(,P,)是凸规划,则有下面的结论。,定理,4,:,设规划(,P,)是凸规划,则,(,1,)(,P,)的可行集,R,为凸集;,(,2,)(,P,)的最优解集合,R*,是凸集;,(,3,)(,P,)的任何局部最优解都是全局最优解,。,定理,5,:,(,1),凸规划的任意局部极小点就是整体极小点,且极小点集合是凸集。,(2),如果凸规划的目标函数是严格凸函数,又存在极小点,则它的极小点还是唯一的。,第四十七页,编辑于星期五:十点 四分。,练习:,1,、求 的梯度和,Hesse,矩阵。,2,、判断函数 的凹凸性。,3,、判断下述非线性规划是否为凸规划?,第四十八页,编辑于星期五:十点 四分。,
展开阅读全文