第二章 优化方法的数学基础.ppt

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

1、第二章 优化方法的数学基础2-1 2-1 方向导数与梯度方向导数与梯度2-2 2-2 凸集、凸函数与凸规划凸集、凸函数与凸规划2-3 2-3 无约束优化问题的极值条件无约束优化问题的极值条件 2-4 2-4 有约束优化问题的极值条件有约束优化问题的极值条件 2-1 方向导数与梯度方向导数与梯度一、函数的方向导数一、函数的方向导数一个二元函数一个二元函数F(x1,x2)在在X0点处的偏导数定义为点处的偏导数定义为:分别是函数在点分别是函数在点X0处沿坐标轴方向的变化率处沿坐标轴方向的变化率.函数 在点 处沿某一方向的变化率如图2-1 称它为函数沿此方向的方向导数（2-1）和 也可看成是函数分别沿

2、坐标轴方向的方向导数推导方向导数与偏导数之间的数量关系：偏导数是方向导数的特例（2-2）n元函数在点元函数在点x0处沿处沿s s方向的方向导数方向的方向导数 Ox2x1x10 x20 x0 x1 x2 sxS 1 2图图2-3二、梯度二元函数的梯度:为函数F(x1，x2)在x0点处的梯度。梯度的模：设梯度方向和s方向重合时，方向导数值最大。梯度方向是函数值变化最快的方向，梯度方向是函数值变化最快的方向，梯度方向是函数值变化最快的方向，梯度方向是函数值变化最快的方向，而梯度而梯度的模就是函数变化率的最大值的模就是函数变化率的最大值。图图2-4 梯度方向与等值线的关系梯度方向与等值线的关系设：设：

3、则有则有 为单位向量。为单位向量。多元函数的梯度多元函数的梯度函数的梯度方向与函数等值面相垂直，也就是和等函数的梯度方向与函数等值面相垂直，也就是和等值面上过值面上过x0的一切曲线相垂直。的一切曲线相垂直。由于梯度的模因点而异，即函数在不同点处的最大由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种变化率是不同的。因此，梯度是函数的一种局部性局部性质质。l梯度梯度 模：模：梯度两个重要性质：梯度两个重要性质：梯度两个重要性质：梯度两个重要性质：性质一性质一性质一性质一 函数在某点的梯度不为零，则必与过该点函数在某点的梯度不为零，则必与过该点函数在某点的梯度不为零

4、，则必与过该点函数在某点的梯度不为零，则必与过该点的等值面垂直；的等值面垂直；的等值面垂直；的等值面垂直；性质二性质二性质二性质二 梯度方向是函数具有最大变化率的方向。梯度方向是函数具有最大变化率的方向。梯度方向是函数具有最大变化率的方向。梯度方向是函数具有最大变化率的方向。图图2-5 梯度方向与等值面的关系梯度方向与等值面的关系例例2-1 求二元函数 在点 沿 和 的方向导数。解解：因此，同理：例例 2-2求函数求函数 在点在点x(1)=3,2T 的的 梯度。梯度。在点在点x(1)=3,2T处的梯度为：处的梯度为：l解：解：例例2-3：试求目标函数：试求目标函数 在点在点 处的处的最速下降方

5、向。最速下降方向。则函数在则函数在 处的最速下降方向是处的最速下降方向是解：解：由于由于 当当极极值值点点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 凸集、凸函数与凸规划凸集、凸函数与凸规划一、凸集

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

8、 1（0 10 1）间的任意实数。）间的任意实数。凸集的性质：凸集的性质：1 1）若）若D D为凸集，为凸集，是一个实数，则集合是一个实数，则集合 D D仍是凸集；仍是凸集；2 2）若）若D D和和F F均为凸集，则其和（或并）仍是凸集；均为凸集，则其和（或并）仍是凸集；3 3）任何一组凸集的积（或交）仍是凸集。）任何一组凸集的积（或交）仍是凸集。二、凸函数二、凸函数二、凸函数二、凸函数 具具有有凸凸性性（表表现现为为单单峰峰性性）或或只只有有唯唯一一的的局局部部最最优优值值亦亦即即全全域域最最优优值值的的函函数数，称称为为凸凸凸凸函函函函数数数数或或或或单单单单峰峰峰峰函函函函数数数数。其其

