● 摘要
本文用分支定界方法求解位姿估计问题和P 扩散和问题。分支定界是重要的求解非凸优化问题的? 最优解的非启发式方法，但是，最坏情况下的复杂度随问题的规模指数级增长，这使得设计一种高效的分支定界方法显得很有必要。
位姿估计是计算机图形学、机器视觉、摄影测量学、机器人学等研究领域中所需要解决的核心问题之一，利用给定的3D-2D 参考点来估计相机与对象间的旋转和平移。我们以极小化目标空间误差为目标函数，首先建立既约模型，把位姿问题表示成一个非凸的二次约束二次规划(QCQP) 问题；其次基于拉格朗日对偶原理，通过添加冗余约束，提出了位姿问题的三个新的QCQP 模型；最后我们用欧拉角参数化旋转矩阵，基于二次规划松弛，对这四个QCQP 模型分别设计了新的高效的分支定界方法。仿真实验结果表明，我们设计的最好的分支定界方法，通常只需一次迭代就终止，即
使? = 10−6。6 个参考点数目时，平均运行时间为0.2005 秒；100 个参考点数目时，平均运行时间为0.0515 秒。另外，我们把最高效的分支定界方法与两个著名的启发式方法进行了比较。
P 扩散和问题(PDSP) 是指，在预先确定的n 个地点放置p 个设备，使得放置设备的p 个地点距离和最大。针对PDSP 我们提出了三个更紧的二次界，并把它们用于分支定界方法中。数值实验表明，我们的分支定界方法在解的质量和计算复杂度方面达到了很好的权衡。