論文の概要: Time-Varying Convex Optimization with $O(n)$ Computational Complexity
- arxiv url: http://arxiv.org/abs/2410.15009v2
- Date: Thu, 24 Oct 2024 20:09:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-28 13:33:38.075489
- Title: Time-Varying Convex Optimization with $O(n)$ Computational Complexity
- Title（参考訳）: O(n)$Computational Complexityを用いた時間変数凸最適化
- Authors: M. Rostami, S. S. Kia,
- Abstract要約: コスト関数が時間とともに変化する非拘束凸最適化の問題を考える。
提案アルゴリズムは,決定変数に対するコスト関数の1次微分のみを必要とする。
具体的には、提案アルゴリズムは、計算コストを1タイムステップあたり$(n3)$から$O(n)$に削減する。
- 参考スコア（独自算出の注目度）: 0.0
- License:
- Abstract: In this article, we consider the problem of unconstrained time-varying convex optimization, where the cost function changes with time. We provide an in-depth technical analysis of the problem and argue why freezing the cost at each time step and taking finite steps toward the minimizer is not the best tracking solution for this problem. We propose a set of algorithms that by taking into account the temporal variation of the cost aim to reduce the tracking error of the time-varying minimizer of the problem. The main contribution of our work is that our proposed algorithms only require the first-order derivatives of the cost function with respect to the decision variable. This approach significantly reduces computational cost compared to the existing algorithms, which use the inverse of the Hessian of the cost. Specifically, the proposed algorithms reduce the computational cost from $O(n^3)$ to $O(n)$ per timestep, where $n$ is the size of the decision variable. Avoiding the inverse of the Hessian also makes our algorithms applicable to non-convex optimization problems. We refer to these algorithms as $O(n)$-algorithms. These $O(n)$-algorithms are designed to solve the problem for different scenarios based on the available temporal information about the cost. We illustrate our results through various examples, including the solution of a model predictive control problem framed as a convex optimization problem with a streaming time-varying cost function.
- Abstract（参考訳）: 本稿では,コスト関数が時間とともに変化するような,制約のない時間変化凸最適化の問題について考察する。
この問題の詳細な技術的分析を行い、各段階でコストを凍結し、最小化に向けて有限のステップを踏むことが、この問題の最良の追跡ソリューションではないことを論じる。
本稿では,コストの時間的変動を考慮したアルゴリズムを提案する。
我々の研究の主な貢献は、提案アルゴリズムが決定変数に関してコスト関数の1次微分のみを必要とすることである。
このアプローチは、既存のアルゴリズムと比較して計算コストを大幅に削減する。
具体的には、提案アルゴリズムは、計算コストを1タイムステップあたり$O(n^3)$から$O(n)$に減らし、$n$は決定変数のサイズである。
ヘッセンの逆の回避により、我々のアルゴリズムは非凸最適化問題にも適用できる。
これらのアルゴリズムを$O(n)$-algorithmsと呼ぶ。
これらの$O(n)$-algorithmは、コストに関する時間的情報に基づいて、異なるシナリオの問題を解決するように設計されている。
本稿では,ストリーム時間変動コスト関数を用いた凸最適化問題として,モデル予測制御問題の解法を含む,様々な例を通して結果について述べる。
関連論文リスト
- First-Order Dynamic Optimization for Streaming Convex Costs [0.0]
最適解を有界誤差で追従する手法を開発する。
本アルゴリズムはコスト関数の1次微分を用いてのみ実行される。
論文 参考訳（メタデータ） (2023-10-11T22:41:00Z) - Deterministic Nonsmooth Nonconvex Optimization [94.01526844386977]
次元自由な次元自由アルゴリズムを得るにはランダム化が必要であることを示す。
我々のアルゴリズムは、ReLUネットワークを最適化する最初の決定論的次元自由アルゴリズムを得る。
論文 参考訳（メタデータ） (2023-02-16T13:57:19Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳（メタデータ） (2023-02-01T08:50:48Z) - Portfolio optimization with discrete simulated annealing [0.0]
離散凸関数と非凸コスト関数の存在下で最適なポートフォリオを求めるための整数最適化法を提案する。
これにより、与えられた品質でソリューションを実現できる。
論文 参考訳（メタデータ） (2022-10-03T10:39:05Z) - A Near-Optimal Algorithm for Univariate Zeroth-Order Budget Convex
Optimization [4.608510640547952]
我々は、Dy Searchのほぼ最適最適化誤差を保証する。
誤差境界における大域リプシッツ定数への古典的依存は、予算の粒度のアーティファクトであることを示す。
論文 参考訳（メタデータ） (2022-08-13T19:57:04Z) - Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。
本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
論文 参考訳（メタデータ） (2021-06-02T22:03:36Z) - Divide and Learn: A Divide and Conquer Approach for Predict+Optimize [50.03608569227359]
予測+最適化問題は、予測係数を使用する最適化プロブレムと、確率係数の機械学習を組み合わせる。
本稿では, 予測係数を1次線形関数として, 最適化問題の損失を直接表現する方法を示す。
本稿では,この制約を伴わずに最適化問題に対処し,最適化損失を用いてその係数を予測する新しい分割アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-04T00:26:56Z) - A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis
and Application to Actor-Critic [142.1492359556374]
双レベル最適化は、2レベル構造を示す問題のクラスである。
このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。
本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
論文 参考訳（メタデータ） (2020-07-10T05:20:02Z) - Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。
Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。
本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
論文 参考訳（メタデータ） (2020-05-10T19:52:03Z) - Constrained Multiagent Rollout and Multidimensional Assignment with the
Auction Algorithm [0.0]
本稿では,制約付き決定論的動的プログラミングに適用可能なロールアウトアルゴリズムの拡張について考察する。
提案手法では,ベースが実現可能な解を生成する場合,ロールアウトアルゴリズムはコスト改善特性を有することを示す。
コスト改善特性は計算要求を大幅に削減した代替実装で維持されていることを示す。
論文 参考訳（メタデータ） (2020-02-18T07:09:06Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。