Combining Constrained Diffusion Models and Numerical Solvers for Efficient and Robust Non-Convex Trajectory Optimization

• URL: http://arxiv.org/abs/2403.05571v3
• Date: Sun, 26 May 2024 16:52:21 GMT
• Title: Combining Constrained Diffusion Models and Numerical Solvers for Efficient and Robust Non-Convex Trajectory Optimization
• Authors: Anjian Li, Zihan Ding, Adji Bousso Dieng, Ryne Beeson,
• Abstract summary: We introduce a general framework that combines diffusion models and numerical optimization solvers. We develop a novel constrained diffusion model to approximate the true distribution of locally optimal solutions. Experiments verify the improved constraint satisfaction and computational efficiency with 4$times$ to 30$times$ acceleration.
• Score: 9.28162057044835
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by the need to solve open-loop optimal control problems with computational efficiency and reliable constraint satisfaction, we introduce a general framework that combines diffusion models and numerical optimization solvers. Optimal control problems are rarely solvable in closed form, hence they are often transcribed into numerical trajectory optimization problems, which then require initial guesses. These initial guesses are supplied in our framework by diffusion models. To mitigate the effect of samples that violate the problem constraints, we develop a novel constrained diffusion model to approximate the true distribution of locally optimal solutions with an additional constraint violation loss in training. To further enhance the robustness, the diffusion samples as initial guesses are fed to the numerical solver to refine and derive final optimal (and hence feasible) solutions. Experimental evaluations on three tasks verify the improved constraint satisfaction and computational efficiency with 4$\times$ to 30$\times$ acceleration using our proposed framework, which generalizes across trajectory optimization problems and scales well with problem complexity.

Related papers

• Exploring the Boundary of Diffusion-based Methods for Solving Constrained Optimization [46.75288477458697]
  We propose a novel diffusion-based framework for Continuous Constrained Optimization problems called DiOpt.<n>DiOpt operates in two distinct phases: an initial warm-start phase, implemented via supervised learning, followed by a bootstrapping phase.<n>It is designed to iteratively refine solutions, thereby improving the objective function while rigorously satisfying problem constraints.
  arXiv  Detail & Related papers  (2025-02-14T17:43:08Z)
• Diffusion Models as Network Optimizers: Explorations and Analysis [71.69869025878856]
  generative diffusion models (GDMs) have emerged as a promising new approach to network optimization. In this study, we first explore the intrinsic characteristics of generative models. We provide a concise theoretical and intuitive demonstration of the advantages of generative models over discriminative network optimization.
  arXiv  Detail & Related papers  (2024-11-01T09:05:47Z)
• Self-Supervised Learning of Iterative Solvers for Constrained Optimization [0.0]
  We propose a learning-based iterative solver for constrained optimization. It can obtain very fast and accurate solutions by customizing the solver to a specific parametric optimization problem. A novel loss function based on the Karush-Kuhn-Tucker conditions of optimality is introduced, enabling fully self-supervised training of both neural networks.
  arXiv  Detail & Related papers  (2024-09-12T14:17:23Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  Diffusion generative models can consider a broader range of solutions and exhibit stronger generalization by learning parameters. We propose a new framework, which leverages intrinsic distribution learning of diffusion generative models to learn high-quality solutions.
  arXiv  Detail & Related papers  (2024-08-13T07:56:21Z)
• DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems [37.205311971072405]
  DISCO is an efficient DIffusion solver for large-scale Combinatorial Optimization problems. It constrains the sampling space to a more meaningful domain guided by solution residues, while preserving the multi-modal properties of the output distributions. It delivers strong performance on large-scale Traveling Salesman Problems and challenging Maximal Independent Set benchmarks, with inference time up to 5.28 times faster than other diffusion alternatives.
  arXiv  Detail & Related papers  (2024-06-28T07:36:31Z)
• Diffusion Models as Constrained Samplers for Optimization with Unknown Constraints [42.47298301874283]
  We propose to perform optimization within the data manifold using diffusion models. Depending on the differentiability of the objective function, we propose two different sampling methods. Our method achieves better or comparable performance with previous state-of-the-art baselines.
  arXiv  Detail & Related papers  (2024-02-28T03:09:12Z)
• Analyzing and Enhancing the Backward-Pass Convergence of Unrolled Optimization [50.38518771642365]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. A central challenge in this setting is backpropagation through the solution of an optimization problem, which often lacks a closed form. This paper provides theoretical insights into the backward pass of unrolled optimization, showing that it is equivalent to the solution of a linear system by a particular iterative method. A system called Folded Optimization is proposed to construct more efficient backpropagation rules from unrolled solver implementations.
  arXiv  Detail & Related papers  (2023-12-28T23:15:18Z)
• Reducing the Need for Backpropagation and Discovering Better Optima With Explicit Optimizations of Neural Networks [4.807347156077897]
  We propose a computationally efficient alternative for optimizing neural networks. We derive an explicit solution to a simple feed-forward language model. We show that explicit solutions perform near-optimality in experiments.
  arXiv  Detail & Related papers  (2023-11-13T17:38:07Z)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• A deep learning method for solving stochastic optimal control problems driven by fully-coupled FBSDEs [1.0703175070560689]
  We first transform the problem into a Stackelberg differential game problem (leader-follower problem) We compute two examples of the investment-consumption problem solved through utility models. The results of both examples demonstrate the effectiveness of our proposed algorithm.
  arXiv  Detail & Related papers  (2022-04-12T13:31:19Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• Automatically Learning Compact Quality-aware Surrogates for Optimization Problems [55.94450542785096]
  Solving optimization problems with unknown parameters requires learning a predictive model to predict the values of the unknown parameters and then solving the problem using these values. Recent work has shown that including the optimization problem as a layer in a complex training model pipeline results in predictions of iteration of unobserved decision making. We show that we can improve solution quality by learning a low-dimensional surrogate model of a large optimization problem.
  arXiv  Detail & Related papers  (2020-06-18T19:11: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.