《优化设计第02课-2数学基础》由会员分享，可在线阅读，更多相关《优化设计第02课-2数学基础（26页珍藏版）》请在金锄头文库上搜索。
1、第四节 无约束优化问题的极值条件,在x =x0处取得极值的必要条件为x0点必须为驻点，即,在x=x0处取得极值充分条件.,一、 一元函数极值的必要条件,二、 多元函数极值的必要条件,1. F(x)在x*处取得极值，其必要条件是:,即在极值点处函数的梯度为n维零向量。,例： 在 处梯度为 但 只是双曲抛物面的鞍点，而不是极小点。,为了判断从上述必要条件求得的x*是否是极值点，需建立极值的充分条件。,根据函数在x*点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。,三、极值的充分条件,海赛（Hessian）矩阵 正定，即各阶主子式均大于零，则x*为极小点。,海赛（Hessian）矩阵 负
2、定，即各阶主子式负、正相间，则x *为极大点。,对于等式约束优化问题数学模型： min f (x) s.t. hj (x)=0 (j=1,2,m),有两种处理方法，即： 1、消元法（降维法） 2、拉格朗日乘子法（升维法）,第五节 等式约束优化问题的极值条件,若将这些关系式代入到目标函数中，从而得到只含xl+1, xl+2,xn共n-l个变量的函数，这样就可以利用无约束优化问题的极值求解。,由l个等式约束方程可以得到表达式 ,即将n个变量中的前l个变量用其余n-l个变量表示。,一、消元法,即通过减少变量将等式约束优化问题变成无约束优化问题。 对于n维情况： min f (x) s.t. hk(x
3、1,x2, ,xn)=0 (k=1,2,l),通过增加变量将等式约束优化问题变成无约束优化问题。,对于具有l个等式约束的N维优化问题： min f(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个方程，从而解得x=x1 xxnT和k(k=1,2, l)
4、 共n+l个未知变量的值。 由上述方程组求得的x*=x1* x*xn*T是函数f(x)极值点的坐标值。,用拉格朗日乘子法计算在约束条件下h(x1,x2)=2x1+3x2-6=0的情况下，目标函数f(x1,x2)=4x12+5x22的极值点坐标。,拉格朗日乘子法解等式约束 例题,解：拉格朗日乘子函数为 F(x,)=4x12+5x22+(2x1+3x2-6)， 则,连立求解得到：x1=1.071，x2=1.286，=-30/7 即极值点为 x1*=1.071，x2*=1.286,在工程上大多数优化问题都可表示为具有不等式约束条件的优化问题，故研究不等式约束极值条件是很有意义的。 不等式约束的多元函
5、数极值的必要条件是库恩-塔克条件，它是非线性优化问题的重要理论。 不等式约束优化模型为：,第六节 不等式约束优化问题的极值条件,为了便于理解，先分析一元函数在给定区间上的极值条件。,h1(x,a1)=g1(x)+a12= a-x+a12 = 0 h2(x,b1)=g2(x)+b12=x-b+b12=0,利用拉格朗日乘子法可得到上述优化问题的拉格朗日函数： F(x,a1,b1,u1,u2)=f(x)+u1h1(x,a1)+u2h2(x,b1) =f(x)+u1(a-x+a12)+u2(x-b+b12) 其中u1和u2是对应于不等式约束条件的拉格朗日乘子，应满足非负的要求， 即： u1=0 u2=
6、0,一、一元函数在给定区间上的极值条件,对于一元函数f(x)在给定区间a,b上的极值问题，首先引入松弛变量变量a1和b1将不等式约束变成等式约束，即：,根据拉格朗日乘子法，此问题的极值条件是：,分析u1a1=0 ，只有两种情况，即： u1=0,a10; u1=0,a1=0 当u1=0,a1=0 时，g1(x)=a-x=0，约束起作用，即为x=a的情况。 当u1=0,a10 时，g1(x)=a-x0，约束不起作用，即为xa的情况。,上式表明， u1与g1(x)至少必有一个为0，因此，可将u1a1=0的条件写成： u1g1(x)=0。 同理，也将u2b1=0的条件写成： u2g2(x)=0。,为起
7、作用约束，即x=a,为不起作用约束，即xa,上述分析可表示为：,根据上述讨论，一元函数f(x)在给定区间上的极值条件可表示为：,在给定区间a,b上，上式中的第一式可简化为：,1) 当a x*b时，u1=u2=0，极值条件为,2) 当x*=a时，u1=0,u2=0，极值条件为,3) 当x*=b时，u1=0,u2 =0，极值条件为,分析极值点x*在区间a,b中所处的位置，有三种可能的情况：,一元函数极值条件式可写成：,对应于不起作用约束的拉格朗日乘子取零值，引入起作用约束的下标集合:,对于多元函数不等式约束优化问题 min f(x) s.t. gj(x) 0 (j=1,2,m),同样可应用拉格朗日
8、乘子法推导出相应的极值条件，引入m个松弛变量y=y1,y2,ym，使不等式约束变成等式约束 gj(x)+yj2=0 (j=1,2, ,m) 从而组成相应的拉格朗日函数：,二、库恩-塔克条件（K-T条件）,仿照对一元函数在给定区间上极值条件的推导过程，同样可得具有不等式约束多元函数极值条件：,若引入起作用约束的下标集合：,库恩-塔 克条件,K-T条件,则：,K-T条件,库恩塔克条件表明： 如点x*是函数 F(x)的极值点，要么F(x*)=0 （此时 j=0），,要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时j0）。,库恩塔克条件的几何意义是: 在约束极小值点x*处，函数F(x) 的负
9、梯度一定能表示成所有起使用约束在该点梯度（法向量）的非负线性组合。,将K-T条件偏微分形式表示为梯度形式，得：,K-T条件的梯度形式,同时具有等式和不等式约束的优化问题 :,K-T条件可表示为：,同时具有等式和不等式约束的K-T条件,K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。,对于目标函数和约束函数都是凸函数的情况， 符合K-T条件的点一定是全局最优点。这种情况K-T条件即为多元函数取得约束极值的充分必要条件。,K-T条件是多元函数取得约束极值的必要条件,既可用来作为约束极值的判断条件，又可以用来直接求解较简单的约束优化问题
10、。,例：优化问题：,s.t,判断1 0T是否为约束最优点。,三、K-T条件应用举例,是当前点，为可行点，因满足约束条件,（3）各函数的梯度：,处起作用约束为g1和g2 , 因,1,解:,（1）,（2）,（4）求拉格朗日乘子,由于拉格朗日乘子均为非负，说明x(1)=1 0T是一个局部最优点，因为它满足K-T条件。,+,即：,可得：,s.t.,K-T条件例题1 图解,本章结束了,第二节 凸集、凸函数与凸规划,第三节 多元函数的泰勒展开,第四节 无约束优化问题的极值条件,第五节 等式约束优化问题的极值条件,第六节 不等式约束优化问题的极值条件,第一节 方向导数与梯度,前面介绍了本章的如下内容： 第二章 优化方法的数学基础,
