[凸优化]算法的复杂度分析-01_耀世娱乐-耀世注册登录官方入口

在复杂度分析中．算法通过子程序来获得所求问题的局部信息。不同的算法需要获得不同的局部信息。比如，对于梯度法来说，对任意给定输入 $x_0\\in X$ , 子程序 $\\mathcal{O}$ 返回函数值信息 $f(x_0)$ 和梯度信息 $\ riangledown f(x_0)$ ; 对于次梯度法, 则需要返回次梯度信息 $\\partial f(x_0)$ ; 对于牛顿法, 需要返回二阶导数信息 $\ riangledown^2 f(x_0)$ .

这些子程序(Oracle)都是事先给定的, 复杂度分析理论并不衡量这些子程序的求解复杂度. 我们假设这些子程序 $\\mathcal{O}$ 具有局部性和黑盒性.

子程序 $\\mathcal{O}$ 是唯一局部信息来源: 数值算法唯一可获得的有关目标优化问题的局部信息来源于子程序.
子程序 $\\mathcal{O}$ 具有局部稳定性: 调用子程序时, 对测试点 $x$ 做微小的扰动, 返回的局部信息 $\\mathcal{O}(x)$ 变化不大.

其中第二条是对算法进行收敛性分析的关键假设. 例如, 在分析梯度法的收敛性时, 由于 $\\mathcal{O}(x)=f(x)$ 或 $\ riangledown f(x)$ , 我们需要假设存在某一常数 $L$ 使得

$\\|\\mathcal{O}(x)-\\mathcal{O}(y)\\|\\le L\\|x-y\\|$

也就是假设目标函数具有Lipschtiz连续性．或者目标函数的导数具有Lipschtiz连续性(甚至是在牛顿法中还要求目标函数的二阶导数Lipschtiz连续)。对于没有这样性质的优化问题的目标函数,数值算法有可能很难收敛, 或者收敛性质很差. 其实这也解释了前面的文章中多次出现了Lipschtiz连续性这一假设的作用.

子程序的类别:

$\\mathcal{ZO}$ (zero order oracle): 适用于无导数优化算法, 对于任意给定的 $x_0$ 返回 $f(x_0)$ .
$\\mathcal{FO}$ (first order oracle): 适用于梯度法, 返回函数在 $x_0$ 处的函数值和一阶导数信息, $f(x_0),\ riangledown f(x_0)$ 或 $\\partial f(x_0)$
$\ ext{2nd}\\mathcal{O}$ (second order oracle): 适用于牛顿法, 返回函数在 $x_0$ 处的函数值和一, 二阶导数信息, $f(x_0),\ riangledown f(x_0),\ riangledown^2 f(x_0)$
$\\mathcal{SFO}$ (stochostic first order oracle): 适用于随机梯度法, 返回 $x_0$ 在 $F(x, \\xi)$ 的函数值和一阶随机梯度信息 $F(x_0,\\xi_0),G(x_i,\\xi_0)$ .
$\\mathcal{PO}$ (projection/prox-operator oracle): 适用于投影梯度法, 返回 $x_0$ 在 $X$ 上的投影

$y \\in \\operatorname{argmin}_{x \\in X}\\left\\|x_{0}-x\\right\\|^{2}$

对于求解合成函数 $f(x)=g(x)+h(x)$ 的临近点梯度法, 返回 $x_0$ 的邻近点投影

$y \\in \\operatorname{argmin}_{x}\\left\\{h(x)+g\\left(x_{0}\\right)+\\left\\langle\ abla g\\left(x_{0}\\right), x-x_{0}\\right\\rangle+\\frac{L}{2}\\left\\|x_{0}-x\\right\\|^{2}\\right\\}$

$\\mathcal{LO}$ (linear optimization oracle): 适用于条件梯度法, 当 $X$ 是多面体时, 对给定 $x_0$ 返回线性规划的解 $y\\in\\arg\\min_{x\\in X}\\langle x_0, x\\rangle$ .
$\\mathcal{SO}$ (separation oracle): 适用于椭球法, 对于有界闭约束集合 $X\\in R^n$ , 给定点 $c_0\\in R^n$ , 如果 $c_0\\in X$ 则返回真, 否则返回一个向量 $w$ 在 $c_0$ 处形成一个分割超平面:

