优化的数学基础

关于优化的数学基础机械设计问题一般是非线性规划问题。实质上是多元非线性函数的极小化问题，因此，机械优化设计是建立在多元函数的极值理论基础上的。机械优化设计问题分为：无约束优化约束优化无条件极值问题条件极值问题第2页,共70页，2024年2月25日，星期天补充：等值（线）面：

对于可计算的函数f(x)，给定一个设计点X(k)(x1(k),x2(k),…,xn

(k))，f(x)总有一个定值c与之对应；而当f(x)取定值c时，则有无限多个设计点X(i)(x1(i),x2(i),…,xn(i))（i=1,2,…）与之对应，这些点集构成一个曲面，称为等值面。

当c取c1,c2,…等值时，就获得一族曲面族，称为等值面族。

当f(x)是二维时，获得一族等值线族；当f(x)是三维时，获得一族等值面族；当f(x)大于三维时，获得一族超等值面族。第3页,共70页，2024年2月25日，星期天等值线的“心”

（以二维为例）

一个“心”：是单峰函数的极（小）值点，是全局极（小）值点。没有“心”：例，线性函数的等值线是平行的，无“心”，认为极值点在无穷远处。

多个“心”：不是单峰函数，每个极（小）值点只是局部极（小）值点，必须通过比较各个极值点和“鞍点”（须正确判别）的值，才能确定极（小）值点。补充：等值（线）面：第4页,共70页，2024年2月25日，星期天等值线的形状：同心圆族、椭圆族，近似椭圆族；等值线的疏密：沿等值线密的方向，函数值变化快；沿等值线疏的方向，函数值变化慢。等值线的疏密定性反应函数值变化率。

严重非线性函数——病态函数的等值线族是严重偏心和扭曲、分布疏密严重不一的曲线族。补充：等值（线）面：第5页,共70页，2024年2月25日，星期天§2.1多元函数的方向导数与梯度一、方向导数

从多元函数的微分学得知，对于一个连续可微函数f(x)在某一点的一阶偏导数为：，，，…它表示函数f(x)值在点沿各坐标轴方向的变化率。有一个二维函数，如图2-1所示。第6页,共70页，2024年2月25日，星期天图2-1函数的方向导数

为d的方向角,即与坐标轴的夹角§2.1多元函数的方向导数与梯度第7页,共70页，2024年2月25日，星期天其函数在点沿d方向的方向导数为§2.1多元函数的方向导数与梯度第8页,共70页，2024年2月25日，星期天§2.1

多元函数的方向导数和梯度

二维问题中，f(x1,x2)在X(0)点沿方向d的方向导数可以写为：二.二元函数梯度第9页,共70页，2024年2月25日，星期天§2.1

多元函数的方向导数和梯度其中：是X(0)点的梯度。为d方向的单位向量，

方向导数为梯度在方向d上的投影。第10页,共70页，2024年2月25日，星期天结论：函数在某点沿各方向的方向导数随

即变化，其最大值在余弦函数取值为1时，也就是当梯度方向与d方向重合时其值最大。可见，梯度方向就是函数值变化最快的方向，而梯度的模就是函数变化率的最大值。第11页,共70页，2024年2月25日，星期天梯度方向和切线方向垂直，即梯度方向为等值面的法线方向。第12页,共70页，2024年2月25日，星期天三、多元函数的梯度沿d方向的方向向量即§2.1

多元函数的方向导数和梯度第13页,共70页，2024年2月25日，星期天总结:

①梯度是X(0)点处最大的方向导数；②梯度的方向是过点的等值线的法线方向；③梯度是X(0)

点处的局部性质；④梯度指向函数变化率最大的方向；⑤正梯度方向是函数值最速上升的方向，负梯度方向是函数值最速下降的方向。§2.1

多元函数的方向导数和梯度第14页,共70页，2024年2月25日，星期天图2-5梯度方向与等值面的关系第15页,共70页，2024年2月25日，星期天§2.2

多元函数的泰勒展开n维函数f(x)在x(k)

点的泰勒展开式:二阶近似式：其中：增量

ΔX(k)=[Δx1(k),Δx2(k),…,Δxn(k)]T梯度

