数值优化（Numerical Optimization）(1)

优化基础

Overview

一般优化问题可以描述为

[公式]

其中， [公式] 为已知待优化的目标函数， [公式] 为等式约束， [公式] 为不等式约束。这里只考虑最小化问题（求目标函数的最小值），最大化问题等价于最小化负目标函数。

优化命题可以按照不同准则进行分类，比如：

  1. 约束和无约束：如果 [公式] ，则这是一个无约束问题；
  2. 线性和非线性规划：如果 [公式] 和 [公式] 都是 [公式] 的线性函数则该优化问题为线性规划问题，否则为非线性规划问题。

优化问题“解”的理论性质

  • 全局最优解、弱局部最优解、严格局部最优解、孤立局部最优解的定义：对于优化问题的解 [公式]，它属于

全局最优：对于任意的 [公式] ，有 [公式]

弱局部最优：对于任意 [公式] 属于 [公式] 的领域 [公式] ，有 [公式]

严格局部最优：对于任意 [公式] 属于 [公式] 的领域 [公式] ，有 [公式]

孤立局部最优：在 [公式] 的领域 [公式] 内，不存在其他最优解。

  • 泰勒定理

假设 [公式] 连续可微，令 [公式] ，对于 [公式] 有

[公式]

如果 [公式] 是二次连续可微的，有

[公式]

且对于 [公式] 有

[公式]

  • 必要条件

一阶必要条件：假设 [公式] 连续可微，如果 [公式] 是 [公式] 的最优解，则 [公式] ；

二阶必要条件：假设 [公式] 二次连续可微，如果 [公式] 是 [公式] 的最优解，则 [公式] 且[公式] （矩阵正半定）。

  • 二阶充分条件

假设 [公式] 是连续的， [公式] ，则 [公式] 为严格局部最优解。

  • 凸性和局部最优

当 [公式] 是凸函数时局部最优就是全局最优。此外，如果 [公式] 可微则任意驻点为全局最优解。

算法概述

通常优化算法从一个初始点 [公式] 开始局部搜索目标函数的下降方向，从而得到迭代解 [公式] ，当满足停止一定条件时停止迭代。

算法通常会对函数 [公式] 在 [公式] 处进行局部模型近似

[公式]

Hessian 矩阵 [公式] 的不同选择对应不同的方法：

  1. [公式] 为最速下降法；
  2. 令 [公式] 为二阶导数 [公式] 的正定近似，对应的是牛顿法；
  3. 对 Hessian 矩阵进行迭代近似，对应拟牛顿法；
  4. 共轭梯度法更新 [公式] 的过程不需要显式计算 [公式] 。

基本定义和结论

  • Q-收敛

[公式] 为Q-线性收敛：存在 [公式] ，对于充分大的 [公式] 有

[公式]

[公式] 为Q-超线性收敛：

[公式]

[公式] 为Q-二次收敛：存在 [公式] 有

[公式]

  • R-收敛

[公式] 为R-线性收敛：如果存在 [公式] 为 Q-线性收敛，且满足 [公式] ;

[公式] 为R-超线性收敛：如果存在 [公式] 为 Q-超线性收敛，且满足 [公式] ;

[公式] 为R-二次收敛：如果存在 [公式] 为 Q-二次收敛，且满足 [公式] 。

  • Sherman-Morrison-Woodbury

如果 [公式] 和 [公式] 非奇异且满足 [公式] ，则

[公式]

线搜法

步长

下降方向的定义：如果 [公式] 则 [公式] 为下降方向。

问题：寻找 [公式] 其中 [公式] ，精确求解步长过于复杂，通常采取不精确求解的方法，即寻找一个能够减小目标函数 [公式] 的次优解。

Wolfe 条件

  • Armijo 条件、曲率条件、Wolfe 条件、强 Wolfe 条件

固定 [公式] 和 [公式] 且 [公式] 为下降方向，令 [公式] 且 [公式] ，固定 [公式]

