論文の概要: Distributed Unconstrained Optimization with Time-varying Cost Functions
- arxiv url: http://arxiv.org/abs/2212.09472v1
- Date: Mon, 12 Dec 2022 23:59:54 GMT
- ステータス: 処理完了
- システム内更新日: 2022-12-25 02:52:46.010182
- Title: Distributed Unconstrained Optimization with Time-varying Cost Functions
- Title(参考訳): 時間変動コスト関数を用いた分散制約なし最適化
- Authors: Amir-Salar Esteki and Solmaz S. Kia
- Abstract要約: 目的は、各時点の総コストを最小限に抑える最適な軌道を追跡することである。
提案手法は,2段階のダイナミックスから成り,まず第1段階と第2段階の局所的コストの導関数をサンプリングし,最適軌道への降下方向の推定を周期的に構築する。
提案手法の性能を示すために,アルゴリズムのパラメータとその局所状態の収束に対する効果を最適軌道に調整する数値実験を行った。
- 参考スコア(独自算出の注目度): 1.52292571922932
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we propose a novel solution for the distributed unconstrained
optimization problem where the total cost is the summation of time-varying
local cost functions of a group networked agents. The objective is to track the
optimal trajectory that minimizes the total cost at each time instant. Our
approach consists of a two-stage dynamics, where the first one samples the
first and second derivatives of the local costs periodically to construct an
estimate of the descent direction towards the optimal trajectory, and the
second one uses this estimate and a consensus term to drive local states
towards the time-varying solution while reaching consensus. The first part is
carried out by the implementation of a weighted average consensus algorithm in
the discrete-time framework and the second part is performed with a
continuous-time dynamics. Using the Lyapunov stability analysis, an upper bound
on the gradient of the total cost is obtained which is asymptotically reached.
This bound is characterized by the properties of the local costs. To
demonstrate the performance of the proposed method, a numerical example is
conducted that studies tuning the algorithm's parameters and their effects on
the convergence of local states to the optimal trajectory.
- Abstract(参考訳): 本稿では,グループネットワークエージェントの時間変動局所コスト関数の総和を総コストとする分散制約なし最適化問題に対する新しい解を提案する。
目的は、各時点の総コストを最小限に抑える最適な軌道を追跡することである。
提案手法は,2段階のダイナミックスから成り,第1段階と第2段階の局所的コストの導関数を定期的にサンプリングして最適軌道への降下方向の推定を行い,第2段階では,この推定とコンセンサス項を用いて局所状態の時間変化解への誘導を行う。
第1部は離散時間フレームワークにおける重み付き平均コンセンサスアルゴリズムの実装により実行され、第2部は連続時間ダイナミクスで実行される。
リアプノフ安定性解析を用いて、漸近的に到達した総コストの勾配上の上限を求める。
この境界は地域費用の特性によって特徴づけられる。
提案手法の性能を示すために,アルゴリズムのパラメータをチューニングした数値実験を行い,局所状態の最適軌道への収束に対する効果について検討した。
関連論文リスト
- Accelerated Distributed Aggregative Optimization [5.5491171448159715]
本稿では,分散集約最適化問題の解法として,DAGT-HBとDAGT-NESという2つの新しいアルゴリズムを提案する。
DAGT-HBとDAGT-NESのアルゴリズムは、大域的な$mathbfR-$linear収束率で最適解に収束できる。
論文 参考訳(メタデータ) (2023-04-17T08:11:01Z) - Fast Computation of Optimal Transport via Entropy-Regularized
Extragradient Methods [98.85583323658366]
2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。
本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
論文 参考訳(メタデータ) (2023-01-30T15:46:39Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal
Convergence Guarantee [96.71652414591051]
本研究では,非制約問題に対するグローバルなサドル点を求めるために,不正確なニュートン型正規化手法を提案し,解析する。
提案アルゴリズムは,有界集合内に留まるイテレートを生成し,制限されたイテレート関数の項で$O(-2/3)$ギャップに収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Faster Algorithm and Sharper Analysis for Constrained Markov Decision
Process [56.55075925645864]
制約付き意思決定プロセス (CMDP) の問題点について検討し, エージェントは, 複数の制約を条件として, 期待される累積割引報酬を最大化することを目的とする。
新しいユーティリティ・デュアル凸法は、正規化ポリシー、双対正則化、ネステロフの勾配降下双対という3つの要素の新たな統合によって提案される。
これは、凸制約を受ける全ての複雑性最適化に対して、非凸CMDP問題が$mathcal O (1/epsilon)$の低い境界に達する最初の実演である。
論文 参考訳(メタデータ) (2021-10-20T02:57:21Z) - Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。
これらの問題に対する新規で簡単な最適化法を開発した。
結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
論文 参考訳(メタデータ) (2021-09-23T17:38:24Z) - Estimation of Stationary Optimal Transport Plans [4.662321040754878]
有限値量が定常的に時間とともに動的に進化する最適輸送問題について検討する。
最適接合と最適接合コストの両方を推定する。
最適接合問題のエントロピーペナル化版に一貫性と速度解析を拡張した。
論文 参考訳(メタデータ) (2021-07-25T17:46:21Z) - Momentum Accelerates the Convergence of Stochastic AUPRC Maximization [80.8226518642952]
高精度リコール曲線(AUPRC)に基づく領域の最適化について検討し,不均衡なタスクに広く利用されている。
我々は、$O (1/epsilon4)$のより優れた反復による、$epsilon$定常解を見つけるための新しい運動量法を開発する。
また,O(1/epsilon4)$と同じ複雑さを持つ適応手法の新たなファミリを設計し,実際により高速な収束を享受する。
論文 参考訳(メタデータ) (2021-07-02T16:21:52Z) - Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex
Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。
我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。
我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文 参考訳(メタデータ) (2021-06-08T15:54:44Z) - Online Stochastic Optimization with Wasserstein Based Non-stationarity [12.91020811577007]
有限期間の地平線上の複数の予算制約を持つ一般的なオンライン最適化問題を検討する。
意思決定者の目標は、予算制約の対象となる累積報酬を最大化することである。
この定式化は、オンラインリニアプログラミングやネットワーク収益管理を含む幅広いアプリケーションを取り込む。
論文 参考訳(メタデータ) (2020-12-13T04:47:37Z) - GTAdam: Gradient Tracking with Adaptive Momentum for Distributed Online
Optimization [4.103281325880475]
本稿では、中央コーディネータを使わずに、局所的な計算と通信によって、オンライン最適化問題を分散的に解決することを目的とした、計算機エージェントのネットワークを扱う。
本稿では,適応運動量推定法(GTAdam)を用いた勾配追従法と,勾配の1次および2次運動量推定法を組み合わせた勾配追従法を提案する。
マルチエージェント学習によるこれらの数値実験では、GTAdamは最先端の分散最適化手法よりも優れている。
論文 参考訳(メタデータ) (2020-09-03T15:20:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。