运筹学非线性规划2ppt课件

《运筹学非线性规划2ppt课件》由会员分享，可在线阅读，更多相关《运筹学非线性规划2ppt课件（36页珍藏版）》请在金锄头文库上搜索。

1、ORXJTU第二章 线性规划 放松对 的要求，只需求目的函数在迭代的每一步都有充 分下降即可。这样可大大减少求 的任务量 不准确LS法。 不准确不准确线性搜索法性搜索法目的：目的：为抑制准确抑制准确线性搜索法的缺乏性搜索法的缺乏在寻求目的函数的最优解时，往往没必要把LS搞得非常准确，特别是在算法的初始阶段更是如此。 准确LS法虽可使目的函数在每次迭代中下降较多，但计算任务量比较大； 非线性规划非线性规划ORXJTU第二章 线性规划建立不同的建立不同的详细规那么，就可以构成不同的不准确那么，就可以构成不同的不准确LS法法常用常用规那么：那么：既不希望既不希望 获得太大而引起得太大而引起 的大幅度

2、的大幅度摆动也不希望也不希望 获得太小而致使得太小而致使 在到达在到达 之前就之前就过早地移早地移步不前步不前nGoldsteinGoldstein准那么准那么n给定给定 ，选取，选取 满足：满足：n n 1 1 左不等式阐明应选取 使 有充分的下降,右不等式保证了步长 不会取值太小。第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划(1)式等价于以下两个不等式令 ，那么由(2)、(3)有，在 平面上，点 应在下述两条直线之间：第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划 也就是说，夹在这两条直线之间的曲线 所对应的 均满足(1)式。称满足称满足1 1式的式的 为

3、可接受步长；为可接受步长；由一切可接受步长构成的区间称为可接受区间。由一切可接受步长构成的区间称为可接受区间。Remark: 这个条件是必要的这个条件是必要的第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划现实上，假设 是满足条件 的二次函数，那么 的全局极小点为 而相应的全局极小值为 由式4可得 由这两个表达式，并留意到 ，那么有 第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划GoldsteinGoldstein不准确不准确LSLS的的计算步算步骤：第四章第四章 非线性规划非线性规划S1：给定初始搜索区间 及 ， 计算 令 ，取 ， S2：计算 ，假设 ，那么转

4、S3； 否那么， ，转S4S4： ，转S2.S3：假设 ，那么 ，输出 ，停顿；否那么， ；ORXJTU第二章 线性规划第四章第四章 非线性规划非线性规划无无约束最束最优化化问题 典型算法：典型算法：解析法：解析法： 可微，算法迭代过程中要用到可微，算法迭代过程中要用到 等信息等信息直接法：直接法： 无需可导，算法迭代过程中仅用到函数值无需可导，算法迭代过程中仅用到函数值ORXJTU第二章 线性规划第四章第四章 非线性规划非线性规划无无约束束优化化问题的最的最优性条件：性条件： 由上由上节引引见下降方向下降方向时的定理易知的定理易知Th(极值的必要条件极值的必要条件)：设：设 在点在点 处可微

5、，处可微， 假设 为问题的部分最优解，那么必有 使 成立的点 称为函数 的驻点、稳定点，或平稳点 Remark: 平稳点可以是极小点，也可以是极大点；平稳点可以是极小点，也可以是极大点；甚至也能够既不是极小点，也不是极大点， ORXJTU第二章 线性规划第四章第四章 非线性规划非线性规划Th(极值的充分条件极值的充分条件)：设：设 即函数具有延续的二即函数具有延续的二阶偏导数， 为它的一个稳定点，那么 为 的一个严 格部分最优解的充分条件是 的Hesse阵 正定。 Proof: 由于由于 为为 的稳定点，故有的稳定点，故有 . 将 在 处进展Taylor展开，有由 的正定性得： 而 为 的高阶

6、无穷小量。 必然存在 ，使得 , . ORXJTU第二章 线性规划第四章第四章 非线性规划非线性规划Example： 稳定点 ： 假设 为正定阵，那么其驻点 必为全局最优解。 Th(凸函数的极值条件凸函数的极值条件)：设：设 ， ， 是是 上的上的 可微凸函数，假设有 ，那么 为问题的全局最优 解。 Proof:因因 为为 上的可微凸函数，故由前述凸函数的等价刻上的可微凸函数，故由前述凸函数的等价刻 画定理知： 由于 ，那么有对于无约束凸规划问题，其目的函数的驻点即为其全局最优解。ORXJTU第二章 线性规划第四章第四章 非线性规划非线性规划最速下降法最速下降法 根本思想：假设 延续可微，且当

