第2章优化方法的数学基础优秀课件.ppt

《第2章优化方法的数学基础优秀课件.ppt》由会员分享，可在线阅读，更多相关《第2章优化方法的数学基础优秀课件.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第2章优化方法的数学基础第1页，本讲稿共47页2-1 2-1 方向导数与梯度方向导数与梯度一、方向导数一、方向导数二元函数在点二元函数在点x0处沿某一方向处沿某一方向s s的的方向导数方向导数方向导数是偏导数概念的推广。方向导数是偏导数概念的推广。方向导数与偏导数之间的数量关系是方向导数与偏导数之间的数量关系是第2页，本讲稿共47页n元函数在点元函数在点x0处沿处沿s s方向的方向导数方向的方向导数 Ox2x1x10 x20 x0 x1x2sxS12图图2-1第3页，本讲稿共47页二、梯度二元函数的梯度 为函数F(x1，x2)在x0点处的梯度。第4页，本讲稿共47页梯度的模：设梯度方向和s方向

2、重合时，方向导数值最大。第5页，本讲稿共47页 梯度方向是函数值变化最快的方向，梯度方向是函数值变化最快的方向，梯度方向是函数值变化最快的方向，梯度方向是函数值变化最快的方向，而梯度的模而梯度的模就是函数变化率的最大值就是函数变化率的最大值。图图2-2 梯度方向与等值线的关系梯度方向与等值线的关系设：设：则有则有 为单位向量。为单位向量。第6页，本讲稿共47页多元函数的梯度多元函数的梯度第7页，本讲稿共47页 函数的梯度方向与函数等值面相垂直，也就是和等值函数的梯度方向与函数等值面相垂直，也就是和等值面上过面上过x0的一切曲线相垂直。的一切曲线相垂直。由于梯度的模因点而异，即函数在不同点处的最

3、大由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种变化率是不同的。因此，梯度是函数的一种局部性质局部性质。l梯度 模：第8页，本讲稿共47页梯度两个重要性质：梯度两个重要性质：梯度两个重要性质：梯度两个重要性质：性质一性质一性质一性质一 函数在某点的梯度不为零，则必与过该点的函数在某点的梯度不为零，则必与过该点的函数在某点的梯度不为零，则必与过该点的函数在某点的梯度不为零，则必与过该点的等值面垂直；等值面垂直；等值面垂直；等值面垂直；性质二性质二性质二性质二 梯度方向是函数具有最大变化率的方向。梯度方向是函数具有最大变化率的方向。梯度方向是函数具有最大变化率的

4、方向。梯度方向是函数具有最大变化率的方向。图图2-2 梯度方向与等值面的关系梯度方向与等值面的关系第9页，本讲稿共47页例题例题 2-12-1求函数 在点3,2T 的 梯度。在点在点x(1)=3,2T处的梯度为：处的梯度为：l解：解：第10页，本讲稿共47页例例2-2：试求目标函数：试求目标函数 在点在点 处的处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。标函数值。则函数在 处的最速下降方向是解：解：由于由于新点是新点是这个方向上的单位向量是：这个方向上的单位向量是：第11页，本讲稿共47页几个常用的梯度公式：几个常用

5、的梯度公式：第12页，本讲稿共47页 当当极极值值点点X X*能能使使f f（X X*）在在整整个个可可行行域域中中为为最最小小值值时时，即即在在整整个个可可行行域域中中对对任任一一X X都都有有f f（X X）f f（X X*）时时，则则X X*就就是是最最优优点点，且且称称为为全全全全域域域域最最最最优优优优点点点点或或或或整整整整体体体体最最最最优优优优点点点点。若若f f（X X*）为为局局部部可可行行域域中中的的极极小小值值而而不不是是整整个个可可行行域域中中的的最最小小值值时时，则则称称X X*为为局局局局部部部部最最最最优优优优点点点点或或或或相相相相对对对对最最最最优优优优点点

6、点点。最最优优化化设设计计的的目目标标是是全全域域最最优优点点。为为了了判判断断某某一一极极值值点点是是否否为为全全域域最最优优点点，研研究究一一下下函函数数的的凸凸性很有必要。性很有必要。函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。只有一个，因而该点既是局部最优点亦为全域最优点。为了研究函数的凸性，现引入凸集的概念：为了研究函数的凸性，现引入凸集的概念：2-2 2-2 凸集、凸函数与凸规划凸集、凸函数与凸规划第13页，本讲稿共47页一、凸集一、凸集一、凸集一、凸集 设设

