第2章优化方法的数学基础精选文档.ppt

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

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

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

3、是不同的。因此，梯度是函数的一种率是不同的。因此，梯度是函数的一种局部性质局部性质。l梯度梯度 模：模：本讲稿第八页，共四十七页梯度两个重要性质：梯度两个重要性质：梯度两个重要性质：梯度两个重要性质：性质一性质一 函数在某点的梯度不为零，则必与过该点的函数在某点的梯度不为零，则必与过该点的等值面垂直；等值面垂直；性质二性质二 梯度方向是函数具有最大变化率的方向。梯度方向是函数具有最大变化率的方向。图图2-2 梯度方向与等值面的关系梯度方向与等值面的关系本讲稿第九页，共四十七页例题例题 2-1求函数求函数 在点在点3,2T 的的 梯度。梯度。在点在点x(1)=3,2T处的梯度为：处的梯度为：l解

4、：解：本讲稿第十页，共四十七页例例2-2：试求目标函数：试求目标函数 在点在点 处的处的最速下降方向，并求沿这个方向移动一个单位长度后新点的目标最速下降方向，并求沿这个方向移动一个单位长度后新点的目标函数值。函数值。则函数在则函数在 处的最速下降方向是处的最速下降方向是解：解：由于由于新点是新点是这个方向上的单位向量是：这个方向上的单位向量是：本讲稿第十一页，共四十七页几个常用的梯度公式：几个常用的梯度公式：本讲稿第十二页，共四十七页 当当极极值值点点X X*能能使使f f（X X*）在在整整个个可可行行域域中中为为最最小小值值时时，即即在在整整个个可可行行域域中中对对任任一一X X都都有有f

5、 f（X X）f f（X X*）时时，则则X X*就就是是最最优优点点，且且称称为为全全全全域域域域最最最最优优优优点点点点或或或或整整整整体体体体最最最最优优优优点点点点。若若f f（X X*）为为局局部部可可行行域域中中的的极极小小值值而而不不是是整整个个可可行行域域中中的的最最小小值值时时，则则称称X X*为为局局局局部部部部最最最最优优优优点点点点或或或或相相相相对对对对最最最最优优优优点点点点。最最优优化化设设计计的的目目标标是是全全域域最最优优点点。为为了了判判断断某某一一极极值值点点是是否否为为全全域域最最优优点点，研究一下函数的凸性很有必要。研究一下函数的凸性很有必要。函数的凸

6、性表现为单峰性。对于具有凸性特点的函数来说，其函数的凸性表现为单峰性。对于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。极值点只有一个，因而该点既是局部最优点亦为全域最优点。为了研究函数的凸性，现引入凸集的概念：为了研究函数的凸性，现引入凸集的概念：2-2 2-2 凸集、凸函数与凸规划凸集、凸函数与凸规划本讲稿第十三页，共四十七页一、凸集一、凸集一、凸集一、凸集 设设D D为为n n维维欧欧氏氏空空间间中中的的一一个个集集合合，若若其其中中任任意意两两点点X X(1)(1)、X X(2)(2)之之间间的的联联接接直直线线都都属属于于D D，则则称称这这种种集集

7、合合D D为为n n维维欧欧氏氏空空间间的的一一个个凸凸集。图集。图2-32-3（a a）是二维空间的一个凸集，而图）是二维空间的一个凸集，而图2-32-3（b b）不是凸集。）不是凸集。图图2-3 二维空间的凸集与非凸集二维空间的凸集与非凸集本讲稿第十四页，共四十七页X X（1 1）、X X（2 2）两点之间的联接直线，可用数学式表达为两点之间的联接直线，可用数学式表达为:式中式中 为由为由0 0到到1 1（0 10 1）间的任意实数。）间的任意实数。凸集的性质：凸集的性质：1 1）若）若D D为凸集，为凸集，是一个实数，则集合是一个实数，则集合 D D仍是凸集；仍是凸集；2 2）若）若D

