当前位置：文档之家 › 最优化理论与算法(第四章)

最优化理论与算法(第四章)

  • 格式：doc
  • 大小：1.11 MB
  • 文档页数：13

1 第四章 共轭梯度法

§4.1 共轭方向法

共轭方向法是无约束最优化问题的一类重要算法。它一方面克服了最速下降法中，迭代点列呈锯齿形前进，收敛慢的缺点，同时又不像牛顿法中计算牛顿方向耗费大量的工作量，尤其是共轭方向法具有所谓二次收敛性质，即当将其用于二次函数时，具有有限终止性质。

一、共轭方向

定义4.1 设G是nn对称正定矩阵，1d，2d是n维非零向量，若

120TdGd （4.1）

则称1d，2d是G－共轭的。类似地，设1,,mdd是nR中一组非零向量。若

0TijdGd()ij （4.2）

则称向量组1,,mdd是G－共轭的。

注：(1) 当GI时，共轭性就变为正交性，故共轭是正交概念的推广。

(2) 若1,,mddG－共轭，则它们必线性无关。

二、共轭方向法

共轭方向法就是按照一组彼此共轭方向依次搜索。

模式算法：

1）给出初始点0x，计算00()ggx，计算0d，使000Tdg，:0k （初始共轭方向）；

2）计算k和1kx，使得0()min()kkkkkfxdfxd，令1kkkkxxd；

3）计算1kd，使10TkjdGd，0,1,,jk，令:1kk，转2）。

三、共轭方向法的基本定理

共轭方向法最重要的性质就是：当算法用于正定二次函数时，可以在有限多次迭代后终止，得到最优解（当然要执行精确一维搜索）。 2 定理4.2 对于正定二次函数，共轭方向法至多经过n步精确搜索终止；且对每个1ix，都是()fx在线性流形00,ijjjjxxxd中的极小点。

证明：首先证明对所有的1in，都有

10Tijgd，0,1,,ji（即每个迭代点处的梯度与以前的搜索方向均正交）

事实上，由于目标函数是二次函数，因而有

11kkkkkkggGxxGd

1）当ji时， 1111iTTTijjjkkjkjgdgdggd

110iTTjjkkjkjgddGd

2）当ji时，由精确搜索性质知：

10Tijgd

综上所述，有 10Tijgd (0,1,,)ji。

再证算法的有限终止结论。若有某个10ig（1in），则结论已知。若不然，那么由上面已证则必有： 0Tnjgd (0,,1)jn。

而由于01,,ndd是nR的一组基，由此可得0ng。故至多经过n次精确一维搜索即可获得最优解。

下面证明定理的后半部分。由于

1()2TTfxxGxbxc

是正定二次函数，那么可以证明

000(,,)()iijjjttfxtd

是线性流形上的凸函数。事实上，

000000000 (,,)()1()()()2iijjjiiiTTjjjjjjjjjttfxtdxtdGxtdbxtdc 3 200000011()[]()22iiTTTTTjjjjjjjjtdGdxGdbdtxGxbxc

由0TjjdGd(0,,)ji知0(,,)itt为0,,itt的凸函数。因而

100(,,)min(,,)0iiittRjttt (0,,)ji

00()0iTjjjjfxtdd (0,,)ji

注意到：当jjt，(0,,)ji时，

00100iijjjjijjxtdxdx。

而由定理前部分证明，在1ix处有

11()0TTijijfxdgd(0,,)ji，

故在00(,,)(,,)iitt处，0(,,)itt取得极小，即

100iiijjxxd

是()fx在线性流形上的极小点。

§4.2 共轭梯度法

上节一般地讨论了共轭方向法，在那里n个共轭方向是预先给定的，而如何获得这些共轭方向并为提及。本节讨论一种重要的共轭方向法——共轭梯度法。这种方法在迭代过程中通过对负梯度方向进行适当校正获得共轭方向，故而称之为共轭梯度法。

一、共轭梯度的构造 （算法设计针对凸二次函数）

设 1()2TTfxxGxbxc

其中G为nn正定矩阵，则

()gxGxb。

对二次函数总有 11kkkkkkggGxxGd 4 1）设0x为初始点。首先取00dg，令1000xxd （0为精确步长因子）

