[工学]4无约束优化方法.ppt

无约束优化方法 可以利用极值定义，将上式变成求以下方程 这是个n个变量n个方程的方程组， 并且一般是非线性的。 与其使用数值计算方法求解非线性 方程组，不如用数值计算方法直接 求解无约束优化问题 无约束优化问题是：求n维设计变量 使目标函数 ，而对 没有任何限制条件。 数值求优的方法主要是爬山法 爬山法是利用已有的信息，通过计算点的一步一步 的直接移动，逐步逼近并最后达到最优点。 即给定初始点和搜索方向，沿该方向寻找最优点。 每一步计算都应该达到两个目的： （）获得目标函数的改进值 （）为下一步计算给出有用的信息 爬山法的计算过程分两步： （）选择爬山方向即搜索方向 （）在确定的方向上选择适当的步长进行探索 搜索方向和步长的生成及确定的方法不同，就派 生出不同的n维无约束优化问题的算法 无约束极小算法的粗框图 随机方向法 1、方向 （1）随机选择一个方向 （2）随机选择一个下降方向 （3）随机选择n个下降方向，选下降最多的方向 2、步长 （1）随机选择一个步长 （2）随机选择一个下降步长 （3）加速步长法：先选择一个下降步长h， 再以h的a(a1)倍向前搜索，直到不下降为止 3、找不到方向：以h的b(b1)倍向前搜索，直到不下降为止 （3） 否则 ，进行下一轮搜索，一直到满足精 度要求为止。 对于n个变量的函数，若在第k轮沿第i个坐标方 向 进行搜索，其迭代公式为 其中搜索方向取坐标方向，即 若 ，则 ， 不同性质目标函数坐标轮换法的求优效能 x1 x2 X(1) X* X(0)0 x1 x2 X* X(0) X(1) X(2) X(3) X(4) 0X(0)0 x1 x2 X* X(1) 收敛速度很快收敛速度很慢求优失效 最速下降法 所以，某点x处下降率最大的方向是其负梯度方向， 称为最速下降方向。 前面已经讨论过： 最速下降法 最速下降法即是以负梯度方向作为搜索方向，又称梯 度法。 所以，相邻两个迭 代点上的函数梯度 方向互相垂直 根据一元函数极 值的必要条件和复合 函数求导公式，得： 相邻两个迭代点上的函数梯度方向互相垂直 ，因此相邻两个搜索方向互相垂直。即在迭代点 向函数极小点靠近的过程中，走的是之字形的曲 折路线。 可以看出，在远离极小点的地方，每次迭代 可以使函数值有较多的下降，而在接近极小点的 地方，由于锯齿现象使每次迭代行进的距离缩短 ，因而收敛速度减慢。 从局部上看，在一点附近函数的下降是快的 ，但从整体上看则走了许多弯路。 求目标函数 的极小点。 解 取初始值 则初始点处函数值及梯度分别为 沿负梯度方向进行一维搜索，有 为一维搜索最佳步长，应满足极值必要条件 从而算出一维搜索最佳步长 及第一次迭代设计点位置和函数值 经过10次迭代，得到最优值 若将上例的目标函数引入变换 其等值线就由一族椭圆变成一族同心圆， 仍从 即 开始寻优 此时有 沿负梯度 方向进行一维搜索，有 为一维搜索最佳步长，可由极值条件算得 得到第一次迭代的结果就是最优解 最速下降法的收敛速度与变量的尺度关系很 大，下面是最速下降收敛速度的估计式 式中 的海赛矩阵最大特征值； 其最小特征值。 对于等值线为椭圆的二次型函数 ， 其海赛矩阵 两个特征值分别为 。因此 可见等值线为椭圆的长短轴相差越大，收敛就越慢。 两个特征值相等 ，因此 代入（4-4），有 得 即经过一次迭代便可到达极值点。 梯度法的特点 n（1）理论明确，程序简单，对初始点要求不严格。 n（2）对一般函数而言，梯度法的收敛速度并不快，因为最速下 降方向仅仅是指某点的一个局部性质。 n（3）梯度法相邻两次搜索方向的正交性，决定了迭代全过程的 搜索路线呈锯齿状，在远离极小点时逼近速度较快，而在接近极 小点时逼近速度较慢。 n（4）梯度法的收敛速度与目标函数的性质密切相关。对于等值 线(面)为同心圆（球）的目标函数，一次搜索即可达到极小点。 n（5）应用最速下降法可以使头几次迭代的收敛速度很快，所以 它可与其他方法配合使用 编程示例： 目标函数：min f(x0,d,a) 求函数值(标量) ：f(题号,初始点向量 x0,方向向量d,步长 a) 求方向导数值(标量)：f1(题号,初始点向量 x0,方向向量d,步长 a) 求梯度值(向量)：g(题号, x) 或 g(题号,初始点向量 x0,方向向量d,步长 a) 一维搜索函数： fmin(一维搜索方法,题号,初始点向量 x0,方向向量d,初始步长 a0) 多变量搜索函数： fmins(多变量方法, 一维搜索方法,题号,初始点向量 x0 ,初始步长 a0) nfunction y=f(no,x0,d,a) nx=x0+a*d; nif no=1 n y=x(1)*x(1)*x(1)*x(1)+2*x(2)*x(2)*x(2)*x(2); nend nfunction y=f(no,x0,d,a) nx=x0+a*d; nif no=1 n y=4*x(1)*x(1)*x(1)*d(1)+8*x(2)*x(2)*x(2)*d(2); nend nfunction y=g(no,x) nif no=1 n y=4*x(1)*x(1)*x(1);8*x(2)*x(2)*x(2); nend nfunction x,y=fmin(m1,no,x0,d,a0,e) na1,a3,a2=range(no,x0,d,a0); nif m1=1 n x,y=gold(no,x0,d,a1,a3,e); nend nfunction xx,yy=gold(no,x0,d,a,b,e) nr=0.618; na1=b-0.618*(b-a); ny1=f(no,x0,d,a1); na2=a+0.618*(b-a); ny2=f(no,x0,d,a2); naa=(a+b)/2; nxx=x0+d*aa; nyy=f(no,x0,d,aa); nfunction x,y=tidu(n1,no,x0,a0,e) nx2=x0;x1=x2-e; nwhile norm(x2-x1)=e n x1=x2; n d=-g(no,x1); n x2=fmin(n1,no,x1,d,a0,e); nend nx=x2;y=f(no,x2,1,0); 不精确的一维搜索 一维搜索过程是最优化方法的最基本组成部分 ，精确的一维搜索方法通常需要花费很大的工作 量，特别是当迭代点远离问题的解时，精确的求 解一个一维子问题通常不是十分有效率的。 另外，在实际上，很多优化方法，例如拟牛 顿法，其收敛速度并不依赖于精确一维搜索过程 。 因此，只要保证目标函数值在每一步都有满 意的下降，使用不是非常精确的一维搜索，就可 以大大节省工作量。 单纯形法 在实际工程的最优化问题中，目标函数的导数往往很难 求出或根本无法求出。 单纯形法只需要计算目标函数值，不需计算导数，因此 计算比较简单，其几何概念也比较清晰，属于直接法一类的 无约束最优化方法。 直接法的一个优点即是适用于不知道目标函数的具体数 学表达式的情况。 单纯形法 单纯形：n维空间中由n+1个线性独立的点构成的简单图 形或凸多面体。 可知，一维空间中的单纯形是线段，二维空间中的单纯 形是三角形，而三维空间中的单纯形则是四面体。 单纯形法： (1) 根据问题的维数n，选取n+1个顶点构成的单纯形 (2) 求出这些顶点处的目标函数值并加以比较，确定有最大 值的点及函数下降方向 (3) 再设法找到一个新的比较好的点替换那个有最大值的点 ，从而构成新的单纯形。 (4) 随着迭代的进行，单纯形将向着最优点收缩。 新单纯形的构造方法有反射、扩张、压缩、收缩等 （1）反射 设除了最劣点X1以外的基余顶点的中心为X4， 作X1关于点X4的对称点X5，称X5为X1的反射点。 求反射点的过程称之为反射。 设当前的单纯形的顶点为X1，X2，X3，且有 （2）扩张在得到反射点X5之后， 如果X5优于原单纯形的最劣点（即有 ）， 表明反射方向（X5X1）是有利方向，反射成功。 若进一步有 ，可沿反射方向前进适当的距离 到点X6。 X6称之为扩张点，求扩张点的过程称之为扩张。 扩张之后，若扩张点X6优于反射点X5，则扩张成功，以X6取代 X1，得新单纯形X6,X2,X3； 否则，扩张失败，舍弃扩张点，以反射X5点取代X1，得新单纯 形X5,X2,X3。 如果出现 。表示反射完全失败，应退回到介于X4 与X1之间的某个点X8。 （3）压缩在得到反射点X5之后，如果有 表示反射部分成功，方向（X5X1）虽然是有利方向，但X5前 进过远，应压缩到介于X4与X5之间的某个点X7。 上述两种从反射点向X1方向后退的过程都称之为压缩。 如果压缩点优于原来的最劣点X1，称压缩成功，并以压缩点 取代原最劣点，构成新单纯形X7,X2,X3或X8,X2,X3；否则 ，称之为压缩失败，舍弃压缩点。 （4）收缩若压缩失败，则应缩短当前单纯形的边长： 令最优点X3不动，而其余顶点向X3方向收缩，使边长缩短 （通常缩短一半），以产生新单纯形。 如下图所示，点X1收缩到点X9，点X2收缩到点X10，得新 单纯形X9,X10,X3，这一过程称之为压缩。 牛顿型方法 一维情况下牛顿迭代公式 利用目标函数在点处的二阶Taylor 展开式去近似目标函数， 用二次函数的极小点 去逼近目标函数的极小点 基本思想: 多维情况下牛顿迭代公式 根据极值的必要条件，得： 对正定二次函数来说，上述的泰勒展开式不 是近似的，而是精确的。海赛矩阵是一个常数矩阵 ，其中各元素均为常数。 因此，用牛顿法求解正定二次函数时，无论 从哪个初始点出发，计算所得牛顿方向直指极小点 ，而且步长等于1 二次收敛的概念：如果某一种迭代方法能够 使二次型函数在有限次迭代内达到极小点，则称此 迭代方法是二次收敛的。 求目标函数 的极小点。 解 取初始值 则： 代入牛顿法迭代方法，得： 对于一般非线性函数，点Xk+1只是原函数的 一个近似极小点。故将此点作为下一个迭代Xk+1 。 另外，从牛顿法迭代公式的推演中可以看到 ，迭代点的位置是按照极值条件确定的，其中并 未含有沿下降方向搜索的概念。 因此对于非正定函数，如果采用上述牛顿法 迭代公式，有时会使函数值上升，为了解决这个 问题，提出“阻尼牛顿法” 其中： 为沿牛顿方向进行一维搜索的最佳步长，可 称为阻尼因子。 可通过如下极小化过程求得 如果把 看作是一个方向， 称其为牛顿方向，则阻尼牛顿法的迭代公式为： 这样，原来的牛顿法就相当于阻尼牛顿法的步 长因子 取成固定值1的情况。 由于阻尼牛顿法每次迭代都在牛顿方向上进行 一维搜索，这就避免了迭代后函数值上升的现象， 从而保持了牛顿法二次收敛的特性，而对初始点的 选取并没有苛刻的要求。 阻尼牛顿法的计算步骤如下： 1）给定初始点 ，收敛精度 ，置 。 2）计算 和 。 3）求 ，其中 为沿 进行一维搜 索的最佳步长。 4）检查收敛精度。若 则 ， 停机；否则，置 ，返回到2继续进行搜 索。 牛顿法优点 (1) 如果正定且初始点选取合适，算法 二阶收敛 (2) 构造搜索方向利用了函数的所有的一阶导数和 二阶导数，产生的搜索方向直指极小点； (3)对于正定二次函数，从任意初始点出发，一次迭 代即可得到极小点。对于一般函数，迭代的次数比 其它算法都要少。 阻尼牛顿法在特定条件下它具有收敛最快的 优点，并为其他的算法提供了思路和理论依据 牛顿法缺点 (1) (2) 对多数问题 算法不是整体收敛的 每次都需要计算计算量大 (3)每次都需要解 方程组有时奇异或病态的 ， 无法确定 或不是下降方向 (4)收敛到鞍点或极大点的可能性并不小 (5)初始点需选在X*附近，有一定难度 用阻尼牛顿法求解： 解： 显然不是正定的， 但： 于是， 沿方向进行线搜索， 得其极小点从而迭代不能继续下去 带保护的牛顿法算法 给出 Step1: 若为奇异的，转Step8，否则， Step2: 令 Step3: 若 为奇异的，转Step8，否则， 则转Step8，否则， Step4: 若 则转Step9，否则， Step5: 沿方向进行线搜索， 求出 并令 Step6: 若停； Step7: 令 转Step1； Step8: 令转Step5； Step9: 令转Step5. 用带保护的牛顿法求解： 解： 显然不是正定的， 但： 于是， 因为，故令， 沿进行线搜索得： 第二次迭代： 而： 使故令 沿进行线搜索， 得出 于是: 此时: 一般迭代式： 梯度法： 牛顿法： 阻尼牛顿法： 梯度法与牛顿法： 梯度法构造简单，只用到一阶偏导数，计算量小，初始点可 任选，且开始几次迭代，目标函数值下降很快；其主要缺点是迭 代点接近X*时，即使对二次正定函数收敛也非常慢。 牛顿法收敛很快，对于二次函数只需迭代一次便达到最优点 ，对非二次函数也能较快迭代到最优点，但要计算二阶偏导数矩 阵及其逆阵，对维数较高的优化问题，其计算工作和存储量都太 大。 针对梯度法收敛速度慢，提出收敛速度更快的共轭梯度法。 针对牛顿法的缺点提出了变尺度法。 变尺度法 一：尺度矩阵的概念 变量的尺度变换是指放大或缩小各个坐标。 通过尺度变换可以把函数的偏心程度降低到最 低限度。尺度变换技巧能显著地改善几乎所有极小 化方法的收敛性质。 求目标函数 的极小点。 引入变换 若矩阵G是正定的，则总存在矩阵Q，使得： 即将函数的偏心降为0 对于一般二次函数 如果进行尺寸变换 则在新的坐标系中，函数 的二次项变为 （单位矩阵） 这说明二次函数矩阵G的逆阵，可以通过尺 度变换矩阵Q来求得。 牛顿方向便可写成 牛顿迭代公式变为 用 右乘等式两边，得 再用Q左乘等式两边，得 所以 例子： 其中 若取 作变换 则在变换后的坐标系中，矩阵G变为 则只需通过一次迭代即可求得极小点 比较牛顿法迭代公式 和梯度法迭代公式 可以看出，差别在于牛顿法中多了 部分(称为尺 度矩阵H)。 故牛顿法就可以看成是经过尺度变换后的 梯度法 。经过尺度变换，使函数的偏心率减小到0，函数的 等值面变成球面，使设计空间中任意点处的梯度都 通过极小点。（对二次函数）。 二、变尺度矩阵 对于一般函数f(x)，当用牛顿法寻求极小点时， 其牛顿迭代公式为 为了避免在迭代公式中计算海赛矩阵的逆矩阵 ，可以用在迭代中逐步建立的变尺度矩阵 来替换 ，即构造一个矩阵序列 来逼近海 赛逆矩阵序列 。 其中 是从 出发，沿方向 搜索而得 到的最佳步长。 1）为了保证迭代公式具有下降性质，要求Hk 中的每个矩阵都是对称正定的 为了使变尺度矩阵 确实与 近似，并必须附 加某些条件： 证：若要求搜索方向 为下降方向，即要 求 也就是 ，即 ，即 应为对称正定。 2）要求 之间的迭代具有简单的形式。显然 为最简单的形式，其中 为校正矩阵。上式 称作校正公式。 3）要求 必须满足拟牛顿条件。 拟牛顿条件： 设迭代过程已经进行了k+1步， ， 均已求出，现 在推导 所需要的条件： 当f(x)为具有正定矩阵G的二次函数时， 因为具有正定海赛矩阵 的一般函数，在极小 点附近可用二次函数很好的近似，所以 如果迫使 满足类似于上式的关系 那么 就可以很好地近似于 。 上述关系称拟牛顿条件 根据上述拟牛顿条件，不通过海赛矩阵求逆就可 以构造一个矩阵 来逼近海赛矩阵的逆阵 ，这类 方法统称作拟牛顿法。 由于变尺度矩阵的建立应用了拟牛顿条件，所以 变尺度法也是属于一种拟牛顿法。 还可以证明，变尺度法对于具有正定矩阵G的二次 函数，能产生对G共轭的搜索方向，因此变尺度法又可 以看成是一种共轭方向法。 三、变尺度法的一般步骤 1）选定初始点 和收敛精度 。 2）计算 ，选取初始对称正定矩阵 （例如 ），置 。 3）计算搜索方向 。 4）沿 方向进行一维搜索 ，计算 5）判断是否满足迭代终止准则，若满足则 ， 停机。 6）当迭代n次后还没找到极小点时，重置 为单位 矩阵I，并以当前设计点为初始点，返回到2进行下 一轮迭代，否则转到7。 7）计算矩阵 ，置 返回到3。 对于校正矩阵 ，可由具体的公式来计算，不 同的公式对应不同的变尺度法，但不论哪种变尺度 法， 必须满足拟牛顿条件 满足上式的 有无穷多个，因此变尺度法（属于 拟牛顿法）构成一族算法。 DFP算法 在变尺度算法中，校正矩阵采用不同的形式， 就形成不同的变尺度算法。 DFP算法中的校正矩阵如下： 其中 、 是n维待定向量， 、 是待定常数 ， 、 都是对称秩一的矩阵 根据校正矩阵 要满足拟牛顿条件 满足上面方程的待定向量 和 有多种取法，我们取 注意到 和 都是数量，再设 这样就可以定出 从而可得DFP算法的校正公式 当初始矩阵 选为对称正定矩阵时，DFP算法 将保证以后的迭代矩阵 都是对称正定的，即使将 DFP算法施用于非二次函数也是如此，从而保证算 法总是下降的。 这种算法用于高维问题（如20个变量以上）， 收敛速度快，效果好。DFP算法是无约束优化方法 中最有效的方法之一，因为它不单纯是利用向量传 递信息，还采用了矩阵来传递信息。 DFP算法是戴维登（Davidon）与1959年提出的 ，后来由弗莱彻（Fletcher）和鲍威尔（Powell）与 1963年作了改进，故用三人名字的字头命名。 用DFP算法求下列问题的极值： 解： 1）取初始点 ，为了按DFP法构造第 一次搜寻方向d0，需计算初始点处的梯度 取初始变尺度矩阵为单位矩阵A0=I，则第一次 搜寻方向为 沿d0方向进行一维搜索，得 为一维搜索最佳步长，应满足 得: , 2）再按DFP法构造点x1处的搜寻方向d1，需计算 代入校正公式 = = 第二次搜寻方向为 再沿d1进行一维搜索，得 为一维搜索最佳步长，应满足 , 得 3）判断x2是否为极值点 梯度: 海赛矩阵 : 梯度为零向量,海赛矩阵正定。可见点满足极值 充要条件，因此为极小点。 BFGS算法 DFP算法由于舍入误差和一维搜索不精确 ，有可能导致计算出的H矩阵奇异，而使数据 稳定性方面不够理想。而BFGS法具有较好的 数值稳定性，它基本上算是最成功的一种变尺 度算法。 BFGS迭代公式： 最小二乘法（Gauss-Newton法） Marquardt法 共轭方向及共轭方向法 共轭方向的概念是在研究二次函数 （G为对称正定矩阵）时引出的。 为了克服最速下降法的锯齿现象以提高 其收敛速度，发展了一类共轭方向法。 为了避免搜索锯齿的出现，我们取下一次迭代 的方向直指极小点。 方向上的最佳步长。 二元二次函数：等值线为同心椭圆族、过椭圆中 心的直线与诸椭圆交点处的切线相互平行。 那么这样的 方向应该满足什么条件？ 将等式两边同是左乘 ，又由于 称 和 对G是共轭方向。 定义 设G为nn对称正定矩阵，若n维空间中有m 个非零向量 满足 则称 对G共轭，或称是G的共轭方向。 当G=I（单位矩阵）时，上式变成 即向量 互相正交。由此可见， 共轭概念是正交概念的推广，正交是共轭的特例。 性质1 若非零向量系 是对G共轭的， 则这m个向量是线性无关的。 性质3 从任意初始点 出发，顺次沿n个G的共轭方 向 进行一维搜索，最多经过n次迭代可 以找到二次函数 极小点 。 此性质表明这种迭代方法具有有限步收敛的 特性，即具有二次收敛性。 性质2 在n维空间中互相共轭的非零向量的个数不超 过n。 共轭方向法 共轭方向法 程序框图如右图 所示。提供共轭 向量系的方法有 许多种，从而形 成各种具体的共 轭方向法，如共 轭梯度法，鲍威 尔（Powell）法 等。 共轭方向的选择有多种，下面介绍格拉姆斯密 特（Gram-Schmidt）向量系共轭化方法，它是格 拉姆斯密特向量系正交化方法的推广。 上述共轭向量法是针对二次函数的，一般也可 以用于非二次函数。为了避免海塞矩阵计算，可以 采用更加有效的构建共轭向量的方法。 共轭梯度法是共轭向量法的一种，因为在该方 法中每个共轭向量都是依赖于迭代点处的负梯度构 造出来的，称共轭梯度法。 共轭梯度法 先讨论共轭方向与梯度的关系。 沿着这些共轭方向一直搜索下去，直到最后迭 代点处梯度的模小于给定允许值为止。 若目标函数为非二次函数，经过n次搜索还未达 到最优点，则以最后得到的点为初始点，重新计算 共轭方向，直到满足精度为止。 ，已知初始点1,1T l解： 1）第一次沿负梯度方向搜寻 计算初始点处的梯度 一维搜索最佳步长应满足 l迭代精度 。 得: 2）第二次迭代： 代入目标函数 得 因 收敛。 由 从而有： 直接利用函数值来构建共轭向量的共轭向量法。 原始共轭方向法、鲍维尔共轭方向法 n二维情况: 1）任选一初始点x0 ，再选两个线性无关 的向量，如坐标轴单 位向量e1=1,0T和 e2=0,1T作为初始 搜索方向。 2）从x0出发，顺次沿e1 ， e1作一维搜索，得 点，两点连线 得一新方向d1 沿d2作一维搜索得点x2 。 即是二维问题的极小点x* 。 方法的基本迭代格式包括共轭方向产生和方向替换两 主要步骤。 用 d1代替e1形成两个线性无关向量d1 ,e2 ，作为 下一轮迭代的搜索方向。再 从出发，沿d1作一 维搜索得点 ，作为下一轮迭代的初始点。 3）从 出发，顺次 沿e2,d1 作一维搜索 ，得到点 ，两点 连线得一新方向: 在使用前述原始共轭向量法时，在产生n个共 轭方向时，有可能是线性相关或接近线性相关的， 这会导致不能形成共轭方向，从而不能收敛到真正 最优点。 鲍维尔共轭向量法的改进之处：在构建第k+1 环共轭方向时： 首先判断原基本向量组是否需要替换 如果需要替换，还要进一步判断原基本向量 组中哪个向量最坏 然后再用新产生的向量替换这个最坏的向量 ，以保证逐次生成共轭方向。 步长加速法（Hook-Reeves算法） 步长加速法也称之为离散步长的Hook- Reeves算法，是一种不使用导数的直接搜索算 法，其算法过程可分成两个基本阶段：坐标循 环试探及模矢加速搜索。 坐标循环试探: 从初始探点Y0出发，依次沿n个坐标方向用固定步长 进行试探，寻找更好的点 。 模矢加速搜索: 沿模矢方向 加大步长前进，以得到第k+1 次迭代的出发点Y0，这样就完成了一次迭代. 然后再从新的Y0出发，进行下一轮坐标循环试探， 如此重复进行，使目标值不断减小。 步长加速法算法 设问题为 X0为初始点 个坐标轴的单位方向向量 初始坐标循环试探的步长为0 模矢加速搜索的加速步长因子为a1（通常取a=2） 迭代终止准则为 ( 为预先确定的正数）。 （1） （2） （3）若 （2）；否则，转（4） 否则转（6） 否则，令 （6） 否则，转（2） （5） （4） 转（5）； 表表1 1 无约束优化方法搜索方向之间的相互联系无约束优化方法搜索方向之间的相互联系 间接法间接法 搜索方向 函数梯度