资源描述
,非线性规划基本概念（1学时）一维搜索（1学时）,重点：下降迭代算法、黄金分割法、二次插值法。难点：下降迭代算法构造基本要求：了解非线性规划的分类，掌握梯度的计算和性质，会用海赛阵判断凸规划，掌握用黄金分割法、二次插值法。,第6讲非线性规划及一维搜索（第3章）,非线性规划基本概念（3.1）,1非线性规划模型分类,一般无约束极值形式为：,一般有约束极值问题形式为：,例1在层次分析（AnalyticHierarchyProcess,简记为AHP）中，为了进行多属性的综合评价，需要确定每个属性的相对重要性，即它们各自的权重。为此，将各属性进行两两比较可得如下判断矩阵：,其中：是第个属性与第个属性的重要性之比。现需要从判断矩阵求出各属性的权重，为使求出的权重向量在最小二乘意义上能最好地反映判断矩阵的估计，建立数学模型：,有约束极值问题,例2模型参数识别问题设已知某问题的数学模型为,试验测得在时刻,时的值为,试用其估计参数。,建立问题为的数学模型采用最小二乘法问题转化为求解,无约束极值问题,2多元函数的极值问题,（1）梯度及Hesse矩阵梯度,Hesse矩阵,例3：求下列函数的梯度：,解：,解：,例4求目标函数f（X）=的梯度和Hesse矩阵。解：则又因为：故Hesse阵为：,（2）局部极值和全局极值,极小点,局部极小点,全局极小点,严格局部极小点,非严格局部极小点,非严格全局极小点,严格全局极小点,例如：图中一元函数f定义在区间ab上为严格局部极小点，非严格局部极小点,a为严格全局极小点,凸（凹）函数,定义:设函数在凸集上有定义,如果对任意和属于及任何实数（）,则称是上的凸函数.,（3）凸函数、凹函数及凸规划,凸（凹）函数二阶判别定理：设是非空开凸集上的二阶连续可微函数，则为凸函数的充分必要条件是在上半正（负）定。,凸规划,若为凸函数为凹函数，则该非线性规划为凸规划。,定义：,凸规划性质：设是凸规划问题的一个局部最优解，则是全局最优解。如果是严格凸函数，则是唯一全局最优解。,证明：反证法设是凸规划的局部最优解但不是全局最优解，则存在可行解满足,由可行域为凸集，则为可行解,由是凸函数,即在的任意小邻域内存在函数值小于的可行解,与是局部极小点矛盾。证毕。,（4）多元函数的泰勒公式,多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。下面就给出多元函数Taylor展开式：,的二阶泰勒展开,例5用泰勒公式将函数在点,解：,给出极小点的一个初始估计值,令,设,其中：为一个方向向量，为一个实数（称为步长）,依次用（1）式计算得一个点列,若有：,则称（1）为下降迭代算法,1）定义：,4下降迭代算法,令,例6试求目标函数在点处的负梯度方向，并求沿这个方向移动一个单位长度后新点的目标函数值。解：由于则函数在处的负梯度方向是,这个方向上的单位向量是：,新的点为：,（2）确定最佳步长：在已知的情况下求,（1）确定搜索方向：不同的搜索方向对应不同的算法,定理：式（1）中按最佳步长得到的新的点处的梯度和其搜索方向正交。即,证明：,得即为最佳步长,例7：试求目标函数在点处的负梯度方向，并求沿这个方向移动最佳步长后新点的目标函数值。解：由于则函数在处的负梯度方向是,2)收敛性：,若其中为极小点。则称该算法是有效的,下降算法得到的点列不一定收敛到极小点，它依赖于初始点的选择。,例显然为极小点,初始点选,不可能收敛于,初始点选,3)收敛速度：,设收敛于若存在与迭代次数无关的数和使得从开始都有,则称为阶收敛。,线性收敛，,超线性收敛，,二阶收敛。,4)计算机迭代时终止计算的准则,（1）绝对误差,（2）相对误差,(3)根据目标函数梯度,一维搜索,本节讨论的主要问题是解决这个问题的方法称为一维搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。在微积分中解的方法限于方程可以直接求解出来的情况。本节介绍的方法对不作严格要求，它可以很复杂，其导数可能不存在或者很难求出。当然对于可以求导数的情况，相应的方法也会简单些。,（1）黄金分割法：适用于一般的函数。（试探法）（2）二次插值法：（3）Newton切线法：适用于的一阶导数和二阶导数都可求出的情况。（函数逼近法）,本章将介绍以下几种直线搜索方法：,1搜索区间的确定,定义1：设，t*是在L上的全局极小点。如果对于L上任取的两点和且均有t*，当t*时，则称是区间L上的单谷函数。以下假设一元函数是单谷函数。,0,t,t*,t*,t,.,.,定义2：，t*是在L上的全局极小点。若找到,则称此区间为的极小点的一个搜索区间，。单谷函数的性质：设是单谷函数极小点的一个搜索区间。在上任取两点，使,若则是极小点的一个搜索区间；若，则是极小点的一个搜索区间。,.,.,.,.,a,b,单谷函数的这一性质可用来将搜索区间无限缩小，以至求到极小点。本章下面就介绍一维搜索法.,证明：利用反证法证明。对于后一种情况，即,若不是搜索区间,即,的极小点必在中。,此时有,矛盾。,根据单谷函数定义知：,故是搜索区间，同样可证前种情形,（负值舍去）,试探点的公式为：,左试点,右试点,为了算法描述方便我们记试点如下：,步骤：1给出初始区间及精度，计算试探点,及函数值令k=1,2若停止计算，中任意一点均可作为所求极小点的近似。否则当时转3，当时转4；,3置,计算,转5；,4置,计算,转5；,5令k=k+1返回2,例8用0.618法求解下列问题,初始区间为,计算结果列于下表：,1-11-0.2360.236-0.653-1.125,2-0.23610.2360.528-1.125-0.970,.,-1,.,1,0,.,.,.,.,3-0.2360.5280.0560.236-1.050-1.125,40.0560.5280.2360.348-1.125-1.106,5,60.1680.3480.2360.279-1.125-1.123,70.1680.279,0.0560.3480.1680.236-1.112-1.125,3二次插值法,考虑问题,二次插值法是以目标函数的二次插值函数的极小点作为新的中间插值点，进行一维搜索的方法。,假设初始区间函数值呈现“两端大中间小”的3个点所确定的区间，三个点为,，对应的函数值为,。令,，过这三个点,，可确定二次插值函数,（1）,（2）,（3）,将式（2）和式（3）联立解得,将区间内的3个点及其函数值分别代入式(2),得到含三个未知数的方程组：,（4）,例9,*4Newton法,牛顿法是函数逼近的一种方法，它的基本思想是，在迭代点附近用二阶泰勒多项式近似表示，进而求出极小点的估计值。,考虑问题,令,得迭代公式,因为是用二阶泰勒公式近似代替函数，故牛顿法的初始迭代点应靠近极小值点，这样收敛的快，否则可能不收敛于极小点。,作业：习题31，2，3，5,
展开阅读全文