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

多元函数泰勒展开 海色矩阵 （Hessian） 对二次函数： 为二次函数的海色（Hessian）矩阵，常量矩阵。 二次函数的梯度为： 一个判断二次函数为凸函数的简单办法： 如果该函数的HESSEN矩阵为正定，则该函数为凸函数。 例：求目标函数f（X）= 的梯度和Hesse矩阵。 解：因为 则 又因为： 故Hesse阵为： 例题: 用泰勒展开将函数 在点 简化成线性函数与二次函数。 解：函数在点 的函数值、梯度和二阶导数矩阵： 简化的线性函数 简化的二次函数 二、无约束优化问题的极值条件 1.F(x)在 处取得极值，其必要条件是: 即在极值点处函数的梯度为n维零向量。 例： 在 处梯度为 但 只是双曲抛物面的鞍点，而不是极小点。 函数的梯度为零的条件仅为必要的，而不是充分的。 则称 为f的驻点。 定义：设 是D的内点，若 图1 二元函数的极值点 图2 驻点不是极值点而是鞍点 根据函数在 点处的泰勒展开式，考虑上述极值必要条件，可得相应的充分条件。 为了判断从上述必要条件求得的 是否是极值点，需建立极值的充分条件。 2. 处取得极值充分条件 海色（Hessian）矩阵 正定，即各阶主子式均大于零，则X*为极小点。 海色（Hessian）矩阵 负定，即各阶主子式负、正相间，则X*为极大点。 §2-5 有约束优化问题的极值条件 （1）库恩—塔克条件 (K-T条件） 对于多元函数不等式的约束优化问题： 不等式约束的多元函数极值的必要条件是著名的库恩--塔克（Kuhn-Tucker）条件（1951年，由库恩、塔克两人推导出），它是非线性优化问题的重要理论。 K-T条件 库恩—塔克条件表明：如点 是函数 的极值点，要么 （此时 ） 要么目标函数的负梯度等于起作用约束梯度的非负线性组合（此时 ）。 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条件即为多元函数取得约束极值的充分必要条件。 K-T条件是多元函数取得约束极值的必要条件,以用来作为约束极值的判断条件，又可以来直接求解较简单的约束优化问题。 例库恩—塔克（K-T）条件应用举例 s.t 判断[1 0]T是否为约束最优点。 (1)当前点 为可行点，因满足约束条件 (3) 各函数的梯度： （2）在 起作用约束为g1和g2 , 因 （4）求拉格朗日乘子 由于拉格朗日乘子均为非负，说明 是一个局部最优点，因为它满足K-T条件。 s.t 1、设 ，试证明 是 的严格全局极小点。 2、设约束优化问题为： ①用无约束优化问题的极值条件求解目标函数的非约束极值点； ②画出该问题的可行域； ③用库恩—塔克条件 (K-T条件)证明点 是该问题的约束极值点。 作业 * * gggggggg 第二章 优化方法的数学基础 §2-1 方向导数与梯度 §2-2 凸集、凸函数与凸规划 §2-3 二次函数及正定矩阵 §2-4 无约束优化问题的极值条件 §2-5 有约束优化问题的极值条件