西南科技大学网络教育系列课程 5. 优 化 设 计 5.2 优化方法的数学基础.

Presentation on theme: "西南科技大学网络教育系列课程 5. 优 化 设 计 5.2 优化方法的数学基础."— Presentation transcript:

1 西南科技大学网络教育系列课程 5. 优 化 设 计 5.2 优化方法的数学基础

2 5.2.1函数的方向导数和梯度 1、函数的方向导数 实例：一块长方形的金属板，四个顶点的坐标是(1,1)，(5,1)，(1,3)，(5,3)。在坐标原点处有一个火焰，它使金属板受热。假定板上任意一点处的温度与该点到原点的距离成反比。在(3,2)处有一个蚂蚁，问这只蚂蚁应沿什么方向爬行才能最快到达较凉快的地点？ 问题的实质：应沿由热变冷变化最剧烈的方向（即梯度方向）爬行． 西南科技大学网络教育系列课程

3 记为 1）方向导数的定义 讨论函数 在一点P沿某一方向的变化率问题． 。 引射线 内有定义，自点 的某一邻域 在点 设函数 l P U y
x ) ( , 函数的增量 与PP`两点间的距离 之比值，当P`沿着L趋于P时，如果此比的极限存在，则称这极限为函数 在点P沿方向L的方向导数。 记为 ) , ( ). p/ U P/ l y x P D + / 上的另一点且 为 并设 的转角 轴正向到射线 设 j （如图）

4 且 考虑 当 沿着 趋于 时， 是否存在？

