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

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

2、)在x0点处的梯度。,梯度的模：,设,梯度方向和s方向重合时，方向导数值最大。,梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值 。,图2-4 梯度方向与等值线的关系,设：,则有,为单位向量。,多元函数的梯度,函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。,由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。,梯度 模：,梯度两个重要性质： 性质一 函数在某点的梯度不为零，则必与过该点的等值面垂直； 性质二 梯度方向是函数具有最大变化率的方向。,图2-5 梯度方向与等值面的关系,例2-1 求二元函数 在点 沿

3、和 的方向导数。,解：,因此，,同理：,例 2-2,求函数 在点x(1)=3,2T 的 梯度。,在点x(1)=3,2T处的梯度为：,解：,例2-3：试求目标函数 在点 处的最速下降方向。,则函数在 处的最速下降方向是,解： 由于,当极值点X*能使f（X*）在整个可行域中为最小值时，即在整个可行域中对任一X都有f（X）f（X*）时，则X*就是最优点，且称为全域最优点或整体最优点。若f（X*）为局部可行域中的极小值而不是整个可行域中的最小值时，则称X*为局部最优点或相对最优点。最优化设计的目标是全域最优点。为了判断某一极值点是否为全域最优点，研究一下函数的凸性很有必要。 函数的凸性表现为单峰性。对

4、于具有凸性特点的函数来说，其极值点只有一个，因而该点既是局部最优点亦为全域最优点。,为了研究函数的凸性，现引入凸集的概念：,2-2 凸集、凸函数与凸规划,一、凸集,设D为n维欧氏空间中的一个集合，若其中任意两点X(1)、X(2)之间的联接直线都属于D，则称这种集合D为n维欧氏空间的一个凸集。图2-6（a）是二维空间的一个凸集，而图2-6（b）不是凸集。,图2-6二维空间的凸集与非凸集,X（1）、X（2）两点之间的联接直线，可用数学式表达为:,式中 为由0到1（0 1）间的任意实数。,凸集的性质：,1）若D为凸集， 是一个实数，则集合 D仍是凸集；,2）若D和F均为凸集，则其和（或并）仍是凸集；