7、前迭代点不是 的平稳点，那么由前述关于下降方向的存在性与性质可知，此时 的负梯度方向为使其下降最快的方向，选取它作为搜索方向 ，那么有 最速下降法的迭代步最速下降法的迭代步骤： S1：选取初始点 ，给定精度参数 ，令 . S2：计算 ，假设 ，停顿，输出 ，否那么转S3.S3：取 . S4：采用某种LS技术确定步长 ，令 ，转S2. Remark:在在S4中选择不同的中选择不同的LS战略，就可以导出不同方式的战略，就可以导出不同方式的最速下降算法。定步长，变步长；不准确LS，准确LS. ORXJTU第二章 线性规划第四章第四章 非线性规划非线性规划最速下降法的全局收最速下降法的全局收敛性定理：

8、性定理：Th.设设 一阶延续可微，一阶延续可微， 是由采用准确是由采用准确LS的最速下降法产的最速下降法产生的迭代序列，那么 的每一个聚点都是 的平稳点。 Th.设设 是二阶延续可微函数且是二阶延续可微函数且 ，对任给初始点，对任给初始点 ，采用准确LS的最速下降法或有限步终止，或 或 . Example:现实上，对恣意的初始点，利用准确LS的最速下降法均有 ,ORXJTU第二章 线性规划第四章第四章 非线性规划非线性规划采用准确LS的最速下降法需求10次迭代才干找到最优解 WHY？对于采取准确LS的最速下降法，有最速下降法中相邻两次迭代的搜索方向是相互正交的。ORXJTU第二章 线性规划第四

9、章第四章 非线性规划非线性规划在二维空间，该二元函数的等值线为椭圆，那么有以下图：思索目的函数 为二次函数的情形， 因此，几何上，最速下降法产生的迭代序列 向极小点 的挪动途径呈“锯齿状。 在迭代开场的几步，挪动步长较大， 下降的幅度亦比较大； 随着迭代的进展，当 越来越接近 时，挪动步长越变越小， 的下降速度越来越缓慢。 ORXJTU第二章 线性规划第四章第四章 非线性规划非线性规划解解释：“最速下降是基于最速下降是基于 梯度描画的，其梯度描画的，其变化的部分特征，化的部分特征， 这仅能保证在当前迭代点的某个邻域内来说可使 下降最快， 并不能保证从问题的整体求解，算法的整体迭代过程来说亦最快

10、。 总之，之， l最速下降法全局收最速下降法全局收敛，对LS要求不高要求不高l最速下降法最速下降法简单易行，易行，计算量每步与存算量每步与存贮量需求小量需求小l在在问题求解的开求解的开场阶段，采用最速下降法是比段，采用最速下降法是比较适宜的适宜的l 与其他算法与其他算法结合合l收收敛速度太慢速度太慢线性收性收敛速度速度ORXJTU第二章 线性规划共共轭方向法方向法特点：特点： 把它用在n维二次函数的极小化问题上时，最多经过n次迭代即可找到其最优解有限步终止性。 共轭方向法的讨论与二次函数是分不开的 运用原理运用原理 ：对于延续可微的普通函数，它在其极小点附近的性态近 似于二次函数从而可用于无约

11、束优化问题。第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划Def共轭方向共轭方向设设A为为n阶实对称矩阵，对于非零向量阶实对称矩阵，对于非零向量 ，假设，假设 1 那么称 和 是相互A共轭的。对于非零向量组 ，假设 那么称 是A共轭方向组 或称它们为一组A共轭方向。 假设在1中取 ，那么 ，即 和 正交。A-共共轭是是线性代数中正交向量概念的推行！性代数中正交向量概念的推行！第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划Example: ，那么向量既满足 ,又满足 而且 故它们既是A共轭的，又是正交的。同样的方法可以检验，向量 和向量 是A共轭的，但不是正交的。

12、第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划共共轭方向的性方向的性质：Th:设设A是是n阶实对称正定矩阵，阶实对称正定矩阵， 为非零向为非零向量。假设 是一组A共轭方向，那么它们一定是线性无 关的。 Proof:设存在一组实数，设存在一组实数， ，使得，使得 .依次用 ，左乘上式得 因知 是一组A共轭方向，故有而A的正定性与第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划将上述两组关系式带入()，那么知必有这意味着 是线性无关的。ln维空间中A共轭的向量的个数最多为n l在n维空间中，假设有 彼此A共轭,那么 便构成了n维空间的一个基。 反之？反之？ Th：任给