5 - } , 1 { = e r ) ( y x f P 的方向导数。 沿方向 则称这极限为函数在点 在， 时，如果此比的极限存 趋于 沿着
当 之比值， 两点间的距离 与 函数的增量 定义 l P P/ y x  D + = 2 ) ( r 记为 } , 1 { = e r 依定义，函数 ) ( y x f 在点 P 沿着 轴正向 、 2 的方向导数分别为 ； 轴负向、 轴负向的方向导数是 - .

6 ) , ( y x f z = P j 2）方向导数的计算 定理 如果函数 在点 是可微分 的，那么函数在该点沿任意方向 存在，且有 其中
定理　如果函数 ) , ( y x f z = 在点 P 是可微分 的，那么函数在该点沿任意方向 L 的方向导数都 存在，且有 ， 其中 j 为 轴到方向 的转角。 证明 由于函数可微，则增量可表示为 两边同除以 得到

7 故有方向导数

8 ) , ( z y x f u = P L 推广可得三元函数方向导数的定义 对于三元函数 ，它在空间一点 沿着方向 的方向导数 ，可定义 为
其中

9 设方向 L 的方向角为 g b a , 同理：当函数在此点可微时，那末函数在该点 沿任意方向 L 的方向导数都存在，且有

10 推导出n元函数f(x)在点X( k)处沿任意给定方向S的方向导数 表达式为：
西南科技大学网络教育系列课程

11 函数在点X( k)的梯度是由函数在该点的各个一阶偏导数组成的向量。 2）梯度的表达式
2、 梯度 1）梯度的定义 函数在点X( k)的梯度是由函数在该点的各个一阶偏导数组成的向量。 2）梯度的表达式 西南科技大学网络教育系列课程

12 函数在某点的梯度是这样一个向量，它的 方向与取得最大方向导数的方向一致 而它的模为 方向导数的最大值。梯度的模为 结论 当 不为零时， x
, 而它的模为 方向导数的最大值。梯度的模为 结论 当 不为零时， x 轴到梯度的转角的正切为　

13 在几何上 表示一个曲面 曲面被平面 所截得 所得曲线在xoy面上投影如图 梯度为等高线上的法向量 等高线

14 根据矢量代数的概念，方向导数的表达式可写成：
3、方向导数和梯度的关系 根据矢量代数的概念，方向导数的表达式可写成： 西南科技大学网络教育系列课程

15 由上式表明：函数在某点沿方向S的方向导数等于该点的梯度在方向身上的投影。见下图。
西南科技大学网络教育系列课程

16 当方向S与点X( k)的梯度相垂直时，函数在该点沿S的方向导数等于零，即
从图中可以看出： 当方向S与点X( k)的梯度相垂直时，函数在该点沿S的方向导数等于零，即 西南科技大学网络教育系列课程 当方向S与梯度方向的夹角为锐角时有： 当方向S与梯度方向的夹角为钝角时有：

17 这说明，与梯度成锐角的方向是函数值上升的方向，而与梯度成钝角的方向则是函数值下降的方向。
西南科技大学网络教育系列课程 这说明，与梯度成锐角的方向是函数值上升的方向，而与梯度成钝角的方向则是函数值下降的方向。

18 (1)函数在一点的梯度是一个向量。梯度的方向是该点函数值上升得最快的方向，梯度的大小就是它的模长。
综上所述，函数的梯度具有以下性质 (1)函数在一点的梯度是一个向量。梯度的方向是该点函数值上升得最快的方向，梯度的大小就是它的模长。 (2)一点的梯度方向为过该点的等值线或等值面的切线或切平面相垂直的方向，或者说是该点等值线或等值面的法线方向。 (3)梯度是函数在一点邻域内局部性态的描述。在一点上升得快的方向，离开该领域后就不一定上升得快，甚至可能下降。 西南科技大学网络教育系列课程

19 例1 求函数f(X)＝(x1－2)2十(x2－1)2在点X(1)＝[3,2]T和X( 2)＝[2,2] T的梯度并作图表示。
解：根据定义，梯度为 西南科技大学网络教育系列课程 则

20 解：梯度的模为： 单位梯度的向量为： 西南科技大学网络教育系列课程

21 在设计平面x1ox2内标出点(2,2)和点(0,2)，并将此两点分别与原点相连得到向量[2,2]T和[0,2]T。将这两个向量各自平移至点X(1)和X(2)，所得新的向量就是点X(1)和X(2)的梯度。 西南科技大学网络教育系列课程 图5.11 例1的梯度

22 5.2.1 函数的方向导数和梯度 例题2 一般二元二次函数的矩阵式为 ，其中 西南科技大学网络教育系列课程 C为常数，求梯度 。

23 5.2.1 函数的方向导数和梯度 解：将二元二次函数的矩阵式展开 西南科技大学网络教育系列课程 其中 ，于是梯度为

24 5.2.1 函数的方向导数和梯度 即 同理，推广到n元二次函数，则一般n元二次函数梯度的矩阵表达式为 西南科技大学网络教育系列课程 式中

25 5.2.2 多元函数的泰勒展开 由高等数学知、一元函数f(x)着在点xk的邻域内n阶可导，则函数可在该点的邻域内作如下泰勒展开：
西南科技大学网络教育系列课程 多元函数f(x)在xk点也可以作泰勒(Taylor)展开,其展开式一般取三项,其形式与一次函数的形式的前三项是相似的.

26 5.2.2 多元函数的泰勒展开 写成矩阵形式： 式中 称为f(x)的海森(Hessian)矩阵，常用H(x)表示。
西南科技大学网络教育系列课程 式中 称为f(x)的海森(Hessian)矩阵，常用H(x)表示。

27 5.2.2 多元函数的泰勒展开 例3 一般二元二次函数 ，求H(X)。 西南科技大学网络教育系列课程 解：

28 5.2.2 多元函数的泰勒展开 西南科技大学网络教育系列课程

29 5.2.2 多元函数的泰勒展开 例4 用泰勒展开的方法将函数f(X)＝x13 - x23+3 x12+3 x22- 9x1在点X(1)=[1,1]T简化成线性函数和二次函数。 解： (1)求函数在点X(1)的函数值、梯度为： 西南科技大学网络教育系列课程

30 5.2.2 多元函数的泰勒展开 (2)求得二阶导数矩阵为： 而且 西南科技大学网络教育系列课程 代入线性泰勒展开式得简化的线性函数：

31 5.2.2 多元函数的泰勒展开 (3)得到泰勒展开式的二次项为： 西南科技大学网络教育系列课程 代入泰勒展开式得简化的二次函数：

32 5.2.3 二次函数 1、二次函数的表达式 2、正定与负定的判断 则矩阵H是正定的。 二次函数是最简单的非线性函数，可以写成以下向量形式：
一阶主子式 二阶主子式 ……… n阶主子式>0 则矩阵H是正定的。 西南科技大学网络教育系列课程

33 5.2.3 二次函数 则矩阵H是负定的。 2）如果矩阵H的各阶主子式正负相间，即 一阶主子式 二阶主子式 ……… n阶主子式<0
西南科技大学网络教育系列课程

34 5.2.3 二次函数 3、极值条件 1）多元函数在点X(k)取得极小值的条件是：函数在该点的梯度为零，二阶导数矩阵为正定。 即
西南科技大学网络教育系列课程

35 5.2.3 二次函数 例5：试求f(x1,x2)＝2x12-8x1+2x22-4x2+20的极值及极值点。 解：由极值点存在的必要条件
西南科技大学网络教育系列课程 得驻点X*=[2，1]T, 在X*点海森矩阵为：

36 5.2.3 二次函数 由于其各阶主子行列式为 可知在X*点海森矩阵正定的，∴X*为极小点，其极小值为： 西南科技大学网络教育系列课程

37 5.2.4 下降迭代算法 多变量、多约束的非线性优化问题，通常采用数值迭代求解，对于极小化问题，这种方法就是下降迭代算法。
1、下降迭代法的定义 按照某一迭代格式，从一个初始点X(0)出发逐步产生一个点列 X(0)、 X(1)、 X(2)、 …、X(k)、 X(k+1)、… 若该点列对应的目标函数值呈下降趋势 f(X(0)) >f(X(1)) > f(X(2)) …> f(X(k)) > f(X(k+1)) … 并且该点列对应的极限就是目标函数的极小点X*，则构成此点列的方法就是优化问题的一种数值解法，称为下降迭代算法。 西南科技大学网络教育系列课程

38 5.2.4 下降迭代算法 2、下降迭代算法的基本格式 下降迭代算法的基本格式如下： (1)下降迭代算法构成的基本步骤：
1）给定一个初始点X(0)和收敛精度ε 2）选取一个搜索方向S(k) 3）确定步长因子ak，按上式得到新的迭代点 4）收敛判断：若X(k+1)满足收敛精度，则以X(k+1)作为最优点，终止计算；否则，以X(k+1)作为新的起点，转2）进行下一轮迭代。 西南科技大学网络教育系列课程

39 5.2.4 下降迭代算法 (2)下降迭代算法的构成需要解决的三个基本问题 1）选择搜索方向。
不同的搜索方向，构成不同的下降迭代算法。在每一类下降迭代法中包含两个关键步骤：得到迭代点 后，如何选择搜索方向 ；在确定搜索方向后，如何进行一维搜索。（在下一节作详细说明） 2）确定步长因子。 （在下一节作详细说明） 一般通过一维搜索法取得最优步长因子。 3）给定收敛准则。 用以判断迭代点是否能够作为近似的最优点。 西南科技大学网络教育系列课程

40 5.2.4 下降迭代算法 3、算法的收敛性与收敛准则 1)算法的收敛性 当迭代算法产生的点列满足
时，称该点列收敛于极不点X* ，即称此下降迭代算法具有收敛性。 算法的收敛性和收敛速度的定义式： 西南科技大学网络教育系列课程

41 5.2.4 下降迭代算法 当β=1时，称算法具有线性收敛性，或者说算法具有线性收敛速度。 最差 当β=2时，称算法具有二次收敛性。
当1<β<2时，称算法具有超线性收敛性。 最差 最好 其次 2）算法的收敛准则 判断迭代点与精确解近似程度的方法称为收敛准则。 (1)点距准则：相邻两迭代点的距离来判断。 西南科技大学网络教育系列课程

42 5.2.4 下降迭代算法 (2)值差准则：相邻两迭代点的函数值之差来判断 西南科技大学网络教育系列课程 (3)梯度准则：梯度的模长判断