几何处理中的非线性优化方法

许多基本的物理和几何任务需要最小化网格变形能量。

算法要求(Requirement)

  • robust
  • efficient
  • automated

算法难点(Difficulties)

  • 适应性的混合的二阶能量近似表示
  • 线性搜索前barrier-aware的过滤器
  • 梯度范数收敛准则

问题陈述(Problem Statement)

几何优化问题通常要解决: \[ x^{*}=\underset{x \in \mathbb{R}^{d n}}{\operatorname{argmin}} E(x) \] \(x\)\(n\)\(d\) 维的坐标组成的向量,\(E(x)\) 表示对形变的度量: \[ E(x)=\sum_{t \in T} a_{t} W\left(F_{t}(x)\right) \] \(a_{t}\) 表示元素 \(t\) 在静止形态(rest shape)时的面积,\(W\) 是一个能量密度函数(energy density function),参数是变形梯度,\({F_t}\) 为每个元素 \(t\) 计算了变形梯度。

迭代求解器(Iterative solvers)

有三个主要部分:

  • 能量近似(Energy Approximation)

    在每个迭代过程 \({i}\) 中,对能量做一个二阶近似(proxy): \[ E_{i}(x)=E\left(x_{i}\right)+\left(x-x_{i}\right)^{T} \nabla E\left(x_{i}\right)+\frac{1}{2}\left(x-x_{i}\right)^{T} H_{i}\left(x-x_{i}\right) \] \({H_i}\) 是一个对称矩阵,如果他能准确的近似Hessian矩阵,迭代就可以快速收敛,确保 \({H_i}\) 对称正定(symmetric positive definite, SPD)也同样关键。我们想要得到一个容易计算的,稀疏的,不用在每次迭代重新分解的 \({H_i}\) 矩阵。

  • 线性搜索(Line Search)

    二阶的能量近似模型使得我们可以使用线性求解器寻找 \(x_{i}^{*}\) ,每一步为: \[ p_{i}=x_{i}^{*}-x_{i}=-H_{i}^{-1} \nabla E\left(x_{i}\right) \] 但是,通常对于非线性的能量,二阶能量近似只在局部比较精确,所以需要用line-search寻找一个 \(\alpha_i>0\) ,使得 \(x_{i}^{*}\)\({x_i}\) 的邻域内,从而可以忽略掉泰勒展开的高次项,这样就得到了一个新的迭代: \[ x_{i+1} \leftarrow x_{i}+\alpha_{i} p_{i} \] 在几何问题中,需要特别注意一个现象,对于退化(如翻转)的元素,能量通常会急速增加至无穷。如果某一个 \(p_i\) 使得元素有这种退化趋向,则 \(\alpha_i\) 需要非常小,来阻止这种迭代。

  • 收敛条件(Termination)

    通常的迭代停止条件是,检查能量梯度的范数,然而,梯度范数与Mesh网的大小、尺度、能量的表示方法等相关联,很难选取一个固定的阈值。

常用能量(Energies)

  • Isometric

    • [Sorkine and Alexa 2007]
    • [Chao et al. 2010]
    • [Smith and Schaefer 2015]
    • [Aigerman et al. 2015]
    • [Liu et al. 2008]
  • Conformal

    • [Hormann and Greiner 2000]
    • [L´evy et al. 2002]
    • [Desbrun et al. 2002]
    • [Ben-chen et al. 2008]
    • [Mullenet al. 2008]
    • [Weber et al. 2012]
  • Do not prohibit inversion

    • [Sorkine and Alexa 2007]
    • [Chao et al. 2010]
    • [L´evy et al. 2002]
    • [Desbrun et al. 2002]
  • Use non-convex terms guarantee preservation of local injectivity

    • [Hormann and Greiner 2000]
    • [Aigerman et al. 2015]
    • [Smith and Schaefer 2015]
  • Currently critical in geometry processing

    • Symmetric Dirichlet (ISO) [Smith and Schaefer 2015]

    • Conformal Distortion (CONF) [Aigerman et al. 2015]

    • Most-Isometric Parameterizations (MIPS) [Hormann and Greiner 2000]

能量近似(Energy Approximations)

对能量的近似在这里就转化为对 \(H_i\) 的近似,主要有以下几种方法:

  • 牛顿法(Newton-type methods)

    牛顿法通常能够得到最快的收敛速度,但是每次迭代的计算成本非常高。它直接用能量函数的海塞矩阵组成 \(H_i\) ,这对于 凸能量函数 有较好的效果,如 ARAP ,但是对于非凸能量函数 需要进行改进,至少要确保 \(H_i\) 是半正定(positive semidefinite, PSD)的。针对非凸能量函数改进的算法有:

    • CM (Composite Majorization)
    • PN (Projected Newton)

    虽然上述两种方法需要的迭代次数较少,但是我们在试图解决大的优化问题时,它们每次迭代的成本和存储空间的增长都令人望而却步。

  • 一阶法(First-order methods)

    Direct gradient descent, Jacobi-preconditioned gradient descent

    • SGD (Sobolev-preconditioned gradient descent) Laplacian matrix
    • AQP (Accelerated Quadratic Proxy)
  • 伪牛顿法(Quasi-Newton Methods)

    lie in between these two extremes

    • L-BFGS
  • 几何近似法(Geometric Approximation Methods)

    • SLIM
    • AKAP

当我们得到搜索方向时,通常想要使用一个大的步长,来最大化下降效果。但是对于非线性的能量函数,太大的步长可能适得其反,偶尔会使得能量增加。几何处理和物理领域中绝大多数的能量函数是由有理分式组成的,