An exact penalty method for binary optimization based on MPEC formulation

Ganzhao Yuan, Bernard Ghanem

Research output: Contribution to conferencePaperpeer-review

9 Scopus citations

Abstract

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)
Pages2867-2875
Number of pages9
StatePublished - Jan 1 2017
Event31st AAAI Conference on Artificial Intelligence, AAAI 2017 - San Francisco, United States
Duration: Feb 4 2017Feb 10 2017

Conference

Conference31st AAAI Conference on Artificial Intelligence, AAAI 2017
CountryUnited States
CitySan Francisco
Period02/4/1702/10/17

ASJC Scopus subject areas

  • Artificial Intelligence

Fingerprint 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