13、：任给n维空间中的一组线性无关向量维空间中的一组线性无关向量 ，可通，可通 过它们的线性组合构造出一组m个向量 ,它们彼此之间是A-共轭的。 第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划Proof：无妨取：无妨取 给出共轭化过程，当然取给出共轭化过程，当然取 均可。故自在度很大。 为产生与 共轭的方向 ，取即 与 是A-共轭的。 因此可取 中任一个异于 的方向，放在 的位置 上，故 的选择也有很大的自在性 由 与 A共轭，有得 设已求出 ，它们彼此是A-共轭的，其中 每一个向量都是 的线性组合。 第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划为得出一个向量 ，

14、它与 均为A-共轭，记 为使 与 A-共轭，即有由此可求出应有 即 (*)与 A-共轭。因 为标量，而每一个 均为 的线性组合，所以 也是 的线性组合。 在(*)中取 ，便得到了m个彼此A-共轭的向量 第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划Th：0向量与任何向量均向量与任何向量均A-共轭，除共轭，除0向量外，向量外， 向量A-共轭的概念与向量的长度是无关的。 极小化极小化严厉凸二次函数的共凸二次函数的共轭方向算法方向算法(QP)思索如下迭代格式(1)第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划这里 为实对称正定阵， ， 是关于A-共轭的一组共轭方向。假

15、设采用准确LS法确定步长 ，那么有以下结论。Th：最正确步：最正确步长的的计算公式算公式 设 是关于A的共轭方向， 那么在迭代公式1中的最正确步长为： 第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划Proof：由于 是的最小点，而 为严厉凸函数 故知 是如下方程的根:第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划由于 关于A共轭，故有从而得知：进而，我们还可以证明此时共轭方向法的有限步收敛性。第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划Th：有限步收：有限步收敛性性 设 为任一组A-共轭方向，那么对恣意的初始点 由(1)式按准确LS法产生的序列

16、 最多经过n次迭代即可找到QP的全局最优解 Proof：假设存在某个：假设存在某个 ，使得，使得那么 必为QP的全局最有解。第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划设当 时，均有 ，下证由其共轭性知 为n个线性无关的向量。要证 ，只须证， 由于第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划所以第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划Fletcher-Reeves共共轭梯度法梯度法 l对于A共轭的方向组 不仅不独一，而且随意性大。 l用不同的方法可产生不同的共轭方向向量组，从而就有不同的共轭方向法。共共轭梯度法梯度法 以各迭代点处的负梯

17、度向量为根底。任选初始点 ，假设 ，那么取 , 从 点沿 方向 进展准确LS，求得 . 令 ，假设 ，那么已获得QP的最优解 . 否那么，第二个搜索方向取 ，这里 的选取 要使 与 关于A共轭，即 .由上式可推得第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划普通地，假设已获得A的共轭方向 ，依次沿它们进展 LS所得迭代点 . 假设 ，那么 .否那么，定义 ,为使 与 是A-共轭，应选 . 从而,而为使 与 为A-共轭，即要求 .第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划Fletcher-Reeves公式：公式：的不同选取方法将导出不同方式的共轭梯度法 vPo

18、lak-Ribiere-Polyak法法 第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划vDixon法法 vCrowder-Wolfe法法 Example: 用用F-R共轭梯度法求解前例共轭梯度法求解前例第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划光滑无光滑无约束束优化化问题的的F-R共共轭梯度算法梯度算法S1：选取初始点 ，给定精度参数S2：计算 ，假设 ，停顿，输出 ，否那么 S3：取 ，S4：进展LS求 ，使 ，令S5：计算 ，假设 ，停顿，输出 S6：用F-R公式，令 ，其中， 令 ，转S4

19、 第四章第四章 非线性规划非线性规划ORXJTU第二章 线性规划ThFR共轭梯度法的全局收敛性：设共轭梯度法的全局收敛性：设 延续可微，延续可微， 且有下界，程度集 有界，那么采用准确LS的FR共轭梯度法产生迭代列 .至少有一个聚点是 的平稳点，即 (1)当 是有限点列时，其最后一个点是 的平稳点；(2)当 是无穷点列时，它必有聚点，且恣意聚点均是 的平稳点。 Remarks与最速下降法与最速下降法类似，共似，共轭梯度法同梯度法同样仅用到梯度信息，用到梯度信息，简单易易行，行，计算量小；算量小；共共轭梯度法的收梯度法的收敛速度要比最速下降法快；速度要比最速下降法快；共共轭梯度法是求解中、大梯度法是求解中、大规模无模无约束束优化化问题的有效算法；的有效算法；对于普通的非于普通的非线性函数，性函数，FR法未必有有限步法未必有有限步终止性止性 n步重新开步重新开场的共的共轭梯度法梯度法: 每迭代每迭代n步，将搜索方向重置步，将搜索方向重置为负梯度方向。梯度方向。第四章第四章 非线性规划非线性规划