优化设计的数学基础.ppt

第二章 优化设计的数学基础,2.1 多元函数的方向导数与梯度,1、方向导数 一个二元函数 在 处的偏导数定义为 而 和 分别是函数 在x0点处沿坐标轴x1和x2方向的变化率。因此函数 在 点处沿某一方向d的变化率如图2-1所示， 其定义应为 称其为该函数沿此方向的方向导数。据此， 偏导数 、 也可以看成是该函数分别沿x1和x2方向的方向导数。所以方向导数是偏导数概念的推广，偏导数是方向导数特例。,方向导数和偏导数之间的关系， 从下述推导可知,类似的， 一个三元函数 在 点处沿d方向的方向导数和偏导数的关系如下所示，见图2-2,类似的， 一个n元函数 在 点处沿d方向的方向导数,其中的cosi为d方向和坐标轴xi方向之间夹角的余弦。,2、二元函数的梯度,令,称其为函数f(x1,x2)在x0点的梯度。,设,为d方向的单位向量， 则可得：,例2-1 求二元函数 在x0 = 0 0T处函数变化率最大的方向和数值。,解：由于函数变化率最大的方向是梯度方向， 这里用单位向量p表示， 函数变化率最大的数值是梯度的模f(x0)。求f(x1,x2)在x0点处的梯度方向和数值，计算 如下,三、向多元函数的推广 函数 f(x1,x2， , xn)在x0 (x1,x2， , xn)处的梯度可定义为 函数 f(x1,x2， , xn)在x0处沿d的方向导数可表示为 d方向上的单位向量 梯度f(x0)的模为 梯度方向单位向量为 ，它与函数等值面 f (x) = c相垂直，也就是和等值面上过x0的一切曲面相垂直，如图2-5所示。,2.2 多元函数的泰勒（Taylor)展开式,多元函数的泰勒(Taylor)展开在优化方法中十分重要，许多方法及其收敛性证明都是从它出发的。,2.3 无约束优化问题的极值条件,一、一元函数极值条件 对于连续可微的一元函数f(x),如在x*点有极值，其必要条件为： f (x*)=0 若x*为有极小值点，其充分条件为： f ”(x*)0 若x*为有极大值点，其充分条件为： f ”(x*)0,2.4 凸集与凸函数与凸规划,2.4.1凸集与非凸集,2.5 等式约束优化问题的极值条件,对于等式约束优化问题： minf(x) s.t. hk(x) = 0 (k = 1,2,m) 需要导出极值存在的条件。 数学上有两种处理方法： 消元法（降维法） 拉格朗日乘子法（升维法）,一、消元法 1）二元函数只有一个等式约束 minf(x1，x2) s.t. h (x1，x2) = 0 处理方法：将x1表示为x1 = (x2), 并代入目标函数中消去x1,变成一元函数F(x2), 则等式约束优化问题变为无约束优化问题。目标函数二维变一维,故称降维法。 2）n维情况 minf(x1，x2，xn) s.t. hk (x1，x2 ，xn) = 0 (k = 1,2,l) 由l个约束方程将n个变量中的前l个变量用其余n-l个变量表示， 有 x1 = (xl+1,xl+2,xn) x2 = (xl+1,xl+2,xn) xn = (xl+1,xl+2,xn) 将这些函数关系代入到目标函数中， 得到只含有xl+1,xl+2,xn共n-l个变量的函数F(xl+1,xl+2,xn), 从而利用无约束优化问题的极值条件求解。（因为将l个约束方程联立往往求不出解来，实际上难于求解）,二、拉格朗日乘子法 通过增加变量将等式约束优化问题变成无约束优化问题。 对于 minf(x) s.t. hk(x) = 0 (k = 1,2,l) 在极值点x*处有 (k = 1,2,l) 令 可通过其中的l个方程 (a) 来求解l个待定系数1，2，l，使得l个变量的微分dx1, dx2, ，dxl 的系数全为零。于是得到,则有 (b) (j = l+1, l+2,n) 式（a),(b)及等式约束条件 hk(x) = 0 (k = 1,2,l) 就是点x达到约束极值的必要条件。 式（a),(b)可以合并写成 (i = 1, 2,n) （c） 令 式中 待定系数k称为拉格朗日乘子， F(x, )称为拉格朗日函数。本方法称为拉格朗日乘子法。 把F(x, )作为一个新的无约束条件的目标函数来求解它的极值点， 所得结果就是满足约束条件的原目标函数的极值点。自F(x, )具有极值的必要条件： 可得l+n个方程。由这些方程组求得函数f(x)的极值点x*=x1* x2* xl*T.,例2-4 用拉格朗日乘子法计算极值点坐标 f(x1，x2)=4x12+5x22 s.t. h (x1，x2) = 2x1+3x2-6=0 解： F(x, )=4x12+5x22+ (2x1+3x2-6) Fx1=8x1+2=0 x1=-/4 Fx2=10x2+3=0 x2=-3/10 F =2x1+3x2-6=0=-30/7 所以得 x1=1.071， x2=1.286 此即为所求极值点x*.,2.6 不等式约束优化问题的极值条件,不等式约束的多元函数极值的必要条件是库恩-塔克（Kuhn-Tucher)条件，是非线性理论的重要基础。,一、一元函数在给定区间上的极值条件 一元函数在给定区间a, b上的极值问题，可写成如下的不等式约束问题 minf(x) s.t. g1(x) = a-x 0 g2(x) = x-b 0 采用拉格朗日乘子法，将上述两个不等式约束变为等式约束 h1(x, a1)=g1(x)+a12 = a-x+a12 h2(x, b1) = g2(x)+b12 = x-b+b12 并得到拉格朗日函数 F(x,a1,b1,1,2)= f(x)+ 1 h1(x, a1)+2 h2(x, b1) 1,2为对应于不等式约束条件的拉格朗日乘子， 10,2 0,根据拉格朗日乘子法，此问题的极值条件是,分析,即1，g1(x)二者必有一个等于0，因此可以写成1g1(x)=0。,同样对于，2b1=0 进行分析可得,因此可以写成2g2(x)=0。,于是，对于一元函数f(x)在给定区间上的极值条件，可以完整地表示为 这样的分析方法可以推广到二元甚至多元函数不等式约束优化问题上去，从而给出著名的库恩一塔克条件。,(a),对于一元函数f(x)在给定区间a, b 上的极值条件，式(a)中的第一式可简化为,分析极值点x*在区间a, b 中的位置，可能出现3种情况，如图2-11所示。 这和如图2-11所示的从几何概念分析的结果完全一致。,由以上分析可知，对应于不起作用约束的拉格朗日乘子取零值。因此可以引入起作用约束的下标集合J(x) = j|gj(x) = 0, j = 1, 2。 当ax*b时，两个约束均不起作用，故有J(x*) = , 1 = 2 = 0。 当x* = a时，第一个约束起作用，故有J(x*) = 1, 1 0， 2 = 0。 当x* = b时，第二个约束起作用，故有J(x*)=2, 1 =0， 2 0。 于是可将式(a)改写成如下形式： 也就是说，在极值条件中只考虑起作用的约束及相应的拉格朗日乘子。,二、库恩-塔克条件 对于多元函数不等式约束优化问题 minf(x) s.t. gj(x) 0 (j = 1,2,m) 同样可以应用拉格朗日乘子法推导出相应的极值条件。为此，需要引入m个松弛变量 使不等式约束gj(x) 0 (j = 1,2,m)变成等式约束 gj(x) + xn+j2 = 0 (j = 1,2,m), 从而组成相应的拉格朗日函数。 其中，是对应于不等式约束的拉格朗日乘子向量 = 1 2 jm T,并且满足非负要求，即 0。 根据无约束极值条件，在极值点处有,仿照对一元函数在给定区间上极值条件的推导过程，可以得到具有不等式约束多元函数极值条件 此即著名的库恩-塔克条件。 若引入起作用约束的下标集合J(x*) = j|gj(x) = 0, j = 1, 2，m。 库恩-塔克条件又可以写成,将上式用梯度形式表示，为 或者 表明库恩-塔克条件的几何意义是，在约束极小值点x*处，函数f(x)的负梯度一定能表示成所有起作用约束在该点梯度（法向量）的非负线性组合。,库恩-塔克条件的几何意义 若xk点是极值点，则可以写成 此条件要求点xk一定要落在约束曲面g1(x)=0和g2(x)=0的交线上，而且-f(xk)和 g1(xk) 及 g2(xk)应该线性相关，即三者共面。,图2-13是在点xk处的截面图形。此时可能出现两种情况：,由于-f(x*)和 g1(x*) 及 g2(x*)在一个平面内，则前者可以看成是后者的线性组合。又因-f(x*)处于 g1(x*) 和 g2(x*)的夹角之间，所以线性组合的系数为正，即有 其中1 0, 20。此为目标函数在两个起作用