流形优化： Manifold Optimization 的 全网最通俗版本详解 (一）

之前忙于论文， 停更了很久。 接下来的一段时间，出于各种原因， 决定在CSDN平台上做 最近在 混合波束成形 及 智能反射面 领域 非常常见的流形优化 (Manifold Optimization) 算法 的专题介绍。尽管目前已有了不少的中文博客， 但出于其各种弊端， 使得本篇的成文仍有其不可或缺的意义。 而如果要盘点最核心的意义， 就在于这篇是对读者的 数学能力 与 阅读理解能力 要求最低的 流形优化讲解了。

唯一参考的文献为 Manopt 工具包作者 Boumal 的 新书： An introduction to optimization on smooth manifolds. (2020)

所谓流行优化， 其实就是为了求解如下所示的问题： min ⁡ x ∈ M f ( x ) \min _{x \in \mathcal{M}} f(x) x∈Mmin​f(x) 其中， f : M → R f: \mathcal{M} \rightarrow \mathbb{R} f:M→R 是一个光滑(smooth)的函数。 M \mathcal{M} M则是一个光滑的， 很可能非线性的空间。

流形优化就是旨在解决 被定义在 某些非线性空间上 的优化问题的 一套成熟的优化框架。

贯穿本文， 我们以最简单的一个非线性空间为例来介绍整套流形的思想： M = S n − 1 = { x ∈ R n : ∥ x ∥ = 1 } \mathcal{M}=\mathrm{S}^{n-1}=\left\{x \in \mathbb{R}^{n}:\|x\|=1\right\} M=Sn−1={x∈Rn:∥x∥=1} 即，问题被定义在了一个 n n n维空间的球面上。

首先， 注意到， 在欧式空间（线性空间）中， 我们已经有了一套极为成熟的基于梯度的优化方法， 即

x k + 1 = x k − α k grad ⁡ f ( x k ) x_{k+1}=x_{k}-\alpha_{k} \operatorname{grad} f\left(x_{k}\right) xk+1​=xk​−αk​gradf(xk​)

显然， 这一方法在流行空间中， 并不能直接使用——因为梯度下降后的结果很可能不在流形中。 然而， 我们可以以此为启发， 来设计流形上的优化方案， 那就是——将流形上的优化尽可能地近似为一个在线性空间中的优化。

这就将引出第一个非常重要的思路， 也是流形优化的核心idea：

给定流形上的某一点， 我们希望我们设计的迭代算法让该点沿着某一方向更新， 且仍留在流形上。

这是很显然的， 传统的梯度下降法之所以行不通，就是因为沿着欧式梯度方向更新后， 得到的解已经远离了流形。 也基于此， 我们有理由期望： 我们选择更新的方向应当是使得新的点尽可能不偏离流形本身的方向。

存在这一类方向吗？显然存在！这就是流形中非常重要的一个概念： 切空间 （tangent space）

注意到： 定义了我们例子中的 流形 S n − 1 \mathrm{S}^{n-1} Sn−1的函数实际上可写为： h ( x ) = x ⊤ x − 1 h(x) = x^{\top} x-1 h(x)=x⊤x−1 当且仅当 h ( x ) = 0 h(x)=0 h(x)=0时，点 x x x位于流形上。 因此， 我们希望的更新方向 v v v， 应当满足： h ( x + v ) = 0 h(x+v)=0 h(x+v)=0 注意到： h ( x + v ) = ( x + v ) T ( x + v ) − 1 = x T x + v T x + x T v + v T v h(x+v) = (x+v)^T(x+v)-1=x^Tx+v^Tx+x^Tv+v^Tv h(x+v)=(x+v)T(x+v)−1=xTx+vTx+xTv+vTv 注意到由于 x x x在流形上， 所以 x T x = 1 x^Tx=1 xTx=1, 而更新量 v v v非常小时（即步长极小的情况下）， v T v = 0 v^Tv=0 vTv=0，也就是说， 我们要找的 v v v其实就是满足： v T x + x T v = 0 v^Tx+x^Tv=0 vTx+xTv=0的 v v v。 我们将所有满足这个条件的 v v v组成的集合，写为： T x S n − 1 = { v ∈ R n : v ⊤ x + x ⊤ v = 0 } = { v ∈ R n : x ⊤ v = 0 } \mathrm{T}_{x} \mathrm{S}^{n-1}=\left\{v \in \mathbb{R}^{n}: v^{\top} x+x^{\top} v=0\right\}=\left\{v \in \mathbb{R}^{n}: x^{\top} v=0\right\} Tx​Sn−1={v∈Rn:v⊤x+x⊤v=0}={v∈Rn:x⊤v=0} 这就是所谓的 切空间 （tangent space）。 更普遍一点呢？ 注意到， 利用泰勒展开，我们有其一阶形式为：

h ( x + v ) ≈ h ( x ) + ∇ h ( x ) T v = ∇ h ( x ) T v            ( h ( x ) = 0 ) h(x+v) \approx h(x) + \nabla h(x)^Tv= \nabla h(x)^Tv \;\;\;\;\;(h(x)=0) h(x+v)≈h(x)+∇h(x)Tv=∇h(x)Tv(h(x)=0) 因此， 切空间就是满足 ∇ h ( x ) T v = 0 \nabla h(x)^Tv=0 ∇h(x)Tv=0的所有 v v v 组成的空间。 他的意义就在于：当流形上点沿着切空间上的方向更新的时候， 当步长足够小的情况下，在一阶意义上， 更新得到的点仍满足在流形上。

然而事实上， 步长不可能无限小。 即使沿着切空间方向走， 也终将偏离流形。 但这是后话了。 可以明确的一点是， 流形优化的理论基石就在于， 以切空间上的向量为优化方向， 是最不偏移流形的优化方向。

在实际中，其实有一个叫 retraction 将更新后偏离流形的点重新映射回流形。 后面会详细介绍。 当 retraction 函数满足一定条件时， 流形优化的每步迭代可以确保函数值的单调收敛。

下图展示了例子的几何示意： 在几何上，可以将切空间理解为在流形上 x x x点处的线性化。 流形优化的思想在这里告一段落。 但作为例子，我们先将其完善， 然后在后续的篇幅里再详细介绍每一个流形优化的重要概念。

首先， 我们可以将 retraction 函数选择为： R x ( v ) = x + v ∥ x + v ∥ \mathrm{R}_{x}(v)=\frac{x+v}{\|x+v\|} Rx​(v)=∥x+v∥x+v​ 很显然， 这能确保 x x x在更新后得到的结果，也就是 R x ( v ) \mathrm{R}_{x}(v) Rx​(v)， 仍然留在流形上。 现在问题来了， 我们其实有无数个 v v v的选择， 只需要 v v v在切空间上就可以。 但是，我们的初衷始终是为了最小化函数 f f f，也就是说我们期望： f ( R x ( v ) ) ≤ f ( x ) f(\mathrm{R}_{x}(v)) \le f(x) f(Rx​(v))≤f(x) 那么，我们有理由选择让 f ( R x ( v ) ) f(\mathrm{R}_{x}(v)) f(Rx​(v))最小的那个 v v v，就如同在欧式空间的梯度下降法中， 我们期望选择代表最快下降方向的梯度方向作为更新方向一样。

也就是说， 接下来我们求解一个 v v v， 他位于切平面（切空间） T x S n − 1 \mathrm{T}_{x} \mathrm{S}^{n-1} Tx​Sn−1上， 且使得 f f f下降最快。

假如对 x x x不做限制，即将定义域拓展到欧式空间上，将之记为函数 f : S n − 1 → R f: \mathrm{S}^{n-1} \rightarrow \mathbb{R} f:Sn−1→R的拓展 f ˉ : R n → R \bar{f}: \mathbb{R}^{n} \rightarrow \mathbb{R} fˉ​:Rn→R。两者只是在定义域上有所差别， 后者为前者的拓展。 而在流形这段定义域上两者完全重合。

对于 f ˉ \bar{f} fˉ​寻找一个 v v v是非常容易的， 这就是我们熟知的欧式梯度方向， 也就是 f ˉ \bar{f} fˉ​ 对 x x x求一阶导， 我们记为 grad ⁡ f ˉ ( x ) \operatorname{grad} \bar{f}(x) gradfˉ​(x)。 然而这个 v v v方向显然不在切空间上。 也就是说， 沿着 v v v方向走将偏离流形本身， 这也是欧式梯度法无法直接应用到流形优化中的原因。但是， 我们可以通过欧式梯度方向来计算得到在切空间上的最优 v v v，注意到有： grad ⁡ f ˉ ( x ) = grad ⁡ f ˉ ( x ) ∥ + grad ⁡ f ˉ ( x ) ⊥ \operatorname{grad} \bar{f}(x)=\operatorname{grad} \bar{f}(x)_{\|}+\operatorname{grad} \bar{f}(x)_{\perp} gradfˉ​(x)=gradfˉ​(x)∥​+gradfˉ​(x)⊥​ 本式的意思是， 任何一个方向， 我们可以将其正交分解为 由两部分组成： 切空间上的分量 grad ⁡ f ˉ ( x ) ∥ \operatorname{grad} \bar{f}(x)_{\|} gradfˉ​(x)∥​ 与 正交于切空间上的分量 grad ⁡ f ˉ ( x ) ⊥ \operatorname{grad} \bar{f}(x)_{\perp} gradfˉ​(x)⊥​。 显然， 前者 grad ⁡ f ˉ ( x ) ∥ \operatorname{grad} \bar{f}(x)_{\|} gradfˉ​(x)∥​就是最优的、使得 f f f下降最快的切空间上的向量 v v v。 很容易反证这一点： 如果有更快的另一个切空间上的方向 v ^ \hat{v} v^， 那么 grad ⁡ f ˉ ( x ) \operatorname{grad} \bar{f}(x) gradfˉ​(x)应该为 grad ⁡ f ˉ ( x ) = grad ⁡ f ˉ ( x ) ⊥ + v ^ \operatorname{grad} \bar{f}(x)=\operatorname{grad} \bar{f}(x)_{\perp}+\hat{v} gradfˉ​(x)=gradfˉ​(x)⊥​+v^。

因此： grad ⁡ f ( x ) = grad ⁡ f ˉ ( x ) ∥ = Proj ⁡ x ( grad ⁡ f ˉ ( x ) ) \operatorname{grad} f(x)=\operatorname{grad} \bar{f}(x)_{\|}=\operatorname{Proj}_{x}(\operatorname{grad} \bar{f}(x)) gradf(x)=gradfˉ​(x)∥​=Projx​(gradfˉ​(x)) 也就是说， 切空间上的 f ( x ) f(x) f(x)的最快下降方向为欧式梯度在切空间上的投影。 在本例中， Proj ⁡ x ( v ) = ( I n − x x ⊤ ) v \operatorname{Proj}_{x}(v)=\left(I_{n}-x x^{\top}\right) v Projx​(v)=(In​−xx⊤)v 这个式子可以这样求得： 所谓对某点的投影， 就是求在切空间上离该点最近的一个点，那么就可以通过最小化欧式梯度，求得投影的闭式解如上式所示了。

现在， 有了确定的 优化方向 后 优化之后的 Retraction 步骤， 流形优化的整体框架也呼之欲出：

其中 α k \alpha_k αk​是用某种方式选定的步长。而： grad ⁡ f ( x ) = ( I n − x x ⊤ ) grad ⁡ f ˉ ( x ) ， R x ( v ) = x + v ∥ x + v ∥ . \operatorname{grad} f(x)=\left(I_{n}-x x^{\top}\right) \operatorname{grad} \bar{f}(x)， \mathrm{R}_{x}(v)=\frac{x+v}{\|x+v\|}. gradf(x)=(In​−xx⊤)gradfˉ​(x)，Rx​(v)=∥x+v∥x+v​.

至此， 定义在流形 S n − 1 \mathrm{S}^{n-1} Sn−1 上的 对 f ( x ) f(x) f(x)的优化算法就叙述完成了。

有一个后续需要篇幅来论证的点要留意一下： 我们尚未证明算法的收敛性。 尽管这是可被严格证明的。 同时， 尽管 流形 S n − 1 \mathrm{S}^{n-1} Sn−1 似乎是一个非常简单的例子， 但是事实上在混合波束成形和智能反射面的研究中， 所用到的就是这个流形。 这是因为， 对于一个复数 ∣ x ∣ = 1 |x|=1 ∣x∣=1，可以看做是一个 2 × 1 2\times 1 2×1的实数向量 x = [ ℜ x , ℑ x ] T \mathbf{x}=[\Re{x}, \Im{x}]^T x=[ℜx,ℑx]T， 而 ∣ x ∣ = 1 |\mathbf{x}|=1 ∣x∣=1， 这就是 S n − 1 \mathrm{S}^{n-1} Sn−1中 n = 2 n=2 n=2的流形。 那么， 一个 N × 1 N\times 1 N×1的复数向量， 如果每个元素的模都为1， 可以被认为是定义在 N N N个流形的交集之上的问题。 而 N N N个流形的交集后续也将看到， 仍是一个流形。