优化设计2数学基础.ppt

《优化设计2数学基础.ppt》由会员分享，可在线阅读，更多相关《优化设计2数学基础.ppt（27页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、优化设计优化设计2 2数学基础数学基础例：例：在在 处梯度为处梯度为但但 只是双曲抛物面的鞍点，而不是极小点。只是双曲抛物面的鞍点，而不是极小点。为了判断从上述必要条件求得的为了判断从上述必要条件求得的x*是否是极值点，需建立极是否是极值点，需建立极值的充分条件。值的充分条件。根据函数在根据函数在x*点处的泰勒展开式，考虑上述极值必要条件，点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。可得相应的充分条件。通过增加变量将等式约束优化问题变成无约束优化问题。通过增加变量将等式约束优化问题变成无约束优化问题。对于具有对于具有l个等式约束的个等式约束的N维优化问题：维优化问题：minf(

2、x)s.t.hk(x)=0 (k=1,2,l)为了求出为了求出f(x)的可能极值点的可能极值点x*=x1*x*xn*T，引入拉格朗日，引入拉格朗日乘子乘子 k(k=1,2,l)，并构成一个新的目标函数：，并构成一个新的目标函数：把把F(x,)作为一个新的无约束条件的目标函数来求解它的极作为一个新的无约束条件的目标函数来求解它的极值点，所得结果就是在满足约束条件值点，所得结果就是在满足约束条件hk(x)=0的原目标函数的原目标函数f(x)的的极值点。极值点。二、拉格朗日乘子法二、拉格朗日乘子法F(x,)具有极值的必要条件：具有极值的必要条件：由此可得由此可得n+l个方程，从而解得个方程，从而解得

3、x=x1 xxnT和和 k(k=1,2,l)共共n+l个未知变量的值。个未知变量的值。由上述方程组求得的由上述方程组求得的x*=x1*x*xn*T是函数是函数f(x)极值点的坐极值点的坐标值。标值。用拉格朗日乘子法计算在约束条件下用拉格朗日乘子法计算在约束条件下h(x1 1,x2 2)=2)=2x1 1+3+3x2 2-6=0-6=0的的情况下，目标函数情况下，目标函数f(x1 1,x2 2)=4)=4x1 12 2+5+5x2 22 2的极值点坐标。的极值点坐标。拉格朗日乘子法解等式约束拉格朗日乘子法解等式约束拉格朗日乘子法解等式约束拉格朗日乘子法解等式约束 例题例题例题例题解：拉格朗日乘子

4、函数为解：拉格朗日乘子函数为 F(x,)=4x12+5x22+(2x1+3x2-6)，则则 连立求解得到：连立求解得到：x1 1=1.071，x2 2=1.286，=-30/7即极值点为即极值点为 x1 1*=1.071，x2 2*=1.286在工程上大多数优化问题都可表示为具有不等式约束条件的在工程上大多数优化问题都可表示为具有不等式约束条件的优化问题，故研究不等式约束极值条件是很有意义的。优化问题，故研究不等式约束极值条件是很有意义的。不等式约束的多元函数极值的必要条件是不等式约束的多元函数极值的必要条件是库恩库恩-塔克条件塔克条件，它，它是非线性优化问题的重要理论。是非线性优化问题的重要

5、理论。不等式约束优化模型为：不等式约束优化模型为：第六节第六节 不等式约束优化问题的极值条件不等式约束优化问题的极值条件为了便于理解，先分析一元函数在给定区间上的极值条件。为了便于理解，先分析一元函数在给定区间上的极值条件。h h1 1(x,a1 1)=g=g1 1(x)+)+a1 12 2=a-x+a1 12=2=0 0h h2 2(x,b1 1)=g=g2 2(x)+)+b1 12 2=x-b+b1 12 2=0=0 利用拉格朗日乘子法可得到上述优化问题的拉格朗日函数：利用拉格朗日乘子法可得到上述优化问题的拉格朗日函数：F(F(x,a1 1,b1 1,u u1 1,u,u2 2)=f()=

6、f(x)+)+u u1 1h h1 1(x,a1 1)+)+u u2 2h h2 2(x,b1 1)=f(=f(x)+)+u u1 1(a-x+a1 12 2)+)+u u2 2(x-b+b1 12 2)其中其中u u1 1和和u u2 2是对应于不等式约束条件的拉格朗日乘子，应满足非是对应于不等式约束条件的拉格朗日乘子，应满足非负的要求，负的要求，即：即：u u1 1=0 u=0 u2 2=0=0一、一元函数在给定区间上的极值条件一、一元函数在给定区间上的极值条件对于一元函数对于一元函数f(x)f(x)在给定区间在给定区间a,ba,b上的极值问题，首先引入松弛上的极值问题，首先引入松弛变量变