5、,3）任何一组凸集的积（或交）仍是凸集。,二、凸函数,具有凸性（表现为单峰性）或只有唯一的局部最优值亦即全域最优值的函数，称为凸函数或单峰函数。其数学定义是：,设 f（X）为定义在 n维欧氏空间中的一个凸集D上的函数，如果对任何实数（ 0 1 ）以及对D中任意两点X(1)、X(2)恒有:,则f（X）为D上的凸函数，若不满足上式，则为凹函数。,凸函数的几何意义如图2-7所示：,图2-7 一元凸函数的几何意义,在凸函数曲线上取任意两点（对应于X轴上的坐标X(1)、X（2）联成一直线线段，则该线段上任一点（对应于X轴上的X(k)点）的纵坐标Y值必大于或等于该点（X(k)）处的原函数值f(X(k)。,

6、凸函数的一些性质：,1）若 f（X）为定义在凸集D上的一个凸函数，且 a是一个正数（a 0），则 af（X）也必是定义在凸集D上的凸函数；,3）若f1(X），f2(X)为定义在凸集D上的两个凸函数，和为两个任意正数，则函数 afl（X）f2(X)仍为D上的凸函数。,2）定义在凸集D上的两个凸函数f1(X），f2(X)，其和 f（X）=f1（X）十f2（X）亦必为该凸集上的一个凸函数。,4）若f（X）为定义在凸集D上且具有连续一阶导数的函数，则f（X）为凸函数的充分必要条件为： 对任意两点X（1），X（2），不等式,恒成立,三、凸规划,对于约束优化问题,式中若F（X）、 均为凸函数，则称此问题为

7、凸规划。,凸规划的一些性质：,2）凸规划问题中的任何局部最优解都是全局最优解；,1）可行域 为凸集；,3）若F（X）可微，则X*为凸规划问题的最优解的充分必要条件为： 对任意 ，对满足,不论是无约束或有约束的优化问题，在实际应用中，要证明一个优化问题是否为凸规划，一般比较困难，有时甚至比求解优化问题本身还要麻烦。尤其对一些工程问题，由于其数学模型的性态都比较复杂，更难实现。因此，在优化设计的求解中，就不必花精力进行求证，而通常是从几个初始点出发，找出几个局部最优解，从中选择目标函数值最好的解。,注意：,一、 多元函数的泰勒展开,2-3 无约束优化问题的极值条件,二元函数：,多元函数泰勒展开,海

8、色矩阵 （Hessian）,二、无约束优化问题的极值条件,1.F(x)在 处取得极值，其必要条件是:,即在极值点处函数的梯度为n维零向量。,例： 在 处梯度为 但 只是双曲抛物面的鞍点，而不是极小点。,函数的梯度为零的条件仅为必要的，而不是充分的。,则称 为f的驻点。,定义：设 是D的内点，若,根据函数在 点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。,为了判断从上述必要条件求得的 是否是极值点，需建立极值的充分条件。,2. 处取得极值充分条件,各阶主子式均大于零:,则海色（Hessian）矩阵 是正定的,即海色（Hessian）矩阵 负定的，则X*为极大点。,各阶主子式负、正相

9、间:,则X*为极小点。,解：因为,则,故Hessian阵为：,例2-5 求函数 的极值。 解：根据极值的必要条件求驻点 得驻点 再根据极值的充分条件，判断此点是否为极值点。由于 其各阶主子式均大于零，H(x*)为正定矩阵，故X*=2,4T为极小点，极小值为F(X*)= -13。,2-4 有约束优化问题的极值条件,不等式约束的多元函数极值的必要条件是著名的库恩-塔克（Kuhn-Tucker）条件，它是非线性优化问题的重要理论 1 库恩塔克条件 (K-T条件） 对于多元函数不等式的约束优化问题：,K-T条件可阐述为： 若 是一个局部极小点，则该点的目标函数梯度 可表示成诸起作用约束面梯度 的线性组

10、合. 即,(2-17),在设计点处的起作用约束不等式约束面数；,非负值的乘子，也称为拉格朗日乘子。,式中,2 有约束问题最优点的几种情况:,有作用约束 目标函数是凸函数,可行域是凸集，则目标函数等值线与作用约束曲面的切点为最优点，而且是全局最优点。,1. 无作用约束 目标函数是凸函数，可行域是凸集，则最优点是内点。相当于无约束问题的最优点。,x (k) 为最优点x*的条件： 必要条件： 充分条件： Hessian矩阵 H(x(k) 是正定矩阵,X*,f (x), x*,库恩塔克条件的几何意义是: 在约束极小值点 x*处， 函数F (x) 的负梯度一定能表示成所有起作用约束在该 点梯度（法向量）

11、的非负线性组合。,K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。,对于目标函数和约束函数都是凸函数的情况， 符合K-T条件的点一定是全局最优点。这种情况K-T条件即为多元函数取得约束极值的充分必要条件。,K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。,例2-6 库恩塔克（K-T）条件应用举例,s.t,判断1 0T是否为约束最优点。,(1)当前点 为可行点，因满足约束条件,(3) 各函数的梯度：,（2）在 起作用约束为g1和g2 , 因,（4）求拉格朗日乘子,由于拉格朗日乘子均为非负，说明 是一个局部最优点，因为它满足K-T条件。,s.t,例2-7 对于约束极值问题,s.t.,试运用K-T条件验证点,为约束极值点。,解：图例2-7给出了由g1(x)=0、 g2(x)=0、 g3(x)=0、及所确定的可行域，同时给出了的几条等值线。,可见起作用的约束函数是,和,1. 计算点 的各个约束函数值,例-7约束极值问题,2、求相关函数在 点的梯度 3、将梯度代入判别公式，求拉格朗日乘子,即,均为非负，满足K-T条件，因此,同时，由于,是凸函数，可行域是凸集，因此点,也是全域最优点。,为约束极值