$w^T(x-c_0)\\le 0,\\forall x\\in X$ .

上述子程序的任意组合可以形成不同算法所需要的子程序. 比如 $\\mathcal{FO+SO}$ 组成椭球法和重心法每一步所需要调用的子程序; $\\mathcal{FO+PO}$ 组成投影梯度法所需的子程序; $\\mathcal{FO+LO, SFO+PO, SFO+LO}$ 分别组成条件梯度法, 随机梯度法, 随机条件梯度法所需要调用的子程序.

我们定义两种测度来衡量算法 $\\mathcal{S}$ 在问题 $\\mathcal{P}$ 上的计算复杂度:

分析复杂度(Analytical complexity): 将问题 $\\mathcal{P}$ 求解到精度 $\\epsilon$ 总共所需要调用子程序 $\\mathcal{O}$ 的次数。
算术复杂度(Arithmetical complexity): 将问题 $\\mathcal{P}$ 求解到精度 $\\epsilon$ 总共所需要执行的算术操作（包括子程序 $\\mathcal{O}$ 内部的操作和算法本身的橾作）。

算术复杂度更能实际体现算法的效率。但当我们用特定算法 $\\mathcal{S}$ 求解某一具体问题 $\\mathcal{P}\\in\\mathcal{F}$ 时候，如果可以知道子程序 $\\mathcal{O}$ 的复杂度．我们可以很容易地从分析复杂度推出算术复杂度。因此在本文中． 我们主要研究算法 $\\mathcal{S}$ 在问题集合 $\\mathcal{F}$ 上的分析复杂度。

分析复杂度与优化收敛性分析理论中的收敛率有一定的关系。

次线性收敛率(Sublinear rate): $f(x^{(k)})-p^*\\le \\frac{c}{\\sqrt{k}}$ , 其中 $c$ 为常数, 令 $\\frac{c}{\\sqrt{k}}\\le\\epsilon$ 得到 $k\\ge\\frac{c^2}{\\epsilon^2}$ , 对应的分析复杂度为 $\\mathcal{O}(\\frac{1}{\\epsilon^2})$ .
线性收敛率(Linear rate): $\\|x^{(k)}-x^{*}\\|\\le c(1-q)^k$ 其中 $c$ 为常数, 令 $c(1-q)^k\\le\\epsilon$ 得到 $k\\ge \\frac{1}{q}(\\ln c+\\ln \\frac{1}{\\epsilon})$ , 对应的分析复杂度为 $\\mathcal{O}(\\ln \\frac{1}{\\epsilon})$ .
二阶收敛率(Quadratic rate): $\\|x^{(k+1)}-x^{*}\\|\\le \\|x^{(k)}-x^{*}\\|^2$ , 对应的分析复杂度为 $\\mathcal{O}(\\ln\\ln\\frac{1}{\\epsilon})$ .

假设序列 $(x_k)$ 收敛到一个数 $L$ (这里的 $L$ 不是Lipschtiz常数, 注意区分), 定义Q-收敛率:

$\\lim_{k\\rightarrow \\infty}\\frac{|x_{k+1}-L|}{|x_k-L|}=\\mu$

即收敛率是指连续两次误差比值的极限, 为保证极限收敛需满足 $0\\le \\mu\\le 1$ .

如果在 $k\\rightarrow \\infty$ 时,

$\\mu\\rightarrow 0$ , 我们称当前的收敛为Q-超线性收敛(converge Q-superlinearly)
$\\mu\\rightarrow 1$ , 我们称当前的收敛为Q-次线性收敛(converge Q-sublinearly)

如果 $\\lim_{k\\rightarrow \\infty}\\frac{|x_{k+2}-x_{k+1}|}{|x_{k+1}-x_{k}|}=1$ , 那么我们称该序列对数(logarithmically)收敛于 $L$ . 注意和前面的两个不同, 对数收敛不称为Q-对数.

为进一步对收敛进行分类, 定义收敛的阶(order)如下.