9、数数学学定定义义是是：设设 f f（X X）为为定定义义在在 n n维维欧氏空欧氏空间间中的一个凸集中的一个凸集D D上的函数，上的函数，如果如果对对任何任何实实数数（0 1）以及）以及对对D D中任意两点中任意两点X X(1)(1)、X X(2)2)恒有恒有:则则f f（X X）为为D D上的上的凸函数凸函数，若不满足上式，则为若不满足上式，则为凹函数凹函数。凸函数凸函数的几何意义如图的几何意义如图2-72-7所示：所示：图图2-7 一元凸函数的几何意义一元凸函数的几何意义 在凸函数曲线上取任意两点（对应于在凸函数曲线上取任意两点（对应于X轴上的坐标轴上的坐标X(1)、X（2）联成一直线线段

10、，则该线段上任一点（对应于）联成一直线线段，则该线段上任一点（对应于X轴上轴上的的X(k)点）的纵坐标点）的纵坐标Y值必大于或等于该点（值必大于或等于该点（X(k)）处的原函）处的原函数值数值f(X(k)。凸函数的一些性质：凸函数的一些性质：1 1）若若 f（X）为为定定义义在在凸凸集集D D上上的的一一个个凸凸函函数数，且且 a是是一一个个正数（正数（a 0），则），则 af（X）也必是定义在凸集）也必是定义在凸集D D上的凸函数；上的凸函数；3 3）若若f f1 1(X X），f f2 2(X X)为为定定义义在在凸凸集集D D上上的的两两个个凸凸函函数数，和和为为两个任意正数，两个任意正

11、数，则则函数函数 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）若若f f（X X）为为定定义义在在凸凸集集D D上上且且具具有有连连续续一一阶阶导导数数的的函函数数，则则f f（X X）为为凸函数的充分必要条件凸函数的充分必要条件为为：对对任意两点任意两点X X（1 1），X X（2 2），不等式，不等

12、式恒成立恒成立三、凸规划三、凸规划三、凸规划三、凸规划 对于约束优化问题对于约束优化问题 式中若式中若F F（X X）、均均为为凸函数，凸函数，则称此问题为则称此问题为凸规划凸规划凸规划凸规划。凸规划的一些性质：凸规划的一些性质：2 2）凸规划问题中的任何局部最优解都是全局最优解凸规划问题中的任何局部最优解都是全局最优解；1 1）可行域）可行域 为凸集；为凸集；3 3）若若F F（X X）可可微微，则则X X*为为凸凸规规划划问问题题的的最最优优解解的的充充分分必必要要条件条件为为：对对任意任意 ，对满足对满足 不论是无约束或有约束的优化问题，在实际应用中，要证不论是无约束或有约束的优化问题，

13、在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，就不必花精力进行求证，而通常是从几个初始点出发，找中，就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。出几个局部最优解，从中选择目标函数值最好的解。注意：注意：注意：注意：一、多元函数的泰勒展开2-3 2-

14、3 无约束优化问题的极值条件无约束优化问题的极值条件 二元函数：二元函数：多元函数泰勒展开海色矩阵海色矩阵（Hessian）二、无约束优化问题的极值条件 1.F(x)在在 处取得极值，其必要条件是处取得极值，其必要条件是:即在极值点处函数的梯度为即在极值点处函数的梯度为n维零向量。维零向量。l例：例：在在 处梯度为处梯度为l但但 只是双曲抛物面的鞍点，而不是极小点。只是双曲抛物面的鞍点，而不是极小点。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。函数的梯度为零的条件仅为必要的，而不是充分的。则称则称 为

15、为f的的驻点驻点驻点驻点。定义：设定义：设 是是D的内点，若的内点，若l根据函数在根据函数在 点处的泰勒展开式，考虑上述极点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。值必要条件，可得相应的充分条件。为了判断从上述必要条件求得的为了判断从上述必要条件求得的 是否是极值是否是极值点，需建立极值的充分条件。点，需建立极值的充分条件。2.处取得极值充分条件，.，各阶主子式均大于零各阶主子式均大于零:则海色（则海色（Hessian）矩阵）矩阵 是是正定正定的的,即海色（即海色（Hessian）矩阵）矩阵 负定的负定的负定的负定的，则，则X*为为极大点极大点极大点极大点。各阶主子式负、正相

16、间各阶主子式负、正相间:则则X*为为极小点极小点极小点极小点。例例2-4：求目标函数：求目标函数f（X）=的梯度和的梯度和HessianHessian矩阵。矩阵。解：因为解：因为 则则故故HessianHessian阵为：阵为：例例2-5 求函数 的极值。解解：根据极值的必要条件求驻点得驻点 再根据极值的充分条件，判断此点是否为极值点。由于其各阶主子式均大于零，H(x*)为正定矩阵，故X*=2,4T为极小点，极小值为F(X*)=-13。2-4 2-4 有约束优化问题的极值条件有约束优化问题的极值条件 l 不等式约束的多元函数极值的必要条件是著名的库不等式约束的多元函数极值的必要条件是著名的库恩

17、恩-塔克（塔克（Kuhn-Tucker）条件，它是非线性优化问）条件，它是非线性优化问题的重要理论题的重要理论1 库恩库恩塔克条件塔克条件(K-T条件）条件）l对于多元函数不等式的约束优化问题：对于多元函数不等式的约束优化问题：l lK-T条件可阐述为：l若 是一个局部极小点，则该点的目标函数梯度 可表示成诸起作用约束面梯度 的线性组合.l即 (2-17)在设计点处的起作用约束不等式约束面数；非负值的乘子，也称为拉格朗日乘子。式中Ox1x2极值点处于等值线的中心极值点处于两个约束曲线的交点上xg1(x)0g2(x)0g3(x)0Ox1x2xg1(x)0g2(x)02 2 有约束问题最优点的几种

18、情况有约束问题最优点的几种情况:2.2.有有作用约束作用约束 目标函数是凸函数目标函数是凸函数,可行域是凸可行域是凸集，则目标函数等值线与集，则目标函数等值线与作用约作用约束束曲面的切点为最优点，而且是曲面的切点为最优点，而且是全局最优点。全局最优点。1.1.无作用约束无作用约束 目标函数是凸函数，可行域是凸集，目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约束问则最优点是内点。相当于无约束问题的最优点。题的最优点。x x(k)(k)为最优点为最优点x*x*的条件：的条件：必要条件：必要条件：充分条件：充分条件：Hessian矩阵矩阵 H(xH(x(k(k)是正定矩阵是正定矩阵X*f

19、(x)x*库恩库恩塔克条件的几何意义是塔克条件的几何意义是:在约束极小值点在约束极小值点 x*处，处，函数函数F(x)的负梯度一定能表示成所有起作用约束在该的负梯度一定能表示成所有起作用约束在该点梯度（法向量）的非负线性组合。点梯度（法向量）的非负线性组合。K-TK-T条件条件是多元函数取得约束极值的是多元函数取得约束极值的必必要条件要条件,以用来作为约束极值的判断条件，以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。又可以来直接求解较简单的约束优化问题。对于目标函数和约束函数都是凸函数对于目标函数和约束函数都是凸函数的情况，的情况，符合符合K-TK-T条件的点一定是全局最

20、条件的点一定是全局最优点。优点。这种情况这种情况K-TK-T条件即为多元函数取条件即为多元函数取得约束极值的充分必要条件。得约束极值的充分必要条件。K-T K-T条件是多元函数取得约束极值的必要条件条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。求解较简单的约束优化问题。例例2-6 2-6 库恩库恩塔克（塔克（K-TK-T）条件应用举例）条件应用举例 ls.tl判断判断1 0T是否为约束最优点。是否为约束最优点。(1)当前点当前点 为可行点，因满足约束条件为可行点，因满足约束条件(3)各函数的梯

21、度：各函数的梯度：（2）在）在 起作用约束为起作用约束为g1和和g2,因因 （4）求拉格朗日乘子）求拉格朗日乘子l由于拉格朗日乘子均为非负，说明由于拉格朗日乘子均为非负，说明是一个局部最优点，因为它满足是一个局部最优点，因为它满足K-T条件。条件。ls.t例例2-7 对于约束极值问题s.t.试运用K-T条件验证点为约束极值点。解解：图例例2-7给出了由g1(x)=0、g2(x)=0、g3(x)=0、及所确定的可行域，同时给出了的几条等值线。可见起作用的约束函数是和1.计算点 的各个约束函数值例例-7约束极值问题约束极值问题2、求相关函数在 点的梯度3、将梯度代入判别公式，求拉格朗日乘子 即 均

22、为非负，满足K-T条件，因此同时，由于是凸函数，可行域是凸集，因此点也是全域最优点。为约束极值点。和设约束优化问题设约束优化问题 (课堂练习课堂练习)它的当前迭代点为它的当前迭代点为=1,0T，试用，试用KT条件条件。判断它是否为约束最优点判断它是否为约束最优点解：解：点的诸约束函数值点的诸约束函数值 点是可行点。点是可行点。点的起作用约束是：点的起作用约束是：1 计算计算2求求3求求点的诸梯度点的诸梯度 4求拉格朗日乘子求拉格朗日乘子 写成线性方程组写成线性方程组 解得：解得：乘子均为非负，乘子均为非负，=1,0T满足约束最优解的一阶必要条件。满足约束最优解的一阶必要条件。由于由于F(X)是凸函数，可行域为凸集，所以点是凸函数，可行域为凸集，所以点也是该问题的全局最优解。也是该问题的全局最优解。