  Binary optimization is a central problem in mathematical optimization and its
applications are abundant. To solve this problem, we propose a new class of
continuous optimization techniques which is based on Mathematical Programming
with Equilibrium Constraints (MPECs). We first reformulate the binary program
as an equivalent augmented biconvex optimization problem with a bilinear
equality constraint, then we propose two penalization/regularization methods
(exact penalty and alternating direction) to solve it. The resulting algorithms
seek desirable solutions to the original problem via solving a sequence of
linear programming convex relaxation subproblems. In addition, we prove that
both the penalty function and augmented Lagrangian function, induced by adding
the complementarity constraint to the objectives, are exact, i.e., they have
the same local and global minima with those of the original binary program when
the penalty parameter is over some threshold. The convergence of both
algorithms can be guaranteed, since they essentially reduce to block coordinate
descent in the literature. Finally, we demonstrate the effectiveness and
versatility of our methods on several important problems, including graph
bisection, constrained image segmentation, dense subgraph discovery, modularity
clustering and Markov random fields. Extensive experiments show that our
methods outperform existing popular techniques, such as iterative hard
thresholding, linear programming relaxation and semidefinite programming
relaxation.
