TY - GEN

T1 - An exact penalty method for binary optimization based on MPEC formulation

AU - Yuan, Ganzhao

AU - Ghanem, Bernard

N1 - KAUST Repository Item: Exported on 2020-12-29
Acknowledgements: This work was supported by the King Abdullah University of Science and Technology (KAUST) Office of Sponsored Research through the Visual Computing Center (VCC) funding. Yuan is also supported by NSF-China (61402182). A special thanks is also extended to Prof. Shaohua Pan and Dr. Li Shen (South China University of Technology) for their helpful discussions on this paper.

PY - 2017/1/1

Y1 - 2017/1/1

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/666700

UR - https://research.kaust.edu.sa/en/publications/an-exact-penalty-method-for-binary-optimization-based-on-mpec-for

UR - http://www.scopus.com/inward/record.url?scp=85030462096&partnerID=8YFLogxK

M3 - Conference contribution

SP - 2867

EP - 2875

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

PB - AAAI press

ER -