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