An Exact Penalty Method for Binary Optimization Based on MPEC Formulation

By Ganzhao Yuan, Bernard Ghanem. 2017

50 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Numerical Analysis

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Neil Zhenqiang Gong
2. Binghui Wang
3. Victor C. M. Leung
4. Zhu Han
5. Xiaofei Wang
6. Jinyuan Jia
7. Yang Zhang
8. Le Zhang

In Computational Theory and Mathematics

1. Neil Zhenqiang Gong
2. Zhu Han
3. Binghui Wang

In Numerical Analysis

1. Neil Zhenqiang Gong
2. Binghui Wang

Citations in the corpus

• Attacking Graph-based Classification via Manipulating the Graph Structure (2019, methodology): “The optimization problem in Equation 19 can be solved exactly by the break point search method [72].”
• Hierarchical Edge Caching in Device-to-Device Aided Mobile Networks: Modeling, Optimization, and Design (2018, methodology): “Note that though the main idea of Algorithm 1 is similar to the proposed EPM in [41], Algorithm 1 is a more complex extension since it focuses on solving a biconvex optimization problem with 3-dimensional matrix variables while the proposed EPM in [41] aims to solve a bicon-vex optimization problem…”