論文の概要: $A^*$ for Graphs of Convex Sets

• arxiv url: http://arxiv.org/abs/2407.17413v2
• Date: Thu, 25 Jul 2024 02:10:08 GMT
• ステータス: 処理完了
• システム内更新日: 2024-07-26 12:59:24.406585
• Title: $A^*$ for Graphs of Convex Sets
• Title（参考訳）: 凸集合グラフの$A^*$
• Authors: Kaarthik Sundar, Sivakumar Rathinam,
• Abstract要約: 本稿では,既存の凸プログラミングに基づくアプローチを情報と融合して最適性を保証する新しいアルゴリズムを提案する。 我々の方法は$A*$にインスパイアされ、指定された頂点の部分集合から最優先的な手順を開始し、さらなる成長が不可能かつ有益になるまで反復的に拡張する。
• 参考スコア（独自算出の注目度）: 7.9756690088226145
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We present a novel algorithm that fuses the existing convex-programming based approach with heuristic information to find optimality guarantees and near-optimal paths for the Shortest Path Problem in the Graph of Convex Sets (SPP-GCS). Our method, inspired by $A^*$, initiates a best-first-like procedure from a designated subset of vertices and iteratively expands it until further growth is neither possible nor beneficial. Traditionally, obtaining solutions with bounds for an optimization problem involves solving a relaxation, modifying the relaxed solution to a feasible one, and then comparing the two solutions to establish bounds. However, for SPP-GCS, we demonstrate that reversing this process can be more advantageous, especially with Euclidean travel costs. In other words, we initially employ $A^*$ to find a feasible solution for SPP-GCS, then solve a convex relaxation restricted to the vertices explored by $A^*$ to obtain a relaxed solution, and finally, compare the solutions to derive bounds. We present numerical results to highlight the advantages of our algorithm over the existing approach in terms of the sizes of the convex programs solved and computation time.
• Abstract（参考訳）: 本稿では,既存の凸プログラミングに基づくアプローチをヒューリスティック情報と融合して,グラフ・オブ・凸集合(SPP-GCS)における最短経路問題に対する最適性保証と準最適経路を求めるアルゴリズムを提案する。 我々の方法は$A^*$にインスパイアされ、指定された頂点の部分集合から最優先的な手順を開始し、さらなる成長が不可能かつ有益になるまで反復的に拡張する。 伝統的に、最適化問題に対する境界付き解を得るには、緩和を解くこと、緩和された解を実現可能なものに修正すること、そして2つの解を比較して境界を確立することが含まれる。 しかし、SPP-GCSでは、特にユークリッド旅行コストにおいて、このプロセスの逆転の方が有利であることを示す。 言い換えれば、まず最初に$A^*$ を用いて SPP-GCS の実現可能な解を求め、次に、$A^*$ で探索された頂点に制限された凸緩和を解いて緩和解を得る。 本稿では,コンベックスプログラムのサイズや計算時間の観点から,既存手法に対するアルゴリズムの利点を明らかにするために,数値計算結果を提案する。

関連論文リスト

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• Reduced Contraction Costs of Corner-Transfer Methods for PEPS [0.0]
  無限に投影された絡み合ったペア状態の収縮を抑えるための最優先計算コストを削減できる近似法を提案する。 計算コストの改善により、大きな結合次元の計算が可能となり、そのポテンシャルを拡大して課題を解決することができる。
  論文  参考訳（メタデータ） (2023-06-14T02:54:12Z)
• Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
  我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。 これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
  論文  参考訳（メタデータ） (2023-02-01T08:50:48Z)
• Efficient First-order Methods for Convex Optimization with Strongly Convex Function Constraints [3.667453772837954]
  強い凸関数制約を受ける凸関数を最小化する方法を示す。 有限個の結果に独立な意味を持つような空間パターンを同定する。
  論文  参考訳（メタデータ） (2022-12-21T16:04:53Z)
• Functional Constrained Optimization for Risk Aversion and Sparsity Control [7.561780884831967]
  リスクとスパーシリティの要件は、ポートフォリオ最適化、アソート計画、放射線計画など、多くのアプリケーションで同時に実施する必要がある。 本稿では,これらの課題に対して凸あるいはスパース軌道を生成するレベル条件勾配(LCG)法を提案する。 提案手法は,極小勾配を解くための内部条件近似(CGO)を最適値のレベル1セット投影することを示す。
  論文  参考訳（メタデータ） (2022-10-11T02:51:51Z)
• Accelerated first-order methods for convex optimization with locally Lipschitz continuous gradient [0.0]
  まず,Lipschitz連続勾配 (LLCG) を用いた非拘束凸最適化について検討し,それを解決するための加速近位勾配 (APG) 法を提案する。 提案手法は検証可能な終端基準を備えており、演算複雑性は$cal O(varepsilon-1/2log varepsilon-1)$である。 提案手法の性能を実証するために,予備的な数値計算結果を示す。
  論文  参考訳（メタデータ） (2022-06-02T10:34:26Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。 新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。 これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
  論文  参考訳（メタデータ） (2021-10-20T02:57:21Z)
• Lower Complexity Bounds of Finite-Sum Optimization Problems: The Results and Construction [18.65143269806133]
  我々は、個々のコンポーネントごとに勾配および近位オラクルにアクセスできる近位インクリメンタルファーストオーダー(PIFO)アルゴリズムを検討する。 古典的な例の三対角行列を$n$群に分割する逆問題を構築するための新しいアプローチを開発する。
  論文  参考訳（メタデータ） (2021-03-15T11:20:31Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。