数值优化（Numerical Optimization）(1)

2024-02-29 18:12:16

数值优化（Numerical Optimization）(1)

养生的控制人浙江大学控制科学与工程博士在读

优化基础

Overview

一般优化问题可以描述为

$\text{arg}\min _{z\in \mathbb{R}^n}f\left( z \right) :\begin{cases} c_i\left( z \right) =0,i\in \mathcal{E}\\ c_i\left( z \right) \ge 0,i\in \mathcal{I}\\ \end{cases}$

其中， $f:\mathbb{R}^n\rightarrow \mathbb{R}$ 为已知待优化的目标函数， $\mathcal{E}$ 为等式约束， $\mathcal{I}$ 为不等式约束。这里只考虑最小化问题（求目标函数的最小值），最大化问题等价于最小化负目标函数。

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

约束和无约束：如果 $\mathcal{E} \cup \mathcal{I} = \varnothing$ ，则这是一个无约束问题；
线性和非线性规划：如果 $f(z)$ 和 $c_i(z)$ 都是 $z$ 的线性函数则该优化问题为线性规划问题，否则为非线性规划问题。

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

全局最优解、弱局部最优解、严格局部最优解、孤立局部最优解的定义：对于优化问题的解 $x^*$ ，它属于

全局最优：对于任意的 $x$ ，有 $f(x^*)\le f(x)$

弱局部最优：对于任意 $x$ 属于 $x^*$ 的领域 $N$ ，有 $f(x^*)\le f(x)$

严格局部最优：对于任意 $x$ 属于 $x^*$ 的领域 $N$ ，有 $f(x^*)< f(x)$

孤立局部最优：在 $x^*$ 的领域 $N$ 内，不存在其他最优解。

泰勒定理

假设 $f$ 连续可微，令 $p\in \mathbb{R}^n$ ，对于 $t\in [0,1]$ 有

$f(x+p)=f(x)+\nabla f(x+tp)^Tp$

如果 $f$ 是二次连续可微的，有

$\nabla f(x+p)=\nabla f(x) +\int_{0}^1 \nabla^2 f(x+tp)pdt$

且对于 $t\in [0,1]$ 有

$f(x+p)=f(x)+\nabla f(x)^Tp + \frac{1}{2} p^T \nabla^2 f(x+tp)p$

必要条件

一阶必要条件：假设 $f$ 连续可微，如果 $x^*$ 是 $f$ 的最优解，则 $\nabla f(x^*)=0$ ；

二阶必要条件：假设 $f$ 二次连续可微，如果 $x^*$ 是 $f$ 的最优解，则 $\nabla f(x^*)=0$ 且 $\nabla ^2f(x^*) \ge 0$ （矩阵正半定）。

二阶充分条件

假设 $\nabla ^2f$ 是连续的， $\nabla ^2f(x^*) >0$ ，则 $x^*$ 为严格局部最优解。

凸性和局部最优

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

算法概述

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

算法通常会对函数 $f$ 在 $x_k$ 处进行局部模型近似

$f(x_k+p)\approx m_k(p) = f_k + p^T \nabla f_k + \frac{1}{2}p^TB_kp$

Hessian 矩阵 $B_k$ 的不同选择对应不同的方法：

$B_k = 0$ 为最速下降法；
令 $B_k$ 为二阶导数 $\nabla ^2 f_k$ 的正定近似，对应的是牛顿法；
对 Hessian 矩阵进行迭代近似，对应拟牛顿法；
共轭梯度法更新 $p$ 的过程不需要显式计算 $B_k$ 。

基本定义和结论

Q-收敛

$x_k$ 为Q-线性收敛：存在 $q\in (0,1)$ ，对于充分大的 $k$ 有

$\frac{||x_{k+1}-x||}{||x_k-x||}\le q$

$x_k$ 为Q-超线性收敛：

$\lim_{k \rightarrow \infty}\frac{||x_{k+1}-x||}{||x_k-x||} \rightarrow 0$

$x_k$ 为Q-二次收敛：存在 $q^2 >0$ 有

$\frac{||x_{k+1}-x||}{||x_k-x||^2}\le q$

R-收敛

$x_k$ 为R-线性收敛：如果存在 $v_k$ 为 Q-线性收敛，且满足 $||x_k -x || \le v_k$ ;

$x_k$ 为R-超线性收敛：如果存在 $v_k$ 为 Q-超线性收敛，且满足 $||x_k -x || \le v_k$ ;

$x_k$ 为R-二次收敛：如果存在 $v_k$ 为 Q-二次收敛，且满足 $||x_k -x || \le v_k$ 。

Sherman-Morrison-Woodbury

如果 $A$ 和 $\tilde{A}$ 非奇异且满足 $\tilde{A}=A+ab^T$ ，则

$\tilde{A}^{-1}=A^{-1}-\frac{A^{-1}ab^TA^{-1}}{1+b^TA^{-1}a}$

线搜法

步长

下降方向的定义：如果 $p^T\nabla f_k <0$ 则 $p$ 为下降方向。

问题：寻找 $\alpha_k \in \arg\min \phi(\alpha)$ 其中 $\phi(\alpha)=f(x_k+\alpha p_k)$ ，精确求解步长过于复杂，通常采取不精确求解的方法，即寻找一个能够减小目标函数 $\phi$ 的次优解。

