最优化方法第一次基础知识.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,最优化方法,1.,教 材：最优化理论与方法,陈宝林，清华大学出版社,2.,参考书：最优化原理与方法,薛嘉庆，冶金工业出版社,基本知识,一.引言,四.极值最优化问题的经典方法,二.最优化问题实例,三.最优化问题及基本概念,五.图解法,六.梯度与,Hesse,阵,七.,Taylor,展开式,八.凸集与凸函数,九.极小点的判定条件,十.算法及相关概念,十一.中止条件,十二.收敛速度,一.引言,1.最优化定义,最优化是从所有可行方案中选择最合理方案以达到最优目标的一门学科。,（1）达到最优目标的方案：最优方案（最优解）,（2）搜寻最优方案的方法：最优化方法,最优化问题：寻求某些变量的取值使其符合某些限制条件，并使某个目标函数达到最大值或最小值的问题。,一般的数学形式为：,2.发展简况,经典最优化理论的研究已有很久，最早可追溯到,Fermat,时代。,1940年前，对多变量函数的数值最优化方法知之甚少，但当时已发现了若干最小二乘法和在物理上应用的最速下降法，多变量的牛顿法也很著名。,40年代与50年代：线性规划（,LP）,的发展。,二战以后，爬山法得到发展与应用（实用，粗糙）。,1959年，,W-,C.Davidon,的一个报告引入了变尺度方,法。,3.应用领域,工程设计、军事科学、自动控制、空间技术、资源分配、计算机科学等等。例如：,桥梁结构设计；,运输问题；,参数拟合；,多波形信号发生仪中正弦波形逼近的优化设计，在 中找,n,个分点，使过这些分点的折线和正弦函数曲线的误差最小。,4.包含内容：,最优化又称数学规划：,LP、NLP、DP、IP,5.分类：,二.最优化问题实例,例1：多参数曲线拟合问题,已知热电阻,R,依赖于温度,t,的函数关系为：,其中 是待定参数。通过试验，得到,i,t,i,R,i,1,50,34780,2,55,28610,3,60,23650,。,。,。,15,120,3307,利用最小二乘思想，可将其化为三维空间的无约束最优化问题，即：,现有,m,种资源的数量为 。计划生产,n,种产品1,2,n。,有关数据如下，试问：怎样安排生产可以使利润达大？,产品,拥有量,1,2,n,资源,1,2,m,单位利润,令 表示第,j,种产品的产量。,例2.生产安排问题,已知有,m,个生产点,B,i,，,可供应某种物质量分别为,n,个销地,，,需求量为 .从 到 的单位运价为 。问：应如何安排运输方案才能使总运费最小？,例3.运输问题（,TP）,运费,销 地,产量,1,2,n,产地,1,2,m,销量,在产销平衡条件下，要求得总运费最小的调运方案，可得如下模型：,设 表示从第,i,个产地向第,j,个销地的运量，则有,三.最优化问题及基本概念,2.解法分类,解析方法：利用函数的解析性质去构造迭代公式使之收敛到最优解（如牛顿法）。,直接方法：它对函数的,解,析性质如可微性没有要求，而是根据一定的数学原理来确定（如0.618法）。,1.,模型,3.全局最优解与局部最优解,四.极值问题的经典方法,1.求驻点的方法,2.Lagrange,乘子法,五.图解法,等值线（面）的特点：,1.不同值的等值线不相交;,2.除极值点外，等值线是连续曲线;,3.等值线稠密处导数变化快，稀疏处变化慢;,六.梯度与,Hesse,阵,1.梯度,性质1：函数在某点的梯度若不为0，则必与过该点的等值线（面）垂直。,x,0,L,f(X)=f(X,0,),f(X,0,),X,0,L,性质2：梯度方向是函数值具有最大变化率的方向，即函数值上升最快的方向。,2.方向导数和下降（上升）方向,（1）,方向导数,：,函数 在点 处沿着方向,p,的方向导数。,（2）给定函数 和方向,p，,如果存在实数 ，使得对于任意的 ，都有 ，则称,p,为 在点 处的下降方向。,（3）性质,(,a).,(,b)p,是下降方向;,(,c)p,是下降方向。,p,是上升方向。,（4）常用梯度公式,3.,Hesse,矩阵,（1）,雅可比矩阵：设,，,（2）,海赛（,Hesse）,矩阵,：,（3）其它,七.,Taylor,展开式,八.凸集与凸函数,1.凸集,（1）,凸组合：已知,任取,k,个点 ，,如果存在常数,，,，使得,，则称,为,的凸组合。,（2）凸集：设集合,，如果,中任意两点的凸组合,仍然属于,，则称,为凸集。,2.凸函数,设,，,任取,，,如果,，,有,，,则称,为,X,上的（严格）,凸函数。,例子：,水平集,：,是凸函数,。,性质：水平集一定是凸集。,3.凸函数的性质,定理.凸函数的局部极小点就是全局极小点。,4.凸函数的判断条件,定理1.,是凸集,X,上的凸函数的充要条件是,，有,.,定理2.设,在凸集,X,上有二阶连续偏导数，则,是凸,函数的充要条件是,，有,半正定。,例：正定二次函数,，其中,是正定矩阵。,是凸函数。,5.凸规划,（1）,其中,是凸函数，,是凸集。,（2）,其中,是线性函数.,是凸函数,6.二次规划,九.极小点的判定条件,（1）必要条件：,（2）充分条件：,（3）,两个结论,函数在极小点附近的等值线为近似的同心椭圆。,十.算法及相关概念,1、迭代算法,集合,D,上的迭代算法,A：,（1）初始点,；,（2）按照某种规则,A,产生下一个迭代点,。,（,i）,如果点列,收敛于最优解,，则称算法,A,收敛。,（,ii）,如果,，则称算法,A,为,下降迭代算法。,.,.,.,.,2.下降迭代算法步骤,（1）给出初始点,，令,；,（2）按照某种规则确定下降搜索方向,；,（3）按照某种规则确定搜索步长,，使得,；,（4）令,，,；,（5）判断,是否满足停止条件。是则停止，否则转第2步。,搜索步长确定方法：,称,。,为最优步长，且有,十一.终止条件,2.,4.,1.,3.,x,k,x,k+1,x,k,x,k+1,x,*,十二.收敛速度,则称 的收敛阶为 。,1.设算法,A,所得的点列为,，如果,2.,