論文の概要: Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm

• arxiv url: http://arxiv.org/abs/2402.15029v1
• Date: Fri, 23 Feb 2024 00:07:34 GMT
• ステータス: 処理完了
• システム内更新日: 2024-02-26 15:59:00.064273
• Title: Calculating the expected value function of a two-stage stochastic optimization program with a quantum algorithm
• Title（参考訳）: 量子アルゴリズムを用いた2段階確率最適化プログラムの期待値関数の計算
• Authors: Caleb Rotello, Peter Graf, Matthew Reynolds, Cody James Winkleblack, Wesley Jones
• Abstract要約: 2段階の最適化では、将来の決定の期待されるコストを計算し、現在の最良の決定を知らせる。 本研究では,2段階最適化問題における期待値関数を,確率変数の複雑性から大きく独立して推定する量子アルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Stochastic optimization problems are powerful models for the operation of systems under uncertainty and are in general computationally intensive to solve. Two-stage stochastic optimization is one such problem, where the objective function involves calculating the expected cost of future decisions to inform the best decision in the present. In general, even approximating this expectation value is a #P-Hard problem. We provide a quantum algorithm to estimate the expected value function in a two-stage stochastic optimization problem in time complexity largely independent from the complexity of the random variable. Our algorithm works in two steps: (1) By representing the random variable in a register of qubits and using this register as control logic for a cost Hamiltonian acting on the primary system of qubits, we use the quantum alternating operator ansatz (QAOA) with operator angles following an annealing schedule to converge to the minimal decision for each scenario in parallel. (2) We then use Quantum Amplitude Estimation (QAE) to approximate the expected value function of the per-scenario optimized wavefunction. We show that the annealing time of the procedure in (1) is independent of the number of scenarios in the probability distribution. Additionally, estimation error in QAE converges inverse-linear in the number of "repetitions" of the algorithm, as opposed to converging as the inverse of the square root in traditional Monte Carlo sampling. Because both QAOA and QAE are expected to have polynomial advantage over their classical computing counterparts, we expect our algorithm to have polynomial advantage over classical methods to compute the expected value function. We implement our algorithms for a simple optimization problem inspired by operating the power grid with renewable generation and uncertainty in the weather, and give numerical evidence to support our arguments.
• Abstract（参考訳）: 確率的最適化問題は不確実性の下でのシステムの操作の強力なモデルであり、一般に計算集約的な解法である。 2段階確率最適化は、目標関数が将来の決定の予測コストを計算し、現在の最良の決定を知らせる問題である。 一般に、この期待値の近似でさえ#pハード問題である。 本稿では,2段階確率最適化問題における期待値関数を,確率変数の複雑性から大きく独立して推定する量子アルゴリズムを提案する。 提案アルゴリズムは,(1) キュービットのレジスタにランダム変数を表現し,このレジスタをコストハミルトニアンがキュービットのプライマリシステムに作用する制御論理として用いることにより,演算子アンサッツ(QAOA)をアニーリングスケジュールに従って演算子アンサッツを用いて,各シナリオの最小決定に並列に収束させる。 次に、量子振幅推定(QAE)を用いて、シナリオごとの最適化波動関数の期待値関数を近似する。 1)における手順のアニール時間は,確率分布のシナリオ数とは無関係であることを示す。 さらに、qaeにおける推定誤差は、従来のモンテカルロサンプリングにおける平方根の逆収束とは対照的に、アルゴリズムの「繰り返し」数で逆線形に収束する。 QAOA と QAE はいずれも,従来の計算法に比べて多項式の優位性が期待されているため,我々のアルゴリズムは期待値関数を計算するために,古典的手法よりも多項式の優位性が期待できる。 我々は,再生可能エネルギーと気象の不確実性を備えた電力網の運用に触発された簡単な最適化問題に対してアルゴリズムを実装し,議論を裏付ける数値的証拠を与える。

関連論文リスト

• Stochastic Optimization for Non-convex Problem with Inexact Hessian Matrix, Gradient, and Function [99.31457740916815]
  信頼領域(TR)と立方体を用いた適応正則化は、非常に魅力的な理論的性質を持つことが証明されている。 TR法とARC法はヘッセン関数,勾配関数,関数値の非コンパクトな計算を同時に行うことができることを示す。
  論文  参考訳（メタデータ） (2023-10-18T10:29:58Z)
• Algorithmic Cluster Expansions for Quantum Problems [0.0]
  計算問題のクラスに対して近似アルゴリズムを開発するための一般的な枠組みを確立する。 我々は,その同一性に近い量子回路の確率振幅を近似するために,我々の枠組みを適用した。 我々のアルゴリズム条件は期待値に対してほぼ最適であり、ゼロ自由度という意味での熱予測値に対して最適であることを示す。
  論文  参考訳（メタデータ） (2023-06-15T09:11:48Z)
• Fast Computation of Optimal Transport via Entropy-Regularized Extragradient Methods [75.34939761152587]
  2つの分布間の最適な輸送距離の効率的な計算は、様々な応用を促進するアルゴリズムとして機能する。 本稿では,$varepsilon$加法精度で最適な輸送を計算できるスケーラブルな一階最適化法を提案する。
  論文  参考訳（メタデータ） (2023-01-30T15:46:39Z)
• Iteration Complexity of Variational Quantum Algorithms [5.684122393859336]
  雑音は量子回路のバイアスによる目的関数の評価を行う。 我々は、欠落した保証を導き、収束率が影響を受けないことを見出す。
  論文  参考訳（メタデータ） (2022-09-21T19:18:41Z)
• Quantum algorithms for numerical differentiation of expected values with respect to parameters [0.0]
  本稿では,変数の関数と実数値パラメータの期待値と,パラメータの期待値の導関数を計算する方法について考察する。 数値微分のためのQMCIと一般階中央差分式に基づいて,この問題に対する2つの量子法を提案する。 関数の滑らかさと利用可能なキュービット数によっては、2つの方法のどちらかが他方よりも優れていることが分かる。
  論文  参考訳（メタデータ） (2021-11-22T06:50:25Z)
• Near-Optimal High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。 クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Adaptive Sequential SAA for Solving Two-stage Stochastic Linear Programs [1.6181085766811525]
  大規模2段階線形プログラムを解くための適応的逐次SAA(sample average approximation)アルゴリズムを提案する。 提案アルゴリズムは,品質の確率論的保証が与えられた解を返すために,有限時間で停止することができる。
  論文  参考訳（メタデータ） (2020-12-07T14:58:16Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  オンラインデータストリームによって生成される有限個の点からなるランダムな確率測度に対する人口推定バリセンタ問題を考察する。 本稿では,この問題の構造を用いて,凸凹型サドル点再構成を行う。 ランダム確率測度の分布が離散的な場合、最適化アルゴリズムを提案し、その複雑性を推定する。
  論文  参考訳（メタデータ） (2020-06-11T19:40:38Z)
• 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)
• Stochastic Gauss-Newton Algorithms for Nonconvex Compositional Optimization [26.313415590777858]
  我々は,非構成最適化問題のクラスを解くための2つの新しいガウスニュートンアルゴリズムを開発した。 標準的な仮定では、期待と有限サムの設定の両方を考慮する。
  論文  参考訳（メタデータ） (2020-02-17T22:56:45Z)

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

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