[公式] 满足 Armijo 条件： [公式] （相当于确定 [公式] 取值的右边界）

[公式] 满足曲率条件： [公式] （相当于确定 [公式] 取值的左边界）

[公式] 满足强曲率条件： [公式] （导数小于固定值相当于步长靠近驻点）

Wolfe 条件等于 Armijo 条件加上曲率条件，强 Wolfe 条件等于 Armijo 条件加上强曲率条件。

  • Armijo 条件保证了下一次迭代的目标函数是下降的，即 [公式]
  • 曲率条件

如果 [公式] 则 [公式] 在 [公式] 处仍然是下降的，因此我们可以取一个大于 [公式] 的步长；

如果 [公式] 则可能已经接近最小值使得 [公式] ，或者意味着 [公式] 超过了最优解。

强条件保证了 [公式] 的选择靠近 [公式] 。

  • 存在满足 Wolfe 条件和强 Wolfe 条件的步长选择区间

假设 [公式] 是连续可微的， [公式] 为在 [公式] 处的下降方向且 [公式] 沿着射线 [公式] 存在一个区间满足 Wolfe 和 强 Wolfe 条件。

Goldstein 条件

  • Goldstein 条件

取 [公式] ，Goldstein 条件：

[公式]

  • 存在满足 Goldstein 条件的步长选择区间

假设 [公式] 连续可微， [公式] 为 [公式] 处的下降方向，函数沿着射线 [公式] 则存在一个区间满足 Goldstein 条件。

回溯（backstracking）法

  • 回溯法定义：令 [公式] 直到 [公式] 满足 Armijo条件
  • 存在满足回溯法的步长

假设 [公式] 连续可微， [公式] 为 [公式] 处的下降方向，存在一个由回溯法得到的步长满足 Armijo 条件。

步长的选择算法

注：这里不考虑使用 Wolfe 条件或 Goldstein 条件的算法。

  • 回溯算法

输入：减小速率 [公式] ，初始估计 [公式] ，参数 [公式] ，函数 [公式] ，令 [公式]

循环：当 [公式] 时，令 [公式]

输出： [公式]

  • 内插算法

本质思想是通过多项式（二次、三次）来拟合 [公式] ，求得拟合函数的最优解作为迭代估计值。

输入：可行搜索区间 [公式] ，初始估计 [公式] ，函数 [公式] ，令 [公式]

循环： 当 [公式] ，令 [公式] ，显式计算拟合函数 [公式] 最小时对应的解并存为 [公式]

返回： [公式]

全局收敛及 Zoutendjik

全局收敛、Zoutendjik 条件

算法 [公式] 全局收敛的定义： [公式] ，即 [公式] 收敛到 stationary 点

假设算法 [公式] 产生搜索方向 [公式] 满足 [公式] ， [公式] 为梯度 [公式] 和 [公式] 之间的夹角，Zoutendjik 条件为

[公式]

Zoutendjik 条件和角度边界意味着全局收敛

假设 [公式] 产生序列 [公式] ，存在 [公式] ， [公式] 。如果算法 [公式] 满足 Zoutendjik 条件则算法是全局收敛的。

Wolfe 条件线搜索满足 Zoutendjik 条件

假设目标函数 [公式] 满足

  1. 有下界
  2. 给定初始点 [公式] ，存在一个开集 [公式] 为 [公式]
  3. [公式] 在开集上连续可微
  4. [公式] 在开集上 Lipschitz 连续

且算法 [公式] 产生 [公式] 使得

  1. [公式] 是一个下降方向（ [公式] ）
  2. [公式] 满足 Wolfe 条件

则 [公式] 满足 Zoutendjik 条件。

Goldstein 条件线搜索满足 Zoutendjik 条件（和上述定理一样，除了 wolfe 条件改为 Goldstein 条件）

回溯法线搜索满足 Zoutendjik 条件（和上述定理一样，除了步长条件改为： [公式] 从 [公式] 回溯）