则有：100Tgd（精确一维搜索性质）。

2）令1100dgd，适当选择0，使100TdGd，

得 101101100001000()()TTTTTTgGdgggggdGddgggg （从而得到1d）

由前一节共轭方向法的基本定理有：

210Tgd，200Tgd，

再由0d与1d的构造，还可得：

210Tgg，200Tgg

3）再令220011dgdd，适当选择0，1，使得20TidGd （0,1i），由此得：

00，22122112111()()TTTTgggggdgggg

4） 一般地，在第k次迭代中，令10kkkiiidgd 适当选取i，使0TkidGd （0,,1ik），

可得到 11()()TTkikiiiTTiiiiigGdgggdGddgg（0,,1ik） （4.3）

同样由前一节共轭方向的基本定理有：

0Tkigd（0,,1ik）， （4.4）

再由ig与id的关系得：

0Tkigg （0,,1ik） （4.5）

将（4.4）与（4.5）代入（4.3）得：当0,,2ik时，0i，

而 111111()()TTkkkkkkTTkkkkkgggggdgggg。

共轭梯度法的迭代公式为：

1kkkkxxd（kd为共轭方向，k为最佳步长因子）

对二次函数 5 TkkkTkkgddGd；

而对非二次函数，则采用精确一维搜索得到k。

共轭方向的修正公式为： 11kkkkdgd （4.6）

其中，k由下面诸式之一计算：

1） 111()()TkkkkTkkkgggdgg （Crowder-Wolfe公式） （4.7）

2) 11TkkkTkkgggg （Fletcher-Reeves公式） （4.8）

3） 11()TkkkkTkkggggg （Polak-Ribiere-Polyak 公式） （4.9）

4） 11TkkkTkkggdg （Dixon公式） （4.10）

注： 对二次函数而言，上述四个公式都是等价的。而且求得的搜索方向均为共轭方向；若对非二次函数，则将导出互不相同的算法，而且据此求出的搜索方向不再保证是共轭的。（事实上，此时不存在一个常值正定矩阵G，共轭的提法都已无意义）。

二、共轭梯度法的性质

定理4.3 对于正定二次函数，采用基于精确一维搜索的共轭梯度算法，必定经过mn步迭代后终止。且对1im，下列关系式成立：

1）0TijdGd （0,1,,1ji） （4.11）

2）0Tijgg （0,1,,1ji） （4.12）

3）TTiiiidggg （4.13）

4）01000[,,,][,,,]iiggggGgGg （4.14）

5）01000[,,,][,,,]iidddgGgGg （4.15）

证明：先用归纳法证明（4.11）～（4.13）。对于1i，容易验证（4.11），（4.12），4.13）成立。现假设这些关系式对某个im成立，下面证明对于1i，这些关系式仍然成立。事实上，对于二 6 次函数，显然有

11()iiiiiiiggGxxgGd （4.16）

对上式左乘Tid，并注意到i是精确步长因子，得

0TTiiiiiTTiiiigdggdGddGd （4.17）

利用（4.16），（4.17），得

111()TTTTTijijiijijiijjjggggdGgggdGdd （4.18）

当ji时，（4.18）成为

10TTTTiiijiiiiTiiggggggdGddGd

当ji时，由归纳法假设可知

111()0TTTijijiijjjggggdGdd

于是（4.12）得证。

再由共轭梯度法的迭代公式及（4.17），有

1111jjTTTTTijijiijiiijjggdGdgGddGdgdGd （4.19）

当ji时，由（4.12），（4.17）及（4.8），（4.19）成为

111110TTTTTiiiiiiiiiiTTiiiiggggdGddGddGdgggg

当ji时，直接由归纳法假设知（4.19）为零，于是（4.11）得证。

又由于 1111111TTTTiiiiiiiiidgggdggg

于是（4.13）得证。

下面利用归纳法证明（4.14）与（4.15）。当1i时，由00dg及1000000ggGdgGg，容易看出： 0100[,][,]gggGg

再由 00dg 及 1100100dgdgg，易见：

010100[,][,][,]ddgggGg。

