工程最优化第三章

《工程最优化第三章》由会员分享，可在线阅读，更多相关《工程最优化第三章（29页珍藏版）》请在金锄头文库上搜索。

1、第三章 非线性规划的几个基本概念 多元函数的Taylor展开 无约束问题的最优性条件 约束问题的最优性条件 最优化的数值计算方法要点：方向导数、下降方向、无约束函数极值的必要条件、平稳点、 可行方向、几何最优性条件、起作用约束、KT定理、KT点、下降迭代算法、算法的收敛性3.1 多元函数泰勒(Taylor)的展开公式 n元函数f(x1, x2, ,xn)在点x(0)= x1, x2, ,xnT附近展开到二次项 的Taylor公式为余 项其中 xxx(0) = x1x1(0), xnxn(0)T = x1, xnT (1) 梯度 是向 量f(x(0)梯度的重要性质：几个常用函数的梯度 f(x)

2、= b1x1+bnxn = BTxf(x) = b1, b2, , bnT =B f(x) = x12+xn2 = xTxf(x) = 2x1, 2x2, , 2xnT =2x f(x) =xTAx (aij = aji)f(x) =2Ax f(x) = c+BTx+1/2xTAxf(x) =B+Axx(0)f(x(1)x(1)点x(0)处的梯度方向与过该点的等值面垂直 。(2) 二阶导数矩阵Hesse矩阵 记为 H(x)n元函数f(x1, x2, ,xn)的Taylor展开公式的矩阵形式梯 度 H(x)3.2 方向导数与最速下降方向 （一）方向导数定义：设p为从x(0)出发的某单位向量，称函

3、数f(x)在点x(0)处沿方向p的变化率为f(x)在点x(0)处沿方向p的方向导数 f(x)x(0) Pf(x(0)（二）最速下降（上升）方向 称方向导数小于零的方向为下降方向, 方向导数大于零的方向为上升方向。最速上升方向为梯度方向f(x(0)，最速下降方向为负梯度方 向 f(x(0) 由于上升方向下降方向变化率为0f(x(0)最速上升方向 f(x(0) 最速下降方向x(0)称 为点x(0)处的下降方向集合3.3 局部最优与全局最优 （一）局部最优定义：设f(x)是定义在可行域S上的一个函数，若存在S中的点x*及其一个邻域N (x*)，使得对任意x N (x*)，都有f(x*) = f(x)

4、f(x*)0称x*为f(x)的局部最小点或极小点；称f* f(x*)为局部最小值 （二）全局最优定义：若存在S中的点x*，使得对所有x S，都有f(x*) = f(x)f(x*)0称x*为f(x)的全局部最小点或整体最小点；称f* f(x*)为全局最小值 xf(x)x1 x2 x3 x4 x5 x6ab3.4 无约束问题的最优性条件 研究最优性条件的目的：约定：实际问题目标函数可能不连续或导数不存在，甚至是离散函数，最优点可能在不连续点或导数不存在的点。以下讨论时假定f(x)处处连续可导. （1）用以求最优点； （2）用以判定给定点是否为最优点； （3）优化方法的基础。（一）无约束函数极值的必

5、要条件 若x*是f(x)的局部最小（大）点，则在x*处必有 以及Hesse矩阵 是半正定（半负定）的。 此条件仅是必要的，即对导数存在的点，若不满足上述条件，肯定不是极值点。但满足此条件，不一定是极值点.定义：对可微函数f(x), 使 的点为平稳点（或驻点 、定点） 对一元函数，两个条件变为 f (x)0及f ”(x)0 .极值点的候选点 平稳点导数不存在的点由必要条件可得“ 有资格”成为最优 的点, 如果有充分 条件该有多好!如 f(x)=x3 , 当 x = 0时，满足上述两个条件，但不是极值点 。（二）无约束函数极值的充分条件 若点x*满足 以及 是正定（负定）的，则 x* 是 f(x)

6、 的一个严格的局部最小（大）点。 例3.4.1 求f(x1,x2)=2x128x1+2x224x2+20的极值点及极值。解： 先求平稳点平稳点为 x*2, 1T Hesse矩阵为x*2, 1T是f(x)的严格极小点，f(x*)=10 其前主子式40， =160 Hesse矩阵是正定的。! ! ! 上述最优性条件都是对局部最优点而言的，工程问题都需要找全局最优点，这方面已进行大量研究，但仍没有一 个统一的判别方法。如果在可行域中只有一个局部最优点，即为全局最优点，有多个局部最优点，则想法全找出来，再比较确定全局最优点。3.5 约束问题的最优性条件 min f(x) s.t.最优点同时与目标函数及

7、约束函数的性质有关。存在两种情况 ： (a) 无约束极值点x(0)Sx2x1x2x1SSx(0) =x*x(0)x*(b) 无约束极值点x(0)S ! 目标函数的梯度等于零并不是约束问题的最优性必要条件！带有不等式约束的优化问题的最优性条件通常是一组不等式与方程，比较复杂的，很难求解，所以在一般情况下，不是直接求解这些条件来获得极值点，而是使用各种迭代法求出近似的极值点。但它在理论上很重要，是各种迭代方法的基础和依据 。 （一）可行方向与起作用约束 定义：设点xS，p是一个方向，如果存在实数a10, 使对所有a0, a1，有x+apS，则称p为点x 的一个可行方向,或容许方向、允许方向。 几何

8、上，若从x处沿方 向p引一射线，若该射 线起始端有一段在可 行域内，则这个方向p 就叫可行方向。 SxpSg1(x)=0g2(x)=0g3(x)=0! 是否为可行方向与起始点的位置有关！(1)若x是S的内点，则任何方向均为可行方向 g1(x) g2(x) g3(x)(2)若x是S的边界点，则有的方向不是可行方向 若x位于第i个约束上，即 ，若p为边界点x的可行方向， 则必有 几何最优性条件: 在判定边界点处的方向是否可行方向时，有必要对约束条件进行分类定义：对可行域S中某个点x, 称成立gi(x) = 0的那些不等式约束gi(x)0为点x处的起作用约束。称集合 为在点x处起作用约束的下标集 最

9、优点x*处一定不存在既可行又下降的方向（1.3.4）（1.3.5）（1.3.6）min f(x) s.t.（二）Kuhn-Tucker最优性必要条件 定理：设x*为非线性规划(1.3.4)-(1.3.6)的最优解，f, gi , hj为可微函数，其中=1,2, ,lT, =1, 2, ,mT 称为Lagrange乘子向量。 以上三式称为KT最优性条件，满足此条件的点称为KT点。 如果在x*处各个起作用约束的梯度向量 线性无关， 则存在向量,使下述条件成立：! 在无约束情形下，上述条件等同于梯度等于0 ！ 互补松驰条件 : 在gi(x)不是起作用 约束时, i *=0KT条件可写成 引入广义La

10、grange函数 和向量函数 g(x) = g1(x), g2(x), , gl(x)T，? 如何理解K-T定理? 它有什么几何意义?下面以最简单的两种情况加以说明：假定不存在等式约束(m=0)且n=2（二维），只有一个或两个起作用的不等式约束。 先考虑只有一个起作用不等式约束 g(x) 0 的情况 ：此时，K-T条件为（其中0 ） g(x)=0x1x2 Sf(x)的等值 线x(1)x(2) = x*x(1)不是最优 点， K-T条 件不成立x(2)是最 优点， K -T条件成 立S g1(x)=0x1x2 g2(x)=0 对有两个起作用不等式约束 g1(x) 0及 g2(x) 0的情况：此时

11、，K-T条件为f(x)的等值线x(1)x(1)不是最 优点，K- T条件不 成立S g1(x)=0x1x2 g2(x)=0f(x)的等值线x*x*是最优 点，K-T条 件成立K-T条件为! 若最优点x*位于几个起作用不等式约束的交点上，则 位于这些起作用约束的梯度所构成的锥角内 关于KT定理的几点说明 （1）定理中向量组 线性无关称为约束规范。但要验证是否满足约束规范是很困难的，因为需要事先知道x* 。对一些特定的非线性规划，约束规范总是成立的。（见p75)（2）约束规范不满足，定理不一定成立，最优点可以不是KT点 。例3.5.1 验证下面的非线性规划在最优点x*处不满足约束规范, 最优点不是

12、K-T点： 显然最优点 x*=x1*, x2*T=1, 0T, f = f (x*) = 4. 下面验证在 x* =1, 0T处不满足约束规范。 因为 g1(x*) = 0, g2(x*) 0，令迭代次数记数变量k=0 ；(2) 假定已得到第k次近似点x(k), (但它还不是极小点)，这时选择一个下降方向p(k) ，即 (3) 由x(k)出发，以p(k)为方向作射线 x(k)+p(k) （0），在此射线上选取步长因子k ，使得到的第k+1次近似点 x(k+1)=x(k)+kp(k) 满足 f(x(k+1)f(x(k) ； x(k)p(k)x(k+1)(4) 检验所得的新点x(k+1)是否满足精

13、度要求，若满足，就以x(k+1)为近似的极小点，终止迭代计算；否则令k=k+1，返回(2)继续作下一次搜索。下降迭代算法中，搜索方向p(k)和步长因子k的选 择是关键， 不同的p(k)和k 就构成不同的算法2、下降迭代算法的说明 (1) 搜索方向p(k)一般不可能直接指向极小点，需多次迭代 (2) 搜索步长的选择 x(k+1)=x(k)+kp(k) a. 固定步长法, 如k=1 b. 一维精确搜索法 f(x(k)+kp(k) = min f(x(k)+p(k)c. 不精确一维搜索法p(k)不一定指向极小点，一维搜索没必要 非常精确，因为对加速收敛的作用不大， 只要每次迭代函数值有所下降即可。

14、(3) 算法的收敛性与收敛速度 收敛性：算法迭代得到的点序列x(k)，能够在有限步内达到问题 的最优解x*，或者序列x(k)有一个极限点x*，则算法是收敛的 ！收敛的算法不一定是好算法，还要看收敛速度 ！x(k)p(k)x(k+1)定义：对于收敛于最优解x*的序列x(k)，若存在与k无关的常数 0和 1，使得当k从某个k0 开始，即 k k0时，恒成立则称序列x(k)具有阶收敛速度，为收敛系数或收敛比 越大，收敛速度越快 1，01，线性收敛1 2，或 1，=0 超线性收敛 2，二阶收敛 二次收敛性：当一个算法用于具有对称正定矩阵的二次函 数时，可在有限步迭代内获得极小点。 两者不是一回事f(x) = c+BTx+1/2xTAx(4) 迭代终止准则由于不知道真正的极小点在哪里, 所以不可能计算迭代点接近极小点的精确程度。只能根据计算过程中的一些信息判断是否终止计算。常用的终止准则有三种： c. 对无约束问题可用a.b.其中1，2，3称为允许误差。 3、算法的评价准则作业：P449 9；10P450 12；13(1) 通用性；(2) 达到一定精度所需计算函数值和导数的次数；(3) 终止时所用CPU时间；(4) 收敛性；(5) 上机准备工作的难易程度。