对于 $q\\ge1$ , 我们称序列是 $q$ 阶收敛到 $L$ 的, 当且仅当

$\\lim_{k\\rightarrow\\infty}\\frac{|x_{k+1}-L|}{|x_{k+1}-L|^q}< M$

对于常数 $M\\ge1$ (该常数不需要小于1)成立. 在实践中, 可以做出以下的划分:

$q=1$ 被称为线性收敛
$q=2$ 被称为2次(quadratic)收敛
$q=3$ 被称为3次(cubic)收敛
以此类推

在上面的定义中 $Q$ 表示商(quotient), 因为这些项都是使用两个相邻项之间的商来定义的, 一般情况下都可以省略.

怎么知道是几阶的?

实践中通常通过求解下面的问题来估算收敛的阶次 $q$ :

$q\\approx \\frac{\\log|\\frac{x_{k+1}-x_k}{x_k-x_{k-1}}|}{\\log|\\frac{x_k-x_{k-1}}{x_{k-1}-x_{k-2}}|}$

Q-收敛的定义有一个缺点, 即它不能涵盖某些序列, 例如我们接下来要说的 $(b_k)$ 序列, 其收敛速度很快, 但是同时速度也是在变化的. 因此下面给出一种拓展的R-收敛的定义:

假设 $(x_k)$ 收敛到 $L$ , 如果存在一个序列 $(\\varepsilon_k)$ 使得:

$|x_k-L|\\le \\varepsilon_k, \\forall k$

且 $(\\varepsilon_k)$ 收敛Q线性到0, 那么我们称该序列是R-线性收敛到 $L$ .

$R$ 的前缀表示的是root

例子:

第一个例子

考虑序列: $\\left(a_{k}\\right)=\\left\\{1, \\frac{1}{2}, \\frac{1}{4}, \\frac{1}{8}, \\frac{1}{16}, \\frac{1}{32}, \\ldots, \\frac{1}{2^{k}}, \\ldots\\right\\}$ , 可以看到随着 $k$ 的增加这个序列会收敛到 $L=0$ .

那么上面序列的收敛类型是什么呢?

为了搞清楚我们把该序列嵌入到Q-线性收敛的定义中:

$\\lim_{k\\rightarrow \\infty}\\frac{|1/2^{k+1}-0|}{|1/2^{k}-0|}=\\lim_{k\\rightarrow \\infty}\\frac{2^k}{2^{k+1}}=\\frac{1}{2}$

因此我们可以看出该序列Q-线性收敛, 且收敛速率为 $\\mu=\\frac{1}{2}$ .

更一般地来说, 对于任意的 $c\\in\\mathbb{R},\\mu\\in(-1, 1)$ , 序列 $(c\\mu^k)$ 以速率 $\\mu$ 线性收敛.

第二个例子:

$\\left(b_{k}\\right)=\\left\\{1,1, \\frac{1}{4}, \\frac{1}{4}, \\frac{1}{16}, \\frac{1}{16}, \\ldots, \\frac{1}{4^{\\left\\lfloor\\frac{k}{2}\\right\\rfloor}}, \\ldots\\right\\}$

在R收敛的定义下, 同样以速率1/2收敛到0, 但是在Q收敛下不成立.

第三个例子:

$\\left(c_{k}\\right)=\\left\\{\\frac{1}{2}, \\frac{1}{4}, \\frac{1}{16}, \\frac{1}{256}, \\frac{1}{65,536}, \\ldots, \\frac{1}{2^{2^{k}}}, \\ldots\\right\\}$

是超线性收敛的. 实际上它是二次收敛的.

第四个例子

$\\left(d_{k}\\right)=\\left\\{1, \\frac{1}{2}, \\frac{1}{3}, \\frac{1}{4}, \\frac{1}{5}, \\frac{1}{6}, \\ldots, \\frac{1}{k+1}, \\ldots\\right\\}$

是次线性且对数收敛的.

以上四个例子的收敛曲线如下图所示

下面给出几个复杂度分析的例子.

例1.1(盒约束全局优化问题的复杂度上界和下界)

考虑如下全局最优化的问题:

$\\min_{x\\in B_n}f(x)\\;\\;\\;\\;\\;(1)$

