Riemannian Optimization · Notes

紧性、完备性与流形优化

流形的两条整体性质分别在优化里买到什么、付出什么:紧性给出存在性与一致常数,完备性给出算法与理论的良定性。全文用青铜色标记与紧性有关的论断、群青色标记与完备性有关的论断。

一句话概括:紧性买到的是"存在性与常数"——极小值必然存在、光滑函数的各阶界自动有限、迭代序列自动有聚点;代价是全局测地凸性不可能、拓扑强制鞍点存在。完备性买到的是"良定性与舞台"——指数映射处处有定义、闭有界集变成紧集、任意两点有最短测地线,是测地凸优化与邻近点方法能够成立的前提;失去完备性时会出现步长受限、极限点逃出流形、甚至"梯度趋零但极限点不驻定"的伪收敛。

紧性(拓扑性质)

买到:存在性 + 一致常数

  • Weierstrass:连续目标必取到全局极小,无需强制性假设
  • $\sup\|\operatorname{grad} f\|$、Hessian 界、曲率界、单射半径下界、直径——全部自动有限
  • 迭代序列必有收敛子列,聚点全在流形内
  • 代价:不存在非常数的测地凸函数;拓扑强制临界点(鞍点)存在

完备性(度量性质)

买到:良定性 + 理论舞台

  • $\exp_x$ 对任意方向、任意步长有定义,测地线不会有限时间跑出流形
  • Hopf–Rinow:闭有界 $\Rightarrow$ 紧;任意两点有最短测地线
  • Hadamard 流形(完备 + 单连通 + 非正曲率)是测地凸优化的标准舞台
  • 失去它:极限点可能不在流形上,一阶方法可能伪收敛(apocalypse)
两者的关系:紧 $\Rightarrow$ 完备(反向不成立);完备性随度量的选取而改变(可以"设计"),紧性由拓扑决定(换度量也改不了)。

1定义与相互关系


紧性是拓扑性质:每个开覆盖有有限子覆盖。对嵌入子流形 $\mathcal{M}\subset\mathbb{R}^n$,紧当且仅当它作为子集有界且闭——这是判断具体流形最快的办法:Stiefel 流形 $\mathrm{St}(n,p)=\{X: X^\top X=I_p\}$ 有界(列正交列范数为 1)且闭(方程的解集),故紧。

完备性是黎曼度量 $g$ 的性质:距离空间 $(\mathcal{M},\mathrm{dist}_g)$ 中每个 Cauchy 列都收敛。它与"测地完备"(每条测地线可以延伸到全时间)等价,这正是 Hopf–Rinow 定理的内容:

定理(Hopf–Rinow)

设 $(\mathcal{M},g)$ 连通。以下等价:(i) $(\mathcal{M},\mathrm{dist}_g)$ 是完备度量空间;(ii) $\mathcal{M}$ 测地完备,即 $\exp_x$ 在整个 $T_x\mathcal{M}$ 上有定义(对某一点成立即对所有点成立);(iii) Heine–Borel 性质:闭有界子集都是紧集。且任一条成立时,任意两点之间存在最短测地线。

注意:无穷维(Hilbert 流形)情形该定理失效——无穷维分析不能照搬这些结论。

由 (iii) 立刻得到:紧流形必完备(紧度量空间总是完备的)。反向不成立:$\mathbb{R}^n$、双曲空间、带仿射不变度量的对称正定矩阵锥 $\mathcal{S}_{++}^n$ 都完备但不紧。也存在两者皆无的流形:固定秩矩阵流形 $\mathcal{M}_r=\{X\in\mathbb{R}^{m\times n}:\operatorname{rank}X=r\}$ 既不有界也不闭(闭包中混入低秩点)。

一个容易忽略的要点:完备性依赖度量。正象限 $\mathbb{R}_{++}^n$ 配欧氏度量不完备(有限长度就能走到边界),但换成 $g_x=\operatorname{diag}(x_i^{-2})$ 后经 $\log$ 映射与欧氏空间 $\mathbb{R}^n$ 等距,从而完备。同一个点集,度量一换,性质相反;而紧性是拓扑的,任何度量都改变不了。这一点在第 3.5 节会变成一个可用的设计自由度。

2紧性买到什么、付出什么


买到存在性:极小值白拿

连续函数在紧集上必取到最大最小值。所以在 Stiefel、Grassmann、球面、$\mathrm{SO}(n)$ 上,任何连续目标的全局极小无条件存在——不需要强制性(coercivity)、不需要正则项。对照非紧的情形:在 $\mathcal{S}_{++}^n$ 上极小化 $\operatorname{tr}(X^{-1})$,下确界为 0 但永远取不到,极小"跑到无穷远";这类目标在紧流形上根本不会发生。

