Self-supervised Equality Embedded Deep Lagrange Dual for Approximate Constrained Optimization

• URL: http://arxiv.org/abs/2306.06674v5
• Date: Mon, 23 Sep 2024 11:28:24 GMT
• Title: Self-supervised Equality Embedded Deep Lagrange Dual for Approximate Constrained Optimization
• Authors: Minsoo Kim, Hongseok Kim,
• Abstract summary: We propose deeprange dual embedding (DeepLDE) as a fast optimal approximators incorporating neural networks (NNs) We prove the convergence of DeepLDE and primal, nondual-learning method to impose inequality constraints. We show that the proposed DeepLDE solutions achieve the optimal Lag gap among all the smallest NN-based approaches.
• Score: 5.412875005737914
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Conventional solvers are often computationally expensive for constrained optimization, particularly in large-scale and time-critical problems. While this leads to a growing interest in using neural networks (NNs) as fast optimal solution approximators, incorporating the constraints with NNs is challenging. In this regard, we propose deep Lagrange dual with equality embedding (DeepLDE), a framework that learns to find an optimal solution without using labels. To ensure feasible solutions, we embed equality constraints into the NNs and train the NNs using the primal-dual method to impose inequality constraints. Furthermore, we prove the convergence of DeepLDE and show that the primal-dual learning method alone cannot ensure equality constraints without the help of equality embedding. Simulation results on convex, non-convex, and AC optimal power flow (AC-OPF) problems show that the proposed DeepLDE achieves the smallest optimality gap among all the NN-based approaches while always ensuring feasible solutions. Furthermore, the computation time of the proposed method is about 5 to 250 times faster than DC3 and the conventional solvers in solving constrained convex, non-convex optimization, and/or AC-OPF.

Related papers

• Lower Bounds and Optimal Algorithms for Non-Smooth Convex Decentralized Optimization over Time-Varying Networks [57.24087627267086]
  We consider the task of minimizing the sum of convex functions stored in a decentralized manner across the nodes of a communication network. Lower bounds on the number of decentralized communications and (sub)gradient computations required to solve the problem have been established. We develop the first optimal algorithm that matches these lower bounds and offers substantially improved theoretical performance compared to the existing state of the art.
  arXiv  Detail & Related papers  (2024-05-28T10:28:45Z)
• A two-phase-ACO algorithm for solving nonlinear optimization problems subjected to fuzzy relational equations [0.0]
  In this paper, we investigate nonlinear optimization problems whose constraints are defined as fuzzy relational equations (FRE) with feasible-min composition. The ability of an ant colony optimization algorithm (denoted by ACOR) to tackle algorithm problems and that of continuous ant colony optimization algorithm (denoted by ACO) to solve continuous optimization problems are discussed.
  arXiv  Detail & Related papers  (2024-05-17T09:24:07Z)
• Low-Rank Extragradient Methods for Scalable Semidefinite Optimization [0.0]
  We focus on high-dimensional and plausible settings in which the problem admits a low-rank solution. We provide several theoretical results proving that, under these circumstances, the well-known Extragradient method converges to a solution of the constrained optimization problem.
  arXiv  Detail & Related papers  (2024-02-14T10:48:00Z)
• Online Non-convex Optimization with Long-term Non-convex Constraints [2.033434950296318]
  A novel Follow-the-Perturbed-Leader type algorithm is proposed and analyzed for solving general long-term constrained optimization problems in online manner. The proposed algorithm is applied to tackle a long-term (extreme value) constrained river pollutant source identification problem.
  arXiv  Detail & Related papers  (2023-11-04T15:08:36Z)
• Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
  An agent aims to maximize the expected accumulated discounted reward subject to multiple constraints on its costs. A new dual approach is proposed with the integration of two ingredients: entropy regularized policy and Vaidya's dual. The proposed approach is shown to converge (with linear rate) to the global optimum.
  arXiv  Detail & Related papers  (2022-06-03T16:26:38Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Efficient Methods for Structured Nonconvex-Nonconcave Min-Max Optimization [98.0595480384208]
  We propose a generalization extraient spaces which converges to a stationary point. The algorithm applies not only to general $p$-normed spaces, but also to general $p$-dimensional vector spaces.
  arXiv  Detail & Related papers  (2020-10-31T21:35:42Z)
• Neural Networks for Encoding Dynamic Security-Constrained Optimal Power Flow [0.0]
  This paper introduces a framework to capture previously intractable optimization constraints and transform them to a mixed-integer linear program. We demonstrate our approach for power system operation considering N-1 security and small-signal stability, showing how it can efficiently obtain cost-optimal solutions.
  arXiv  Detail & Related papers  (2020-03-17T21:01:17Z)

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.