CCG 00-11:能量与优化——为什么几何算法总在最小化

本课只解决一个问题

为什么“求一个好参数化”经常被改写成“让某个能量最小”?

能量把许多局部要求汇总成一个数,优化则从允许的候选中寻找这个数最小的那个。

1. 从一元二次函数开始

E(x)=12ax2−bx,a>0.E(x)=\frac12ax^2-bx, \qquad a>0.

求导:

E′(x)=ax−b.E'(x)=ax-b.

令导数为零:

x∗=ba.x_*=\frac ba.

二阶导数E′′(x)=a>0E''(x)=a>0,所以图像开口向上,x∗x_* 是唯一全局最小值。

2. 多维二次能量

把数aa 换成对称矩阵AA:

E(x)=12xTAx−bTx.E(x)=\frac12x^TAx-b^Tx.

梯度为

∇E(x)=Ax−b.\nabla E(x)=Ax-b.

因此驻点满足

Ax=b.Ax=b.

这说明解线性方程和最小化二次能量是同一个问题的两种视角。

3. 正定性保证碗口朝上

若对任意非零vv 都有

vTAv>0,v^TAv>0,

则AA 正定。沿任意方向离开最小点,能量都会二次增加,所以最小值唯一。

若存在非零vv 使Av=0Av=0,沿这个方向能量可能完全不变。这就是对称性导致的零空间。

4. 一个弹簧例子

两个标量未知量u1,u2u_1,u_2 之间放一根弹簧:

E(u1,u2)=12w(u1−u2)2,w>0.E(u_1,u_2)=\frac12w(u_1-u_2)^2, \qquad w>0.

只有差值重要,两者同时加常数cc 不改变能量:

(u1+c)−(u2+c)=u1−u2.(u_1+c)-(u_2+c)=u_1-u_2.

写成矩阵:

E(u)=12uTw(1−1−11)⏟Lu.E(u)=\frac12u^T \underbrace{w\begin{pmatrix}1&-1\\-1&1\end{pmatrix}}_L u.

L(1,1)T=0L(1,1)^T=0,所以常数向量是零空间。这就是最小型图 Laplacian。

5. 网格平滑能量

对图或网格所有边求和:

E(u)=12∑(i,j)∈Ewij(ui−uj)2.E(u)=\frac12\sum_{(i,j)\in E}w_{ij}(u_i-u_j)^2.

若相邻顶点值差异大,能量增加;最小化会让值尽量平滑。对每个内部顶点求偏导:

∂E∂ui=∑j∼iwij(ui−uj).\frac{\partial E}{\partial u_i} =\sum_{j\sim i}w_{ij}(u_i-u_j).

令其为零:

ui=∑j∼iwijuj∑j∼iwij.u_i=\frac{\sum_{j\sim i}w_{ij}u_j}{\sum_{j\sim i}w_{ij}}.

所以调和条件表示:每个内部值是邻居的加权平均。

6. 约束优化

若只最小化上面的平滑能量,所有uiu_i 取同一个常数就得到零能量,几何会塌缩。参数化必须加约束,例如固定边界:

ui=uˉi,i∈∂M.u_i=\bar u_i,\qquad i\in\partial M.

此时只优化内部未知量。约束决定哪些候选允许参与竞争,能量决定允许候选中谁最好。

7. 梯度下降与直接求解

梯度下降迭代为

x(k+1)=x(k)−η∇E(x(k)).x^{(k+1)}=x^{(k)}-\eta\nabla E(x^{(k)}).

η\eta 是步长。对二次能量,若系统规模允许,直接解Ax=bAx=b 通常更准确;对非线性能量或巨大模型,迭代法更常见。

算法选择不改变数学目标,只改变寻找最小点的方式。

8. 局部最小与全局最小

  • 局部最小:附近候选都不更好;
  • 全局最小:整个可行域内没有更好候选。

正定二次能量是凸的,局部最小就是全局最小。含三角形翻转屏障、非线性曲率或神经网络参数的能量可能非凸,初值就会影响结果。

9. 评价一个几何能量要问什么

  1. 每一项惩罚的几何现象是什么?
  2. 能量是否有平移、旋转或缩放零空间?
  3. 约束是否足以去掉零空间?
  4. 最小值存在吗,唯一吗?
  5. 最低能量是否真的意味着没有翻转?

最后一点尤其重要:LSCM 最小化共形误差,但一般不自动保证所有三角形朝向正确。

10. 常见误区

  1. 能量是人为构造的评价规则,不是自然界唯一给定的答案。
  2. 梯度为零不总是最小值,也可能是最大值或鞍点。
  3. 残差很小只说明方程解得准,不说明能量模型选得对。
  4. 加约束会改变可行域,必须解释其几何含义。

11. 自测与答案

题 1。 求E(x)=x2−4xE(x)=x^2-4x 的最小点。

答案。E′(x)=2x−4=0E'(x)=2x-4=0,所以x=2x=2;二阶导数为2>02>0。

题 2。 为什么∑(i,j)(ui−uj)2\sum_{(i,j)}(u_i-u_j)^2 对整体加常数不敏感?

答案。 每个差值中的常数相消。

题 3。 固定网格边界后,内部调和值满足什么局部性质?

答案。 每个内部顶点值等于邻居值的加权平均。

前后课程

上一课:复数与复平面 | 下一模块:从集合到拓扑空间