An exact penalty method for binary optimization based on MPEC formulation

Ganzhao Yuan, Bernard Ghanem

Research output: Chapter in Book/Report/Conference proceedingConference contribution

17 Scopus citations


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 an exact penalty method to solve it. The resulting algorithm seeks a desirable solution to the original problem via solving a sequence of linear programming convex relaxation subproblems. In addition, we prove that the penalty function, induced by adding the complementarity constraint to the objective, is exact, i.e., it has the same local and global minima with those of the original binary program when the penalty parameter is over some threshold. The convergence of the algorithm can be guaranteed, since it essentially reduces to block coordinate descent in the literature. Finally, we demonstrate the effectiveness of our method on the problem of dense subgraph discovery. Extensive experiments show that our method outperforms existing techniques, such as iterative hard thresholding and linear programming relaxation.
Original languageEnglish (US)
Title of host publication31st AAAI Conference on Artificial Intelligence, AAAI 2017
PublisherAAAI press
Number of pages9
StatePublished - Jan 1 2017


Dive into the research topics of 'An exact penalty method for binary optimization based on MPEC formulation'. Together they form a unique fingerprint.

Cite this