論文の概要: A quantum central path algorithm for linear optimization
- arxiv url: http://arxiv.org/abs/2311.03977v1
- Date: Tue, 7 Nov 2023 13:26:20 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-08 15:20:36.505558
- Title: A quantum central path algorithm for linear optimization
- Title(参考訳): 線形最適化のための量子中央経路アルゴリズム
- Authors: Brandon Augustino, Jiaqi Leng, Giacomo Nannicini, Tam\'as Terlaky and
Xiaodi Wu
- Abstract要約: 中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
最大$mathcalO left( (m + n) textnnz (A) kappa (mathcalM) L cdot textpolylog left(m, n, kappa)$ elementary gates and $mathcalO left() を用いて、$m$制約と$n$変数を含む線形最適化問題の正確な解を得る。
- 参考スコア(独自算出の注目度): 5.774924046750588
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We propose a novel quantum algorithm for solving linear optimization problems
by quantum-mechanical simulation of the central path. While interior point
methods follow the central path with an iterative algorithm that works with
successive linearizations of the perturbed KKT conditions, we perform a single
simulation working directly with the nonlinear complementarity equations.
Combining our approach with iterative refinement techniques, we obtain an exact
solution to a linear optimization problem involving $m$ constraints and $n$
variables using at most $\mathcal{O} \left( (m + n) \text{nnz} (A) \kappa
(\mathcal{M}) L \cdot \text{polylog} \left(m, n, \kappa (\mathcal{M}) \right)
\right)$ elementary gates and $\mathcal{O} \left( \text{nnz} (A) L \right)$
classical arithmetic operations, where $ \text{nnz} (A)$ is the total number of
non-zero elements found in the constraint matrix, $L$ denotes binary input
length of the problem data, and $\kappa (\mathcal{M})$ is a condition number
that depends only on the problem data.
- Abstract(参考訳): 中央経路の量子力学的シミュレーションにより線形最適化問題を解く新しい量子アルゴリズムを提案する。
内部点法は,摂動kkt条件の逐次線形化を扱う反復アルゴリズムを用いて中心経路を追従するが,非線形相補性方程式と直接作用する単一シミュレーションを行う。
Combining our approach with iterative refinement techniques, we obtain an exact solution to a linear optimization problem involving $m$ constraints and $n$ variables using at most $\mathcal{O} \left( (m + n) \text{nnz} (A) \kappa (\mathcal{M}) L \cdot \text{polylog} \left(m, n, \kappa (\mathcal{M}) \right) \right)$ elementary gates and $\mathcal{O} \left( \text{nnz} (A) L \right)$ classical arithmetic operations, where $ \text{nnz} (A)$ is the total number of non-zero elements found in the constraint matrix, $L$ denotes binary input length of the problem data, and $\kappa (\mathcal{M})$ is a condition number that depends only on the problem data.
関連論文リスト
- Structured Semidefinite Programming for Recovering Structured
Preconditioners [41.28701750733703]
正定値$mathbfK を mathbbRd times d$ と $mathrmnnz(mathbfK)$ の 0 でないエントリで与えられるアルゴリズムは、時間内に$epsilon$-optimal diagonal preconditioner を計算する。
我々は、行列辞書近似SDPと呼ばれる半定値プログラムのクラスに対して、新しいアルゴリズムを用いて結果を得る。
論文 参考訳(メタデータ) (2023-10-27T16:54:29Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Fast $(1+\varepsilon)$-Approximation Algorithms for Binary Matrix
Factorization [54.29685789885059]
本稿では, 2次行列分解(BMF)問題に対する効率的な$(1+varepsilon)$-approximationアルゴリズムを提案する。
目標は、低ランク因子の積として$mathbfA$を近似することである。
我々の手法はBMF問題の他の一般的な変種に一般化する。
論文 参考訳(メタデータ) (2023-06-02T18:55:27Z) - Primal Dual Alternating Proximal Gradient Algorithms for Nonsmooth
Nonconvex Minimax Problems with Coupled Linear Constraints [5.142024994067472]
近年,機械学習や信号処理の分野では,非数学的ミニマックス問題に注目が集まっている。
線形制約を用いた非ミニマックス点数問題の解法として,複雑性保証付き2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-12-09T05:32:30Z) - Efficient quantum algorithms for solving quantum linear system problems [0.0]
拡張行列 $C$ の特異値 0 の右特異ベクトルを求める問題を解くための2つの量子アルゴリズムを提案する。
どちらのアルゴリズムも$kappa $の最適なクエリ複雑性を満たす。
論文 参考訳(メタデータ) (2022-08-14T02:49:26Z) - Decomposable Non-Smooth Convex Optimization with Nearly-Linear Gradient
Oracle Complexity [15.18055488087588]
上記の凸定式化を$widetildeO(sum_i=1n d_i log (1 /epsilon))$グラデーション計算で$epsilon$-accuracyに最小化するアルゴリズムを与える。
我々の主な技術的貢献は、カットプレーン法とインテリアポイント法を組み合わせた新しい組み合わせにより、各イテレーションで$f_i$項を選択する適応的な手順である。
論文 参考訳(メタデータ) (2022-08-07T20:53:42Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳(メタデータ) (2022-04-13T22:18:47Z) - Learning Stochastic Shortest Path with Linear Function Approximation [74.08819218747341]
線形関数近似を用いた強化学習における最短経路 (SSP) 問題について検討し, 遷移カーネルを未知モデルの線形混合として表現する。
本稿では,線形混合SSPを学習するための新しいアルゴリズムを提案し,このアルゴリズムにより,$tilde O(d B_star1.5sqrtK/c_min)$ regretを実現する。
論文 参考訳(メタデータ) (2021-10-25T08:34:00Z) - Global Convergence of Gradient Descent for Asymmetric Low-Rank Matrix
Factorization [49.090785356633695]
非対称な低ランク分解問題: [mathbbRm min d , mathbfU$ および MathV$ について検討する。
論文 参考訳(メタデータ) (2021-06-27T17:25:24Z) - Solving the Robust Matrix Completion Problem via a System of Nonlinear
Equations [28.83358353043287]
低階行列 $L_*$ とスパース行列 $S_*$ をそれらの和 $M=L_*+S_*inmathbbRmtimes n$ の不完全観測から回復することを目的としたロバスト行列完備化の問題を考える。
このアルゴリズムは並列性が高く、大規模な問題に適している。
数値シミュレーションにより、単純な手法は期待通りに動作し、最先端の手法に匹敵することを示した。
論文 参考訳(メタデータ) (2020-03-24T17:28:15Z) - Second-order Conditional Gradient Sliding [79.66739383117232]
本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。
SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。
実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
論文 参考訳(メタデータ) (2020-02-20T17:52:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。