第2章优化方法的数学基础课件.ppt

第二章 优化方法的数学基础 §2-1 方向导数与梯度 §2-2 凸集、凸函数与凸规划 §2-3 二次函数及正定矩阵 §2-4 无约束优化问题的极值条件 §2-5 有约束优化问题的极值条件 §2-1 方向导数与梯度 n元函数在点x0处沿s方向的方向导数 二、 梯度 二元函数的梯度 梯度的模： 梯度方向是函数值变化最快的方向，而梯度的模就是函数变化率的最大值 。 多元函数的梯度 例题 2-1 §2-2 凸集、凸函数与凸规划 一、 多元函数的泰勒展开 多元函数泰勒展开 例题: 二、无约束优化问题的极值条件 2. 处取得极值充分条件 §2-5 有约束优化问题的极值条件 不等式约束的多元函数极值的必要条件是著名的库恩--塔克（Kuhn-Tucker）条件，它是非线性优化问题的重要理论 （1）库恩—塔克条件 (K-T条件） 对于多元函数不等式的约束优化问题： K-T条件 K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。 K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。 例：求目标函数f（X）= 的梯度和Hesse矩阵。 解：因为 则 又因为： 故Hesse阵为： 用泰勒展开将函数 在点 简化成线性函数与二次函数。 解：函数在点 的函数值、梯度和二阶导数矩阵： 简化的线性函数 简化的二次函数 1.F(x)在 处取得极值，其必要条件是: 即在极值点处函数的梯度为n维零向量。 例： 在 处梯度为 但 只是双曲抛物面的鞍点，而不是极小点。 函数的梯度为零的条件仅为必要的，而不是充分的。 则称 为f 的驻点。 定义：设 是D的内点，若 根据函数在 点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。 为了判断从上述必要条件求得的 是否是极值点，需建立极值的充分条件。 海赛（Hessian）矩阵 如 正定，即各阶主子式均大于零，则X*为极小点。 海赛（Hessian）矩阵如 负定，即各阶主子式为负，则X*为极大点。 库恩—塔克条件表明：如点 是函数 的极值点，要么 （此时 ） 要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时 ）。 O x1 x2 极值点处于等值线的中心 极值点处于两个约束曲线的交点上 x﹡ g1 (x)≤0 g2 (x)≤0 g3 (x)≤0 O x1 x2 x﹡ g1(x)＝0 g2(x)＝0 起作用约束： 库恩—塔克条件的几何意义是: 在约束极小值点 处，函数 的负梯度一定能表示成所有起使用约束在该点梯度（法向量）的非负线性组合。 x1 x2 O g2(x)=0 g1(x)=0 F (x)=C ?g2(xk) ?g1(xk) －?F(xk) xk 可行域 点xk处的切平面 x1 x2 O g2(x)=0 g1(x)=0 F (x)=C ?g2(xk) ?g1(xk) －?F (xk) xk 可行域 点xk处的切平面 (a) (b) 同时具有等式和不等式约束的优化问题 : K-T条件： 对于目标函数和约束函数都是凸函数的情况， 符合K-T条件的点一定是全局最优点。这种情况K-T条件即为多元函数取得约束极值的充分必要条件。 例库恩—塔克（K-T）条件应用举例 s.t 判断[1 0]T是否为约束最优点。 * * 一、方向导数 二元函数在点x0处沿某一方向s的方向导数 方向导数是偏导数概念的推广。 方向导数与偏导数之间的数量关系是 O x2 x1 x10 x20 x0 ?x1 ?x2 ?s x S ?1 ?2 图2-1 为函数F(x1，x2)在x0点处的梯度。 设 梯度方向和s方向重合时，方向导数值最大。 图2-2 梯度方向与等值线的关系 设： 则有 为单位向量。 函数的梯度方向与函数等值面相垂直，也就是和等值面上过x0的一切曲线相垂直。 由于梯度的模因点而异，即函数在不同点处的最大变化率是不同的。