Getting Feasible Variable Estimates from Infeasible Ones: MRF Local Polytope Study
Getting Feasible Variable Estimates from Infeasible Ones: MRF Local Polytope Study
复制标题
从不可行的变量估计中获得可行的变量估计：MRF 局部多面体研究
DOI：
10.1109/iccvw.2013.43
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
S. Schmidt
中科院分区：
文献类型：
--
作者：
Bogdan Savchynskyy;S. Schmidt
本文提出了一种由不可行原解构造近似可行原解的方法，该方法适用于具有一定分离性的大规模优化问题。虽然不可行的原始估计通常可以从对偶函数的（子）梯度中产生，但通常不容易将它们投影到原始可行集，因为投影本身的复杂性与初始问题的复杂性相当。我们提出了另一种有效的方法，以获得可行性，并表明其性质影响收敛到最佳的是类似的性质的欧几里德投影。我们将我们的方法应用到马尔可夫随机场的局部多面体松弛推理问题，并讨论了它的优点，现有的方法。
This paper proposes a method for the construction of approximate feasible primal solutions from infeasible ones for large-scale optimization problems possessing certain separability properties. Whereas the infeasible primal estimates can typically be produced from (sub-) gradients of the dual function, it is often not easy to project them to the primal feasible set, since the projection itself has a complexity comparable to the complexity of the initial problem. We propose an alternative efficient method to obtain feasibility and show that its properties influencing the convergence to the optimum are similar to the properties of the Euclidean projection. We apply our method to the local polytope relaxation of inference problems for Markov Random Fields and discuss its advantages over existing methods.