一.Hessian矩阵与正定第16页,共70页，2024年2月25日，星期天§2.2

多元函数的泰勒展开Hesse矩阵：将函数进行泰勒展开取到二次项时得到二次函数形式，优化计算经常把目标函数表示成二次函数以便使问题简化。第17页,共70页，2024年2月25日，星期天Hesse矩阵的特性：是实对称矩阵。矩阵正定的充要条件：主子式det(ait)＞0当主子式det(ait)≥0时，矩阵半正定

det(ait)＜0时，矩阵负定

det(ait)≤0时，矩阵半负定Hesse矩阵的正定性：H(x*)正定，是x*为全局极小值点的充分条件；H(x*)半正定,是x*为局部极小值点的充分条件；H(x*)负定，是x*为全局极大值点的充分条件；H(x*)半负定,是x*为局部极大值点的充分条件。正定的二次函数：曲面为椭圆抛物面；等值线族为椭圆曲线族，椭圆中心为极小值点。正定Hesse矩阵§2.2多元函数的泰勒展开第18页,共70页，2024年2月25日，星期天若目标函数f(x)处处存在一阶导数，则极值点的必要条件一阶偏导数等于零，即满足此条件仅表明该点为驻点，不能肯定为极值点，即使为极值点，也不能判断为极大点还是极小点，还得给出极值点的充分条件设目标函数在点至少有二阶连续的偏导数，则在这一点的泰勒二次近似展开式为：§2.3无约束优化问题的极值条件第19页,共70页，2024年2月25日，星期天为N维函数f(x)在点处的Hesse矩阵第20页,共70页，2024年2月25日，星期天多元函数f(x)在处取得极值，则极值的条件为（1）▽F(X*)=0；必要条件（2）Hesse矩阵G(X*)为正定。充分条件为无约束极小点的充分条件是其Hesse矩阵G(X*)为正定的。为无约束优化问题的极值条件第21页,共70页，2024年2月25日，星期天同学考虑二元函数在处取得极值的充分必要条件。各阶主子式大于零第22页,共70页，2024年2月25日，星期天§2.3无约束优化问题的极值条件极值点存在的必要条件：如果函数f（x）的一阶导数f’（x）存在的话，则欲使x*为极值点的必要条件为：f’（x*）=0极值点存在的的充分条件：f’’（x）<0，则该点为极大值；f’’（x）>0，则改点为极小值。一.一元函数二.二元函数极值点存在的必要条件：如果函数f（x1，x2）在某点处取得极值，必要条件为：极值点存在的的充分条件：如果函数f（x1，x2）在某点处取得极值，充分条件为在该点处的海塞矩阵正定。第23页,共70页，2024年2月25日，星期天例1：例2：第24页,共70页，2024年2月25日，星期天第四节凸集、凸函数与凸规划前面我们根据函数极值条件确定了极小点则函数f(x)在附近的一切x均满足不等式所以函数f(x)在处取得局部极小值，称为局部极小点。而优化问题一般是要求目标函数在某一区域内的全局极小点。函数的局部极小点是不是一定是全局极小点呢？第25页,共70页，2024年2月25日，星期天图2-7下凸的一元函数第26页,共70页，2024年2月25日，星期天一、凸集的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。一个点集（或区域），如果连接其中任意两点第27页,共70页，2024年2月25日，星期天凸集的性质：（1）若A是一个凸集，b是一个实数，则bA还是凸集。（2）若A和B是凸集，则集合A+B还是凸集。（3）任何一组凸集的交集还是凸集。第28页,共70页，2024年2月25日，星期天二、凸函数函数f(x）为凸集定义域内的函数，若对任何的及凸集域内的任意两点存在如下不等式：称是定义在凸集上的一个凸函数。

当上式中的≤为＜时，f(x)是严格凸函数。第29页,共70页，2024年2月25日，星期天图2-10凸函数的定义第30页,共70页，2024年2月25日，星期天§2.4

凸集、凸函数与凸规划凸函数的性质：

若f(x)是定义在凸集D上的严格凸函数，则f(x)在D上的一个极小点，也就是全局最小点。凸函数的线性组合仍然为凸函数。设x(1),x(2)为凸函数f(x)上的两个最小点，则其连线上的任意点也都是最小点。第31页,共70页，2024年2月25日，星期天三、凸性条件（判别函数为凸函数）1.根据一阶导数（函数的梯度）来判断函数的凸性设f(x)为定义在凸集R上，且具有连续的一阶导数的函数，则f(x)在R上为凸函数的充要条件是对凸集R内任意不同两点，不等式恒成立。第32页,共70页，2024年2月25日，星期天设f(x)为定义在凸集R上且具有连续二阶导数的函数，则f(x)在R上为凸函数的充要条件：Hesse矩阵在R上处处半正定。若Hesse矩阵处处正定，则f(x)为严格凸函数。2.根据二阶导数（

Hesse矩阵)来判断函数的凸性第33页,共70页，2024年2月25日，星期天四、凸规划对于约束优化问题若都为凸函数，则此问题为凸规划。第34页,共70页，2024年2月25日，星期天凸规划的性质：1.若给定一点，则集合为凸集。2.可行域为凸集。3.凸规划的任何局部最优解就是全局最优解。当f(x)为二元函数时，其等值线呈现大圈套小圈形式。第35页,共70页，2024年2月25日，星期天§2.4