买到一致常数:收敛性定理的假设自动成立

光滑函数 $f\in C^\infty(\mathcal{M})$ 在紧流形上自动满足 $\sup_{\mathcal{M}}\|\operatorname{grad} f\|<\infty$、$\sup_{\mathcal{M}}\|\operatorname{Hess} f\|<\infty$,于是沿测地线(以及沿任何光滑收缩映射 $R$)有一致的下降引理 $$f(R_x(t\eta))\;\le\; f(x)+t\,\langle \operatorname{grad} f(x),\eta\rangle+\tfrac{L}{2}\,t^2\|\eta\|^2,$$ 常数 $L$ 对整个流形一致。几何常数同样白拿:截面曲率有界 $|K|\le K_{\max}$、单射半径有正下界 $\operatorname{inj}(\mathcal{M})>0$、直径有限。翻译成算法语言:黎曼梯度法在紧流形上找 $\varepsilon$-驻定点的 $O(\Delta L/\varepsilon^2)$ 复杂度里,每个常数都真实存在,不需要额外假设。文献里"设迭代点列含于某紧集"这类条件,在紧流形上是空话——而在非紧流形上,它其实是整个证明里最强的假设(见 3.6 节)。

买到子列紧性:聚点必在流形内

任何迭代序列 $\{x_k\}$ 自动有界、自动有收敛子列,且子列极限仍是流形上的点。配合单调下降与 Armijo 型步长的标准论证,就得到"每个聚点都是驻定点";若目标实解析,再配 Łojasiewicz 不等式可升级为整列收敛。梯度流也对所有时间存在——轨线无处可逃。这些在非紧流形上统统要另外花假设去买。

付出全局测地凸性不可能

