Dual Lagrangian Learning for Conic Optimization

• URL: http://arxiv.org/abs/2402.03086v2
• Date: Fri, 24 May 2024 15:53:01 GMT
• Title: Dual Lagrangian Learning for Conic Optimization
• Authors: Mathieu Tanneau, Pascal Van Hentenryck,
• Abstract summary: The paper introduces a systematic dual completion procedure, differentiable conic projection layers, and a self-supervised learning framework based on Lagrangian duality. It also provides closed-form dual completion formulae for broad classes of conic problems, which eliminate the need for costly implicit layers. The proposed methodology significantly outperforms a state-of-the-art learning-based method, and achieves 1000x speedups over commercial interior-point solvers with optimality gaps under 0.5% on average.
• Score: 18.006916033168494
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper presents Dual Lagrangian Learning (DLL), a principled learning methodology for dual conic optimization proxies. DLL leverages conic duality and the representation power of ML models to provide high-duality, dual-feasible solutions, and therefore valid Lagrangian dual bounds, for linear and nonlinear conic optimization problems. The paper introduces a systematic dual completion procedure, differentiable conic projection layers, and a self-supervised learning framework based on Lagrangian duality. It also provides closed-form dual completion formulae for broad classes of conic problems, which eliminate the need for costly implicit layers. The effectiveness of DLL is demonstrated on linear and nonlinear conic optimization problems. The proposed methodology significantly outperforms a state-of-the-art learning-based method, and achieves 1000x speedups over commercial interior-point solvers with optimality gaps under 0.5\% on average.

Related papers

• Majorization-Minimization Dual Stagewise Algorithm for Generalized Lasso [2.1066879371176395]
  We propose a majorization-minimization dual stagewise (MM-DUST) algorithm to efficiently trace out the full solution paths of the generalized lasso problem. We analyze the computational complexity of MM-DUST and establish the uniform convergence of the approximated solution paths.
  arXiv  Detail & Related papers  (2025-01-04T05:20:26Z)
• Learning Constrained Optimization with Deep Augmented Lagrangian Methods [54.22290715244502]
  A machine learning (ML) model is trained to emulate a constrained optimization solver. This paper proposes an alternative approach, in which the ML model is trained to predict dual solution estimates directly. It enables an end-to-end training scheme is which the dual objective is as a loss function, and solution estimates toward primal feasibility, emulating a Dual Ascent method.
  arXiv  Detail & Related papers  (2024-03-06T04:43:22Z)
• Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
  We study the Constrained Convex Decision Process (MDP), where the goal is to minimize a convex functional of the visitation measure. Design algorithms for a constrained convex MDP faces several challenges, including handling the large state space.
  arXiv  Detail & Related papers  (2024-02-16T16:35:18Z)
• Dual Interior-Point Optimization Learning [18.006916033168494]
  DIPL and DSL learn dual feasible solutions to parametric linear programs with bounded variables. They produce high-fidelity dual-feasible solutions to large-scale optimal power flow problems.
  arXiv  Detail & Related papers  (2024-02-04T20:06:20Z)
• Toward Rapid, Optimal, and Feasible Power Dispatch through Generalized Neural Mapping [0.0]
  We propose LOOP-LC 2.0 as a learning-based approach for solving the power dispatch problem. A notable advantage of the LOOP-LC 2.0 framework is its ability to ensure near-optimality and strict feasibility of solutions. We demonstrate the effectiveness of the LOOP-LC 2.0 methodology in terms of training speed, computational time, optimality, and solution feasibility.
  arXiv  Detail & Related papers  (2023-11-08T17:02:53Z)
• Hierarchical Optimization-Derived Learning [58.69200830655009]
  We establish a new framework, named Hierarchical ODL (HODL), to simultaneously investigate the intrinsic behaviors of optimization-derived model construction and its corresponding learning process. This is the first theoretical guarantee for these two coupled ODL components: optimization and learning.
  arXiv  Detail & Related papers  (2023-02-11T03:35:13Z)
• Lagrangian Method for Q-Function Learning (with Applications to Machine Translation) [0.0]
  The paper shows that the Lagrangian enjoys strong duality, in spite of its nonlinearity, which paves the way to a general Lagrangian method to Q-function learning.
  arXiv  Detail & Related papers  (2022-07-22T15:57:52Z)
• Meta-Learning with Neural Tangent Kernels [58.06951624702086]
  We propose the first meta-learning paradigm in the Reproducing Kernel Hilbert Space (RKHS) induced by the meta-model's Neural Tangent Kernel (NTK) Within this paradigm, we introduce two meta-learning algorithms, which no longer need a sub-optimal iterative inner-loop adaptation as in the MAML framework. We achieve this goal by 1) replacing the adaptation with a fast-adaptive regularizer in the RKHS; and 2) solving the adaptation analytically based on the NTK theory.
  arXiv  Detail & Related papers  (2021-02-07T20:53:23Z)
• An Online Method for A Class of Distributionally Robust Optimization with Non-Convex Objectives [54.29001037565384]
  We propose a practical online method for solving a class of online distributionally robust optimization (DRO) problems. Our studies demonstrate important applications in machine learning for improving the robustness of networks.
  arXiv  Detail & Related papers  (2020-06-17T20:19:25Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  We introduce a Cogradient Descent algorithm (CoGD) to address the bilinear problem. We solve one variable by considering its coupling relationship with the other, leading to a synchronous gradient descent. Our algorithm is applied to solve problems with one variable under the sparsity constraint.
  arXiv  Detail & Related papers  (2020-06-16T13:41:54Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.