2优化设计的数学基础

1第二章优化设计的数学基础优化设计中绝大多数是多变量有约束的非线性规划问题，即是求解多变量非线性函数的极值问题。由此可见，优化设计是建立在多元函数的极值理论基础上的，对于无约束优化问题为数学上的无条件极值问题，而对于约束优化问题则为数学上的条件极值问题。本章主要叙述与此相关的数学基础知识。第一节函数的方向导数与梯度一、函数的方向导数一个二元函数21,xxF在点02010,xxX处的偏导数，即函数沿坐标轴方向的变化率定义为：而沿空间任一方向S的变化率即方向导数为：2方向导数与偏导数之间的数量关系为依此类推可知n维函数nxxxF,,,21在空间一点002010,,,nxxxX沿S方向的方向导数为二、函数的梯度函数XF在某点X的方向导数表明函数沿某一方向S的变化率。—般函数在某一确定点沿不同方向的变化率是不同的。为求得函数在某点X的方向导数为最大的方向，引入梯度的概念。仍以二元函数21,xxF为例进行讨论，将函数沿方向S的方向导数写成如下形式令：图2-1二维空间中的方向图2-2三维空间中的方向3称为21,xxF在点X处的梯度XFgrad，而同时设S为单位向量于是方向导数可写为：此式表明，函数XF沿S方向的方向导数等于向量XF在S方向上的投影。且当1,cosSXF，即向量XF与S的方向相向时，向量XF在S方向上的投影最大，其值为XF。这表明梯度XF是函数XF在点X处方向导数最大的方向，也就是导数变化率最大的方向。上述梯度的定义和运算可以推广到n维函数中去，即对于n元函数nxxxF,,,21，其梯度定义为由此可见，梯度是一个向量，梯度方向是函数具有最大变化率的方向。即梯度XF方向是函数XF的最速上升方向，而负梯度XF方向则为函数XF的最速下降方向。例2-1求二元函数2214xxFX在T1,10X点沿44211S和63212S的方向导数。解：21212142xxxxFxFFXXX，将T1,10X代入可得442XF，因此而这说明同一函数在不同方向上的方向导数不同，其变化率也不同。函数XF由0X出发，沿S1方向的变化率大于沿S2方向的变化率。所以，函数XF沿S1方向增长得较快。第二节凸集、凸函数与凸规划如果函数在整个可行域中有两个或两个以上的极值点，则称每一个极值点为局部极值点。在整个可行域中，函数值最小的点为全域极值点。为求得全域极值点，以获得最好的可行设计方案，就需要进一步讨论局部最小点和全域最小点的关系，因而涉及到凸集、凸函数及凸规划问题。一、凸集设D为n维欧氏空间内的一个集合，如果D内任意两点X1和X2的连线整个都包围在D内，即对于任意实数（10），点DXX211，则称这种集合为凸集，如图2-3a所示，否则为非凸集，如图2-3b、c所示。凸集满足以下性质：若D是一个凸集，是一个实数，则集合D仍为凸集；若D与F均为凸集，则其和（或5并）还是凸集；任何一组凸集的积（或交）还是凸集。二、凸函数设D为En中的一凸集，XF为定义在D上的一个函数，若对于任意实数（10）和D内任意两点X1和X2，恒有则XF为D上的凸函数；若式中不等号反向，则为凹函数。凸函数的几何意义如图2-4所示。若XF在区间ba,内为凸函数，则曲线上任意两点A、B间（与X1和X2相对应）所连成直线上的点K’总不会落在这两点间曲线的下方，即大于相应点K的函数值。因而，若XF为凸函数，则－XF为凹函数；线性函数既可视为凸函数，又可视为凹函数。凸函数的性质：1）设取XF为定义在凸集D的凸函数，则对于任意正实数，图2-3凸集a）与非凸集b）、c）图2-4凸函数的几何含义6函数XF在D上也是凸函数；2）设X1F、X2F为定义在凸集D上的凸函数，则函数XXX21FFF在D上也是凸函数：3）若函数XF在n维欧氏空间En一阶可微，则对于任意2121,XXXXnE，XF为凸函数的充分必要条件为(其证明可参见教材p.26)12112XXXXXTFFF图2-5所示为一维函数情况，其凸函数的几何意义在于函数曲线永远在切线的上面。若XF是凸集D上的凸函数，并且在D内有极小点，则极小点是唯一的。最优化方法中很多结论都是以函数具有凸性为前提的。三、凸规划对于约束优化问题式中，若XF、Xug、u＝1，2，…，n均为凸函数，则称此问题为凸规划。凸规划的性质：1）可行域nugu,,2,1,0XX为凸集。2）凸规划问题的任何局部最优解都是全局最优解。图2-5一维凸函数73）若XF可微，则X为凸规划问题的最优解的充分必要条件是：对于DX，都满足（该式表明在X的邻域内的所有点的目标函数值均大于X处的值）但在实际应用中，要证明一个线性规划问题是否为凸规划，一般比较困难，有时甚至比求解一个优化问题还要麻烦得多，尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难以实现。因此，在优化设计的求解时，就不必花精力进行求证，而通常是从几个初始点出发，看它是否能收敛于同一点上，否则从求得的几个方案中，选取相对较好的方案，作为最优设计的结果，也就是从局部最优解的比较中来选取全局的最优解。第三节无约束优化问题的极值条件优化问题的几何表达只能形象地给出最优解的有关概念，而最优解数值的求得，还得靠必要的定量计算来达到。这种运算的理论依据8是函数的极值理论，因而有必要对其有关概念作必要的回顾和介绍。多元目标函数的表达形式往往十分复杂，为了便于讨论，需用简单的函数作局部逼近，使其简化。用泰勒展开式求目标函数在某点邻近的近似表达式，则是常用的方法。一、多元函数的泰勒展开式一元函数XF在Xk点的泰勒展开式为而多元函数XF在Xk点的泰勒展开式为式中，ikxFX为函数在Xk点处对xi的偏导数；jikxxFX2为函数在Xk点处对xi、xj的二阶偏导数；xi、xj分别表示变量X的第i和j个分量；n为变量的个数。若用向量矩阵表示，可写为：9因此，多元函数XF在Xk点的泰勒展开式可用向量矩阵形式表达为其中，为XF在Xk点的一阶偏导数的列向量，称为梯度；为XF在Xk点的二阶偏导数矩阵，由于函数的二次连续性，它是一个n×n阶的对称方阵，统称为函数XF在点Xk的海色（Hessian）矩阵。在优化设计中，目标函数取到自变量（设计变量）的二次函数表10达式已足够准确（这称为目标函数的平方近似表达式），因为数学上己证明：对于非标准球面或椭球抛物面的一般非线性目标函数（即高次函数），在其极值点附近的等值线簇仍为同心椭圆簇，即目标函数在极值点附近是二次函数。此外，二次函数的某些特征还为一些高效寻优方法的建立提供了理论依据，因此要重视二次函数。这样，对多元函数的泰勒展开式只取前三项就可以，记为如下形式：二、无约束优化问题的极值条件从高等数学可知，一元函数存在极值点的必要和充分条件是：函数的一阶导数0'xFxxF（即找到驻点）和二阶导数0''22xFxxF。当0''xF时为极大；0''xF时为极小。类似地，对于n元函数nxxxFF,,,21X的无约束极值问题点X为一个局部极值点的充分必要条件是：1）一阶导数向量0XF，即nixFi,,2,10X；2）二阶导数矩阵，即海色矩阵XF2为正定或负定，即11为正定或负定，且当XH为正定时X为极小点；当XH为负定时X为极大点。（其证明可参见教材p.20～22）判断矩阵A正定或负定的方法是检验其各阶顺序主子式，若各阶顺序主子式均大于0，如下：则A为正定矩阵；若各阶顺序主子式行列式值正负号交替出现，则为负定矩阵。若不满足正负定矩阵条件则为不定矩阵，则不可采用上述方法计算极值。例2-2求函数744,21222121xxxxxxF的极值。解：根据极值的必要条件求驻点得到驻点T4,2X再根据极值的充分条件，判断此点是否为极值点。由于12其各阶主子式均大于0，即XH为正定，故T4,2X为极小点，极小值为13XF第四节约束优化问题的极值条件求解约束优化问题求解上述问题的实质是在所有的约束条件所形成的可行域内，求得目标函数的极值点，即约束最优点。由于约束最优点不仅与目标函数本身的性质有关，还与约束函数的性质有关，因此约束条件下的优化问题比无约束条件下的优化问题更为复杂。库恩-塔克（Kuhn-Tucker）条件（简称K-T条件）是非线性规划领域中最重要的理论成果之一，通常借助库恩－塔克条件来判断和检验约束优化问题中某个可行点是否为约束极值点，即将K-T条件作为确定一般非线性规划问题中某点是否为极值点的必要条件，对于凸规划问题，K-T条件同时也是一个充分条件。但是如何判别所找到的极值点是全域最优点还是局部极值点，至今还没有一个统一而有效的判别方法。K-T条件可阐述为：若X是一个局部极小点，则该点的目标函数梯度XF可表示13成诸约束面梯度Xug和Xvh的线性组合的负值，即式中，q为设计点处的不等式约束面数；j为设计点处的等式约束面数；quu,,2,1、jvv,,2,1为非负值的乘子，也称为拉格朗日乘子。式中，在点X处不起作用的约束条件Xug对应的义u一定为零，只有当某一约束Xug在点X为起作用约束时，u才可以不为零。如果是约束最优解，则必然满足上式。对凸规划问题而言，K-T条件不仅是确定约束极值点的必要条件，同时也是充分条件。凸规划问题有唯一的K-T点，但它所对应的拉格朗日乘子不一定是唯—的。K-T条件的几何意义在于：如果X是一个局部极小点，则该点的目标函数梯度XF应落在该点诸约束面（所有起作用的约束条件）梯度Xug和Xvh在设计空间所组成的锥角范围内。如图2-6所示，图2-6a中设计点X不是约束极值点，图2-6b的设计点X是约束极值点。（其求证可参见教材p.32）图2-6K-T条件的几何意义a）设计点X不是约束极值点；b）设计点X是约束极值点14现在通过图2-7所示的二维问题说明上述几何意义。图2-7表示在设计点kX处有两个约束，且目标函数及约束条件均为凸函数的情况。图2-7a中，kX点处目标函数的负梯度为kFX，两约束函数的梯度分别为kgX1、kgX2，此时kFX位于kgX1和kgX2组成的锥角之外，这样在kX点附近的可行域内存在目标函数比kFX更小的设计点，故点kX不能成为约束极值点。图2-7b中，kX点处的目标函数负梯度kFX位于锥角之内，则在该点附近邻域内任何目标由数值比kFX更小的设计点都在可行域之外，因而kX是约束极值点，它必然满足K-T条件：K-T条件主要应用于约束极值问题的数值解法中，用以检验设计点kX是否为约束极值点或局部最优点，并用以判断和消除那些不再起作用的约束条件，以保证在迭代中维持正确的起作用约束集合，对图2-7约束极值点存在的条件a）设计点kX不是约束极值点；b）设计点kX是约束极值点15于目标函数和约束函数是凸函数的情况，符合K-T条件的点一定是全域最优点。例2-3对于约束极值问题试运用K-T条件验证点T0,2X为约束极值点。解：图2-8给出了出了01Xg、02Xg和03Xg所确定的可行域，同时给出了XF的几条等值线。（1）计算X点的各个约束函数值图2-8例2-3图16可见，在X处起作用的约束函数是X1g和X2g；（2）求相关函数在X点的梯度（3）将梯度代入K-