7、D D为为n n维维欧欧氏氏空空间间中中的的一一个个集集合合，若若其其中中任任意意两两点点X X(1)(1)、X X(2)(2)之之间间的的联联接接直直线线都都属属于于D D，则则称称这这种种集集合合D D为为n n维维欧欧氏氏空空间间的的一一个个凸凸集集。图图2-32-3（a a）是是二二维维空空间间的的一一个个凸凸集集，而而图图2-32-3（b b）不不是是凸集。凸集。图2-3 二维空间的凸集与非凸集第14页，本讲稿共47页X X（1 1）、X X（2 2）两点之间的联接直线，可用数学式表达为两点之间的联接直线，可用数学式表达为:式中式中 为由为由0 0到到1 1（0 10 1）间的任意实

8、数。）间的任意实数。凸集的性质：凸集的性质：1）若D为凸集，是一个实数，则集合 D仍是凸集；2 2）若）若D D和和F F均为凸集，则其和（或并）仍是凸集；均为凸集，则其和（或并）仍是凸集；3 3）任何一组凸集的积（或交）仍是凸集。）任何一组凸集的积（或交）仍是凸集。第15页，本讲稿共47页二、凸函数二、凸函数二、凸函数二、凸函数 具具有有凸凸性性（表表现现为为单单峰峰性性）或或只只有有唯唯一一的的局局部部最最优优值值亦亦即即全全域域最最优值优值的函数，称的函数，称为为凸凸凸凸函数函数函数函数或或或或单单单单峰函数峰函数峰函数峰函数。其数学定。其数学定义义是是：设设 f f（X X）为为定定义

