最优化方法第1章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,最优化方法,主要内容,第一章 最优化简介,第二章 基本概念和理论基础,第三章 线性规划,第四章 最优化搜索算法结构与一维搜索,第五章 无约束最优化方法,第六章 约束最优化方法,第一章,最优化简介,最优化,寻求,最优方案,的方法称为最优化方法。,最优方案：从所有可能的方案中选择最合理的一,种以达到,最优目标,。,最优目标：与工程设计密切相关。如：产值最大,、,耗能最小,、,速度最快等等。,处理方法：对实际问题建立一个数学模型。,发展过程,运筹学、线性规划、非线性规划、动态规划、组合优化等。,促进最优化发展的主要因素,近代科技与生产发展的需要,计算机技术的飞速发展,参考书目,最优化理论与方法,袁亚湘等编，科学出版社,数学规划讲义,马仲蓄等编，人大出版社,实用线性规划,D.M,希梅尔布劳著,无约束最优化计算方法,邓乃杨等编,基础：高等数学，线性代数,1,最优化问题的数学模型及分类,共同特点：,求,x,1,x,2,x,n,使函数,f,（,x,1,x,2,x,n,）,（被称为目标函数或评价函数）,达到极小,min,；,若求极大,max,，相当于一个,min,（,-,f,）。,优化模型的一般形式,min.,f,(,x,i,y,j,k,),s.t.,g,h,(,x,i,y,j,k,),0,h=1,2,m,其中x,i,为,决策变量（可控制）,y,j,为,已知参数,k,为随机因素,f,g,h,为（一般或广义）函数,建模举例（略）,自看,（一）根据问题的不同特点分类,无约束最优化问题,约束最优化问题,等式约束优化问题,不等式约束优化问题,一般的约束优化问题,以上为标准形式，某些问题可标准化：,1,）,2,）,（二）根据函数类型分类,线性规划：目标函数,、,约束条件都是线性的,二次规划：目标函数为二次函数，约束条件,中的函数为线性的。,非线性规划：目标函数不是一次,or,二次的，,或约束条件中的函数不全是线,性的。,（三）根据函数性质分类,动态与静态,随机与确定,单目标与多目标,（四）解法的分类,解析方法,:,利用函数的分析性质去构造迭代,公式，使之收敛到极值点。,直接方法：按一定的数学原理，用尽量少的,计算量，直接比较函数值的大小。,2,最优化方法解决问题的工作步骤,1,）提出问题：目标、约束、决策变量、参数,2,）建立模型：变量、参数、目标之间的关系,表示,3,）模型求解：数学方法及其他方法,4,）解的检验：制定检验准则、讨论与现实的,一致性,5,）灵敏性分析：参数扰动对解的影响情况,6,）解的实施：回到实践中,7,）后评估：考察问题是否得到完满解决,1,、最优解与极值点,容许解集：,Def1:,若,使得 ，恒有,称 为问题（,p,）的最优解,or,全局极小,值点。,记,g.opt,.global optimum),简,记,opt.,3,基本概念,Def2:,若 ，使得 ，,恒有 ，,称 为问题（,p,）的严格全局极小值点。,Def3:,若 ，,使得 ，恒有,称 为问题（,p,）的局部极小值点。,记,l.,opt.,(,local,optimum,),Def4:,若 ，,恒有 ，,称 为问题（,p,）的严格局部极小值点。,严格,l.opt.,严格,g.opt.,l.opt.,由以上定义，可得到两个简单定理：,Th1,：,问题（,p,）的任意全局极小值点必为局部,极小值点。,Th2,：,若目标,f(x,),和,g(x,),都为定义域上的连续,函数，则：,（,1,）问题（,p的容许解集,R,为闭集。,（,2,）问题（,p,）的最优解集,R,为闭集。,2,、向量和子空间投影定理,(1),n,维欧氏空间：,R,n,点（向量）,：,x,R,n,x,=(,x,1,x,2,x,n,),T,分量,x,i,R,(,实数集,),方向（自由向量）,：,d,R,n,d,0,d,=(,d,1,d,2,d,n,),T,表示从,0,指向,d,的方向,实用中，常用,x+,d,表示从,x,点出发沿,d,方向移动,d,长度得到的点,d,0,x,x+(1/2)d,(2),向量运算：,x,y,R,n,x,y,的内积：,x,T,y,=,x,i,y,i,=x,1,y,1,+x,2,y,2,+,x,ny,n,i=1,x,y,的,距离,：,x-y,=(,x-y,),T,(,x-y,),(1/2),x,的,长度,：,x,=,x,T,x,(1/2),三角不等式,：,x+y,x,y,点列的收敛：,设点列,x,(,k,),R,n,x,R,n,点列,x,(,k,),收敛到,x,，,记,lim,x,(,k,),=,x,lim,x,(,k,),-x,=0,lim,x,i,(,k,),=,x,i,i,k,k,k,x+y,y,x,(3),子空间：设,d,(,1,),d,(,2,),d,(,m,),R,n,d,(,k,),0,m,记,L,(,d,(,1,),d,(,2,),d,(,m,),)=,x=,j,d,j,),j,R,j=1,为由向量,d,(,1,),d,(,2,),d,(,m,),生成的子空间，简记,为,L,。,正交子空间：设,L,为,R,n,的,子空间，其正交子空间为,L,x,R,n,x,T,y,=0,y,L,子空间投影定理,：,设,L,为,R,n,的,子空间。那么,z,R,n,，,唯一,x,L,y,L,使,z,=,x,+,y,且,x,为问题,min ,z-u,s.t.,u,L,的唯一解，最优值为,y,。,特别，,L,R,n,时，正交子空间,L,0,（,零空间,）,规定：,x,y,R,n,，,x,y,x,i,y,i,，,i,类似规定,x,y,，,x=y,，,x y.,一个有用的定理,设,x,R,n,，,R,，,L,为,R,n,的,线性子空间，,(1),若,x,T,y,y,R,n,且,y,0,，,则,x,0,，,0,.,(2),若,x,T,y,y,L,R,n,，,则,x,L,，,0,.,(,特别,L,R,n,时,x,=0,),定理的其他形式：,“若,x,T,y,y,R,n,且,y,0,，,则,x,0,，,0,.”,“,若,x,T,y,y,R,n,且,y,0,，,则,x,0,，,0,.”,“,若,x,T,y,y,R,n,且,y,0,，,则,x,0,，,0,.”,“,若,x,T,y,y,L,R,n,，,则,x,L,，,0,.”,3,、多元函数及其导数,(1),n,元函数：,f,(,x,):,R,n,R,线性函数,：,f(x)=,c,T,x,+b=,c,i,x,i,+,b,二次函数,：,f(x)=(1/2),x,T,Qx,+,c,T,x,+b,=(1/2),i,j,a,ij,x,i,x,j,+,c,i,x,i,+,b,向量值线性函数：,F(x)=Ax+d,R,m,其中,A,为,m,n,矩阵，,d,为,m,维向量,F(x)=(,f,1,(x),f,2,(x),f,m,(x),),T,记,a,i,T,为,A,的第,i,行向量，,f,i,(x,)=,a,i,T,x+d,i,(2),梯度（一阶偏导数向量）：,f,(,x,),R,n,.,线性函数,：,f(x)=,c,T,xb,f(x)=c,二次函数,：,f(x)=(1/2),x,T,Qx,+,c,T,x,+b,f(x)=,Qx,+c,注：,Q,为对称阵,向量值线性函数：,F(x)=Ax+d,R,m,F/x=A,T,(3),Hesse,阵（二阶偏导数矩阵）：,线性函数,：,f(x)=,c,T,x,+b,2,f(x)=,0,二次函数,：,f(x)=(1/2),x,T,Qx,+,c,T,x,+b,2,f(x)=Q,注：,Q,为对称阵,(4),n,元函数的,Taylor,展开式及中值公式：,设,f,(,x,):,R,n,R,，,二阶可导。在,x*,的邻域内,一阶,Taylor,展开式：,f(x)=f(x*)+,f,T,(x*)(x-x*)+o,x-x*,二阶,Taylor,展开式：,f(x)=f(x*)+,f,T,(x*)(x-x*)+(,1/2,)(x-x*),T,2,f(x*)(x-x*),+o,x-x*,2,一阶中值公式：对,x,使,f(x)=f(x*)+,f(x*+,(x-x*),T,(x-x*),Lagrange,余项：,对,x,记,x,x*+,(,x-x*,),f(x)=f(x*)+,f,T,(x*)(x-x*)+(,1/2,)(x-x*),T,H,(x,)(x-x*),(5),多元函数的极值,二元函数,Th1(,必要条件,),（,可微的极值点为驻点,）：,设,f,(,x,y,):D,()(D,定义域,),(1),为,D,的一个内点,;,(2),f,(,x,y,),在 可微,;,(3),为,f,(,x,y,),的极值点,;,则,:,在 处,Th2(,充分条件,),：,设,f,(,x,y,):D,()(,D,定义域,),(1),为,D,的一个内点,;,(2),f,(,x,y,),在 处二次可微,;,(3),;,(,即,:),则,:,.,若,(,矩阵正定,),则 为,f,(,x,y,),的严格极小点,.,则,:,.,若,(,矩阵负定,),则 为,f,(,x,y,),的严格极大点,.,.,若,则 不是,f,(,x,y,),的极值点,.,此时称,为,f,(,x,y,),的鞍点,.,一般多元函数的极值判别条件,Th3(,必要条件,),（,可微的极值点为驻点,）：,设,f,:D,()(,D,定义域,),(1),为,D,的一个内点,;,(2),f,(,x,),在 可微,;,(3),为,f,(,x,),的极值点,;,则,:,Th3(,充分条件,),：,设,f,:D,()(,D,定义域,),(1),为,D,的一个内点,;,(2),f,(,x,),在 处二次可微,;,(3),;,(4)(,或,),;,（即 ；或,0,）,则：为,f,(,x,),的严格局部极小点（,或极大值点,）,.,第一章 其它基础知识,复习下列知识：,线性代数的有关概念：向量与矩阵的运算、向量的线性相关和线性无关，矩阵的秩，正定、半正定矩阵，线性空间等；,集合的有关概念：开集、闭集，集合运算，内点、边界点等。,