論文の概要: A Class of Linear Programs Solvable by Coordinate-Wise Minimization
- arxiv url: http://arxiv.org/abs/2001.10467v5
- Date: Mon, 14 Sep 2020 10:47:55 GMT
- ステータス: 処理完了
- システム内更新日: 2023-01-06 02:52:06.230375
- Title: A Class of Linear Programs Solvable by Coordinate-Wise Minimization
- Title（参考訳）: 座標最小化によって解ける線形プログラムのクラス
- Authors: Tom\'a\v{s} Dlask, Tom\'a\v{s} Werner
- Abstract要約: 座標最小化を正確に解く線形プログラムのクラスを示す。
いくつかのよく知られた最適化問題の2つのLP緩和がこのクラスにあることを示す。
我々の結果は理論的には非自明であり、将来的には新たな大規模最適化アルゴリズムがもたらされる可能性がある。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Coordinate-wise minimization is a simple popular method for large-scale
optimization. Unfortunately, for general (non-differentiable) convex problems
it may not find global minima. We present a class of linear programs that
coordinate-wise minimization solves exactly. We show that dual LP relaxations
of several well-known combinatorial optimization problems are in this class and
the method finds a global minimum with sufficient accuracy in reasonable
runtimes. Moreover, for extensions of these problems that no longer are in this
class the method yields reasonably good suboptima. Though the presented LP
relaxations can be solved by more efficient methods (such as max-flow), our
results are theoretically non-trivial and can lead to new large-scale
optimization algorithms in the future.
- Abstract（参考訳）: 座標最小化は大規模最適化のための単純な一般的な方法である。
残念ながら、一般的な(微分不能な)凸問題では、大域的ミニマは見つからない。
座標最小化が正確に解く線形プログラムのクラスを提案する。
本稿では,いくつかのよく知られた組合せ最適化問題の双対lp緩和がこのクラスにあり,合理的な実行時において十分な精度を持つ大域的最小値を求める。
さらに、このクラスに存在しないこれらの問題を拡張するために、メソッドは適度に良いサブオプティマをもたらす。
提案したLP緩和はより効率的な手法(マックスフローなど)で解けるが、理論上は非自明であり、将来的には新たな大規模最適化アルゴリズムがもたらされる可能性がある。
関連論文リスト
- An Accelerated Gradient Method for Convex Smooth Simple Bilevel Optimization [16.709026203727007]
下層問題の解集合を局所的に近似する新しい双レベル最適化法を提案する。
我々は,提案手法の性能を,最適度と不実現可能性の誤差の観点から測定する。
論文 参考訳（メタデータ） (2024-02-12T22:34:53Z) - Optimal Guarantees for Algorithmic Reproducibility and Gradient
Complexity in Convex Optimization [55.115992622028685]
以前の研究は、一階法はより良い収束率(漸進収束率)をトレードオフする必要があることを示唆している。
最適複雑性と準最適収束保証の両方を、滑らかな凸最小化と滑らかな凸最小化問題に対して達成できることを実証する。
論文 参考訳（メタデータ） (2023-10-26T19:56:52Z) - Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of
Newton Method [4.62316736194615]
準自己調和平滑成分を用いた複合凸最適化問題について検討する。
この問題クラスは、古典的な自己調和函数とリプシッツ連続ヘッセン函数の間に自然に補間する。
準自己協和関数を最小化するためには、グラディエント正規化を伴う基本ニュートン法を用いることができる。
論文 参考訳（メタデータ） (2023-08-28T17:43:04Z) - Accelerating Cutting-Plane Algorithms via Reinforcement Learning
Surrogates [49.84541884653309]
凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。
多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。
そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
論文 参考訳（メタデータ） (2023-07-17T20:11:56Z) - Linearization Algorithms for Fully Composite Optimization [61.20539085730636]
本稿では,完全合成最適化問題を凸コンパクト集合で解くための一階アルゴリズムについて検討する。
微分可能および非微分可能を別々に扱い、滑らかな部分のみを線形化することで目的の構造を利用する。
論文 参考訳（メタデータ） (2023-02-24T18:41:48Z) - Optimal Algorithms for Stochastic Complementary Composite Minimization [55.26935605535377]
統計学と機械学習における正規化技術に触発され,補完的な複合化の最小化について検討した。
予測と高い確率で、新しい過剰なリスク境界を提供する。
我々のアルゴリズムはほぼ最適であり、このクラスの問題に対して、新しいより低い複雑性境界によって証明する。
論文 参考訳（メタデータ） (2022-11-03T12:40:24Z) - A Constrained Optimization Approach to Bilevel Optimization with
Multiple Inner Minima [49.320758794766185]
そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。
このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
論文 参考訳（メタデータ） (2022-03-01T18:20:01Z) - Coordinate Descent Methods for DC Minimization [12.284934135116515]
差分凸(英: difference-of-Convex、DC)とは、2つの凸関数の差を最小化する問題である。
本稿では,非次元の1次元サブプロブレムを世界規模で提案し,座標の定常点に収束することが保証される。
論文 参考訳（メタデータ） (2021-09-09T12:44:06Z) - Complementary Composite Minimization, Small Gradients in General Norms,
and Applications to Regression Problems [14.759688428864157]
複合最小化は大規模凸最適化における強力なフレームワークである。
補完的複合最小化のための新しいアルゴリズムフレームワークを提案する。
我々は,フレームワークから得られるアルゴリズムが,ほとんどの標準最適化設定においてほぼ最適であることを証明した。
論文 参考訳（メタデータ） (2021-01-26T19:21:28Z) - Recent Theoretical Advances in Non-Convex Optimization [56.88981258425256]
近年、深層ネットワークにおける非最適化アルゴリズムの解析やデータ問題への関心が高まっており、非最適化のための理論的最適化アルゴリズムの最近の結果の概要を概説する。
論文 参考訳（メタデータ） (2020-12-11T08:28:51Z) - Meta-learning based Alternating Minimization Algorithm for Non-convex
Optimization [9.774392581946108]
複数変数の非プロブレムに挑戦する新しい解を提案する。
提案手法では,他の手法が一般的に失敗するケースに対して,効果的なイテレーションを実現することができる。
論文 参考訳（メタデータ） (2020-09-09T10:45:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。