Dual Interior Point Optimization Learning

• DOI: 10.48550/arxiv.2402.02596
• Publication Date: 2024-01-01
• Authors: Klamkin, Michael; Tanneau, Mathieu; Van Hentenryck, P...
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; Optimization and Control (math.OC); FOS: Mathematics; Mathematics - Optimization and Control; Machine Learning (cs.LG)

In many practical applications of constrained optimization, scale and solving time limits make traditional optimization solvers prohibitively slow. Thus, the research question of how to design optimization proxies -- machine learning models that produce high-quality solutions -- has recently received significant attention. Orthogonal to this research thread which focuses on learning primal solutions, this paper studies how to learn dual feasible solutions that complement primal approaches and provide quality guarantees. The paper makes two distinct contributions. First, to train dual linear optimization proxies, the paper proposes a smoothed self-supervised loss function that augments the objective function with a dual penalty term. Second, the paper proposes a novel dual completion strategy that guarantees dual feasibility by solving a convex optimization problem. Moreover, the paper derives closed-form solutions to this completion optimization for several classes of dual penalties, eliminating the need for computationally-heavy implicit layers. Numerical results are presented on large linear optimization problems and demonstrate the effectiveness of the proposed approach. The proposed dual completion outperforms methods for learning optimization proxies which do not exploit the structure of the dual problem. Compared to commercial optimization solvers, the learned dual proxies achieve optimality gaps below $1\%$ and several orders of magnitude speedups.