优化数学基础.ppt

关于优化的数学基础第一张，PPT共七十页，创作于2022年6月机械设计问题一般是非线性规划问题。实质上是多元非线性函数的极小化问题，因此，机械优化设计是建立在多元函数的极值理论基础上的。机械优化设计问题分为：无约束优化约束优化无条件极值问题条件极值问题第二张，PPT共七十页，创作于2022年6月补充：补充：等值（线）面等值（线）面：对于可计算的函数对于可计算的函数 f(x)f(x)，给定一个设计点，给定一个设计点 X X(k)(k)(x(x1 1(k)(k),x,x2 2(k)(k),x,xn n (k)(k)，f(x)f(x)总有一个定值总有一个定值c c 与之对应；而当与之对应；而当f(x)f(x)取定值取定值 c c 时，则有无限多个设计点时，则有无限多个设计点X X(i)(i)(x(x1 1(i)(i),x,x2 2(i)(i),x,xn n(i)(i)（i=1,2,i=1,2,）与之对应，这些点集构成一个曲面，）与之对应，这些点集构成一个曲面，称为称为等值面等值面。当当 c c 取取c c1 1,c,c2 2,等值等值时，就获得一族曲面族，称时，就获得一族曲面族，称为为等值面族等值面族。当当f(x)f(x)是二维时，获得是二维时，获得一族等值线族；一族等值线族；当当f(x)f(x)是三维时，获是三维时，获得一族等值面族；得一族等值面族；当当f(x)f(x)大于三维时，获大于三维时，获得一族超等值面族。得一族超等值面族。第三张，PPT共七十页，创作于2022年6月等值线的等值线的“心心”（以二维为例）一个一个“心心”：是单峰函数的：是单峰函数的极（小）值点极（小）值点，是全局极（小）值点。，是全局极（小）值点。没有没有“心心”：例，线性函数的等值线是平行的，无：例，线性函数的等值线是平行的，无“心心”，认为极值点在，认为极值点在无穷远处。无穷远处。多个多个“心心”：不是单峰函数，每个极（小）值点只是局部极（小）值点，必须通：不是单峰函数，每个极（小）值点只是局部极（小）值点，必须通过比较各个极值点和过比较各个极值点和“鞍点鞍点”（须正确判别）的值，才能确定极（小）值点。（须正确判别）的值，才能确定极（小）值点。补充：等值（线）面：补充：等值（线）面：第四张，PPT共七十页，创作于2022年6月等值线的形状等值线的形状：同心圆族、椭圆族，近似椭圆族；同心圆族、椭圆族，近似椭圆族；等值线的疏密等值线的疏密：沿等值线密的方向，函数值变化快；沿等值线密的方向，函数值变化快；沿等值线疏的方向，函数值变化慢。沿等值线疏的方向，函数值变化慢。等值线的疏密定性反应函数值变化率。等值线的疏密定性反应函数值变化率。严重非线性函数严重非线性函数病态函数的等值线族病态函数的等值线族是严重偏心和扭曲、分布疏密严重不一的曲线是严重偏心和扭曲、分布疏密严重不一的曲线族。族。补充：等值（线）面：补充：等值（线）面：第五张，PPT共七十页，创作于2022年6月2.1 多元函数的方向导数与梯度一、方向导数 从多元函数的微分学得知，对于一个连续可微函数f(x)在某一点 的一阶偏导数为：，它表示函数f(x)值在 点沿各坐标轴方向的变化率。有一个二维函数，如图2-1所示。第六张，PPT共七十页，创作于2022年6月图2-1 函数的方向导数 为为 d d 的方向角的方向角,即与坐标轴的夹角即与坐标轴的夹角2.1 多元函数的方向导数与梯度第七张，PPT共七十页，创作于2022年6月其函数在 点沿d方向的方向导数为2.1 多元函数的方向导数与梯度第八张，PPT共七十页，创作于2022年6月2.12.1 多元函数的方向导数和梯度多元函数的方向导数和梯度 二维问题中，二维问题中，f(xf(x1 1,x,x2 2)在在 X X(0)(0)点沿方向点沿方向d d的方向导数可以写的方向导数可以写为：为：二二.二元函数梯度二元函数梯度第九张，PPT共七十页，创作于2022年6月2.12.1 多元函数的方向导数和梯度多元函数的方向导数和梯度其中：其中：是是 X X(0)(0)点的梯度。点的梯度。为为d d方向的单位向量，方向的单位向量，方向导数方向导数为梯度为梯度在方向在方向 d d 上的投影。上的投影。第十张，PPT共七十页，创作于2022年6月结论：函数在某点沿各方向的方向导数随结论：函数在某点沿各方向的方向导数随 即变化，其最大值在余弦函数取值为变化，其最大值在余弦函数取值为1 1时，也就是当梯时，也就是当梯度方向与度方向与d d方向重合时其值最大。可见，方向重合时其值最大。可见，梯度方向就是梯度方向就是函数值变化最快的方向，而梯度的模就是函数变化率的最函数值变化最快的方向，而梯度的模就是函数变化率的最大值。大值。第十一张，PPT共七十页，创作于2022年6月梯度方向和切线方向垂梯度方向和切线方向垂直，即梯度方向为等值直，即梯度方向为等值面的法线方向。面的法线方向。第十二张，PPT共七十页，创作于2022年6月三、多元函数的梯度沿d方向的方向向量即2.12.1 多元函数的方向导数和梯度多元函数的方向导数和梯度第十三张，PPT共七十页，创作于2022年6月总结总结:梯度是梯度是 X X(0)(0)点处最大的方向导数；点处最大的方向导数；梯度的方向是过点的等值线的法线方向；梯度的方向是过点的等值线的法线方向；梯度是梯度是X X(0)(0)点处的局部性质；点处的局部性质；梯度指向函数变化率最大的方向；梯度指向函数变化率最大的方向；正梯度方向是函数值最速上升的方向，正梯度方向是函数值最速上升的方向，负梯度方向是负梯度方向是函数值最速下降的方向函数值最速下降的方向。2.12.1 多元函数的方向导数和梯度多元函数的方向导数和梯度第十四张，PPT共七十页，创作于2022年6月图2-5 梯度方向与等值面的关系第十五张，PPT共七十页，创作于2022年6月2.22.2 多元函数的泰勒展开多元函数的泰勒展开n n 维函数维函数 f(x)f(x)在在 x x(k)(k)点的泰勒展开式点的泰勒展开式:二阶近似式：二阶近似式：其中：增量其中：增量 X(k)=x1(k),x2(k),xn(k)T梯度梯度 一一.Hessian.Hessian 矩阵与正定矩阵与正定第十六张，PPT共七十页，创作于2022年6月2.22.2 多元函数的泰勒展开多元函数的泰勒展开Hesse Hesse 矩阵：矩阵：将函数进行泰勒展开取到二次项时得到二次函数形式，优化计算经常将函数进行泰勒展开取到二次项时得到二次函数形式，优化计算经常把目标函数表示成二次函数以便使问题简化。把目标函数表示成二次函数以便使问题简化。第十七张，PPT共七十页，创作于2022年6月Hesse Hesse 矩阵的特性：是实对称矩阵。矩阵的特性：是实对称矩阵。矩阵正定的充要条件：矩阵正定的充要条件：主子式主子式 det(ait)det(ait)0 0当主子式当主子式 det(ait)0 det(ait)0 时，矩阵半正定时，矩阵半正定 det(ait)det(ait)0 0时，矩阵负定时，矩阵负定 det(ait)0det(ait)0时，矩阵半负定时，矩阵半负定Hesse Hesse 矩阵的正定性：矩阵的正定性：H(x*)H(x*)正定，正定，是是 x*x*为全局极小值点的充分条件为全局极小值点的充分条件；H(x*)H(x*)半正定半正定,是是 x*x*为局部极小值点的充分条件；为局部极小值点的充分条件；H(x*)H(x*)负定，负定，是是 x*x*为全局极大值点的充分条件；为全局极大值点的充分条件；H(x*)H(x*)半负定半负定,是是 x*x*为局部极大值点的充分条件。为局部极大值点的充分条件。正定的二次函数：曲面为椭圆抛物面；正定的二次函数：曲面为椭圆抛物面；等值线族为椭圆曲线族，椭圆中心为极小值点。等值线族为椭圆曲线族，椭圆中心为极小值点。正定正定Hesse Hesse 矩阵矩阵2.2 多元函数的泰勒展开第十八张，PPT共七十页，创作于2022年6月若目标函数f(x)处处存在一阶导数，则极值点的必要条件一阶偏导数等于零，即满足此条件仅表明该点为驻点，不能肯定为极值点，即使为极值点，也不能判断为极大点还是极小点，还得给出极值点的充分条件设目标函数在 点至少有二阶连续的偏导数，则在这一点的泰勒二次近似展开式为：2.3 无约束优化问题的极值条件第十九张，PPT共七十页，创作于2022年6月为N维函数f(x)在点处的Hesse矩阵第二十张，PPT共七十页，创作于2022年6月多元函数f(x)在 处取得极值，则极值的条件为（1）F(X*)=0；必要条件（2）Hesse矩阵G(X*)为正定。充分条件为无约束极小点的充分条件是其Hesse矩阵G(X*)为正定的。为无约束优化问题的极值条件第二十一张，PPT共七十页，创作于2022年6月同学考虑二元函数在 处取得极值的充分必要条件。各阶主子式大于零第二十二张，PPT共七十页，创作于2022年6月2.3 2.3 无约束优化问题的极值条件无约束优化问题的极值条件极值点存在的必要条件：极值点存在的必要条件：如果函数如果函数f f（x x）的一阶导数）的一阶导数ff（x x）存在的话，则欲使）存在的话，则欲使x*x*为极值点的必要条为极值点的必要条件为：件为：ff（x*x*）=0=0极值点存在的的充分条件：极值点存在的的充分条件：f（x）0，则改点为极小值。，则改点为极小值。一一.一元函数一元函数二二.二元函数二元函数极值点存在的必要条件：极值点存在的必要条件：如果函数如果函数f f（x x1 1，x x2 2）在某点处取得极值，必要条件为：）在某点处取得极值，必要条件为：极值点存在的的充分条件：极值点存在的的充分条件：如果函数如果函数f f（x1x1，x2x2）在某点处取得极值，充分条件为在该）在某点处取得极值，充分条件为在该点处的海塞矩阵正定。点处的海塞矩阵正定。第二十三张，PPT共七十页，创作于2022年6月例1：例2：第二十四张，PPT共七十页，创作于2022年6月第四节 凸集、凸函数与凸规划前面我们根据函数极值条件确定了极小点则函数f(x)在 附近的一切x均满足不等式所以函数f(x)在 处取得局部极小值，称 为局部极小点。而优化问题一般是要求目标函数在某一区域内的全局极小点。函数的局部极小点是不是一定是全局极小点呢？第二十五张，PPT共七十页，创作于2022年6月图2-7 下凸的一元函数第二十六张，PPT共七十页，创作于2022年6月一、凸集的线段都全部包含在该集合内，就称该点集为凸集，否则为非凸集。一个点集（或区域），如果连接其中任意两点第二十七张，PPT共七十页，创作于2022年6月凸集的性质：凸集的性质：（1 1）若）若A A是一个凸集，是一个凸集，b b是一个实数，则是一个实数，则bAbA还是凸集。还是凸集。（2 2）若）若A A和和B B是凸集，则集合是凸集，则集合A+BA+B还是凸集。还是凸集。（3 3）任何一组凸集的交集还是凸集。）任何一组凸集的交集还是凸集。第二十八张，PPT共七十页，创作于2022年6月二、凸函数函数f(x）为凸集定义域内的函数，若对任何的及凸集域内的任意两点存在如下不等式：称是定义在凸集上的一个凸函数。当上式中的当上式中的为时，为时，f(x)f(x)是严格凸函数。是严格凸函数。第二十九张，PPT共七十页，创作于2022年6月图2-10 凸函数的定义第三十张，PPT共七十页，创作于2022年6月2.42.4 凸集、凸函数与凸规划凸集、凸函数与凸规划凸函数的性质：凸函数的性质：l 若若f(x)f(x)是定义在凸集是定义在凸集D D上的严格凸函数，则上的严格凸函数，则f(x)f(x)在在D D上的一个上的一个极小点，也就是全局最小点。极小点，也就是全局最小点。l 凸函数的线性组合仍然为凸函数。凸函数的线性组合仍然为凸函数。l 设设x x(1)(1),x,x(2)(2)为凸函数为凸函数 f(x)f(x)上的两个最小点，则其连线上的上的两个最小点，则其连线上的任意点也都是最小点。任意点也都是最小点。第三十一张，PPT共七十页，创作于2022年6月三、凸性条件（判别函数为凸函数）1.根据一阶导数（函数的梯度）来判断函数的凸性设f(x)为定义在凸集R上，且具有连续的一阶导数的函数，则f(x)在R上为凸函数的充要条件是对凸集R内任意不同两点 ，不等式恒成立。第三十二张，PPT共七十页，创作于2022年6月设f(x)为定义在凸集R上且具有连续二阶导数的函数，则f(x)在R上为凸函数的充要条件：Hesse矩阵在R上处处半正定。若Hesse矩阵处处正定，则f(x)为严格凸函数。2.根据二阶导数（Hesse矩阵)来判断函数的凸性第三十三张，PPT共七十页，创作于2022年6月四、凸规划对于约束优化问题若都为凸函数，则此问题为凸规划。第三十四张，PPT共七十页，创作于2022年6月凸规划的性质：1.若给定一点 ，则集合为凸集。2.可行域为凸集。3.凸规划的任何局部最优解就是全局最优解。当f(x)为二元函数时，其等值线呈现大圈套小圈形式。第三十五张，PPT共七十页，创作于2022年6月2.42.4 凸集、凸函数与凸规划凸集、凸函数与凸规划总结总结：第三十六张，PPT共七十页，创作于2022年6月第五节 等式约束优化问题的极值条件约束优化等式约束不等式约束求解这一问题的方法消元法拉格朗日乘子法第三十七张，PPT共七十页，创作于2022年6月一、消元法（降维法）以二元函数为例讨论。基本思想：根据等式约束条件将一个变量x1表示成另一个变量x2的函数关系 。然后将这一函数关系带入到目标函数 中消去x1，使目标函数变成一元函数这就将等式约束转化为无约束优化问题。对于n维，有几个等式约束就可以消去几个变量。第五节 等式约束优化问题的极值条件第三十八张，PPT共七十页，创作于2022年6月二、拉格朗日乘子法（升维法）对于具有L个等式约束的n维优化问题处有第五节 等式约束优化问题的极值条件基本思想：通过增加变量将等式约束优化问题变成无约束优化问题：第三十九张，PPT共七十页，创作于2022年6月拉格朗日函数待定系数新目标函数的极值的必要条件将原来的目标函数作如下改造：第四十张，PPT共七十页，创作于2022年6月例2-4 用拉格朗日乘子法计算在约束条件的情况下，目标函数的极值点坐标。第四十一张，PPT共七十页，创作于2022年6月第六节 不等式约束优化问题的极值条件在工程中大多数优化问题，可表示为不等式约束条件的优化问题。有必要引出非线性优化问题的重要理论，不等式约束的多元函数的极值的必要条件是：库恩-塔克（Kuhn-Tucker）条件一、一元函数在给定区间上的极值条件一元函数f(x)在给定区间a,b上的极值问题，可以写成下列具有不等式约束条件的优化问题：第四十二张，PPT共七十页，创作于2022年6月拉格朗日乘子法，除了可以应用于等式的极值问题，还可以用于不等式的极值问题。用拉格朗日乘子法时，需引入松弛变量，将不等式约束变成等式约束。设a1和b1为两个松弛变量，则上述的不等式约束可写为：第六节 不等式约束优化问题的极值条件第四十三张，PPT共七十页，创作于2022年6月则该问题的拉格朗日函数：根据拉格朗日乘子法，此问题的极值条件：第六节 不等式约束优化问题的极值条件第四十四张，PPT共七十页，创作于2022年6月由（起作用约束）（不起作用约束）同样 ，来分析 起作用何不起作用约束。因此，一元函数在给定区间的极值条件，可以表示为：第六节 不等式约束优化问题的极值条件第四十五张，PPT共七十页，创作于2022年6月多元库恩-塔克条件分析极值点 在区间的位置，有三种情况第六节 不等式约束优化问题的极值条件第四十六张，PPT共七十页，创作于2022年6月当时，此时，则极值条件为：第四十七张，PPT共七十页，创作于2022年6月当时，此时则极值条件为即第六节 不等式约束优化问题的极值条件第四十八张，PPT共七十页，创作于2022年6月当时，此时，则极值条件为即第六节 不等式约束优化问题的极值条件第四十九张，PPT共七十页，创作于2022年6月从以上分析可以看出，对应于不起作用的约束的拉格朗日乘子取零值，因此可以引入起作用约束的下标集合。一元函数在给定区间的极值条件，可以改写为：极值条件中只考虑起作用的约束和相应的乘子。第六节 不等式约束优化问题的极值条件第五十张，PPT共七十页，创作于2022年6月二、库恩-塔克条件仿照一元函数给定区间上极值条件的推导过程，可以得到具有不等式约束多元函数极值条件：用起作用约束的下标集合表示第六节 不等式约束优化问题的极值条件第五十一张，PPT共七十页，创作于2022年6月用梯度形式表示，可得或库恩-塔克条件的几何意义：在约束极小点处，函数的负梯度一定能表示成所有起作用约束在该点梯度的非负线性组合。第五十二张，PPT共七十页，创作于2022年6月下面以二维问题为例，说明K-T条件的几何意义第六节 不等式约束优化问题的极值条件第五十三张，PPT共七十页，创作于2022年6月从图中可以看出，处在和角锥之内，即线性组合的系数为正，是在取得极值的必要条件。第六节 不等式约束优化问题的极值条件第五十四张，PPT共七十页，创作于2022年6月三、库恩-塔克条件应用举例若给定优化问题的数学模型为K-T条件第六节 不等式约束优化问题的极值条件第五十五张，PPT共七十页，创作于2022年6月第五十六张，PPT共七十页，创作于2022年6月2.5 2.5 约束优化问题的极值条件约束优化问题的极值条件 一一.优化设计最优解优化设计最优解无约束优化设计问题最优解：无约束优化设计问题最优解：约束优化设计问题最优解约束优化设计问题最优解：不受约束条件限制，使目标函数达到最小值的一组设计变量，即最优点不受约束条件限制，使目标函数达到最小值的一组设计变量，即最优点 x*=xx*=x1 1*,x*,x2 2*,x*,x n n*和最优值和最优值 f(x*)f(x*)构成无约束问题最优解。构成无约束问题最优解。满足约束条件，使目标函数达到满足约束条件，使目标函数达到最小值的一组设计变量，最小值的一组设计变量，即最优即最优点点 x*=xx*=x1 1*,x*,x2 2*,x*,x n n*和最优值和最优值 f(x*)f(x*)构成约束问题最优解。构成约束问题最优解。第五十七张，PPT共七十页，创作于2022年6月二二.有约束问题最优点的几种情况有约束问题最优点的几种情况2.2.有适时约束有适时约束3.3.目标函数是凸函数目标函数是凸函数,可行域是凸集，可行域是凸集，则目标函数等值线与适时约束曲面的则目标函数等值线与适时约束曲面的切点为最优点，而且是全局最优点。切点为最优点，而且是全局最优点。1.1.无适时约束无适时约束2.2.目标函数是凸函数，可行域是凸集，目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约束问题的则最优点是内点。相当于无约束问题的最优点。最优点。x x(k)(k)为最优点为最优点x*x*的条件：的条件：必要条件：必要条件：充分条件：充分条件：HesseHesse矩阵矩阵 H(xH(x(k)(k)是正定矩阵是正定矩阵f(x)x*X*2.52.5 约束优化问题的极值条件约束优化问题的极值条件 第五十八张，PPT共七十页，创作于2022年6月3.3.有适时约束有适时约束4.4.目标函数是非凸函数（图目标函数是非凸函数（图 a a），或可行域是非凸集（图），或可行域是非凸集（图 b b）：）：则目标函数等值线与适时约束曲面可能存在多个切点，是局部极值点，则目标函数等值线与适时约束曲面可能存在多个切点，是局部极值点，其中只有一个点是全局最优点。其中只有一个点是全局最优点。二二.有约束问题最优点的几种情况有约束问题最优点的几种情况pQQp2.5 2.5 等式约束优化问题的极值条件等式约束优化问题的极值条件 第五十九张，PPT共七十页，创作于2022年6月三三.K-T(Kuhn-Tucker .K-T(Kuhn-Tucker 库恩库恩-塔克塔克)条件条件 它是约束极值点存在条件，用来判断某个可行点是否为约束极值点。它是约束极值点存在条件，用来判断某个可行点是否为约束极值点。2.5 2.5 约束优化问题的极值条件约束优化问题的极值条件 第六十张，PPT共七十页，创作于2022年6月2.5 2.5 约束优化问题的极值条件约束优化问题的极值条件 KT条件的图形说明：几何上，几何上，x x(k)(k)成为约束最优点（极小点）成为约束最优点（极小点）x*x*时，目标函数的负梯度向量位于时，目标函数的负梯度向量位于 m m 适时约束梯度向量所张成的子空间内。适时约束梯度向量所张成的子空间内。第六十一张，PPT共七十页，创作于2022年6月2.5 2.5 约束优化问题的极值条件约束优化问题的极值条件 第六十二张，PPT共七十页，创作于2022年6月2.5 2.5 约束优化问题的极值条件约束优化问题的极值条件 第六十三张，PPT共七十页，创作于2022年6月1.1.有一个适时约束时：有一个适时约束时：从几何上看，当从从几何上看，当从 x(k)x(k)点出发不存在一个点出发不存在一个 S S 方向能同时满足方向能同时满足:与与x x(k)(k)点目标函数的负梯度方向成锐角，即沿点目标函数的负梯度方向成锐角，即沿 S S 方向方向目标函数值下降；目标函数值下降；与与x x(k)(k)点约束函数的梯度方向成钝角，即保证点约束函数的梯度方向成钝角，即保证 S S方向上各点在可行域内。方向上各点在可行域内。此时，获得最优解此时，获得最优解 x x(k)(k)为最优点为最优点 x*x*，f(xf(x(k)(k)为最优值为最优值 f(x*)f(x*)。2.5 2.5 约束优化问题的极值条件约束优化问题的极值条件 第六十四张，PPT共七十页，创作于2022年6月 从几何上看，当从从几何上看，当从 x x(k)(k)点出发存在一个点出发存在一个 S S 方向方向能同时满足：能同时满足：与与x x(k)(k)点目标函数的负梯度方向成锐角，即沿点目标函数的负梯度方向成锐角，即沿 S S 方向目标函数值下降；方向目标函数值下降；与与x x(k)(k)点约束函数的梯度方向成钝角，即保证点约束函数的梯度方向成钝角，即保证 S S方向方向上各点在可行域内。上各点在可行域内。此时，此时，x x(k)(k)不是最优点不是最优点 x*x*。2.5 2.5 约束优化问题的极值条件约束优化问题的极值条件 第六十五张，PPT共七十页，创作于2022年6月2.2.有二个适时约束时：有二个适时约束时：x x(k)(k)成为约束最优点成为约束最优点 x*x*的必要条件为的必要条件为:几何上几何上 位于位于和和 所张的扇形子空间内。所张的扇形子空间内。即不存在一个即不存在一个 S S 方向能同时满足：方向能同时满足：2.5 约束优化问题的极值条件约束优化问题的极值条件 第六十六张，PPT共七十页，创作于2022年6月相反，不符合以上条件：相反，不符合以上条件：不能表达成不能表达成 和和 的线性组合。的线性组合。几何上几何上 不位于不位于 和和 所张的扇形子空间内。所张的扇形子空间内。则则 x x(k)(k)点不是最优点。点不是最优点。即存在一个即存在一个 S S 方向能同时满足：方向能同时满足：2.5 约束优化问题的极值条件约束优化问题的极值条件 第六十七张，PPT共七十页，创作于2022年6月K-TK-T条件的作用：条件的作用：l 判别边界设计点判别边界设计点 x x(k)(k)为最优点的依据，（要求会判断）；为最优点的依据，（要求会判断）；l 作为约束优化的收敛条件。作为约束优化的收敛条件。问题：问题：l K-TK-T条件是否为充分必要条件？若是，说明理由；若不是，则说条件是否为充分必要条件？若是，说明理由；若不是，则说明什么情况下，可成为充要条件？明什么情况下，可成为充要条件？l 有等式约束时，有等式约束时，K-TK-T条件是否还能适用？条件是否还能适用？2.5 约束优化问题的极值条件约束优化问题的极值条件 第六十九张，PPT共七十页，创作于2022年6月感感谢谢大大家家观观看看第七十张，PPT共七十页，创作于2022年6月