p-Box ADMM: A Versatile Framework for Integer Programming
- 11 June 2018
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 41 (7) , 1695-1708
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
Keywords
All Related Versions
Funding Information
- King Abdullah University of Science and Technology
- Tencent AI Lab
This publication has 45 references indexed in Scilit:
- Distributed Optimization and Statistical Learning via the Alternating Direction Method of MultipliersFoundations and Trends in Machine Learning, 2011
- On the copositive representation of binary and continuous nonconvex quadratic programsMathematical Programming, 2008
- "GrabCut"ACM Transactions on Graphics, 2004
- An experimental comparison of min-cut/max- flow algorithms for energy minimization in visionIEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Second order cone programming relaxation of nonconvex quadratic optimization problemsOptimization Methods and Software, 2001
- Normalized cuts and image segmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2000
- The Cutting-Plane Method for Solving Convex ProgramsJournal of the Society for Industrial and Applied Mathematics, 1960
- An Automatic Method of Solving Discrete Programming ProblemsEconometrica, 1960
- Algorithms for the Assignment and Transportation ProblemsJournal of the Society for Industrial and Applied Mathematics, 1957
- An algorithm for quadratic programmingNaval Research Logistics Quarterly, 1956