TY - JOUR
T1 - lp-Box ADMM: A Versatile Framework for Integer Programming
AU - Wu, Baoyuan
AU - Ghanem, Bernard
N1 - KAUST Repository Item: Exported on 2020-04-23
Acknowledgements: This work is supported supported by competitive research funding from King Abdullah University of Science and Technology (KAUST), and is partially supported by Tencent AI Lab.
PY - 2018/6/11
Y1 - 2018/6/11
N2 - 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
AB - 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
UR - http://hdl.handle.net/10754/628307
UR - https://ieeexplore.ieee.org/document/8378001/
UR - http://www.scopus.com/inward/record.url?scp=85048504588&partnerID=8YFLogxK
U2 - 10.1109/TPAMI.2018.2845842
DO - 10.1109/TPAMI.2018.2845842
M3 - Article
C2 - 29994196
AN - SCOPUS:85048504588
VL - 41
SP - 1695
EP - 1708
JO - IEEE Transactions on Pattern Analysis and Machine Intelligence
JF - IEEE Transactions on Pattern Analysis and Machine Intelligence
SN - 0162-8828
IS - 7
ER -