Wu Baoyuan, Ghanem Bernard
IEEE Trans Pattern Anal Mach Intell. 2019 Jul;41(7):1695-1708. doi: 10.1109/TPAMI.2018.2845842. Epub 2018 Jun 11.
This paper revisits the integer programming (IP) problem, which plays a fundamental role in many computer vision and machine learning applications. The literature abounds with many seminal works that address this problem, some focusing on continuous approaches (e.g., linear program relaxation), while others on discrete ones (e.g., min-cut). However, since many of these methods are designed to solve specific IP forms, they cannot adequately satisfy the simultaneous requirements of accuracy, feasibility, and scalability. To this end, we propose a novel and versatile framework called $\ell _p$ℓp-box ADMM, which is based on two main ideas. (1) The discrete constraint is equivalently replaced by the intersection of a box and an $\ell _p$ℓp-norm sphere. (2) We infuse this equivalence into the Alternating Direction Method of Multipliers (ADMM) framework to handle the continuous constraints separately and to harness its attractive properties. More importantly, the ADMM update steps can lead to manageable sub-problems in the continuous domain. To demonstrate its efficacy, we apply it to an optimization form that occurs often in computer vision and machine learning, namely binary quadratic programming (BQP). In this case, the ADMM steps are simple, computationally efficient. Moreover, we present the theoretic analysis about the global convergence of the $\ell _p$ℓp-box ADMM through adding a perturbation with the sufficiently small factor $\epsilon$ε to the original IP problem. Specifically, the globally converged solution generated by $\ell _p$ℓp-box ADMM for the perturbed IP problem will be close to the stationary and feasible point of the original IP problem within $O(\epsilon)$O(ε). We demonstrate the applicability of $\ell _p$ℓp-box ADMM on three important applications: MRF energy minimization, graph matching, and clustering. Results clearly show that it significantly outperforms existing generic IP solvers both in runtime and objective. It also achieves very competitive performance to state-of-the-art methods designed specifically for these applications.
本文重新审视整数规划（IP）问题，该问题在许多计算机视觉和机器学习应用中起着基础性作用。文献中有许多开创性的工作致力于解决此问题，一些专注于连续方法（例如线性规划松弛），而另一些则关注离散方法（例如最小割）。然而，由于这些方法中的许多都是为解决特定的IP形式而设计的，它们无法充分满足准确性、可行性和可扩展性的同时要求。为此，我们提出了一种新颖且通用的框架，称为$\ell _p$ℓp-box ADMM，它基于两个主要思想。（1）离散约束被等效地替换为一个盒子和一个$\ell _p$ℓp范数球体的交集。（2）我们将这种等效性融入交替方向乘子法（ADMM）框架中，以分别处理连续约束并利用其吸引人的特性。更重要的是，ADMM更新步骤可以在连续域中导致可处理的子问题。为了证明其有效性，我们将其应用于计算机视觉和机器学习中经常出现的一种优化形式，即二元二次规划（BQP）。在这种情况下，ADMM步骤简单且计算效率高。此外，我们通过向原始IP问题添加一个因子$\epsilon$ε足够小的扰动，给出了关于$\ell _p$ℓp-box ADMM全局收敛性的理论分析。具体而言，$\ell _p$ℓp-box ADMM为扰动后的IP问题生成的全局收敛解将在$O(\epsilon)$O(ε)范围内接近原始IP问题的驻点和可行点。我们在三个重要应用中展示了$\ell _p$ℓp-box ADMM的适用性：马尔可夫随机场（MRF）能量最小化、图匹配和聚类。结果清楚地表明，它在运行时和目标方面均显著优于现有的通用IP求解器。它在针对这些应用专门设计的最先进方法方面也取得了极具竞争力的性能。
