lp-Box ADMM: A Versatile Framework for Integer Programming

Baoyuan Wu, Bernard Ghanem

Research output: Contribution to journalArticlepeer-review

10 Scopus citations

Abstract

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 $l_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 $l_p$ -norm sphere. (2) We infuse this equivalence into the ADMM (Alternating Direction Method of Multipliers) 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 $l_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 $l_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)$ . We demonstrate the applicability of $l_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
Original languageEnglish (US)
Pages (from-to)1695-1708
Number of pages14
JournalIEEE Transactions on Pattern Analysis and Machine Intelligence
Volume41
Issue number7
DOIs
StatePublished - Jun 11 2018

Fingerprint Dive into the research topics of 'lp-Box ADMM: A Versatile Framework for Integer Programming'. Together they form a unique fingerprint.

Cite this