9、义在在 n n维维欧氏空欧氏空间间中的一个凸集中的一个凸集D D上的函数，如果上的函数，如果对对任何任何实实数数a a（0a10a 0），则），则 af（X）也必是定义在凸集）也必是定义在凸集D D上的凸函数；上的凸函数；3 3）若若f f1 1(X X），f f2 2(X X)为为定定义义在在凸凸集集D D上上的的两两个个凸凸函函数数，和和为为两两个个任意正数，任意正数，则则函数函数 afafl l（X X）ff2 2(X X)仍仍为为D D上的凸函数上的凸函数。2 2）定定义义在在凸凸集集D D上上的的两两个个凸凸函函数数f f1 1(X X），f f2 2(X X)，其其和和 f f（X

10、 X）=f=f1 1（X X）十）十f f2 2（X X）亦必）亦必为该为该凸集上的一个凸函数。凸集上的一个凸函数。4 4）若若f f（X X）为为定定义义在在凸凸集集D D上上且且具具有有连连续续一一阶阶导导数数的的函函数数，则则f f（X X）为为凸函数的充分必要条件凸函数的充分必要条件为为：对对任意两点任意两点X X（1 1），X X（2 2），不等式，不等式恒成立恒成立第18页，本讲稿共47页三、凸规划三、凸规划三、凸规划三、凸规划 对于约束优化问题对于约束优化问题 式中若式中若F F（X X）、均均为为凸函数，凸函数，则称此问题为则称此问题为凸规划凸规划凸规划凸规划。第19页，本讲稿

11、共47页凸规划的一些性质：凸规划的一些性质：2 2）凸规划问题中的任何局部最优解都是全局最优解凸规划问题中的任何局部最优解都是全局最优解；1）可行域 为凸集；3）若F（X）可微，则X*为凸规划问题的最优解的充分必要条件为：对任意 ，对满足第20页，本讲稿共47页 不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难麻烦。尤其对一些工程问题，由于

12、其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，就不必花精力进行求证，而通常是实现。因此，在优化设计的求解中，就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。解。注意：注意：注意：注意：第21页，本讲稿共47页外，最简单最重要的一类就是二次函数。外，最简单最重要的一类就是二次函数。在在n元函数中，除了线形函数：元函数中，除了线形函数：或或 f(X)=aX+c2-3 2-3 二次函数及正定矩阵二次函数及正定矩阵第22页，本讲稿共47页其中 均为常数。若若 ，X0 ，均有，

13、均有 0 ，则称矩阵，则称矩阵Q是是正定正定正定正定的。的。在代数学中将特殊的二次函数在代数学中将特殊的二次函数 称为称为二次型二次型二次型二次型。对于二次函数，我们更关心的是对于二次函数，我们更关心的是Q为正定矩阵的情形。为正定矩阵的情形。若若若若 ，且，且，且，且X0X0，均有，均有，均有，均有 0 0，则称，则称，则称，则称QQ是是是是负定负定负定负定负定负定的。的。的。的。定义：设定义：设Q为为nn对称矩阵对称矩阵其中 Q=b=Q为对称矩阵其向量矩阵表示形式是：其向量矩阵表示形式是：二次函数的一般形式为：二次函数的一般形式为：第23页，本讲稿共47页解：对称矩阵解：对称矩阵Q的三个主子

14、式依次为：的三个主子式依次为：例：判定矩阵Q=是否正定一个一个一个一个nnnn对称矩阵对称矩阵对称矩阵对称矩阵QQ是正定矩阵的充要条件是矩阵是正定矩阵的充要条件是矩阵是正定矩阵的充要条件是矩阵是正定矩阵的充要条件是矩阵QQ的各阶主子式都是的各阶主子式都是的各阶主子式都是的各阶主子式都是正的。正的。正的。正的。一个一个一个一个nnnn对称矩阵对称矩阵对称矩阵对称矩阵QQ是负定矩阵的充要条件是矩阵是负定矩阵的充要条件是矩阵是负定矩阵的充要条件是矩阵是负定矩阵的充要条件是矩阵QQ的各阶主子式的值的各阶主子式的值的各阶主子式的值的各阶主子式的值负、正相间。负、正相间。负、正相间。负、正相间。因此知矩阵

15、因此知矩阵Q是正定的。是正定的。第24页，本讲稿共47页定理：若二次函数 中Q正定，则它的等值面是同心椭球面族，且中心为证明：作变换 ，代入二次函数式中：根据解析几何知识，Q为正定矩阵的二次型 的等值面是以坐标原点 为中心的同心椭球面族。由于上式中的 是常数，所以 的等值面也是以 =0为中心的同心椭球面族，回到原坐标系中去，原二次函数就是以 为中心的同心椭球面族。第25页，本讲稿共47页 前面已说过，一般目标函数的等值面在极小点附近近似地呈现为前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次目标函数有效的求极小点的算法，当用椭球面族。由此可见对于二次目标函数有

16、效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。因此在最优化理论于一般目标函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于中判定一个算法好坏的标准之一，是把该算法用于Q为正定的二次目为正定的二次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。特别地若算法对于特别地若算法对于Q为正定的二次目标函数能在有限步内找出为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。极小点来，就称此算法为二次收敛算法，或具有二次收敛性。

17、另外，这族椭球面的中心 恰是二次目标函数的唯一极小点。例：把二次函数 化为矩阵向量形式并检验Q是否正定，如正定，试用公式 求这个函数的极小点。第26页，本讲稿共47页极小点是 =解：展开解：展开=与题中函数比较各项系数为：Q=b=由前例知由前例知Q正定正定第27页，本讲稿共47页一、多元函数的泰勒展开2-4 2-4 无约束优化问题的极值条件无约束优化问题的极值条件 二二元函数元函数：二二元函数：在点元函数：在点X Xk k处处第28页，本讲稿共47页多元函数泰勒展开多元函数泰勒展开海色矩阵海色矩阵（Hessian）第29页，本讲稿共47页对二次函数：对二次函数：为二次函数的为二次函数的海色（海

18、色（海色（海色（HessianHessian）矩阵，常量矩阵。）矩阵，常量矩阵。）矩阵，常量矩阵。）矩阵，常量矩阵。二次函数的梯度为：第30页，本讲稿共47页例：求目标函数f（X）=的梯度和Hesse矩阵。解：因为解：因为 则则又因为：又因为：故故Hesse阵为：阵为：第31页，本讲稿共47页例题例题:l用泰勒展开将函数在点简化成线性函数与二次函数。解：函数在点的函数值、梯度和二阶导数矩阵：第32页，本讲稿共47页l简化的线性函数简化的线性函数l简化的二次函数简化的二次函数第33页，本讲稿共47页二、无约束优化问题的极值条件 1.F(x)在 处取得极值，其必要条件是:即在极值点处函数的梯度为即

19、在极值点处函数的梯度为n维零向量。维零向量。第34页，本讲稿共47页l例：在 处梯度为l但 只是双曲抛物面的鞍点，而不是极小点。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。则称则称 为为f的的驻点驻点驻点驻点。定义：设 是D的内点，若第35页，本讲稿共47页l根据函数在 点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。为了判断从上述必要条件求得的 是否是极值点，需建立极值的充分条件。第36页，本讲稿共47页2 2.处取得极值充分条件l海色（海色

20、（Hessian）矩阵）矩阵 正定正定正定正定，即各阶主，即各阶主子式均大于零，则子式均大于零，则X*为为极小点极小点极小点极小点。l海色（海色（Hessian）矩阵）矩阵 负定负定负定负定，即各阶主，即各阶主子式负、正相间，则子式负、正相间，则X*为为极大点极大点极大点极大点。第37页，本讲稿共47页2-5 2-5 有约束优化问题的极值条件有约束优化问题的极值条件 l 不等式约束的多元函数极值的必要条件是著名不等式约束的多元函数极值的必要条件是著名的库恩的库恩-塔克（塔克（Kuhn-Tucker）条件，它是非线性）条件，它是非线性优化问题的重要理论优化问题的重要理论l（1）库恩）库恩塔克条件

21、塔克条件(K-T条件）条件）l对于多元函数不等式的约束优化问题：对于多元函数不等式的约束优化问题：l 第38页，本讲稿共47页K-TK-T条件条件条件条件l库恩库恩塔克条件表明：如点塔克条件表明：如点 是函数是函数 的极值的极值点，要么点，要么 （此时（此时 ）l要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时 ）。第39页，本讲稿共47页Ox1x2极值点处于等值线的中心极值点处于两个约束曲线的交点上xg1(x)0g2(x)0g3(x)0Ox1x2xg1(x)0g2(x)0起作用约束：第40页，本讲稿共47页库恩库恩塔克条件的几何意义是塔克条件的几何意义是:在约束极小值点在约束极小值

22、点 处，处，函数函数 的负梯度一定能表示成所有起使用约束在该点的负梯度一定能表示成所有起使用约束在该点梯度（法向量）的非负线性组合。梯度（法向量）的非负线性组合。x1x2Og2(x)=0g1(x)=0F(x)=Cg2(xk)g1(xk)F F(x xk k)xk可行域点xk处的切平面x1x2Og2(x)=0g1(x)=0F(x)=Cg2(xk)g1(xk)F F(x xk k)xk可行域点xk处的切平面(a)(b)第41页，本讲稿共47页同时具有等式和不等式约束的优化问题同时具有等式和不等式约束的优化问题:lK-T条件：条件：第42页，本讲稿共47页 K-TK-T条件条件是多元函数取得约束极值

23、的是多元函数取得约束极值的必要条必要条件件,以用来作为约束极值的判断条件，又可以以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。来直接求解较简单的约束优化问题。对于目标函数和约束函数都是凸函数的情对于目标函数和约束函数都是凸函数的情况，况，符合符合K-TK-T条件的点一定是全局最优点。条件的点一定是全局最优点。条件的点一定是全局最优点。条件的点一定是全局最优点。这这种情况种情况K-TK-T条件即为多元函数取得约束极值的条件即为多元函数取得约束极值的充分必要条件。充分必要条件。第43页，本讲稿共47页 K-TK-T条件是多元函数取得约束极值的必要条件条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。求解较简单的约束优化问题。例库恩例库恩塔克（塔克（K-TK-T）条件应用举例）条件应用举例 ls.tl判断判断1 0T是否为约束最优点。是否为约束最优点。第44页，本讲稿共47页(1)当前点 为可行点，因满足约束条件(3)各函数的梯度：各函数的梯度：（2）在 起作用约束为g1和g2,因 第45页，本讲稿共47页（4）求拉格朗日乘子）求拉格朗日乘子l由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足K-T条件。第46页，本讲稿共47页ls.t第47页，本讲稿共47页