其中约束集合 $B_n$ 是一个 $n$ 维的盒子 $B_n=\\{x\\in R^n|0\\le x^{(i)}\\le 1, i=1,...,n\\}$ , 其中 $x^{(i)}$ 表示 $x$ 的第 $i$ 个元素的值. 在 $\\mathbb{R}^n$ 中我们使用 $\\infty$ 范数来做为距离的度量. 假设函数 $f(x)$ 在 $B_n$ 上相对于 $\\ell_{\\infty}$ 范数是Lipschitz连续的:

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

问题模型: 盒约束全局优化问题模型 $\\mathcal{F}=(\\Sigma, \\mathcal{O}, \\mathcal{P})$ 的三个部分:

全局信息 $\\Sigma$ : $f(x)$ 在 $B_n$ 上 $\\ell_{\\infty}$ -Lipschtiz连续 ,
局部信息 $\\mathcal{O}$ : $\\mathcal{ZO}$ 子程序, 对于任意给定的 $x_0$ 返回函数值 $f(x_0)$ ,
解的精度 $\\mathcal{T}_{\\epsilon}$ : 求近似解 $\\bar{x}\\in B_n$ , 使得 $f(\\bar{x})-f^*\\le\\epsilon$ .

对于问题集合1.1 $\\mathcal{F}$ 中的任何一个具体优化问题 $\\mathcal{P}\\in \\mathcal{F}$ , 我们考虑求解它的一个简单解算法 $\\mathcal{S}(p)$ :

无导数全局优化算法 $\\mathcal{S}(p)$ 将 $B_n$ 均匀分成 $(p+1)^n$ 个网格点, 然后计算每个网格点上的函数值, 最后返回函数值最小的网格点作为上面问题的近似解. 容易看到, $\\mathcal{S}(p)$ 也属于我们的抽象迭代算法框架, 它需要迭代 $(p+1)^n$ 次, 全部遍历测试点列才能找到函数值最小的点. 只是它是按照顺序更新新的点, 并未对收集的历史点列信息做任何实际操作. 于是我们可以衡量算法 $\\mathcal{S}(p)$ 的效率.

定理1.2 记 $f^{*}$ 为上面问题模型(1)的全局最优解, 利用无导数全局优化算法1.2求解(1)有,

$f(\\bar{x})-f^{*}\\le \\frac{L}{2p}$

对于问题模型(1)中的每一个具体的问题 $\\mathcal{P}\\in \\mathcal{F}$ , 算法 $\\mathcal{S}(p)$ 的分析复杂度满足:

$N_{\\mathcal{S}(p)}(\\mathcal{P}, \\epsilon)\\le\\left(\\left \\lfloor \\frac{L}{2\\epsilon}\\right \\rfloor+2\\right)^n\\;\\;\\;\\;\\;\\;(2)$ .

其中 $\\left \\lfloor a \\right \\rfloor$ 表示取 $a$ 的整数部分.

证明:

由算法1.2不难看出问题模型(1)的全局最优解 $x^*$ 要么落在测试点列上, 要么被测试点列组成的网格包含. 即存在 $\\{i_1,...,i_n\\}\\in\\{0,...,p\\}^n$ 使得

$x \\equiv x_{\\left(i_{1}, \\ldots, i_{n}\\right)}\\leq x_{*}\\leq x_{\\left(i_{1}+1, \\ldots, i_{n}+1\\right)}\\equiv y$

这里 $a \\equiv\\left(a^{(1)}, \\ldots, a^{(n)}\\right) \\leq b \\equiv\\left(b^{(1)}, \\ldots, b^{(n)}\\right), a, b \\in \\mathbb{R}^{n}$ 当且仅当 $a^{(i)}\\le b^{(i)}$ 对任意 $i=1,...,n$ 成立. 注意到 $y^{(i)}-x^{(i)}=\\frac{1}{p}$ 对任意 $i=1,...,n$ 成立, 且

$x_{*}^{(i)}\\in\\left[x^{(i)}, y^{(i)}\\right], \\quad i=1, \\ldots, n$

记 $\\hat{x}=(x+y)/2$ , 构造点 $\ ilde{x}$ 如下:

