摘要翻译：
研究了马尔可夫随机场能量极小化问题的线性规划松弛问题。该问题的对偶目标可以看作是一个凹的、无约束的、非光滑的函数。在最近的一系列论文中提出了在优化之前先平滑目标的思想。他们中的一些人建议减少平滑量（所谓的温度），同时更接近最佳值。然而，没有提供理论上的证据。提出了一种基于松弛原始目标和对偶目标之间的对偶间隙的自适应平滑递减算法，并用序列树重加权消息传递（TRW-S）算法的平滑版本验证了该算法的有效性。该策略也适用于其他算法，避免了迭代过程中对平滑的自调整，并可证明地保证收敛到最优值。
---
英文标题：
《Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing》
---
作者：
Bogdan Savchynskyy, Stefan Schmidt, Joerg Kappes, Christoph Schnoerr
---
最新提交年份：
2012
---
分类信息：

一级分类：Computer Science        计算机科学
二级分类：Artificial Intelligence        人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
一级分类：Computer Science        计算机科学
二级分类：Data Structures and Algorithms        数据结构与算法
分类描述：Covers data structures and analysis of algorithms. Roughly includes material in ACM Subject Classes E.1, E.2, F.2.1, and F.2.2.
涵盖数据结构和算法分析。大致包括ACM学科类E.1、E.2、F.2.1和F.2.2中的材料。
--

---
英文摘要：
  We consider the linear programming relaxation of an energy minimization problem for Markov Random Fields. The dual objective of this problem can be treated as a concave and unconstrained, but non-smooth function. The idea of smoothing the objective prior to optimization was recently proposed in a series of papers. Some of them suggested the idea to decrease the amount of smoothing (so called temperature) while getting closer to the optimum. However, no theoretical substantiation was provided. We propose an adaptive smoothing diminishing algorithm based on the duality gap between relaxed primal and dual objectives and demonstrate the efficiency of our approach with a smoothed version of Sequential Tree-Reweighted Message Passing (TRW-S) algorithm. The strategy is applicable to other algorithms as well, avoids adhoc tuning of the smoothing during iterations, and provably guarantees convergence to the optimum.
---
PDF链接：
https://arxiv.org/pdf/1210.4906