数字配方/多维根搜索(使用newt):如何最小化最大错误

Question

这个问题与"C++中的数字配方"一书有关,因此它将保留给了解它的人以及多维优化.

我正在编写一个需要搜索多维根的程序,为了解决这个问题,我使用的是多维牛顿根查找方法,即"newt"程序.

对于那些对细节感兴趣的人,我试图将一个可变形的3D模型拟合到一个物体的立体视图,基于一些特征点(两个摄像机可以看到的特征点).

为此,我使用newt过程如下:

• 11输入参数:我的可变形模型可以用11个参数建模(由5个几何参数和6个3D对象位置的自由度组成):
• 14我需要找到根的输出参数:基于摄像机识别的特征点,并给出"输入参数"的设置,我可以计算摄像机看到的特征点与它们之间的一组距离理论位置.我有7个这样的点,所以这给了我14个参数(7个距离乘2,因为我计算两个摄像头的距离)

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

但是我希望错误在输出参数之间统一划分.

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

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

有没有人知道更通用的方法,其中根查找算法会支持在输出参数之间均匀划分的错误,而不是支持第一个参数？

Answer 1

您尝试通过F(x)求解m 维向量并将其映射到 n 维向量来最小化。如果（在您的情况下 11 < 14），您的优化问题是不确定的。f(x)=0xfm < n

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

有关使用牛顿方法执行此操作的更多详细信息，请参阅例如这篇论文。