Wolfe 条件

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

固定 $x$ 和 $p$ 且 $p$ 为下降方向，令 $\phi(\alpha)=f(x+\alpha p)$ 且 $\phi '(\alpha)=f^T(x+\alpha p)p$ ，固定 $0<c_1 <c_2 <1$

$\alpha$ 满足 Armijo 条件： $\phi(\alpha)\le \phi(0)+\alpha c_1 \phi '(0)$ （相当于确定 $\alpha$ 取值的右边界）

$\alpha$ 满足曲率条件： $\phi'(\alpha) \ge c_2 \phi '(0)$ （相当于确定 $\alpha$ 取值的左边界）

$\alpha$ 满足强曲率条件： $|\phi '(\alpha)| \le c_2 |\phi '(0)|$ （导数小于固定值相当于步长靠近驻点）

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

Armijo 条件保证了下一次迭代的目标函数是下降的，即 $\phi(\alpha)< \phi(0)$
曲率条件

如果 $\phi '(\alpha) < c_2 \phi '(0)$ 则 $\phi$ 在 $\alpha$ 处仍然是下降的，因此我们可以取一个大于 $\alpha$ 的步长；

如果 $\phi '(\alpha) \ge c_2 \phi '(0)$ 则可能已经接近最小值使得 $\phi '=0$ ，或者意味着 $\phi ' >0$ 超过了最优解。

强条件保证了 $\alpha$ 的选择靠近 $\phi ' =0$ 。

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

假设 $f$ 是连续可微的， $p$ 为在 $x$ 处的下降方向且 $f$ 沿着射线 ${x+\alpha p:\alpha >0}$ 存在一个区间满足 Wolfe 和强 Wolfe 条件。

Goldstein 条件

Goldstein 条件

取 $c \in (0,1/2)$ ，Goldstein 条件：

$\phi(0)+(1-c)\alpha \phi '(0)\le \phi (\alpha) \le \phi(0)+c \alpha \phi'(0)$

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

假设 $f$ 连续可微， $p$ 为 $x$ 处的下降方向，函数沿着射线 ${x+\alpha p : \alpha >0}$ 则存在一个区间满足 Goldstein 条件。

回溯（backstracking）法

回溯法定义：令 $\rho \in (0,1),\bar{\alpha}>0$ 直到 $\alpha$ 满足 Armijo条件
存在满足回溯法的步长

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

步长的选择算法

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

回溯算法

输入：减小速率 $\rho \in (0,1)$ ，初始估计 $\bar{\alpha}$ ，参数 $c$ ，函数 $\phi(\alpha)$ ，令 $\alpha \leftarrow \bar{\alpha}$

循环：当 $\phi(\alpha)\ge \phi(0)+\alpha c \phi '(0)$ 时，令 $\alpha \leftarrow \rho \alpha$

输出： $\alpha$

内插算法

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

输入：可行搜索区间 $[\bar{a},\bar{b}]$ ，初始估计 $\alpha_0$ ，函数 $\phi$ ，令 $\alpha \leftarrow 0, \beta \leftarrow \alpha_0$

循环：当 $\phi(\beta)\ge \phi(0)+c\beta \phi'(0)$ ，令 $\alpha \leftarrow \beta$ ，显式计算拟合函数 $m$ 最小时对应的解并存为 $\beta$

返回： $\beta$

全局收敛及 Zoutendjik

全局收敛、Zoutendjik 条件

算法 $\Omega$ 全局收敛的定义： $||\nabla f_k || \rightarrow 0$ ，即 $x_k$ 收敛到 stationary 点

假设算法 $\Omega$ 产生搜索方向 $p_k$ 满足 $||p_k||=1$ ， $\theta_k$ 为梯度 $\nabla f_k$ 和 $p_k$ 之间的夹角，Zoutendjik 条件为

$\sum_{k=1}^{\infty} cos^2(\theta_k)||\nabla f_k ||^2 < \infty$

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

假设 $\Omega$ 产生序列 $(x_k,p_k,\nabla f_k,\theta_k)$ ，存在 $\delta >0$ ， $cos(\theta_k)\ge \delta$ 。如果算法 $\Omega$ 满足 Zoutendjik 条件则算法是全局收敛的。

Wolfe 条件线搜索满足 Zoutendjik 条件

假设目标函数 $f$ 满足

有下界
给定初始点 $x_0$ ，存在一个开集 $N$ 为 $\mathcal{L}=\{x:f(x)\le f(x_0)\}$
$f$ 在开集上连续可微
$\nabla f$ 在开集上 Lipschitz 连续

且算法 $\Omega$ 产生 $(x_k,p_k,\nabla f_k,\theta_k,\alpha_k)$ 使得

$p_k$ 是一个下降方向（ $||p_k||=1$ ）
$\alpha_k$ 满足 Wolfe 条件

则 $\Omega$ 满足 Zoutendjik 条件。

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

回溯法线搜索满足 Zoutendjik 条件（和上述定理一样，除了步长条件改为： $\alpha_k$ 从 $\bar{\alpha}=1$ 回溯）

发布于 08-27

码农公寓

数值优化（Numerical Optimization）(1)

优化基础

Overview

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

算法概述

基本定义和结论

线搜法

步长

步长的选择算法

全局收敛及 Zoutendjik

相关文章