凸集、凸函数与凸规划总结：第36页,共70页，2024年2月25日，星期天第五节等式约束优化问题的极值条件约束优化等式约束不等式约束求解这一问题的方法消元法拉格朗日乘子法第37页,共70页，2024年2月25日，星期天一、消元法（降维法）以二元函数为例讨论。基本思想：根据等式约束条件将一个变量x1表示成另一个变量x2的函数关系。然后将这一函数关系带入到目标函数中消去x1，使目标函数变成一元函数这就将等式约束转化为无约束优化问题。对于n维，有几个等式约束就可以消去几个变量。

第五节等式约束优化问题的极值条件第38页,共70页，2024年2月25日，星期天二、拉格朗日乘子法（升维法）对于具有L个等式约束的n维优化问题处有第五节等式约束优化问题的极值条件基本思想：通过增加变量将等式约束优化问题变成无约束优化问题：第39页,共70页，2024年2月25日，星期天拉格朗日函数待定系数新目标函数的极值的必要条件将原来的目标函数作如下改造：第40页,共70页，2024年2月25日，星期天例2-4用拉格朗日乘子法计算在约束条件的情况下，目标函数的极值点坐标。第41页,共70页，2024年2月25日，星期天第六节不等式约束优化问题的极值条件在工程中大多数优化问题，可表示为不等式约束条件的优化问题。有必要引出非线性优化问题的重要理论，不等式约束的多元函数的极值的必要条件是：库恩-塔克（Kuhn-Tucker）条件一、一元函数在给定区间上的极值条件一元函数f(x)在给定区间[a,b]上的极值问题，可以写成下列具有不等式约束条件的优化问题：第42页,共70页，2024年2月25日，星期天拉格朗日乘子法，除了可以应用于等式的极值问题，还可以用于不等式的极值问题。用拉格朗日乘子法时，需引入松弛变量，将不等式约束变成等式约束。设a1和b1为两个松弛变量，则上述的不等式约束可写为：第六节不等式约束优化问题的极值条件第43页,共70页，2024年2月25日，星期天则该问题的拉格朗日函数：根据拉格朗日乘子法，此问题的极值条件：第六节不等式约束优化问题的极值条件第44页,共70页，2024年2月25日，星期天由（起作用约束）（不起作用约束）同样，来分析起作用何不起作用约束。因此，一元函数在给定区间的极值条件，可以表示为：第六节不等式约束优化问题的极值条件第45页,共70页，2024年2月25日，星期天多元库恩-塔克条件分析极值点在区间的位置，有三种情况第六节不等式约束优化问题的极值条件第46页,共70页，2024年2月25日，星期天当时，此时，则极值条件为：第47页,共70页，2024年2月25日，星期天当时，此时则极值条件为即第六节不等式约束优化问题的极值条件第48页,共70页，2024年2月25日，星期天当时，此时，则极值条件为即第六节不等式约束优化问题的极值条件第49页,共70页，2024年2月25日，星期天从以上分析可以看出，对应于不起作用的约束的拉格朗日乘子取零值，因此可以引入起作用约束的下标集合。一元函数在给定区间的极值条件，可以改写为：极值条件中只考虑起作用的约束和相应的乘子。第六节不等式约束优化问题的极值条件第50页,共70页，2024年2月25日，星期天二、库恩-塔克条件仿照一元函数给定区间上极值条件的推导过程，可以得到具有不等式约束多元函数极值条件：用起作用约束的下标集合表示第六节不等式约束优化问题的极值条件第51页,共70页，2024年2月25日，星期天用梯度形式表示，可得或库恩-塔克条件的几何意义：在约束极小点处，函数的负梯度一定能表示成所有起作用约束在该点梯度的非负线性组合。第52页,共70页，2024年2月25日，星期天下面以二维问题为例，说明K-T条件的几何意义第六节不等式约束优化问题的极值条件第53页,共70页，2024年2月25日，星期天从图中可以看出，处在和角锥之内，即线性组合的系数为正，是在取得极值的必要条件。第六节不等式约束优化问题的极值条件第54页,共70页，2024年2月25日，星期天三、库恩-塔克条件应用举例若给定优化问题的数学模型为K-T条件第六节不等式约束优化问题的极值条件第55页,共70页，2024年2月25日，星期天第56页,共70页，2024年2月25日，星期天§2.5约束优化问题的极值条件一.优化设计最优解无约束优化设计问题最优解：约束优化设计问题最优解：

