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