汽车优化设计 第二章：优化方法的数学基础 王琥 湖南大学 机械与运载工程学院

Presentation on theme: "汽车优化设计 第二章：优化方法的数学基础 王琥 湖南大学 机械与运载工程学院"— Presentation transcript:

1 汽车优化设计 第二章：优化方法的数学基础 王琥 wanghu@hnu.edu.cn 湖南大学 机械与运载工程学院
汽车车身先进设计制造国家重点实验室

2 主要内容 优化设计=极值问题 多变量、多约束非线性优化 高等数学极值理论是求解基础，但是不能直接求出最优解。
对多变量约束优化问题的求解方法所涉及的数学概念及有关理论进行补充和扩展。 方向导数与梯度；二次函数及正定矩阵；无约束优化问题的极值条件 ；等式约束优化问题的极值条件 ；不等式约束优化问题的极值条件；优化设计问题的基本解法

3 方向导数与梯度 方向导数 二元函数在点x0处沿某一方向s的方向导数 方向导数是偏导数概念的推广 方向导数与偏导数之间的数量关系是 O x2
1 2

4 方向导数与梯度 一个三元函数f(x1, x2,x3)在x0(x10, x20, x30) 点处沿s方向的方向导数为
n元函数在点x0处沿s方向的方向导数

5 梯度 二元函数的梯度 为函数F(x1，x2)在x0点处的梯度。

6 梯度 设 梯度的模： 设： 为单位向量。 则有

7 梯度 若上式为0，则说明方向导数是沿着等值线的切线向，而梯度是沿着与等值线切线相垂直的方向，且这时方向导数达到最大值，这说明梯度是函数值变化最快的方向，而梯度的模就是函数变化率的最大值 。 当方向s与梯度方向的夹角为锐角时，上式大于0，当方向s与梯度的夹角为钝角时，上式小于0，这说明与梯度成锐角的方向是函数值增加（上升）的方向，而与梯度成钝角的方向是函数值减小（下降）的方向。 梯度方向与等值线的关系

8 梯度 多元函数梯度 多元函数的方向导数表示为

9 梯度 梯度 模： 对于二元函数来说，函数的梯度方向与函数等值线面相垂直，也就是和等值面上过x0的一切曲线相垂直。
梯度 模： 对于二元函数来说，函数的梯度方向与函数等值线面相垂直，也就是和等值面上过x0的一切曲线相垂直。 由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。因此，梯度是函数的一种局部性质。

10 梯度 函数的梯度具有以下特征： 函数一点的梯度是由函数在该点上的所有一阶偏导数组成的向量。梯度的方向是该点函数值上升最快的方向，梯度的大小就是它的模。 函数在一点的梯度方向与函数过该点的等值线（面）的切线（平面）相垂直，或者说是该点等值线（面）的外法线方向。 梯度是函数在一点邻域内局部性态的描述。在邻域内上升得快的方向，离开邻域后就不一定上升得快，甚至可能下降。

11 梯度的计算实例 求函数 在点[3,2]T 的 梯度。 在点x(1)=[3,2]T处的梯度为： 解:

12 二次函数及正定矩阵 二次函数的一般形式为： 其中 均为常数。 其向量矩阵表示形式是： 其中 Q为对称矩阵
其中 均为常数。 其向量矩阵表示形式是： 其中 Q为对称矩阵 在代数学中将特殊的二次函数 称为二次型。对于二次函数，我们更关心的是Q为正定矩阵的情形。

13 二次函数及正定矩阵 定义：设Q为n×n对称矩阵 若 ，X≠0，均有 ，则称矩阵Q是正定的。 若 ，且 X≠0，均有 ，则称Q是负定的。
一个n×n对称矩阵Q是正定矩阵的充要条件是矩阵Q的各阶主子式都是正的。 一个n×n对称矩阵Q是负定矩阵的充要条件是矩阵Q的各阶主子式的值负、正相间。

14 算例 判定矩阵 是否正定 解：对称矩阵Q的三个主子式依次为： 因此知矩阵Q是正定的。

15 无约束优化问题的极值条件 多元函数的泰勒展开 二元函数： 二元函数：在点Xk处

16 无约束优化问题的极值条件 多元函数泰勒展开 海赛矩阵 （Hessian）

17 无约束优化问题的极值条件 对二次函数： Q 为二次函数的海赛（Hessian）矩阵，常量矩阵。 二次函数的梯度为：

18 算例 求目标函数 的梯度和Hessian矩阵。 解：因为 则 又因为： 故Hessian阵为：

19 算例 用泰勒展开将函数 在点 简化成线性函数与二次函数。 解：函数在点 的函数值、梯度和二阶导数矩阵：

20 算例 简化的线性函数 简化的二次函数