7、量变量变量a a1 1和和b b1 1将不等式约束变成等式约束，即：将不等式约束变成等式约束，即：根据拉格朗日乘子法，此问题的根据拉格朗日乘子法，此问题的极值条件极值条件是：是：分析分析u u1 1a1 1=0=0，只有两种情况，即：，只有两种情况，即：u u1 1=0,=0,a1 10;0;u u1 1=0,=0,a1 1=0 =0 当当u u1 1=0,=0,a1 1=0=0 时，时，g g1 1(x)=)=a-x=0=0，约束起作用，即为约束起作用，即为x=a的情况。的情况。当当u u1 1=0,=0,a1 10 0 时，时，g g1 1(x)=)=a-x0 0，约束不起作用，即为约束不

8、起作用，即为x a的情况。的情况。上式表明，上式表明，u1与与g1(x)至少必有一个为至少必有一个为0，因此，可将，因此，可将u u1 1a a1 1=0=0的条件的条件写成：写成：u u1 1g g1 1(x)=0)=0。同理，也将同理，也将u u2 2b1 1=0=0的条件写成：的条件写成：u u2 2g g2 2(x)=0)=0。为起作用约束，即为起作用约束，即x=a为不起作用约束，即为不起作用约束，即xa上述分析可表示为：上述分析可表示为：根据上述讨论，一元函数根据上述讨论，一元函数f(x)在给定区间上的极值条件可在给定区间上的极值条件可表示为：表示为：在在给定区间给定区间 a,b 上

9、，上式中的第一式可简化为：上，上式中的第一式可简化为：0 xf(x)x x*=ab0 xf(x)ax x*=b1)当当a x*=0,u2=0，极值条件为，极值条件为3)当当x*=b时，时，u1=0,u2 =0，极值条件为，极值条件为0 xf(x)ax x*b分析极值点分析极值点x x*在在区间区间 a,b 中所处的位置，有三种可能的情况：中所处的位置，有三种可能的情况：一元函数极值条件式可写成：一元函数极值条件式可写成：一元函数极值条件式可写成：一元函数极值条件式可写成：对应于不起作用约束的拉格朗日乘子取零值对应于不起作用约束的拉格朗日乘子取零值，引入起作，引入起作用约束的下标集合用约束的下标

10、集合:对于多元函数不等式约束优化问题对于多元函数不等式约束优化问题 min f(x)s.t.gj(x)0 (j=1,2,m)同样可应用拉格朗日乘子法推导出相应的极值条件，引入同样可应用拉格朗日乘子法推导出相应的极值条件，引入同样可应用拉格朗日乘子法推导出相应的极值条件，引入同样可应用拉格朗日乘子法推导出相应的极值条件，引入mm个松弛变量个松弛变量个松弛变量个松弛变量y=yy=yy=yy=y1 1 1 1,y,y,y,y2 2 2 2,y,y,y,ym m m m ，使不等式约束变成等式约束，使不等式约束变成等式约束，使不等式约束变成等式约束，使不等式约束变成等式约束 g gj j(x x)+)

