[教学课件]第4讲非线性规划基本知识.doc

《[教学课件]第4讲非线性规划基本知识.doc》由会员分享，可在线阅读，更多相关《[教学课件]第4讲非线性规划基本知识.doc（4页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、教学课件第4讲非线性规划根本知识 例3：求以下函数的梯度： 例3 求目标函数 fX= 的梯度和Hesse矩阵。 解： 那么 又因为： 故Hesse阵为： 2局部极值和全局极值 4多元函数的泰勒公式 多元函数Taylor展开式在最优化理论中十分重要。许多方法及其收敛性的证明都是从它出发的。下面就给出多元函数Taylor展开式： 给出 极小点的一个初始估计值 4) 计算机迭代时终止计算的准那么 1黄金分割法：适用于一般的函数。试探法 2Newton切线法：适用于 的一阶导数和二阶导数都可求出的情况。函数逼近法 1 搜索区间确实定 定义1：设 ，t*是 在L 上的全局极小点。如果对于L上任取的两点

2、和 且 均有 t* ，当 t*时， 那么称 是区间L上的单谷函数。 以下假设一元函数 是单谷函数。 定义2： ，t*是 在L上的全局极小点。假设找到 ,那么称此区间 为 的极小点的一个搜索区间，。 单谷函数的性质： 设 是单谷函数极小点的一个搜索区间。在 上任取两点 ，使 ,假设 那么 是 极小点的一个搜索区间；假设 ，那么 是 极小点的一个搜索区间。 单谷函数的这一性质可用来将搜索区间无限缩小，以至求到极小点。 本章下面就介绍一维搜索法. 在搜索区间确实定时如何定 步骤： 1 给出初始区间 及精度 ，计算试探点 试探点的公式为： 及函数值 令k=1 2 假设 停止计算， 中任意一点均可作为所

3、求极小点的近似。否那么当 时转3，当 时转4； 3 置 计算 转5； 4 置 计算 转5； 5 令 k=k+1返回2 * * * * 非线性规划根本概念 1学时 一维搜索 1学时 重 点：下降迭代算法、黄金分割法、二次插值法。 难 点：下降迭代算法构造 根本要求：了解非线性规划的分类，掌握梯度的计算和性质， 会用海赛阵判断凸规划，掌握用黄金分割法、二次插值法。 第4讲 非线性规划及一维搜索第3章 非线性规划根本概念3.1 1 非线性规划模型分类 一般无约束极值形式为： 一般有约束极值问题形式为： 例1 在层次分析Analytic Hierarchy Process, 简记为 AHP中，为了进行

4、多属性的综合评价，需要确定每个属性的相对重要性，即它们各自的权重。为此，将各属性进行两两比拟可得如下判断矩阵： 其中：是第个属性与第个属性的重要性之比。 现需要从判断矩阵求出各属性的权重，为使求出的权重向量在最小二乘意义上能最好地反映判断矩阵的估计，建立数学模型： 有约束极值问题 例2 模型参数识别问题 设某问题的数学模型为 试验测得在时刻 时 的值为 试用其估计参数 。 建立问题为的数学模型 采用最小二乘法问题转化为求解 无约束极值问题 2 多元函数的极值问题 1梯度及Hesse 矩阵 梯度 Hesse矩阵 解： 解： 极小点 局部极小点 全局极小点 严格局部极小点 非严格局部极小点 非严格

5、全局极小点 严格全局极小点 例如：图中一元函数f定义在区间a b上 为严格局部极小点， 非严格局部极小点 a为严格全局极小点 凸凹函数 定义: 设函数 在凸集 上有定义,如果对任意 和 属于 及任何实数? 那么称 是 上的凸函数. 3凸函数、凹函数及凸规划 凸凹函数二阶判别定理： 设 是 非空开凸集 上的二阶连续 可微函数，那么 为凸函数的充分必要条件是 在 上半正负定。 凸规划 假设 为凸函数 为凹函数 ， 那么该非线性规划为凸规划。 定义： 凸规划性质：设 是凸规划问题的一个局部最优解，那么 是全局最优解。如果 是严格凸函数，那么 是唯一全局最优解。 证明：反证法 设 是凸规划的局部最优解

6、但不是全局最优解，那么存在可行解 满足 由可行域为凸集，那么 为可行解 由 是凸函数 即在 的任意小邻域内存在函数值小于 的可行解 与 是局部极小点矛盾。证毕。 的二阶泰勒展开 例4 用泰勒公式将函数 在点 解： 令 设 其中： 为一个方向向量， 为一个实数称为步长 依次用1式计算得一个点列 假设有： 那么称1为下降迭代算法 1 定义： 4 下降迭代算法 例 4 试求目标函数 在点 处的 负梯度方向，并求沿这个方向移动一个单位长度后新点的目标函数值。 解： 由于 那么函数在 处的负梯度方向是 这个方向上的单位向量是： 新的点为： 2确定最正确步长 ：在 的情况下求 1确定搜索方向 ：不同的搜索

7、方向对应不同的算法 定理 ：式1中按最正确步长得到的新的点 处的梯度和其搜索方向正交。即 证明： 得 即为最正确步长 例 5：试求目标函数 在点 处的 负梯度方向，并求沿这个方向移动最正确步长后新点的目标函数值。 解： 由于 那么函数在 处的负梯度方向是 2) 收敛性： 假设 其中 为极小点。那么称该算法是有效的 下降算法得到的点列 不一定收敛到极小点，它依赖于初始点的选择。 例 显然 为极小点 初始点选 不可能收敛于 初始点选 3 )收敛速度： 设 收敛于 假设存在与迭代次数无关的数 和 使得从 开始都有 那么称 为 阶收敛。 线性收敛， 超线性收敛， 二阶收敛。 1绝对误差 2相对误差 (

8、3) 根据目标函数梯度 上升方向 我们有结论： 变化率为0方向 函数在与其梯度正交的方向上变化率为0 下降方向 函数在与其梯度成锐角的方向上是上升的 - 函数在与其梯度成钝角的方向上是下降的 5 梯度的性质 设f(X) 在定义域内有连续偏导数，即有连续梯度 ，那么梯度 有以下两个重要性质： 性质一 函数在某点的梯度不为零，那么必与过该点的等值面垂直 性质二 梯度方向是函数具有最大变化率的方向。 一维搜索 本节讨论 的主要问题是 解决这个问题的方法称为一维搜索。这种方法不仅对于解决一维最优化本身具有实际意义，而且也是解多维最优化问题的重要支柱。 在微积分中解 的方法限于方程 可以直接求解出来的情况。本节介绍的方法对 不作严格要求，它可以很复杂，其导数可能不存在或者很难求出。当然对于可以求导数的情况，相应的方法也会简单些。 本章将介绍以下两种直线搜索方法： 0 t t* t* t . a b 证明：利用反证法证明。对于后一种情况，即 假设 不是搜索区间 即 的极小点必在 中。 此时有 , 矛盾。 根据单谷函数定义知： 故 是搜索区间，同样可证前种情形 2 黄金分割法0.618法 1. 在 中取对称的位置 2. 保持每次的缩短率相同 原那么 . . . . 故有 令 得： 代入1，2式 取 那么 负根舍去 * * * *