最优化方法 第一章 最优化问题与凸分析基础.ppt

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