规划数学非线性规划基本知识.ppt

,非线性规划基本概念 （1学时） 一维搜索 （1学时）,重 点：下降迭代算法、黄金分割法、二次插值法。 难 点：下降迭代算法构造 基本要求：了解非线性规划的分类，掌握梯度的计算和性质， 会用海赛阵判断凸规划，掌握用黄金分割法、二次插值法。,第6讲 非线性规划及一维搜索（第3章）,非线性规划基本概念（3.1）,1 非线性规划模型分类,一般无约束极值形式为：,一般有约束极值问题形式为：,例1 在层次分析（Analytic Hierarchy Process, 简记为 AHP）中，为了进行多属性的综合评价，需要确定每个属性的相对重要性，即它们各自的权重。为此，将各属性进行两两比较可得如下判断矩阵：,其中：是第个属性与第个属性的重要性之比。 现需要从判断矩阵求出各属性的权重，为使求出的权重向量在最小二乘意义上能最好地反映判断矩阵的估计，建立数学模型：,有约束极值问题,例2 模型参数识别问题 设已知某问题的数学模型为,试验测得在时刻,时 的值为,试用其估计参数 。,建立问题为的数学模型 采用最小二乘法问题转化为求解,无约束极值问题,2 多元函数的极值问题,（1）梯度及Hesse 矩阵 梯度,Hesse矩阵,例3：求下列函数的梯度：,解：,解：,例4 求目标函数 f（X）= 的梯度和Hesse矩阵。 解： 则 又因为： 故Hesse阵为：,（2）局部极值和全局极值,极小点,局部极小点,全局极小点,严格局部极小点,非严格局部极小点,非严格全局极小点,严格全局极小点,例如：图中一元函数f定义在区间a b上 为严格局部极小点， 非严格局部极小点,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 -1 1 -0.236 0.236 -0.653 -1.125,2 -0.236 1 0.236 0.528 -1.125 -0.970,.,-1,.,1,0,.,.,.,.,3 -0.236 0.528 0.056 0.236 -1.050 -1.125,4 0.056 0.528 0.236 0.348 -1.125 -1.106,5,6 0.168 0.348 0.236 0.279 -1.125 -1.123,7 0.168 0.279,0.056 0.348 0.168 0.236 -1.112 -1.125,3 二次插值法,考虑问题,二次插值法是以目标函数的二次插值函数的极小点作为新的中间插值点，进行一维搜索的方法。,假设初始区间函数值呈现“两端大中间小”的3个点所确定的区间，三个点为,，对应的函数值为,。令,，过这三个点,，可确定二次插值函数,（1）,（2）,（3）,将式（2）和式（3）联立解得,将区间内的3个点及其函数值分别代入式(2),得到含三个未知数 的方程组：,（4）,例9,*4 Newton法,牛顿法是函数逼近的一种方法，它的基本思想是，在迭代点附近用二阶泰勒多项式近似表示 ，进而求出极小点的估计值。,考虑问题,令,得迭代公式,因为是用二阶泰勒公式近似代替函数，故牛顿法的初始迭代点应靠近极小值点，这样收敛的快，否则可能不收敛于极小点。,作业：习题3 1，2，3，5,