最优化方法教案(2).doc

PAGE PAGE 35 第3章 无约束最优化方法 无约束最优化问题：， 方法：迭代法 ● 直线搜索： 直线搜索方法：黄金分割法，抛物线插值法，平分法 §3.1 直线搜索 一、黄金分割法 二、平分法 问题：设，，，，并给出精 度.求近似极小点和极小值。 基本原理：在内有极小点,且. 令,若,则在内有极小点,将的右边一半去掉,得新的搜索区间;若,则在内有极小点,将的左边一半去掉,得新的搜索区间。 计算步骤 1．令； 2．若，则转4，否则； 3．计算，若，则转4； 若，则，转1； 若，则，转1； 4．令，停止。 注：若满足条件的尚未得到，则可按以下步骤确定： 首先任取一点，指定步长。 1．计算，若，则，停止； 若，则转4；若，则； 2．令； 3．若，则，停止； 若，则令，，停止； 若，则令，转2； 4．令； 5．若，则，停止； 若，则令，，停止； 若，则令，转4。 例： 三、抛物线插值法 §3.2 最速下降法 最速下降法，又称梯度法。是最古老的一种算法。在每次迭代中，沿最速下降方向进行搜索。迭代公式为： §3.3 牛顿法 设二次函数的最优解存在，用梯度法迭代一次即得最优解：。由极值的必要条件，有 则 若取，则。 推广到一般函数，取 其中，为在处的海色矩阵。 一、牛顿法的基本思想： 在迭代过程中将在点附近按泰勒公式展开，取到二次项 以二次函数的极小点作为的极小点的第次近似： 得牛顿法的迭代公式： ………………（*） 特殊地，若（一维），（*）式为 即为一维情形（一维搜索）的牛顿法的迭代公式。 牛顿法的步骤 已知及梯度，海色矩阵，给出精度。 1．选定初始点，计算，，令； 2．计算；若，则令，停止，否则； 3．计算； 4．计算，； 5． 计算； 6．令，转2。 三、主要结论 定理：已知目标函数及梯度，正定，则由式（*）确定的为下降方向。 证明：由正定，则也正定。又，则有 则为下降方向。 例1： 例2： §3.4 共轭方向法与共轭梯度法 （一）共轭方向法 一、共轭方向 定义1：设为n阶对称正定方阵，若对于n维空间中的两个非零向量和有，和正交，即，则称向量和关于共轭，或称和是共轭的。 推广：设为n阶对称正定方阵，n维非零向量满足 ， 即其中任何两个向量都是共轭的，则称向量组是共轭（向量）。 特殊：当，共轭即为正交。 例： 定理1：设为n阶对称正定方阵，非零向量组为共轭，则此向量组线性无关。 二、共轭方向法 1. 特点：第次迭代时所取的方向和以前各次迭代所取的方向都是共轭的。 2. 性质 设二次函数，其中为n阶正定矩阵， ，为常数，为初始点。 定理2：设是n元二次函数的极小点，方向为共轭，是由共轭方向法产生的点列，则至多迭代n次就能够达到极小点。 （对于二次函数，该性质称为二次终止性） 共轭方向的形成可以概括为以下定理： 定理3：设1o二次函数，为n阶正 定矩阵，为初始点； 2o； 3o； 4o若，则确定方向： 则 i) 都是下降方向; ii) 是共轭的; iii) ,; iv) ,. (二) 共轭梯度法 一、系数的其它形式 1. 对于上述二次函数, 由, 得 （由3o：) 则有 ————SW共轭梯度法 2. 由，，得 （由4o：） 则有 ————FR共轭梯度法 3. ————PRP共轭梯度法 二、最佳步长的计算公式 由 有 得最佳步长： 三、FR共轭梯度法的步骤（适用于一般非线性函数，包括二次函数） 已知初始点及收敛精度。 1．计算；若，令，停；否则 2．令，，转6 3．按FR公式计算： ， 4．令，若，转8；否则 5．若，转8；否则 6．作线搜索： 7．计算；若，则令，停；否则转3 8．令，，，，转6； 例：试用FR共轭梯度法求下列函数 的极小点，取初始点。 解： §3.5 步长加速法 §3.6 方向加速法（Powell法） 方向加速法，又称Powell法，是无约束最优化的直接方法之一。 一、基本思想：在迭代过程中的每个阶段都作n+1次线搜索。首先，依次沿给定的n个线性无关的方向作线搜索，再沿由这一阶段的起点到第n次搜索所得点的方向作一次线搜索，把这次所得的点作为下一阶段的起点。下一阶段的n个搜索方向。 二、步骤 设的极小点的初始近似为，控制误差为。取n个线性无关的方向，是第个分量为1的单位向量。 1．，； 2．，； 3．作线搜索： 令 4．令； 5．若，则转3，否则； 6．； 7．作线搜索： 令 8．若 或 。则转10，否则； 9．令， （可略），，转2； 10．令，停. 例：设，初始点为. 试用Powell法求的极小点。 解：1. 第一次迭代, . (