AN EFFICIENT UNSUPERVISED FRAMEWORK FOR CONVEX QUADRATIC PROGRAMS VIA DEEP UNROLLING

作     者：Yang, Linxin Li, Bingheng Ding, Tian Wu, Jianghua Wang, Akang Wang, Yuyi Tang, Jiliang Sun, Ruoyu Luo, Xiaodong 

作者机构：School of Data Science The Chinese University of Hong Kong Shenzhen China Shenzhen International Center for Industrial and Applied Mathematics Shenzhen Research Institute of Big Data China Michigan State University United States Tengen Intelligence Institute 

出 版 物：《arXiv》 (arXiv)

年 卷 期：2024年

核心收录：

主　　题：Unsupervised learning 

摘      要：Quadratic programs (QPs) arise in various domains such as machine learning, finance, and control. Recently, learning-enhanced primal-dual hybrid gradient (PDHG) methods have shown great potential in addressing large-scale linear programs;however, this approach has not been extended to QPs. In this work, we focus on unrolling PDQP, a PDHG algorithm specialized for convex QPs. Specifically, we propose a neural network model called PDQP-net to learn optimal QP solutions. Theoretically, we demonstrate that a PDQP-net of polynomial size can align with the PDQP algorithm, returning optimal primal-dual solution pairs. We propose an unsupervised method that incorporates KKT conditions into the loss function. Unlike the standard learning-to-optimize framework that requires optimization solutions generated by solvers, our unsupervised method adjusts the network weights directly from the evaluation of the primal-dual gap. This method has two benefits over supervised learning: first, it helps generate better primal-dual gap since the primal-dual gap is in the objective function;second, it does not require solvers. We show that PDQP-net trained in this unsupervised manner can effectively approximate optimal QP solutions. Extensive numerical experiments confirm our findings, indicating that using PDQP-net predictions to warm-start PDQP can achieve up to 45% acceleration on QP instances. Moreover, it achieves 14% to 31% acceleration on out-of-distribution instances. © 2024, CC BY.