不受约束条件限制，使目标函数达到最小值的一组设计变量，即最优点x*=[x1*,x2*,…,xn*]和最优值f(x*)构成无约束问题最优解。

满足约束条件，使目标函数达到最小值的一组设计变量，即最优点x*=[x1*,x2*,…,xn*]和最优值f(x*)构成约束问题最优解。第57页,共70页，2024年2月25日，星期天二.有约束问题最优点的几种情况有适时约束目标函数是凸函数,可行域是凸集，则目标函数等值线与适时约束曲面的切点为最优点，而且是全局最优点。无适时约束目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约束问题的最优点。x(k)

为最优点x*的条件：必要条件：充分条件：Hesse矩阵H(x(k))

是正定矩阵·f(x)·x*·X*§2.5

约束优化问题的极值条件

第58页,共70页，2024年2月25日，星期天有适时约束目标函数是非凸函数（图a），或可行域是非凸集（图b）：

则目标函数等值线与适时约束曲面可能存在多个切点，是局部极值点，其中只有一个点是全局最优点。二.有约束问题最优点的几种情况pQQp§2.5等式约束优化问题的极值条件

第59页,共70页，2024年2月25日，星期天三.K-T(Kuhn-Tucker库恩-塔克)条件它是约束极值点存在条件，用来判断某个可行点是否为约束极值点。§2.5约束优化问题的极值条件

第60页,共70页，2024年2月25日，星期天§2.5约束优化问题的极值条件

K—T条件的图形说明：

几何上，x(k)成为约束最优点（极小点）x*时，目标函数的负梯度向量位于m适时约束梯度向量所张成的子空间内。第61页,共70页，2024年2月25日，星期天§2.5约束优化问题的极值条件

第62页,共70页，2024年2月25日，星期天§2.5约束优化问题的极值条件

第63页,共70页，2024年2月25日，星期天1.有一个适时约束时：

从几何上看，当从x(k)点出发不存在一个S方向能同时满足:与x(k)点目标函数的负梯度方向成锐角，即沿S方向目标函数值下降；与x(k)点约束函数的梯度方向成钝角，即保证S方向上各点在可行域内。此时，获得最优解x(k)

为最优点x*，f(x(k))为最优值f(x*)。§2.5约束优化问题的极值条件

第64页,共70页，2024年2月25日，星期天

从几何上看，当从x(k)点出发存在一个S方向能同时满足：与x(k)点目标函数的负梯度方向成锐角，即沿S方向目标函数值下降；与x(k)点约束函数的梯度方向成钝角，即保证S方向上各点在可行域内。此时，x(k)不是最优点x*。§2.5约束优化问题的极值条件

第65页,共70页，2024年2月25日，星期天2.