故当1i时，（4.14）与（4.15）成立。假定（4.14）与（4.15）对i成立。下证结论对1i也成立。 7 由于 1iiiiggGd，

合集下载

最优化理论与方法

最优化理论与方法

最优化理论与方法综述李超雄

最优化方法是近几十年形成的，它主要运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。最优化方法的主要研究对象是各种管理问题及其生产经营活动。最优化方法的目的在于针对所研究的系统，求得一个合理运用人力、物力和财力的最佳方案，发挥和提高系统的效能及效益，最终达到系统的最优目标。实践表明，随着科学技术的日益进步和生产经营的日益发展，最优化方法已成为管理科学的重要理论基础和不可缺少的方法，被人们广泛地应用到公共管理、经济管理、工程建设、国防等各个领域，发挥着越来越重要的作用。这就是我理解的整个课程的流程。在这整个学习的过程当中，当然也会遇到很多的问题，不论是从理论上的还是从实际将算法编写出程序来解决一些问题。下面给出学习该课程的必要性及结合老师讲解以及在作业过程中遇到的问题来阐述自己对该课程的理解。20世纪40年代以来，由于生产和科学研究突飞猛进地发展，特别是电子计算机日益广泛应用，使最优化问题的研究不仅成为一种迫切需要，而且有了求解的有力工具。因此最优化理论和算法迅速发展起来，形成一个新的学科。至今已出现线性规划、整数规划、非线性规划、几何规划、动态规划、随机规划、网络流等许多分文。最优化理论与算法包括线性规划单纯形方法、对偶理论、灵敏度分析、运输问题、内点算法、非线性规划K-T条件、无约束最优化方法、约束最优化方法、参数线性规划、运输问题、线性规划路径跟踪法、信赖域方法、二次规划路径跟踪法、整数规划和动态规划等内容。最优化理论所研究的问题是讨论在众多的方案中什么样的方案最优以及怎样找出最优方案。这类问题普遍存在。例如，工程设计中怎样选择设计参数，使得设计方案满足设计要求，又能降低成本；资源分配中，怎样分配有限资源，使得分配方案既能满足各方面的基本要求，又能获得好的经济效益；生产评价安排中，选择怎样的计划方案才能提高产值和利润；原料配比问题中，怎样确定各种成分的比例，才能提高质量，降低成本；城建规划中，怎样安排基本单位的合理布局，才能方便群众，有利于城市各行各业的发展；农田规划中，怎样安排各种农作物的合理布局，才能保持高产稳产，发挥地区优势；军事指挥中，怎样确定最佳作战方案，才能有效地消灭敌人，保存自己，有利于战争的全局；在人类活动的各个领域中，诸如此类，不胜枚举。最优化这一数学分支，正是为这些问题的解决，提供理论基础和求解方法，它是一门应用广泛、实用性强的学科。

最优化理论与方法 遗传算法

最优化理论与方法 遗传算法

遗传算法研究综述

罗九晖 统计学 132111059

优化是科学研究、工程技术以及经济管理等等领域的重要研究对象。优化问题广泛存在于各个领域中，学者对该问题的求解研究从未停止。

一、优化算法概述

优化问题是个古老的课题，目前，对优化问题的求解研究主要有三个方向：

（1）经典精确优化算法（数值最优化）

该算法主要用来处理目标函数以及约束条件有具体的解析表达式且存在导数的情况。它是先利用求导或者变分法得到极值点存在的必要条件（通常是一组方程或不等式），然后再求解细方程或不等式。

（2）经典近似优化算法（解析最优化）

通过最优解的性质建立迭代公式求最优解。

（3）智能算法（仿生算法、演化算法、进化算法）

数值优化算法和解析优化算法必须建立在目标函数存在导数的性质条件下进行，而在实际中碰到的很多优化问题的目标函数并不存在导数。因此，近年来，学者们以模拟物质变化过程或模拟生命体而设计的搜索方式为基础，提出各种算法，这类算法就是智能算法。

二、智能算法概述

智能是在任意给定的环境和目标条件下，正确制定决策和实现目标的能力。智能优化算法则是将生物行为与计算机科学相结合，解决优化问题，制定最优化决策。目前，智能算法有以下几类：

（1）模拟退火算法