$\ ilde{x}^{(i)}=\\left\\{\\begin{array}{ll}y^{(i)}, & \ ext{ 如果 }x_{*}^{(i)}\\geq \\hat{x}^{(i)}\\\\ x^{(i)}, & \ ext{ 其它. }\\end{array}\\right.$

可以看到 $\\left|\ ilde{x}^{(i)}-x_{*}^{(i)}\\right| \\leq \\frac{1}{2 p}, i=1, \\ldots, n$ . 因此

$\\left\\|\ ilde{x}-x_{*}\\right\\|_{\\infty}=\\max _{1 \\leq i \\leq n}\\left|\ ilde{x}^{(i)}-x_{*}^{(i)}\\right| \\leq \\frac{1}{2 p}$

注意到 $\ ilde{x}$ 也属于测试点列, 因此

$f(\\bar{x})-f\\left(x_{*}\\right) \\leq f(\ ilde{x})-f\\left(x_{*}\\right) \\leq L\\left\\|\ ilde{x}-x_{*}\\right\\|_{\\infty}\\leq \\frac{L}{2 p}$

当 $n=2$ 时, $x,y,\ ilde{x}, \\hat{x}, x^*$ 的关系如图1. 取 $p=\\left\\lfloor\\frac{L}{2 \\epsilon}\\right\\rfloor+1$ , 则 $p\\ge\\frac{L}{2\\epsilon}$ . 由定理1.2我们有

$f(\\bar{x})-f^{*}\\leq \\frac{L}{2 p}\\leq \\epsilon$

注意到我们需要调用 $(p+1)^n$ 次的函数值, 因此算法 $\\mathcal{S}(p)$ 的分析复杂度满足不等式(2). 那么它的收敛率怎么算呢? $\\square$

可以看出算法 $\\mathcal{S}(p)$ 的收敛速度与盒约束集合每一维划分的密度 $p$ 有关. 复杂度分析中, 我们更关心算法的分析复杂度, 也就是 $\\mathcal{S}(p)$ 在得到 $\\epsilon$ 精度的近似解时, 需要调用用少次 $\\mathcal{ZO}$ 子程序. 于是我们有了如下关于 $\\mathcal{F}$ 复杂度上界的推论.

在不等式(2)两边关于问题集合 $\\mathcal{F}$ 中取极大, 我们可以得到问题集合 $\\mathcal{F}$ 的复杂度上界的估值:

$\\operatorname{Compl}_{\\mathcal{S}(p)}(\\epsilon)=\\max _{\\mathcal{P}\\in \\mathcal{F}}N_{\\mathcal{S}(p)}(\\mathcal{P}, \\epsilon) \\leq\\left(\\left\\lfloor\\frac{L}{2 \\epsilon}\\right\\rfloor+2\\right)^{n}\\;\\;\\;\\;\\;\\;(3)$

也就是说, 存在一个算法(比如 $\\mathcal{S}(p)$ )在解决 $\\mathcal{F}$ 中每个具体问题 $\\mathcal{P}$ 时(近似解满足 $f(\\bar{x})-f^*\\le\\epsilon,\\bar{x}\\in B_n$ ). 所需要调用的 $\\mathcal{ZO}$ 子程序次数之多不超过 $\\left(\\left\\lfloor \\frac{L}{2\\epsilon}\\right\\rfloor+2\\right)^n$

关于结论(3), 我们会提出一些问题.

我们在估计算法 $\\mathcal{S}(p)$ 时太过粗略, 是否存在比式(3)更好的界?
是否存在其他算法, 其效率比 $\\mathcal{S}(p)$ 要好?

要回答这两个问题, 我们就需要推导问题集合 $\\mathcal{F}$ 的复杂度下界.

我们首先需要定义问题集合 $\\mathcal{F}$ 的解算法集合 $\\mathcal{M}$ .

定理1.3 令 $\\epsilon<\\frac{1}{2}L$ , 对于式(1)对应的问题集合 $\\mathcal{F}$ 来说, 对于其中每一个具体问题 $\\mathcal{P}\\in \\mathcal{F}$ , 对于其解算法集合 $\\mathcal{M}:=\\mathcal{M(F, ZO)}$ 中任意一个算法 $\\mathcal{S\\in M}$ , 其分析复杂度满足

$\\left(\\left\\lfloor\\frac{L}{2 \\epsilon}\\right\\rfloor\\right)^{n}\\leq N_{S}(\\mathcal{P}, \\epsilon)$ .

证明:

考虑 $\\mathcal{ZO}$ 子程序定义的解算法集合 $\\mathcal{M:=M(F, ZO)}$ 中的任意一个解算法 $\\mathcal{S}$ . $\\mathcal{S}$ 通过对约束集合 $B_n$ 进行采样得到测试点列 $\\{x_k\\}$ . 然后在每一个测试点列上调用 $\\mathcal{ZO}$ 子程序, 通过处理(排序)子程序返回的信息(函数值信息)得到最优近似解. $\\mathcal{M}$ 中解算法之间的差异仅在于测试点列的选取方式, 比如算法1.2是在 $B_n$ 上采用均匀采样的方式.

我们现在利用反证法来证明定理1.3.

令采样的测试点列个数 $p=\\left\\lfloor\\frac{L}{2\\epsilon}\\right\\rfloor\\ge 1$ , 若存在 $\\mathcal{M}$ 中的一个解算法 $\\mathcal{S}$ .

在求解问题模型(1) 得到 $\\epsilon$ 精度时调用 $\\mathcal{ZO}$ 子程序的次数 ${N}<p^n$ (这个是我们要推倒的悖论).

我们只需要证明存在某一目标函数，使得 $\\mathcal{S}_0$ 在求解该目标函数时, 迭代 ${N}<p^n$ 次后的精度大于等于 $\\epsilon$ 即可证伪.

由于 $\\mathcal{S}_0$ 在 $B_n$ 上采样的测试点列个数 ${N}<p^n$ , 采样点的个数少于集合中总的点的个数.

因此存在非测试点 $\\hat{x}$ (并非所有点都参与了测试)以及集合 $B=\\{x|\\hat{x}\\le x\\le \\hat{x}+\\frac{1}{p}\\epsilon\\}\\subseteq B_n$ 使得 $B$ 中不包含任何测试点。

令 $x^*=\\hat{x}+\\frac{1}{2p}\\epsilon$ , 在集合不包含任何测试点的集合 $B$ 上构造函数:

$f_{p}(x)=\\min \\left\\{0, L\\left\\|x-x^{*}\\right\\|_{\\infty}-\\epsilon\\right\\}, \\quad \ ext{ 当 }x \\in B .$

令 $f_p(x)=0$ 当 $x$ 是测试点时, $x \\in B_n \\setminus B$ (这里表示的是差集, 即相当于 $B_n-B$ ).

注意到 $\\left\\|x_{*}-\\hat{x}\\right\\|_{\\infty}\\geq \\frac{\\epsilon}{L}$ , 因此 $f_p(\\hat{x})=0$ , 其图像如图2所示:

注意到 $f_p(x)$ 是 $\\ell_{\\infty}$ -Lipschtiz连续的:

$|f_p(x)-f_p(y)|\\le L\\|x-y\\|_\\infty$ .

全局最优解为 $f_p(x^*)=-\\epsilon$ .

利用 $\\mathcal{S}_0$ 求解 $f_p(x)$ 时，由于在所要测试点列处谓用 $\\mathcal{ZO}$ 子程序都返回 $f_p(x^{(k)})=0$ , 因此求得近似最优解为 $f_p(\\bar{x})=0$ , 于是有

$f_{p}(\\bar{x})-f_{p}\\left(x_{*}\\right) \\geq \\epsilon$

因此我们得到结论若测试点列的个数 $N<\\left(\\left\\lfloor\\frac{L}{2 e}\\right\\rfloor\\right)^{n}$ ( 子程序 $\\mathcal{ZO}$ 的调用次数）则对应的解算法求得的精度不可能比 $\\epsilon$ 更好。即问题模型(1)的复杂度下界为 $\\left(\\left\\lfloor\\frac{L}{2 e}\\right\\rfloor\\right)^{n}$ .