定理(Bishop–O'Neill 1969;Yau 1974)

完备流形上若存在非常数的(连续)测地凸函数,则流形体积无穷。紧流形体积有限,故紧流形上的测地凸函数只有常数

后果是结构性的:在 Stiefel、Grassmann 上谈"全局测地凸目标"没有意义,凸优化的整套机制(全局最优性条件、凸收敛率)无法全局移植;能做的全局理论只有非凸型的(驻定性、复杂度),更强的结论必须走局部路线(极小点附近的 Polyak–Łojasiewicz / 二次增长)或景观分析(严格鞍点性质、良性非凸)。此外正曲率还限制局部凸性的范围:单位球面上测地球只在半径小于 $\pi/2$ 时是测地凸的,距离函数的凸性也只在这个尺度内可用。

付出拓扑强制临界点:鞍点躲不掉

紧流形上任何光滑函数至少有两个临界点(最大、最小),Morse 理论进一步用 Betti 数给出下界。典型例子:Rayleigh 商 $f(x)=x^\top A x$ 在 $S^{n-1}$ 上的临界点恰是 $A$ 的全部 $\pm$ 特征向量——特征值互异时有 $2n$ 个,除最大最小外全是鞍点。也就是说非凸性不是建模失误,而是紧拓扑的必然;逃离鞍点的机制(扰动、信赖域、利用负曲率方向)在紧流形上不是可选项,而是全局收敛到极小点的必需品。

3完备性买到什么、失去后会怎样


买到指数映射处处有定义:算法本身良定

完备时 $\exp_x(t\eta)$ 对一切 $t$ 有意义:任意步长的测地步都合法,线搜索可以在整个 $(0,\infty)$ 上进行,沿任意测地线的平行移动都存在。不完备时,测地线可能有限时间跑出流形——去掉原点的平面、开球(配欧氏度量)、固定秩流形(测地线有限时间撞上降秩点)都是这样,算法必须限制步长,且这个限制在靠近"缺失边界"处趋于零。

买到Hopf–Rinow 的三重红利

其一,存在性论证的标准通道。非紧流形上证明极小存在的惯用套路是"下水平集有界 + 闭 $\Rightarrow$ 紧 $\Rightarrow$ Weierstrass",第一步到第二步用的正是 Heine–Borel,它只在完备流形上成立。不完备时下确界会从缺失的边界"漏出去":固定秩流形上很多目标的下确界在低秩点处取得,而低秩点根本不在流形里。

其二,最短测地线与由此定义的对象。任意两点间最短测地线存在,距离处处取到,于是 Fréchet/Karcher 均值、邻近算子 $\operatorname{prox}_{\lambda f}(x)=\operatorname{argmin}_y f(y)+\tfrac{1}{2\lambda}\mathrm{dist}^2(x,y)$、测地凸集上的投影这些"用距离定义的对象"才是良定的。黎曼邻近点法(Ferreira–Oliveira)的理论从头到尾建立在完备性之上。

其三,比较几何的机器。Toponogov 型三角比较定理要求完备性,而它是曲率进入收敛率的通道:Zhang–Sra 的测地凸收敛率中,曲率下界 $\kappa_{\min}=-|\kappa|$ 与可行域直径 $D$ 通过 $$\zeta \;=\; \frac{\sqrt{|\kappa|}\,D}{\tanh\!\big(\sqrt{|\kappa|}\,D\big)}\;\ge\;1$$ 进入所有常数——负曲率越强、域越大,率越差。没有完备性,这套机器无从谈起。

买到Hadamard 流形:测地凸优化的标准舞台

定理(Cartan–Hadamard)

完备、单连通、截面曲率 $K\le 0$ 的流形(Hadamard 流形)上,$\exp_x:T_x\mathcal{M}\to\mathcal{M}$ 是微分同胚。于是任意两点间测地线唯一,$\mathrm{dist}^2(\cdot,y)$ 测地强凸,到测地凸集的投影存在唯一。

这是凸优化理论能够整体移植到流形上的唯一标准场景:$\mathcal{S}_{++}^n$ 配仿射不变度量(曲率非正有下界)、双曲空间都属于此类。定理里的完备性不可删——欧氏空间里一个开凸集照样单连通、曲率为零,但投影可以取不到。与第 2 节对照可以看清分工:测地凸优化天生只属于完备非紧的世界(紧流形上没有非常数凸函数),而紧流形的世界只能做非凸理论,两边的分析工具箱是分开的。

失去不完备的四种失败模式

步长受限,常数退化。测地线有限时间出界,靠近缺失边界时允许的步长趋零,光滑性常数 $L$ 不再一致(固定秩流形上曲率与 $L$ 在降秩点附近爆掉)。理论上"固定步长梯度法"的框架直接不适用。

极限点不在流形上。下降序列完全可以是 Cauchy 列却在流形内没有极限——固定秩流形上的迭代点悄悄降秩,收敛陈述变成空话。

伪收敛(apocalypse)。Levin–Kileel–Boumal 给出的现象:$x_k\to \bar{x}$,$\operatorname{rank}\bar{x}<r$,沿途驻定性度量 $\|\operatorname{grad} f(x_k)\|\to 0$,但 $\bar{x}$ 对闭包上的问题并不驻定。一阶方法会被"梯度趋零"这个证据欺骗。对策都绕开不完备本身:升维参数化($X=LR^\top$)、去奇异化、秩自适应。

距离对象失定义。最短测地线可能不存在(去掉原点的平面上,关于原点近似对称的两点),Fréchet 均值、prox、投影随之失去良定性。

一个实务提醒:收缩映射全局有定义 $\ne$ 流形完备。固定秩流形上截断 SVD 给出的投影收缩几乎处处有定义,代码跑得毫无异样——但上面四条照样发生。"能跑"和"理论成立"之间隔着完备性。

买到度量是设计变量:完备性可以被制造

既然完备性属于度量,它就可以被主动设计:给开集选一个把边界推到无穷远的度量。正象限配 $g_x=\operatorname{diag}(x_i^{-2})$ 完备;一般锥的内部配自和谐障碍函数的 Hessian 度量后完备——内点法本质上就是这套几何里的下降法,"约束"被度量吃掉了。$\mathcal{S}_{++}^n$ 是最好的对照组:仿射不变度量完备(Hadamard,但指数映射、平行移动较贵),log-Euclidean 度量完备(平坦,便宜),Bures–Wasserstein 度量不完备(完备化是半正定锥,曲率非负,计算便宜)。选度量时的真实权衡是:迭代点可能靠近边界(接近奇异的矩阵)就选完备度量,确定远离边界则可以用便宜的不完备度量换计算量。

注意完备 $\ne$ 万事大吉

完备非紧的流形仍然什么都不白给:极小存在要靠强制性或正则项自己挣(双曲嵌入训练中点跑向无穷远就是极小在无穷远处的表现);一致常数要靠曲率界、有界几何或"迭代点列有界"的假设——最后这条其实是把紧性从后门借回来。完备性只保证问题与算法良定,不保证它们好解

4常见流形一览


流形度量完备要点
球面 $S^{n-1}$圆度量$K=1$,单射半径 $\pi$,凸性半径 $\pi/2$——凸性只在半球内可用
Stiefel $\mathrm{St}(n,p)$嵌入 / 典范有界且闭;曲率有界,常数全部自动有限
Grassmann $\mathrm{Gr}(n,p)$典范紧流形的商仍紧;曲率 $K\in[0,2]$
$\mathrm{SO}(n)$ 等紧李群双不变$K\ge 0$;测地线 = 单参数子群,好算
$\mathbb{R}^n$欧氏平坦;经典凸优化所在地
双曲空间 $\mathbb{H}^n$双曲$K=-1$,Hadamard;体积指数增长,极小易在无穷远
$\mathcal{S}_{++}^n$仿射不变Hadamard,曲率非正有下界;测地凸优化的主力例子
$\mathcal{S}_{++}^n$log-Euclidean经 $\log$ 与欧氏空间等距,平坦而便宜
$\mathcal{S}_{++}^n$Bures–Wasserstein完备化 = 半正定锥;靠近奇异矩阵时理论失效
固定秩 $\mathcal{M}_r$嵌入闭包混入低秩点;apocalypse 的原产地
正象限 $\mathbb{R}_{++}^n$欧氏有限长度可达边界
正象限 $\mathbb{R}_{++}^n$$\operatorname{diag}(x_i^{-2})$同一点集换度量即完备——完备性是度量的性质
开单位球Poincaré与上一行同理:欧氏度量下不完备,双曲度量下完备

5落到具体算法上


把前两节的结论按算法类别重排一遍。每条按三种场景对照: / 完备非紧 / 不完备

黎曼梯度法 + 线搜索

教科书情形:一致 $L$、Armijo 良定、聚点全驻定,$O(1/\varepsilon^2)$ 复杂度常数真实存在。
完备非紧
算法良定,但收敛性要补假设:下水平集紧(强制性)或迭代点列有界,否则可能下降着跑向无穷远。
不完备
收缩映射可能照常可算,但 $L$ 在缺失边界附近爆掉,且存在伪收敛风险——"梯度范数小"不再是可信的停机证据。

信赖域 / 三次正则化(二阶方法)

Hessian 沿收缩的 Lipschitz 常数自动一致,二阶复杂度 $O(1/\varepsilon^{1.5})$ 与逃离鞍点的保证都拿得干净——这在紧流形上尤其要紧,因为鞍点是拓扑强制的(§2)。
完备非紧
需在包含迭代点的集合上假设二阶常数;通常与"下水平集紧"捆绑给出。
不完备
信赖域半径的意义在边界附近失真,现有理论基本不覆盖。

测地凸方法(投影、邻近点、Fréchet 均值)

整类方法不适用——紧流形上没有非常数测地凸函数。
完备非紧
唯一的主场,且实际要求 Hadamard:唯一测地线、唯一投影、$\zeta$ 因子进入收敛率。
不完备
prox 与投影可能根本无定义。

随机 / 在线方法

梯度自动一致有界——方差与噪声条件里最难验证的一条白拿;各种一致有界性假设自动成立。
完备非紧
指数映射对所有随机步良定;但有界梯度、有界迭代要另设。
不完备
随机步长可能直接把点带出流形,理论与实现都要逐步截断。

双层问题(内层在流形上)

内层解对每个外层变量都存在;隐函数定理所需的 Hessian 正定一旦成立,其最小特征值与三阶导数界在紧流形上对外层变量一致,超梯度的误差常数因此一致可控。把内层实验放在球面 / Stiefel / Grassmann 上,不只是方便,而是整套超梯度分析的常数都真实存在。
完备非紧
内层解的存在性与唯一性要靠内层目标自己的强凸性 / 强制性挣;常数的一致性需另行假设。
不完备
内层解可能漂向缺失边界,解映射 $y^\ast(x)$ 失去定义,超梯度无从谈起。

6备忘清单


  1. 紧 $\Rightarrow$ 完备;反向不成立($\mathbb{R}^n$、$\mathcal{S}_{++}^n$、$\mathbb{H}^n$)。
  2. 完备性是度量的性质,可以通过换度量制造;紧性是拓扑的性质,换度量无效。
  3. "闭有界 $\Rightarrow$ 紧"在流形的内在几何里要靠完备性(Hopf–Rinow);把嵌入子流形当 $\mathbb{R}^n$ 的子集看时才无条件成立。
  4. 不要在紧流形上假设全局测地凸——这样的函数只有常数;测地凸优化的主场是 Hadamard 流形。
  5. 紧流形上鞍点是拓扑强制的,二阶信息 / 逃逸机制不是奢侈品。
  6. 不完备流形上"梯度范数趋零"不是可信的收敛证据(apocalypse);停机准则要对降秩 / 趋边界另设监测。
  7. 定理里"迭代点列含于紧集"的假设,在非紧流形上是借来的紧性——用强制性、正则项或投影把它真正挣回来。
  8. 收缩映射全局可算 $\ne$ 流形完备;代码正常运行不代表理论前提成立。
  9. 无穷维情形 Hopf–Rinow 失效,上述以它为轴的结论都要重新检查。

主要参考