CO C1 Complexity bounds for global optimization

N-dimensional Box Constraint Problem

考虑没有泛函约束的有约束最小化问题:

$$\min_{x\in \mathbb{B}_n} f(x)$$

其中$\mathbb{B}_n$是一个$\mathbb{R}^n$上的 $n$ 维盒子：

$$\mathbb{B}_n = \{x \in\mathbb{R}^n| 0\le x^{(i)}\le1, i=1\cdots n\}$$

• $l_p$范数：

• Lipschitz 连续：函数 $f(x)$ 在 $\mathbb B_n$ 上是 Lipschitz 连续的，若

  $$\forall x,y \in \mathbb B_n,|f(x)-f(y)| \le L||x-y||_{\infty}$$

  $L$ 是某个 Lipschitz constant。

Uniform Grid Method

现介绍方法 $G(p$) ：

• 构造 $(p+1)^n$ 个点，形成形如网格的结构：

  $$x_{(i_1,\cdots,i_n)} = (\frac{i_1}{p},\cdots,\frac{i_n}{p})^\top$$

  其中 $(i_1,\cdots,i_n) \in \{0,\cdots,p\}$

• 在以上所有点中找到具有最小目标函数值的点，记为 $\overline x$。

• 返回 $(\overline x,f(\overline x))$。

总结即：均匀网格法在盒子内构建了一个由测试点构成的均匀网格，在这个网格上计算目标函数的最小值，并返回这个最小值，作为问题 的逼近解。

Thm. 令$f^∗ $是问题的全局最优值。那么

$$f( \bar x)− f^∗ ≤ \frac{L}{2p}$$

Pf. 假设 $x_*$ 是问题的全局最小点。若对于 $x,y \in \mathbb R^n, x \le y \mathrm{iff} \forall i = 1\cdots n, x^{(i)} \le y^{(i)}$，则存在一个坐标 $(i_1,\cdots,i_n)$ 满足

$$x \equiv x_{(i_1,\cdots,i_n)} \le x_* \le x_{(i_1 + 1,\cdots,i_n + 1)}\equiv y$$

注意到：$y^{(i)} - x^{(i)} = \frac{1}{p}$ 且 $x_*^{(i)} \in [x^{(i)},y^{(i)}]$，记 $\hat x = \frac{x + y}{2}$，则根据 $l_{\infty}$ 范数的定义可构造一点：

$$\tilde x = \begin{cases} y^{(i)}, \mathrm{if} x^{(i)}_* \ge \hat x^{(i)}\\ x^{(i)}, \mathrm{otherwise} \end{cases}$$

$i=1\cdots n, |\tilde x^{(i)} - x_*^{(i)}|\le \frac{1}{2p}$，且该点是一个网格点。综上即

$$f(\hat x)− f(x_∗) ≤ f( \tilde x)− f(x_∗) ≤L∥ \tilde x−x_∗∥_∞ ≤ \frac{L}{2p}$$

考虑优化的误差 $\epsilon$，有 $\frac{L}{2p} \le \epsilon$，即 $p \ge \frac{L}{2\epsilon}$。那么对每个维度，有$p + 1 = ⌊\frac{L}{2\epsilon}⌋ + 2$ 个格点取值，共构造了 $(p+1)^n$ 个格点。即解析复杂度至多为

$$A(G) = (⌊\frac{L}{2\epsilon}⌋ + 2)^n$$

Lower Complexity Bound

• 基于黑盒 (black box) 概念

• works 所有合理的迭代方案下: lower estimate

• resisting oracle：

  resisting oracle 对于每个特定的方法 (for example, G§) 试图创建一个最坏 worst 问题。

  • 最坏的方式回答该方法的每一个调用
  • 同时每个回答与 前述回答 + 问题的描述 相容 compatible

  它重构 reconstruct 了一个问题：完全符合算法最后累积的信息集合。若我们对该问题执行该方法，将从 oracle 得到相同的回答序列，因而它将重现同样的测试点序列。

重新考虑 N-dimensional Box Constraint Problem， 考虑零阶局部黑盒抵抗 oracle的工作：