8、D和和F F均为凸集，则其和（或并）仍是凸集；均为凸集，则其和（或并）仍是凸集；3 3）任何一组凸集的积（或交）仍是凸集。）任何一组凸集的积（或交）仍是凸集。本讲稿第十五页，共四十七页二、凸函数二、凸函数 具具有有凸凸性性（表表现现为为单单峰峰性性）或或只只有有唯唯一一的的局局部部最最优优值值亦亦即即全全域域最最优值优值的函数，称的函数，称为为凸凸凸凸函数函数函数函数或或或或单单单单峰函数峰函数峰函数峰函数。其数学定。其数学定义义是是：设设 f f（X X）为为定定义义在在 n n维维欧氏空欧氏空间间中的一个凸集中的一个凸集D D上的函数，如上的函数，如果果对对任何任何实实数数a a（0a10

9、a 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 X）=f=f1 1（X X）十）十f f2 2（X X）亦必）亦必为该为该凸集上的一个凸函数。凸集上的一个凸函数。4 4）若若

10、f f（X X）为为定定义义在在凸凸集集D D上上且且具具有有连连续续一一阶阶导导数数的的函函数数，则则f f（X X）为为凸函数的充分必要条件凸函数的充分必要条件为为：对对任意两点任意两点X X（1 1），X X（2 2），不等式，不等式恒成立恒成立本讲稿第十八页，共四十七页三、凸规划三、凸规划三、凸规划三、凸规划 对于约束优化问题对于约束优化问题 式中若式中若F F（X X）、均均为为凸函数，凸函数，则称此问题为则称此问题为凸规划凸规划凸规划凸规划。本讲稿第十九页，共四十七页凸规划的一些性质：凸规划的一些性质：2 2）凸规划问题中的任何局部最优解都是全局最优解凸规划问题中的任何局部最优解都

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

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

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

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

15、子式的值负、正相间。因此知矩阵因此知矩阵Q是正定的。是正定的。本讲稿第二十四页，共四十七页定理：定理：若二次函数若二次函数 中中Q正定，则它的等值正定，则它的等值面是同心椭球面族，且中心为面是同心椭球面族，且中心为证明：作变换证明：作变换 ，代入二次函数式中：，代入二次函数式中：根据解析几何知识，根据解析几何知识，Q为正定矩阵的二次型为正定矩阵的二次型 的的等值面是以坐标原点等值面是以坐标原点 为中心的同心椭球面族。为中心的同心椭球面族。由于上式中的由于上式中的 是常数，所以是常数，所以 的等值面的等值面也是以也是以 =0为中心的同心椭球面族，回到原坐标系中为中心的同心椭球面族，回到原坐标系中

16、去，原二次函数就是以去，原二次函数就是以 为中心的同心椭球面族。为中心的同心椭球面族。本讲稿第二十五页，共四十七页 前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面前面已说过，一般目标函数的等值面在极小点附近近似地呈现为椭球面族。由此可见对于二次目标函数有效的求极小点的算法，当用于一般目标族。由此可见对于二次目标函数有效的求极小点的算法，当用于一般目标函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法函数时，至少在极小点附近同样有效。因此在最优化理论中判定一个算法好坏的标准之一，是把该算法用于好坏的标准之一，是把该算法用于Q为正定的二次目标函数，如能迅速找为正定的二

17、次目标函数，如能迅速找到极小点，就是好算法；否则就不是太好的算法。到极小点，就是好算法；否则就不是太好的算法。特别地若算法对于特别地若算法对于Q为正定的二次目标函数能在有限步内找出极小为正定的二次目标函数能在有限步内找出极小点来，就称此算法为二次收敛算法，或具有二次收敛性。点来，就称此算法为二次收敛算法，或具有二次收敛性。另外，这族椭球面的中心另外，这族椭球面的中心 恰是二次目标函数的唯一极小点。恰是二次目标函数的唯一极小点。例：把二次函数例：把二次函数 化为矩化为矩阵向量形式并检验阵向量形式并检验Q是否正定，如正定，试用公式是否正定，如正定，试用公式 求这个函数的极小点。求这个函数的极小点。

