优化-2-零梯度优化

零梯度优化 Derivative Free Optimization

本章中我们讨论零梯度的非凸优化问题。

Introduction

Grid Search

先考虑一个最简单的场景，考虑如下优化问题：

$$\min_{x\in[0,1]} f(x)$$

一个问题是，如果直接使用 Grid Search，需要间隔 多小才能使 满足

$$\hat{f}-f^*\leq \epsilon$$

其中 表示所求最小值， 表示实际最优解， 表示收敛精度。

在对函数 没有任何 assumption 时，答案是无解。因为如果优化目标中存在形如

$$\delta(x)=\begin{cases} +\infty,& x=0 \\0 ,& \textbf{otherwise} \end{cases}$$

的间断点，那 Grid Search 选中最小值的概率是 0，因此无法保证结果收敛精度。

Lipschitz Continuous

为了消除上一节所述情况，我们往往假定目标函数是连续的，由此我们引入 Lipschitz continuous ，即

$$|f(x)-f(y)|\leq L||x-y||\quad \forall x,y$$

当函数满足 Lipschitz continuity 时，在获取任意位置处的 Zero Order Oracle 时，即可限定其附近位置函数的取值范围。在证明算法收敛性时，可以用来计算预测值与真实值之间的差。

Algorithm

Model Free: Directional Direct-search Methods

一类零梯度算法采用 Model Free 方法，即不对优化目标进行建模，直接进行求解，算法流程如下:

• INPUT: 优化目标 , 步长 , 衰减率
• S1: 随机初始化解
• S2: 依次选择各个维度 ，获得候选解 ；其中 为在 基础上在第 维上增加 ； 记录最好的结果
• S3: 如果 ，则接受 ，否则拒绝本次更新，并且
• S4：回到 S2 直到算法收敛
• OUTPUT:

Model Based: Polynomial Models

另一类 Model Based 方法则将目标当成高维多项式函数进行优化，考虑单项式基 ，如二次形式 ，有替代优化目标 $m(x)=\sum_i \alpha_i \phi_i(x)$

需要注意的是，替代优化目标形式必须足够简单，能够快速找到最小值，如上述的二次形式，存在闭式解。

计算时，首先随机在 上进行 Zero Order Oracle 采样进行插值得到替代优化目标 ， 然后找到 的最小值点，并用新得到的点进行插值，周而复始，算法流程如下：

• INPUT: 优化目标 ，项数为 的单项式基
• S1: 随机 个点加入初始化样本集合
• S2: 计算 中每个点对应的 Zero Order Oracle，记为
• S3: 使用 计算 中多项式系数
• S4: 计算 最小值点 和最小值
• S5: 使用 替换 中函数值最大的点，并回到 S3；直到算法收敛
• OUTPUT:

Model Based: Trust-region method

上一节中我们引入了 Model Based 思想，即用一个有着良好性质的替代目标函数来拟合真正的目标函数，但是直接使用一个多项式函数还是过于简单粗暴了。一个想法是，泰勒展开

$$f(x)\approx f(x_k) + \langle\nabla f(x_k),x-x_k\rangle + \frac{1}{2} (x-x_k)^T\nabla^2 f(x_k)(x-x_k)$$

可以在展开位置的附近很好的近似原函数，如果我们的替代目标函数能在 附近半径 的邻域 内采样并进行插值，就能近似得到原目标函数在 附近的函数 。

考虑 ，我们有最小化目标

$$\min_{s_k\in B(0,\Delta)} m_k(x_k+s)$$

接下来，考虑 的大小，我们定义

$$\rho_k=\frac{f(x_k)-f(x_k+s)}{m_k(x_k)-m_k(x_k+s)}$$

每一轮迭代时，如果 ，则说明替代函数选的很好，可以增大步长，即增大 ；反之则减小 。算法伪代码如下所示：

Reference

本节中算法均来自 [LMW19] Derivative-free optimization methods. (Jeffrey Larson, Matt Menickelly, and Stefan M Wild. Acta Numerica, 28:287–404, 2019.
)，关于算法细节与收敛性证明可以查询上述文献。