論文の概要: An efficient algorithm for the $\ell_{p}$ norm based metric nearness
problem
- arxiv url: http://arxiv.org/abs/2211.01245v1
- Date: Wed, 2 Nov 2022 16:29:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-11-03 13:11:50.901136
- Title: An efficient algorithm for the $\ell_{p}$ norm based metric nearness
problem
- Title（参考訳）: $\ell_{p}$ノルムに基づく距離近接性問題の効率的なアルゴリズム
- Authors: Peipei Tang, Bo Jiang, Chengjing Wang
- Abstract要約: 本稿では, 半平滑なニュートン型近位拡張ラグランジアン法(PALM)で解いた各サブプロブレムを用いた遅延制約生成法を提案する。
我々のアルゴリズムの喜ばしい側面は、最大108ドルの変数と1013ドルの制約を含むこれらの問題を解決することができることである。
- 参考スコア（独自算出の注目度）: 4.700135257490953
- License: http://creativecommons.org/publicdomain/zero/1.0/
- Abstract: Given a dissimilarity matrix, the metric nearness problem is to find the
nearest matrix of distances that satisfy the triangle inequalities. This
problem has wide applications, such as sensor networks, image processing, and
so on. But it is of great challenge even to obtain a moderately accurate
solution due to the $O(n^{3})$ metric constraints and the nonsmooth objective
function which is usually a weighted $\ell_{p}$ norm based distance. In this
paper, we propose a delayed constraint generation method with each subproblem
solved by the semismooth Newton based proximal augmented Lagrangian method
(PALM) for the metric nearness problem. Due to the high memory requirement for
the storage of the matrix related to the metric constraints, we take advantage
of the special structure of the matrix and do not need to store the
corresponding constraint matrix. A pleasing aspect of our algorithm is that we
can solve these problems involving up to $10^{8}$ variables and $10^{13}$
constraints. Numerical experiments demonstrate the efficiency of our algorithm.
In theory, firstly, under a mild condition, we establish a primal-dual error
bound condition which is very essential for the analysis of local convergence
rate of PALM. Secondly, we prove the equivalence between the dual nondegeneracy
condition and nonsingularity of the generalized Jacobian for the inner
subproblem of PALM. Thirdly, when $q(\cdot)=\|\cdot\|_{1}$ or
$\|\cdot\|_{\infty}$, without the strict complementarity condition, we also
prove the equivalence between the the dual nondegeneracy condition and the
uniqueness of the primal solution.
- Abstract（参考訳）: 類似性行列が与えられたとき、距離近接性問題は三角不等式を満たす距離の最も近い行列を見つけることである。
この問題には、センサネットワークや画像処理など、幅広い応用がある。
しかし、$O(n^{3})$の計量制約と、通常、重み付き$\ell_{p}$のノルム基底距離である非滑らかな目的関数のために、適度に正確な解を得るのも大きな課題である。
本稿では, 半平板ニュートン法に基づく近似ラグランジアン法 (PALM) により解法された各サブプロブレムを用いた遅延制約生成法を提案する。
メトリック制約に関連する行列の格納に対するメモリの要求が大きいため、行列の特別な構造を利用し、対応する制約行列を格納する必要がない。
アルゴリズムの喜ばしい側面は、最大10^{8}$変数と10^{13}$制約を含むこれらの問題を解くことができることである。
数値実験はアルゴリズムの効率を実証する。
理論上は、まず穏やかな条件下で、PALMの局所収束速度の解析に非常に不可欠である原始二重誤差境界条件を確立する。
第二に、PALMの内部部分確率に対する一般化ヤコビアンの双対非退化条件と非特異性との同値性を証明する。
第三に、q(\cdot)=\|\cdot\|_{1}$ または $\|\cdot\|_{\infty}$ のとき、厳密な相補性条件がなければ、双対非退化条件と原始解の一意性の間の同値性も証明する。
関連論文リスト
- A quantum central path algorithm for linear optimization [5.450016817940232]
中心経路の量子力学的シミュレーションにより線形最適化問題を解くための新しい量子アルゴリズムを提案する。
このアプローチは、$m$制約と$n$変数を含む線形最適化問題を$varepsilon$-optimalityに解くアルゴリズムをもたらす。
標準ゲートモデル(すなわち、量子RAMにアクセスせずに)では、我々のアルゴリズムは少なくとも$$mathcalO left( sqrtm + n textsfnnz (A) fracR_1 を用いてLO問題の高精度な解を得ることができる。
論文 参考訳（メタデータ） (2023-11-07T13:26:20Z) - Fast Minimization of Expected Logarithmic Loss via Stochastic Dual
Averaging [8.990961435218544]
本稿では,対数障壁を用いたB$-sample双対平均化法を提案する。
Poisson逆問題に対して、我々のアルゴリズムは$smashtildeO(d3/varepsilon2)$ timeで$varepsilon$解を得る。
量子状態トモグラフィーの最大線量推定を計算するとき、我々のアルゴリズムは $smashtildeO(d3/varepsilon2)$ time で $varepsilon$-optimal Solution を得る。
論文 参考訳（メタデータ） (2023-11-05T03:33:44Z) - Analyzing and Improving Greedy 2-Coordinate Updates for
Equality-Constrained Optimization via Steepest Descent in the 1-Norm [12.579063422860072]
我々は,この問題に対する2座標更新と,1ノルムにおける等式制約付き急降下との接続を利用する。
次に、サポートベクトルマシン双対問題において生じるような、和制約と有界制約の両方で最小化を検討する。
論文 参考訳（メタデータ） (2023-07-03T17:27:18Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳（メタデータ） (2023-06-30T08:34:29Z) - Differentially Private Algorithms for the Stochastic Saddle Point
Problem with Optimal Rates for the Strong Gap [12.446156563700482]
凸凹型リプシッツサドル点問題は、$(epsilon,delta)$differential privacyの制約の下で解決可能であることを示す。
また、安定性と精度の間には根本的なトレードオフがあることも示している。
論文 参考訳（メタデータ） (2023-02-24T21:50:02Z) - Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。
我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
論文 参考訳（メタデータ） (2023-02-03T03:19:14Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Quantum Goemans-Williamson Algorithm with the Hadamard Test and
Approximate Amplitude Constraints [62.72309460291971]
本稿では,n+1$ qubitsしか使用しないGoemans-Williamsonアルゴリズムの変分量子アルゴリズムを提案する。
補助量子ビット上で適切にパラメータ化されたユニタリ条件として目的行列を符号化することにより、効率的な最適化を実現する。
各種NPハード問題に対して,Goemans-Williamsonアルゴリズムの量子的効率的な実装を考案し,提案プロトコルの有効性を実証する。
論文 参考訳（メタデータ） (2022-06-30T03:15:23Z) - Revisiting Modified Greedy Algorithm for Monotone Submodular
Maximization with a Knapsack Constraint [75.85952446237599]
修正されたグリードアルゴリズムは、近似係数が0.305$であることを示す。
最適なデータ依存上界を導出する。
また、分岐やバウンドといったアルゴリズムの効率を大幅に改善するためにも使うことができる。
論文 参考訳（メタデータ） (2020-08-12T15:40:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。