## 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 language | English (US) |
---|---|

Pages | 2867-2875 |

Number of pages | 9 |

State | Published - Jan 1 2017 |

Event | 31st AAAI Conference on Artificial Intelligence, AAAI 2017 - San Francisco, United States Duration: Feb 4 2017 → Feb 10 2017 |

### Conference

Conference | 31st AAAI Conference on Artificial Intelligence, AAAI 2017 |
---|---|

Country | United States |

City | San Francisco |

Period | 02/4/17 → 02/10/17 |

## ASJC Scopus subject areas

- Artificial Intelligence