定义问题类 \scr C:

• 模型: $\min_{x∈\mathbb B_n} f(x)$，$ f(x)$ 在 $\mathbb B_n$ 上是 $ℓ_∞-Lipschitz$ 连续的。
• Oracle: 零阶局部黑盒。
• 逼近解: 寻找$\bar x ∈ \mathbb B_n : f( \bar x)− f^∗ ≤ ϵ$。

Thm .对于零阶方法，要取得 $ϵ$ 精度，则 \scr C 的解析复杂度至少为 $(\lfloor \frac{L}{2ϵ}\rfloor)^n$。

注： 这里 $\epsilon < \frac{1}{2}L$。且测试点不是按照前述的均分格点选取的。

Pf. 方便起见记 $p = ⌊ \frac{L}{ 2ϵ} ⌋(≥ 1)$。 假定对于求解来自问题类 \scr l 的任意问题，存在一个方法需要 $N< p^n$ 次 oracle 调用。

设计以下的 抵抗策略 应用：在任何测试点 $x$ ，oracle返回 $f(x) = 0$。即此方法只能寻找到$\bar x \in \mathbb R^n, f(\bar x) = 0$。

由于测试点的数量 $N< p^n$，故必然存在 (Rmk.2)$\hat x ∈\mathbb B_n:\hat x + \frac{1}{p}e ∈\mathbb B_n, e = (1, . . . ,1)^⊤ ∈\mathbb R^n $使得一个区间 $\mathbb B= \{x| \hat x ≤ x ≤ \hat x+ \frac{1}{p} e\}$中不含有任何测试点。

作偏移 $x_* = \hat x + \frac{1}{2p}e$。则 $\hat x = x_* - \frac{1}{2p}e, \mathbb B$ 可写作

$$\{x | x_* - \frac{1}{2p}e \le x \le x_* + \frac{1}{2p}e\} \equiv \{x|\ ||x - x_*||_{\infty} < \frac{1}{2p}\}$$

考虑 $ℓ_∞-Lipschitz$ 连续的性质，设计函数

$$\bar f(x) = \min\{0,L||x - x_*||_{\infty} - \epsilon \}$$

显然这是一个取非正值的函数，且只有在 $L||x - x_*||_{\infty} - \epsilon < 0$即 $||x - x_*||_{\infty} < \frac{\epsilon}{L}$ 时函数取值非零。将该区间记为 $\mathbb B'$。

又 $p = ⌊ \frac{L}{ 2ϵ} ⌋(≥ 1)$，则 $\frac{1}{2(p+1)} < \frac{\epsilon}{L} \le \frac{1}{2p}$。那么

$$\mathbb B' = \{x|\ ||x - x_*||_{\infty} < \frac{\epsilon}{L}\}\\ \sube\mathbb B = \{x|\ ||x - x_*||_{\infty} < \frac{1}{2p}\}$$

即说明没有测试点落入函数取非零值的空间。也即所有的测试点 $\bar f(x) = 0$。由于函数取值的非零说明 $|f(x)-f(x_*)| \le L||x-x_*||_{\infty} \le \epsilon$，即在调用 oracle 的数量小于 $p^n$ 时，结果的准确度不可能好于 $ϵ$。

Remarks

• 函数 $\bar f(x)$ 的 Lipschitz 连续性。
• 由于 $N < p^n$，那么前述 $\hat x$ 一定存在。
  反证法：若不存在，则若划一个均匀网格，格边长为 $\frac{1}{p}$，那么此时每个格子中都有测试点。从而测试点的数量大于等于 $p^n$，和条件矛盾。

综上，对于该问题，计算的上界是

$$(⌊\frac{L}{2\epsilon}⌋ + 2)^n$$

下界为

$$(\lfloor \frac{L}{2ϵ}\rfloor)^n$$

如果 $ϵ =O(\frac{L}{n})$，下界和上界乘上一个因子后是重合的。这说明 $G(p)$ 是 \scr C 的一个优化的 optimal 方法。