第4章优化2(10.5).ppt

4 3无约束最优化方法 4 3 1凸集和凸函数 定义1设D Rn 若对D中任意两点x 1 与x 2 连接x 1 与x 2 的线段仍属于D 换言之 对 x 1 x 2 D 0 1 恒有 x 1 1 x 2 D则称D为凸集 x 1 1 x 2 称为x 1 和x 2 的凸组合 例 i 下图中 a b 为凸集 c 为非凸集 iv 射线L x x x 0 d 0 为凸集 其中d为给定的非零向量 x 0 为定点 定义2设D为Rn中非空凸集 若对 x 1 x 2 D a 0 1 恒有 则称f x 为D上的凸函数 进一步 若x 1 x 2 时 式仅 成立 则称为f x D上严格凸函数 凸函数定义中的条件也可描述为 a1 a2 0 a1 a2 1 有 f a1x 1 a2x 2 a1f x 1 a2f x 2 所以 f x x2是R上凸函数 例如 对f x x2 因 x1 x2 R a 0 1 2 凸函数的性质 定理1设f1 f2为定义在凸集D上的凸函数 为非负实数 则 f1 f1 f2也是D上凸函数 定理2设D是Rn中一个凸集 f是定义在D上的一个凸函数 则f在D的内部连续 定理3设D是Rn中一个非空凸集 f是定义在D上的一个凸函数 则 1 水平集D x x D f x 是凸集 2 f在D上的局部极小点是整体极小点 且极小点的集合为凸集 3 凸函数的判断 设函数f x 存在一阶偏导数 x Rn 向量 为f x 在点x处的梯度 进一步 我们有 定义3设函数f x 存在二阶偏导数 x Rn 则称矩阵 为f x 在点x处的Hesse矩阵 例2给定二次函数f x1 x2 2x12 x22 2x1x2 x1 1 3 1 求 f x 及 2f x f x 4x1 2x2 1 2x1 2x2 T 3 2 其中A为n阶 此例n 2 对称方阵 x b为n维列向量 c为常数 而 3 2 式及 3 3 式可表为 实际上 对任意的由 3 4 式给出的二次函数 均有 f x Ax b 2f x A 定理4设D是Rn中非空开凸集 f x 是定义在D上的可微函数 则f x 是凸函数的充要条件为 x y D 有 f y f x y x T f x 3 5 而f x 是D上严格凸函数为 x y D x y 3 5 式仅 成立 例如 对f x x2f y f x y x T f x y2 x2 y x 2x y2 2xy x2 0 f x x2是R上凸函数 例如 对二次函数f x1 x2 2x12 x22 2x1x2 x1 1 其顺序主子式 4 0 f x1 x2 是R上严格凸函数 4凸规划 定义5若规划 中 f x 和 gi x 为凸函数 hj x 是线性函数 则上述问题为求凸函数在凸集上的极小点 这类问题称为凸规划 凸规划是非线性规划中的一种重要特殊情形 它具有很好的性质 正如定理3所述 凸规划的局部极小点就是整体极小点 且极小点集合是凸集 如果凸规划的目标函数是严格凸函数 又存在极小点 则它的极小点还是唯一的 4 3 2最速下降法 1 最速下降方向 该方法在每次迭代中沿最速下降方向进行搜索 那么什么方向是函数 f x 在点x Rn处的最速下降方向呢 分析 设f x 在x处可微 由台劳公式有 再对上式右边用Cauchy不等式可得 可见当 取负梯度方向时 f x 下降最快 这个方向称为最速下降方向 2 最速下降法 问题 minf x x Rn 本节的优化问题均作此假定 计算步骤 1 取初始点x 0 Rn 精度 0 令k 0 x k 1 x k lkd k k k 1 转2 定理6 收敛性定理 设f x 一阶可微 水平集 G0 x f x f x 0 有界 则最速下降算法或在有限步终止 或点列 x k 的任何极限点都是f x 的驻点 一阶偏导数为0的点 推论7在定理6的假设下 若f x 为凸函数 则应用最速下降算法 或在有限步迭代后达到最小点 或 x k 的任何极限点都是总体最小点 解第一次迭代 目标函数f x 在点x处的梯度及搜索方向为 从x 1 1 1 T出发 沿方向d 1 进行一维搜索 求得步长 1 5 18 在直线上的极小点 第二次迭代 不满足精度要求 从x 2 出发 沿方向d 2 进行一维搜索 求得步长 2 5 12 沿此方向得到的极小点 第三次迭代 f x 在点x 3 处的最速下降方向 实际上 问题的最优解x 0 0 T 4 3 3牛顿法 最速下降法是以函数的一次近似为基础而提出的算法 牛顿法是以函数的二次近似为基础提出的算法 一般说来二近似比一次近似更精确 设f x 二阶可微 2f x 0 保证极值存在 记 g f x H 2f x f x 在点x附近有 牛顿法的思想是通过求q 的极小值点来作为f x 的极小点的近似 q 是一个二次函数 可通过求q 的驻点 即一阶导数为0的点 而求得q 的极小值点 即令 阻尼牛顿法 1 取初始点x 0 0 令k 0 3 计算d k 2f x k 1gk x k 1 x k lkd k k k 1 转2 特点 2 对一般函数 二次可微连续 2f x 0 水平集G0 x f x f x 0 有界 则牛顿算法或有限步停 或得无穷点列 x k 有如下性质 f x K x k x 唯一 且x 是f x 的最小点 3 x 0 接近x 时收敛很快 计算 2f x k 1量大 4 与最速下降法比较 最速下降法迭代过程一般呈锯齿形 开始快 其后慢 见图 属线性收敛 而阻尼牛顿法属二阶收敛 1 若f x 是二次凸函数 用牛顿算法只要一步就达最小点 则称序列 x k 为p阶收敛 若p 1 则称 x k 为线性收敛 值得注意的是阻尼牛顿法有两个缺点 一是可能出现Hesse矩阵H奇异的情况 因此不能确定后继点 二是即使H非奇异 也未必正定 因而牛顿方向不一定是下降方向 这就可能导致算法失败 实际应用时可将最速下降法与牛顿法结合运用 开始用最速下降法 其后用牛顿法 4 3 4共轭梯度法 一 共轭方向与共轭向量 1 等高线 z f x y 在R3中为一曲面 f x y c称为等高线或等值线 Rn中的等高线可类似定义 等高线的一个性质 设f x y 二阶可导 2f x0 y0 0 若 x0 y0 为f x y 的极值点 则在极值点 x0 y0 充分小的邻域内 f x y 的等高线族近似于同心椭圆 2 共轭方向 3 共轭 关系的表示 表明 由在平行于P1的两条直线上 通过一维搜索找出的最小点x 1 和x 2 而得到的P2 x 2 x 1 过椭圆的中心 引理8证明 又x 1 x 2 为f x 在所述二直线上的最小点 有 g1 f x 1 Ax 1 b g2 f x 2 Ax 2 b P1Tg1 0 P1Tg2 0 P1TA x 2 x 1 P1TAP2 0 定义1设A为n阶对称矩阵 1 若P1TAP2 0 则称向量P1与P2为A共轭的或A正交的 PiTAPj 0 i j i j 1 m 则称P1 P2 Pm为A共轭 或A正交 的向量组 说明 定义1中的A通常为正定矩阵 当A E 单位阵 时 A正交即为通常意义下的正交 2 若一组向量P1 P2 Pm Rn 满足 引理9设n阶矩阵QT Q 0 非零向量P1 P2 Pm Rn m n 为Q共轭的 则P1 P2 Pm为线性无关的 证明设 i R1 i 1 2 m 使 则对任一个j 1 j m 有 jPjTQPj PjTQPj 0 Q正定 二次型 0 j 0 j 1 2 m P1 P2 Pm线性无关 推论10Rn中Q共轭的向量组中向量的个数最多n个 而PiT pi1 pi2 pin i 1 2 n x 0 例如 n 2时 若向量P1与P2线性无关 则P1与P2不平行 由 二产生共轭方向的算法 1 取初始点x 1 Rn 置k 1 2 计算d k f x k 5 若k n 1 则停 否则置k k 1转3 说明 2 上算法至多迭代n次必达到最优点 称为二次收敛 3 ak还可取 1 由上算法产生的d 1 d 2 d n 是一组Q共轭向量 g1 g2 gn是一组正交向量 其中gk f x k 三 共轭梯度法 Fletcher Reeves共轭梯度法 1 取初始点x 1 Rn 允许误差 0 3 令d 1 f x 1 置k 1 7 若k n 则置x 1 x n 1 转3 否则转8 说明 1 第7 步为重新开始步 用于非二次函数 对非二次函数某x k 之前不一定共轭 但是是下降方向 故某x k 之后近似二次函数 为了避免误差积累和加快收敛 也可采用重新开始整个算法 4 若f x 不是二次函数 加一个修正项 二次严格凸函数时 此修正项为0 较好 即用 这就是Polyak Polak Ribiere共轭梯度法 定理12 共轭梯度法收敛定理 1 设 1 f x 一阶连续可导 且为