21 无约束优化问题的极值条件 1.F(x)在 处取得极值，其必要条件是: 即在极值点处函数的梯度为n维零向量。
函数的梯度为零的条件仅为必要的，而不是充分的。 例： 在 处梯度为 但 只是双曲抛物面的鞍点，而不是极小点。 则称 为 f 的驻点。 定义：设 是D的内点，若

22 Rastrigin function 为了判断从上述必要条件求得的 是否是极值点，需建立极值的充分条件。
为了判断从上述必要条件求得的 是否是极值点，需建立极值的充分条件。 根据函数在 点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。

23 Rastrigin function 处取得极值充分条件 Hessian矩阵 正定，即各阶主子式均大于零，则X*为极小点。

24 算例 求函数 的极值。 解：由极值的必要条件 由此知X1是函数的极小值点， X4是函数的极大值点，X2和X3均为非极值点。

25 等式约束优化问题的极值条件 求解等式约束优化问题为： min f(x) s.t. hk(x)=0 (k=1,2,…,m) 对这一问题，在数学上有两种处理方法： 消元法（降维法） 拉格朗日乘子法（升维法）

26 等式约束优化问题的极值条件 消元法 对n维函数的优化问题： min f(x1,x2,…,xn)
s.t. hk(x1,x2,…,xn)=0 (k=1,2,…,l) 由l个约束方程将n个变量中的前l个变量用其余n-l个变量表示，即有 将这些函数关系代入到目标函数中，从而得到只xl+1,xl+2,…,xl+n共有n-l个变量的函数（n-l维），这样就可以利用无约束优化问题的极值条件求解，此法称为消元法或降维法。

27 等式约束优化问题的极值条件 拉格朗日乘子法 对于具有l个等式约束的n维优化问题 minf(x1,x2,…,xn)
s.t. hk(x1,x2,…,xn)=0 (k=1,2,…,l) 把原目标函数f(x)改造成为如下形式的新的目标函数 式中的hk(x)就是原目标函数f(x)的等式约束条件，而待定系数k称为拉格朗日乘子。这种方法称为拉格朗日乘子法。 在极值点处，有 共有n+l个方程，足以解出这n+l个变量，此法也称为升维法。

28 算例 用拉格朗日乘子法计算在约束条件 h(x1,x2)=2x1+3x2-6=0的情况下，目标函数f(x1,x2)=4x12+5x22的极值点坐标。 解 改造的目标函数是 则 联立得极值点x*(1.071,1.286)

29 不等式约束优化问题的极值条件

30 不等式约束优化问题的极值条件

31 不等式约束优化问题的极值条件

32 不等式约束优化问题的极值条件 对于一元函数在给定区间[a, b]上的极值条件，上式中的第一式为
分析极值点x*在区间[a, b]中所处的位置，将会出现三种可能的情况 当a<x*<b时,μ1= μ2 =0，则极值条件为 2）当x*=a时， μ1≥0 ， μ2＝0 ，则极值条件为 3）当x*=b时， μ1 ＝0 ， μ2 ≥ 0 ，则极值条件为

33 不等式约束优化问题的极值条件

34 库恩－塔克条件 要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时 ）。
不等式约束的多元函数极值的必要条件是著名的 库恩—塔克（Kuhn-Tucker）条件，它是非线性优化问 题的重要理论 （1）库恩—塔克条件 (K-T条件） 对于多元函数不等式的约束优化问题： 库恩—塔克条件表明：如点 是函数 的极值点，要么 （此时 ） 要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时 ）。

35 库恩－塔克条件 起作用约束： 极值点处于等值线的中心 x2 x1 x2 x1 极值点处于两个约束曲线的交点上 g1 (x)＝0 x﹡
O x1 x2 x﹡ g1 (x)＝0 g2 (x)＝0 g3 (x)＝0 起作用约束： 极值点处于等值线的中心 O x1 x2 x﹡ g1(x)＝0 g2(x)＝0 极值点处于两个约束曲线的交点上

36 库恩－塔克条件 库恩—塔克条件的几何意义是: 在约束极小值点 处，函数 的负梯度一定能表示成所有起作用约束在该点梯度（法向量）的非负线性组合。

37 库恩－塔克条件 同时具有等式和不等式约束的优化问题 : K-T条件：

38 库恩－塔克条件 K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。
对于目标函数和约束函数都是凸函数的情况， 符合K-T条件的点一定是全局最优点。这种情况K-T条件即为多元函数取得约束极值的充分必要条件。

39 库恩－塔克条件 库恩—塔克（K-T）条件应用举例 s.t 判断[1 0]T是否为约束最优点。 (1)当前点 为可行点，因满足约束条件

40 库恩－塔克条件 (2)在 起作用约束为g1和g2 , 因 (3) 各函数的梯度：

41 库恩－塔克条件 （4）求拉格朗日乘子 由于拉格朗日乘子均为非负，说明 是一个局部最优点，因为它满足K-T条件。

42 库恩－塔克条件 s.t.