c++ - 数值食谱/多维根搜索(使用newt): How to minimize the maximum error

Question

本题与《C++中的数值秘诀》一书有关，所以留给对它有一定了解以及对多维优化有一定了解的人。

我正在编写一个需要搜索多维根的程序，为了解决这个问题，我使用了多维牛顿求根方法，即“newt”过程。

对于那些对细节感兴趣的人，我正在尝试根据一些特征点(由两个相机看到的特征点)将可变形的 3D 模型拟合到物体的立体 View 中。

为此，我使用了 newt 程序和以下内容:

• 11 个输入参数:我的可变形模型可以用 11 个参数建模(由 5 个几何参数和 6 个 3D 对象位置自由度组成):
• 14 个我需要求根的输出参数:基于相机识别的特征点，并给定一组“输入参数”，我可以计算一组距离相机看到的特征点与其理论位置之间的关系。我有 7 个这样的点，所以这给了我 14 个参数(7 个距离乘以 2，因为我计算了两个相机的距离)

我的问题是我的输出参数 (14) 多于输入参数 (11):每当我调用“newt”时，算法总是会收敛，但是它会找到一个几乎完美地最小化 11 个第一个输出参数的解决方案，但是剩下的 3 个参数有很多错误。

但是我希望错误在输出参数之间均匀分配。

我已经尝试过下面描述的方法:

1. 尝试将 14 个输出参数组合成 11 个参数(对于例如，您取一些距离的平均值，而不是使用两个距离)。但是我对这种方法不是 100% 满意
2. 根据以下原则混合多种解决方案:
   • 调用mnewt并记住找到的根
   • 改变14个输出参数的顺序
   • 再次调用mnewt，记住找到的root
   • 计算一个解是两个找到的根的平均值

有谁知道一种更通用的方法，在这种方法中，求根算法会偏向于在输出参数之间均匀分配的错误，而不是偏向于第一个参数？

Answer 1

您尝试最小化 F(x)通过解决 f(x)=0其中 x是一个 m 维 vector 并且 f将其映射到一个 n 维 vector 。如果m < n，您的优化问题欠定 (在你的情况下 11 < 14)。

对于此类系统，解决它们的通用方法是最小化 x 上的 vector 范数 .您可以通过最小化系统来做到这一点 x^T A x + c f(x)^T f(x)关于x和拉格朗日乘数 c .如果没有更多信息，您可以将 A 视为 nxn 单位矩阵。这将找到 x解决了 f(x)=0同时具有最小的范数。

有关使用牛顿法执行此操作的更多详细信息，请参见例如这个paper .