函数的极值条件

函数的极值条件前言我们处理的各种优化问题可以大致分为两类：有约束的优化问题和无约束的优化问题。工程优化问题往往都是有约束的，但经过适当的处理可以用无约束的优化方法加以解决。因此无约束极值点存在的条件是优化理论的基本问题。关键字：无约束有约束优化求解无约束优化问题的实质是求解目标函数f(x)在n维空间𝑅𝑛中的极值。我们先来看看一元函数的极值条件。1.无约束优化问题的极值条件1.1一元函数的极值条件由高等数学可知，任何一个单值、连续、可微的一元函数f(x)在给定区间内某点𝑥=𝑥∗有极值的必要条件，是它在该点处的一阶导数为零，即：𝑓′(𝑥∗)=0即函数的极值必须在驻点处取得。此条件是必要的，但不是充分的，也就是说驻点不一定就是极值点。如图1.1-1所示，x=0是驻点，但ab图1.1-1其中图a中的𝑥∗点是极小值点，而图b中的𝑥∗并不是极值点。驻点是否为极值点，还需要函数在该点的二阶导数来判断。驻点为极小值点的充分条件是，𝑥∗满足不等式：𝑓′′(𝑥∗)0驻点为极大值点的充分条件是，𝑥∗满足不等式：𝑓′′(𝑥∗)0若：𝑓′′(𝑥∗)=0则𝑥∗是否为极值点，还需要逐次检验其更高阶导数的符号。开始不为零的导数阶数为偶数，则为极值点；若为奇次，则为拐点，而不是极值点。1.2二元函数的极值条件对于二维无约束优化问题，即对二元函数f(x)=f(𝑥1，𝑥2)来说，若在𝑋∗（𝑥1∗，𝑥2∗）处取得极值，其必要条件是：𝜕𝑓(𝑥1，𝑥2)𝜕𝑥1=𝑑𝑓(𝑥1，𝑥2∗)𝑑𝑥1|𝑥1=𝑥1∗=0𝜕𝑓(𝑥1，𝑥2)𝜕𝑥2=𝑑𝑓(𝑥1∗，𝑥2)𝑑𝑥2|𝑥2=𝑥2∗=0写成梯度形式可得：∇f(x)=[𝜕𝑓(𝑥1，𝑥2)𝜕𝑥1，𝜕𝑓(𝑥1，𝑥2)𝜕𝑥2]𝑇=0为推得二元函数极值存在的充分条件，将二元函数f(x)在驻点𝑥∗=[𝑥1∗，𝑥2∗]𝑇作泰勒二次近似展开，得到近似表达式为：f(x)=f(𝑥∗)+[∇f(𝑥∗)]𝑇(𝑥−𝑥∗)+12(𝑥−𝑥∗)𝑇∇2f(𝑥∗)(𝑥−𝑥∗)因为驻点满足∇f(𝑥∗)=0，故由上式可得：f(x)−f(𝑥∗)=12(𝑥−𝑥∗)𝑇∇2f(𝑥∗)(𝑥−𝑥∗)当f(x)−f(𝑥∗)0，则由上式可知，应有：12(𝑥−𝑥∗)𝑇∇2f(𝑥∗)(𝑥−𝑥∗)0此时，𝑥∗为极小值。而为使上式成立，根据二次型的理论可知，只要Hessian矩阵∇2f(𝑥∗)为正定矩阵。故由此可得二元函数极小值存在的充分条件为：∇2f(𝑥∗)0仿此可推得二元函数极大值存在的充分条件为：∇2f(𝑥∗)01.3多元函数的极值条件由之前对二元函数的极值条件的推导不难将二元函数极值存在的充分必要条件推广至n元函数。n元函数f(𝑥1，𝑥2，……，𝑥𝑛)在点𝑥∗存在极值的充分必要条件为：条件1：∇f(𝑥∗)=0条件2：当∇2f(𝑥∗)0时，𝑥∗为极小值点；而当∇2f(𝑥∗)0时，𝑥∗为极大值点。条件1为极值存在的必要条件；条件2为极值存在的充分条件。图1.2-1表示满足极值存在的必要条件的驻点不是极值点而是鞍点的情况。图1.2-12.有约束优化问题的极值条件求解约束优化问题的极值条件的实质是在所有约束条件所形成的可行域内，求得目标函数的极值点。因而约束优化问题比无约束优化问题更为复杂。因为约束优化问题的极值点不仅与目标函数的性态有关，而且还与约束条件的性态密切相关，它可能与目标函数的极值点重合（如图2-1a所示），也可能不是目标函数的极值点（如图2-1b所示）。图2-1a表示的是有四个不等式约束的二维约束优化问题。其目标函数是凸函数，且目标函数的极值点𝑥∗处于可行域内，故𝑥∗即为该约束优化问题的极值点。图2-1b所示的目标函数和约束函数都是凸图2-1函数。约束边界g(x)=0与目标函数的等值线𝑥∗点相切，而目标函数的自然极值点隔到了可行域之外。因此，此约束优化问题的极值点不是目标函数的自然极值点，而是切点𝑥∗。若目标函数或约束函数的性态不同，致使求解约束优化问题带来许多困难。为了研究约束优化问题的求解方法，有必要介绍约束优化问题的极值条件。先阐述等式约束优化问题的极值条件，然后导出不等式约束优化问题的极值条件。2.1等式约束优化问题的极值条件求解等式优化问题：minf(X)s.t.ℎ𝑘(𝑋)=0(𝑘=1，2，……𝑙)需要导出极值存在的条件，这是求解等式约束优化问题的理论基础。一般处理这一类问题有两种方法：消元法（降维法）和拉格朗日乘子法（升维法）。2.1.1消元法二元函数只有一个等式约束的简单情况：𝑚𝑖𝑛𝑓(𝑥1，𝑥2)𝑠.𝑡.ℎ(𝑥1，𝑥2)=0求解这一问题可采用消元法。根据等式约束条件将其中一个变量𝑥1表示成另一个变量x2的函数关系𝑥1=φ(x2)，然后将此关系式带入目标函数𝑓(𝑥1，𝑥2)消去𝑥1，变成一元函数F(𝑥2)，这样就将等式约束优化问题转化成了无约束优化问题。目标函数通过消元法由二元函数变成了一元函数，即由二维变成了一维，达到降维的目的。同理，对于n维函数：𝑚𝑖𝑛𝑓(𝑥1，𝑥2，……，𝑥𝑛)𝑠.𝑡.ℎ𝑘(𝑥1，𝑥2，……，𝑥𝑛)=0(𝑘=1，2，……𝑙)由𝑙个约束方程将n个变量中的前𝑙个变量用其余n−𝑙个变量表示：𝑥1=φ1(x𝑙+1，x𝑙+2，……，x𝑛)𝑥1=φ2(x𝑙+1，x𝑙+2，……，x𝑛)……𝑥𝑙=φ𝑙(x𝑙+1，x𝑙+2，……，x𝑛)将这些函数关系代入目标函数，从而得到只含x𝑙+1，x𝑙+2，……，x𝑛共n−𝑙个变量的函数F(x𝑙+1，x𝑙+2，……，x𝑛)，这样就可以利用无约束优化问题的极值条件求解。消元法是一种间接寻求优化的方法，其实质是利用等式约束消去某些变量，把等式约束优化问题变换成无约束优化问题的一种最简单的方法。若约束条件是比较简单的函数，消元法是十分方便的，但若约束条件是复杂的多维高次隐函数，这种方法就显得相当不便，有时甚至根本不可能。2.1.2拉格朗日乘子法拉格朗日乘子法，其实质也是将有约束优化问题转换成无约束优化的问题来求解，同样也是一种间接求解法，但由于引进了一个待定系数（乘子），其结果是简化了数学变化过程，因此是一种更为有效的方法。拉格朗日乘子法通过增加变量，将等式约束优化问题变成无约束优化问题，所以又称升维法。先考虑只有一个等式约束的二维优化问题：min𝑓(𝑥)=𝑓(𝑥1，𝑥2)𝑠.𝑡.ℎ(𝑥)=ℎ(𝑥1，𝑥2)=0为推导出此问题的极值条件，引入乘子λ，构造等式约束优化问题的拉格朗日函数：𝐿(𝑥1，𝑥2，λ)=𝑓(𝑥1，𝑥2)+λℎ(𝑥1，𝑥2)从而将约束优化问题转化成无约束优化问题。可以证明，二者的极值条件是等价的。而拉格朗日函数极值存在的必要条件为：∂𝐿(𝑥1，𝑥2，λ)∂𝑥1=∂𝑓(𝑥1，𝑥2)∂𝑥1+λ∂ℎ(𝑥1，𝑥2)∂𝑥1=0∂𝐿(𝑥1，𝑥2，λ)∂𝑥2=∂𝑓(𝑥1，𝑥2)∂𝑥2+λ∂ℎ(𝑥1，𝑥2)∂𝑥2=0∂𝐿(𝑥1，𝑥2，λ)∂λ=ℎ(𝑥1，𝑥2)=0为将上述条件推广到有p个等式约束的多维优化问题min𝑓(𝑥)𝑥∈𝑅𝑛𝑠.𝑡.ℎ𝑣(𝑥)=0(𝑣=1，2，…，𝑝)引入𝑝个乘子λ𝑣(𝑣=1，2，…，𝑝)，并构造此问题的拉格朗日函数：𝐿(𝑥，λ)=𝑓(𝑥)+∑λ𝑣ℎ𝑣(𝑥)𝑝𝑣=1列出次拉格朗日函数极值存在的必要条件为∂𝐿(𝑥，λ)∂𝑥𝑖=∂𝑓(𝑥)∂𝑥𝑖+∑λ𝑣∂ℎ𝑣(𝑥)∂𝑥𝑖(𝑖=1，2，…，𝑛)𝑝𝑣=1∂𝐿(𝑥，λ)∂λ𝑣=ℎ𝑣(𝑥)=0(𝑣=1，2，…，𝑝)在上述各式中，λ=[λ1，λ2，…，λ𝑝]。若令ℎ(𝑥)=[ℎ1(𝑥)，ℎ2(𝑥)，…，ℎ𝑝(𝑥)]𝑇∇ℎ(𝑥)=[∂ℎ1(𝑥)∂𝑥1∂ℎ1(𝑥)∂𝑥2⋯∂ℎ1(𝑥)∂𝑥𝑛⋮⋱⋮∂ℎ𝑝(𝑥)∂𝑥1∂ℎ𝑝(𝑥)∂𝑥2⋯∂ℎ𝑝(𝑥)∂𝑥𝑛]可将上式简化成梯度和矩阵的形式：∇𝑓(𝑥)+[∇ℎ(𝑥)]𝑇λ=0ℎ(𝑥)=0此即等式约束优化问题极值存在的必要条件。为说明等式约束优化问题极值存在的必要条件的几何意义，可将上式写作：−∇𝑓(𝑥)=∑λ𝑣ℎ𝑣(𝑥)𝑝𝑣=1ℎ𝑣(𝑥)=0(𝑣=1，2，…，𝑝)该式中的第一项表明目标函数的负梯度−∇𝑓(𝑥)可表示为约束函数梯度ℎ𝑣(𝑥)，(𝑣=1，2，…，𝑝)的线性组合。其中𝑝为设计点x处的约束曲面的数目。图2.1.2-1表示了必要条件的几何意义。其中ℎ1(𝑥)=0与ℎ2(𝑥)=0分别代表两个约束曲面，E为此二约束曲面的交线，显然最优点𝑥∗必在此交线上，∇ℎ1(𝑥∗)与∇ℎ2(𝑥∗)分别为约束函数ℎ1(𝑥)与ℎ2(𝑥)在点𝑥∗处的梯度，即相应的约束曲面在交线E处的法向量。根据结果式可知，−∇𝑓(𝑥)与∇ℎ1(𝑥∗)、∇ℎ2(𝑥∗)应是线性相关的。图2.1.2-1这一概念在图上表示为：如果𝑥∗是最优点，目标函数在该点处的负梯度−∇𝑓(𝑥∗)一定要处在由约束函数在该点梯度∇ℎ1(𝑥∗)、∇ℎ2(𝑥∗)做确定的平面P上，这是一个过点𝑥∗且与交线E正交的平面。如果三个向量−∇𝑓(𝑥∗)、∇ℎ1(𝑥∗)、∇ℎ2(𝑥∗)不在同一平面上，显然不存在上述线性相关条件了。可以这样来理解：如果−∇𝑓(𝑥∗)不在平面P上，而与平面倾斜一个角度，则−∇𝑓(𝑥∗)在点𝑥∗处的交线E的切线上的投影将不为零，因而沿这个投影方向在交线E上作微小移动时，目标函数值将有所下降，故点𝑥∗就不是最优点了。这是因为−∇𝑓(x)是目标函数等值面的法向量，它在交线E的𝑥∗处切线上的投影不为零，意味着等值面与交线E在𝑥∗处不相切，𝑥∗处不是切点，所以不是最优点。2.2不等式约束优化问题的极值条件工程上大多数优化问题都可表示成具有不等式约束条件的优化问题，求解此类问题的实质是在所有约束条件所形成的可行域内求得目标函数的极值点，即约束最优点。K-T条件是在非线性规划领域中最重要的理论成果之一，通常借助K-T条件来判断和检验约束优化问题中某个可行点是否为约束极值点，即将K-T条件作为确定一般非线性规划问题中某一点是否为极值点的必要条件。2.2.1K—T条件对于多元函数不等式约束优化问题：min𝑓(𝑋)𝑠.𝑡.𝑔𝑖(𝑋)≤0(𝑗=1，2，…，𝑚)其中，设计变量𝑋=[𝑥1𝑥2…𝑥𝑖𝑥𝑛]𝑇为n维向量，它受有m个不等式约束的限制。可用拉格朗日乘子法推导出相应的极值条件：∂𝑓(𝑋∗)∂𝑥𝑖+∑𝜇𝑗∂𝑔𝑖(𝑋∗)∂𝑥𝑖=0(𝑖=1，2，…，𝑛)𝑚𝑗=1𝜇𝑗𝑔𝑖(𝑋∗)=0(𝑗=1，2，…，𝑛)𝜇𝑗≥0(𝑗=1，2，…，𝑛)其中，𝜇是对应于不等式约束的拉格朗日乘子向量𝜇=[𝜇1𝜇2…𝜇𝑗…𝜇𝑚]𝑇，并有𝜇𝑗≥0，这就是著名的K—T条件。若引用约束的下标集合：𝐽(𝑋∗)={𝑗|𝑔𝑖(𝑋∗)=0(𝑗=1，2，…，𝑛)}则K—T条件可写成如下形式：∂𝑓(𝑋∗)∂𝑥𝑖+∑𝜇𝑗∂𝑔𝑖(𝑋∗)∂𝑥𝑖=0(𝑖=1，2，…，𝑛)𝑚𝑗=1𝑔𝑗(𝑋∗)=0(𝑗∈𝐽)𝜇𝑗≥0(𝑗∈𝐽)2.2.2同时具有等式和不等式约束的优化问题的K—T条件对于min𝑓(𝑋)𝑠.𝑡.𝑔𝑖(𝑋)≤0(𝑗=1，2，…，𝑚)ℎ𝑘(𝑋)=0(𝑘=1，2，…，𝑙)K—T条件可表示为：∂𝑓∂𝑥𝑖+∑𝜇𝑗∂𝑔𝑖∂𝑥𝑖+∑𝜆𝑘