18、本讲稿第二十六页，共四十七页极小点是极小点是 =解：展开解：展开=与题中函数比较各项系数为：与题中函数比较各项系数为：Q=b=由前例知由前例知Q正定正定本讲稿第二十七页，共四十七页一、多元函数的泰勒展开2-4 2-4 无约束优化问题的极值条件无约束优化问题的极值条件 二二元函数元函数：二二元函数：在点元函数：在点X Xk k处处本讲稿第二十八页，共四十七页多元函数泰勒展开海色矩阵海色矩阵（Hessian）本讲稿第二十九页，共四十七页对二次函数：对二次函数：为二次函数的为二次函数的海色（海色（Hessian）矩阵，常量矩阵。）矩阵，常量矩阵。二次函数的梯度为：二次函数的梯度为：本讲稿第三十页，共

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

20、在极值点处函数的梯度为n维零向量。维零向量。本讲稿第三十四页，共四十七页l例：例：在在 处梯度为处梯度为l但但 只是双曲抛物面的鞍点，而不是极小点。只是双曲抛物面的鞍点，而不是极小点。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。则称则称 为为f的的驻点驻点驻点驻点。定义：设定义：设 是是D的内点，若的内点，若本讲稿第三十五页，共四十七页l根据函数在根据函数在 点处的泰勒展开式，考虑上述极点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。值必要条件

21、，可得相应的充分条件。为了判断从上述必要条件求得的为了判断从上述必要条件求得的 是否是极值是否是极值点，需建立极值的充分条件。点，需建立极值的充分条件。本讲稿第三十六页，共四十七页2.处取得极值充分条件l海色（海色（Hessian）矩阵）矩阵 正定正定，即各阶主，即各阶主子式均大于零，则子式均大于零，则X*为为极小点极小点。l海色（海色（Hessian）矩阵）矩阵 负定负定，即各阶主，即各阶主子式负、正相间，则子式负、正相间，则X*为为极大点极大点。本讲稿第三十七页，共四十七页2-5 2-5 有约束优化问题的极值条件有约束优化问题的极值条件 l 不等式约束的多元函数极值的必要条件是著名不等式约

22、束的多元函数极值的必要条件是著名的库恩的库恩-塔克（塔克（Kuhn-Tucker）条件，它是非线性）条件，它是非线性优化问题的重要理论优化问题的重要理论l（1）库恩）库恩塔克条件塔克条件(K-T条件）条件）l对于多元函数不等式的约束优化问题：对于多元函数不等式的约束优化问题：l 本讲稿第三十八页，共四十七页K-TK-T条件条件l库恩库恩塔克条件表明：如点塔克条件表明：如点 是函数是函数 的极值的极值点，要么点，要么 （此时（此时 ）l要么目标函数的负梯度等于起作用约束梯度的非负要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时线性组合（此时 ）。）。本讲稿第三十九页，共四十七页Ox1x

23、2极值点处于等值线的中心极值点处于两个约束曲线的交点上xg1(x)0g2(x)0g3(x)0Ox1x2xg1(x)0g2(x)0起作用约束：本讲稿第四十页，共四十七页库恩库恩塔克条件的几何意义是塔克条件的几何意义是:在约束极小值点在约束极小值点 处，处，函数函数 的负梯度一定能表示成所有起使用约束在该点的负梯度一定能表示成所有起使用约束在该点梯度（法向量）的非负线性组合。梯度（法向量）的非负线性组合。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)

24、F F(x xk k)xk可行域点xk处的切平面(a)(b)本讲稿第四十一页，共四十七页同时具有等式和不等式约束的优化问题同时具有等式和不等式约束的优化问题:lK-T条件：条件：本讲稿第四十二页，共四十七页 K-TK-T条件条件是多元函数取得约束极值的是多元函数取得约束极值的必要必要条件条件,以用来作为约束极值的判断条件，又可以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。以来直接求解较简单的约束优化问题。对于目标函数和约束函数都是凸函数的情对于目标函数和约束函数都是凸函数的情况，况，符合符合K-TK-T条件的点一定是全局最优点。条件的点一定是全局最优点。这这种情况种情况K

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