模拟退火算法是基于蒙特卡洛迭代求解策略的一种随机寻优算法,其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性(即:退火过程中,固体最终达到能量最小的状态,对应于优化算法最终找到了最优解)而设计的一种智能优化算法,该算法将固体的退火过程与优化问题的求解过程有机的结合起来,因此该算法被称为模拟退火算法。

（2）禁忌搜索算法

所谓禁忌就是禁止重复前面的工作。为了回避局部邻域搜索陷入局部最优的主要不足,禁忌搜索算法用一个禁忌表来记录已经达到过的局部最优点,在下一次的搜索中,利用禁忌表中的信息不再或有选择地搜索这些点,以此来跳出局部最优点。

最优化理论与方法 2

最优化理论与方法 2

- 1 - 最优化理论与方法

近代科学技术发展迅猛，人类从不同的领域对事物的探索也日益深入，把握规律的重要性也日益凸显。最优化理论与方法，就是人类探索规律的一种重要工具，也是科技发展的先锋派之一。它被广泛应用于解决实际问题，成为众多科技领域的最佳实践方法。

最优化理论与方法，是理解和阐释许多复杂现象的有效方式。它是一类工具，可以通过对复杂系统建模、设计实验并仿真分析，解决现实世界中的复杂问题。它具有优势，能够让我们整合系统中的数据，分析出各种潜在的解决方案，以达到全局最优的效果。

最优化理论与方法，主要涉及优化原理、数学建模、数理算法等知识体系。在建立数学模型时，意在求解满足一系列优化约束条件下，极小或极大化某一函数或变量，以达到系统最优化目标。它采用各种优化算法，其中包括最小二乘法、牛顿法、拟牛顿法、多层约束算法和动态规划等，不仅可以实现数学模型的构建，而且可以对数学模型进行有效的优化计算。

当前，最优化理论与方法已在工业技术、决策与决策分析、知识工程、经济学等诸多领域中得到广泛应用，从而解决了实际中许多复杂问题。例如，在决策分析中，它可以改善决策机制，从而使我们能够达到更完美的决策效果；在工程技术中，它可以为解决因参数设置不当而导致的质量问题提供有效方案；在机器学习领域，它可以为神经网络设计提供技术支持。

未来，随着科技的发展高速发展，最优化理论与方法将在解决实 - 2 - 际问题中发挥越来越大的作用，它将会帮助我们更好地理解世界，给我们更便捷地解决实际问题，从而为人类提供更大的实际利益和价值。

综上所述，最优化理论与方法，不仅是实现科学技术进步最有效方法之一，更是解决实际问题的重要工具，它将在解决实际问题中发挥越来越大的作用。

最优化理论与方法袁亚湘

最优化理论与方法袁亚湘

最优化理论与方法袁亚湘

袁亚湘（Nai-Yue YUEN，1922-1991）是中国著名数学家，他的研究领域包括最优化理论与方法。最优化理论与方法是数学中的一个重要分支，研究如何在给定条件下找到能达到最优目标的最优解。袁亚湘在这一领域做出了重要贡献，其研究成果被广泛应用于工程、经济学、管理学等领域。

袁亚湘的主要研究方向包括线性规划、非线性规划、多目标规划等。线性规划是最基础也是最常见的最优化问题，研究如何在线性约束条件下找到能使目标函数达到最大（或最小）的解。非线性规划则研究在非线性约束条件下如何找到最优解。多目标规划考虑多个目标函数的最优化问题，研究如何在这种情况下找到一个平衡的最优解。袁亚湘在这些问题的理论研究和方法设计方面都有重要的贡献。

袁亚湘提出了许多有效的最优化算法，包括被广泛应用的单纯形法、梯度法、对偶法等。这些算法在解决最优化问题时具有高效性和可行性，并且在实际应用中得到了广泛的验证和应用。袁亚湘的研究成果对于优化问题的求解以及相关领域中的决策和问题解决都有重要的指导意义。

总之，袁亚湘在最优化理论与方法领域做出了杰出的贡献，他的研究成果为该领域的发展和应用提供了重要的理论基础和实用方法。袁亚湘的工作对于提高决策效率、优化资源配置以及解决实际问题都具有重要的意义。