11、+y yj j2 2=0 (=0 (j j=1,2,=1,2,mm)从而组成相应的拉格朗日函数：从而组成相应的拉格朗日函数：从而组成相应的拉格朗日函数：从而组成相应的拉格朗日函数：二、库恩二、库恩-塔克条件（塔克条件（K-TK-T条件）条件）仿照对一元函数在给定区间上极值条件的推导过程，同样仿照对一元函数在给定区间上极值条件的推导过程，同样仿照对一元函数在给定区间上极值条件的推导过程，同样仿照对一元函数在给定区间上极值条件的推导过程，同样可得具有不等式约束多元函数极值条件：可得具有不等式约束多元函数极值条件：可得具有不等式约束多元函数极值条件：可得具有不等式约束多元函数极值条件：若引入起作用约

12、束的下标集合：若引入起作用约束的下标集合：库恩库恩库恩库恩-塔塔塔塔克条件克条件克条件克条件K-TK-TK-TK-T条件条件条件条件则：则：K-TK-T条件条件库恩库恩塔克条件表明：塔克条件表明：如点如点x*是函数是函数 F(x)的极值点，要么的极值点，要么F(x*)=0)=0（此时（此时 j j=0=0），），要么目标函数的负梯度等于起作用约束梯度的非负线性组合要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时（此时j j00）。）。库恩库恩塔克条件的几何意义是塔克条件的几何意义是:在约束极小值点在约束极小值点x*处，函数处，函数F(x)的负梯度一定能表示成所有的负梯度一定能表示成所

13、有起使用约束在该点梯度（法向量）的非负线性组合。起使用约束在该点梯度（法向量）的非负线性组合。将将K-TK-T条件条件条件条件偏微分形式表示为梯度形式，得：偏微分形式表示为梯度形式，得：K-TK-T条件的梯度形式条件的梯度形式同时具有等式和不等式约束的优化问题同时具有等式和不等式约束的优化问题:K-T条件可表示为：条件可表示为：同时具有等式和不等式约束的同时具有等式和不等式约束的K-TK-T条件条件K-TK-TK-TK-T条件条件条件条件是多元函数取得约束极值的是多元函数取得约束极值的必要条件必要条件必要条件必要条件,以用以用来作为约束极值的判断条件，又可以来直接求解较简来作为约束极值的判断条

14、件，又可以来直接求解较简单的约束优化问题。单的约束优化问题。对于目标函数和约束函数都是凸函数的情况，对于目标函数和约束函数都是凸函数的情况，对于目标函数和约束函数都是凸函数的情况，对于目标函数和约束函数都是凸函数的情况，符符符符合合合合K-TK-TK-TK-T条件的点一定是全局最优点。条件的点一定是全局最优点。条件的点一定是全局最优点。条件的点一定是全局最优点。这种情况这种情况K-TK-T条件条件即为多元函数取得约束极值的充分必要条件。即为多元函数取得约束极值的充分必要条件。K-TK-T条件是多元函数取得约束极值的必要条件条件是多元函数取得约束极值的必要条件,既可用来作为既可用来作为约束极值的

15、判断条件，又可以用来直接求解较简单的约束优化约束极值的判断条件，又可以用来直接求解较简单的约束优化问题。问题。例：优化问题：例：优化问题：s.t判断判断1 0T是否为约束最优点。是否为约束最优点。三、三、K-TK-T条件应用举例条件应用举例是当前点，为可行点，因满足约束条件是当前点，为可行点，因满足约束条件（3）各函数的梯度：）各函数的梯度：处起作用约束为处起作用约束为g1和和g2,因因 1解解解解:（1）（2）（4）求拉格朗日乘子）求拉格朗日乘子由于拉格朗日乘子均为非负，说明由于拉格朗日乘子均为非负，说明x(1)=1 0T是一个局部最优是一个局部最优点，因为它满足点，因为它满足K-T条件。条

16、件。+即：即：可得：可得：s.t.K-TK-TK-TK-T条件例题条件例题条件例题条件例题1 1 1 1 图解图解图解图解本章结束了本章结束了本章结束了本章结束了第二节第二节 凸集、凸函数与凸规划凸集、凸函数与凸规划第三节第三节 多元函数的泰勒展开多元函数的泰勒展开第四节第四节 无约束优化问题的极值条件无约束优化问题的极值条件第五节第五节 等式约束优化问题的极值条件等式约束优化问题的极值条件第六节第六节 不等式约束优化问题的极值条件不等式约束优化问题的极值条件第一节第一节 方向导数与梯度方向导数与梯度前面介绍了本章的如下内容：前面介绍了本章的如下内容：前面介绍了本章的如下内容：前面介绍了本章的如下内容：第二章第二章第二章第二章 优化方法的数学基础优化方法的数学基础优化方法的数学基础优化方法的数学基础结束语结束语谢谢大家聆听！谢谢大家聆听！27