論文の概要: Inference and Optimization for Engineering and Physical Systems
- arxiv url: http://arxiv.org/abs/2208.13880v1
- Date: Mon, 29 Aug 2022 20:50:40 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-31 13:30:58.083043
- Title: Inference and Optimization for Engineering and Physical Systems
- Title(参考訳): 工学と物理システムの推論と最適化
- Authors: Mikhail Krechetov
- Abstract要約: この博士論文の中心的な対象は、コンピュータ科学と統計力学の分野で異なる名前で知られている。
計算機科学では、有名な21のカープのNPハード問題と呼ばれる。
この論文の最後の章では、さらに一歩進めて、解決したい問題に対する解決策のコントロールを目指しています。
- 参考スコア(独自算出の注目度): 1.027974860479791
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The central object of this PhD thesis is known under different names in the
fields of computer science and statistical mechanics. In computer science, it
is called the Maximum Cut problem, one of the famous twenty-one Karp's original
NP-hard problems, while the same object from Physics is called the Ising Spin
Glass model. This model of a rich structure often appears as a reduction or
reformulation of real-world problems from computer science, physics and
engineering. However, solving this model exactly (finding the maximal cut or
the ground state) is likely to stay an intractable problem (unless $\textit{P}
= \textit{NP}$) and requires the development of ad-hoc heuristics for every
particular family of instances.
One of the bright and beautiful connections between discrete and continuous
optimization is a Semidefinite Programming-based rounding scheme for Maximum
Cut. This procedure allows us to find a provably near-optimal solution;
moreover, this method is conjectured to be the best possible in polynomial
time. In the first two chapters of this thesis, we investigate local non-convex
heuristics intended to improve the rounding scheme.
In the last chapter of this thesis, we make one step further and aim to
control the solution of the problem we wanted to solve in previous chapters. We
formulate a bi-level optimization problem over the Ising model where we want to
tweak the interactions as little as possible so that the ground state of the
resulting Ising model satisfies the desired criteria. This kind of problem
arises in pandemic modeling. We show that when the interactions are
non-negative, our bi-level optimization is solvable in polynomial time using
convex programming.
- Abstract(参考訳): この博士論文の中心的な対象は、コンピュータ科学と統計力学の分野で異なる名前で知られている。
計算機科学では、最大カット問題(maximum cut problem)と呼ばれ、有名な21個のカルプのnpハード問題の一つであり、物理学の同じ対象はイジングスピングラスモデルと呼ばれる。
リッチな構造のこのモデルは、しばしば計算機科学、物理学、工学から現実の問題を減らしたり修正したりする。
しかし、このモデルを正確に解く(最大カットや基底状態を決定する)と、難解な問題($\textit{P} = \textit{NP}$)を保ち、特定のインスタンスの族ごとにアドホックなヒューリスティックスを開発する必要がある。
離散最適化と連続最適化の間の明るく美しい関係の1つは、最大カットのための半定義のプログラミングベースの丸めスキームである。
この手順により、証明可能な近似解を見つけることができ、さらに多項式時間で可能な最良の解であると推測される。
本論文の最初の2章では,ラウンドリングスキームを改善するための局所的非凸ヒューリスティックスについて検討する。
この論文の最後の章では、さらに一歩進めて、前章で解決したい問題に対する解決策のコントロールを目指しています。
イジングモデル上で二段階最適化問題を定式化し、その相互作用を可能な限り微調整して、得られたイジングモデルの基底状態が所望の基準を満たすようにしたい。
このような問題はパンデミック・モデリングで発生する。
相互作用が非負の場合、凸プログラミングを用いて多項式時間で2レベル最適化が解けることを示す。
関連論文リスト
- Outer Approximation and Super-modular Cuts for Constrained Assortment Optimization under Mixed-Logit Model [6.123324869194196]
混合ロジット顧客選択モデルに基づくアソシエーション最適化問題について検討する。
既存の正確な手法は、主にMILP (mixed-integer linear programming) やCONIC (Second-order cone) の修正に依存している。
我々の研究は、単調に超モジュラーかつ凸であることを示す客観的関数の成分に焦点をあてることによって、この問題に対処する。
論文 参考訳(メタデータ) (2024-07-26T06:27:11Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳(メタデータ) (2023-10-08T23:39:38Z) - Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。
これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。
本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
論文 参考訳(メタデータ) (2022-02-17T18:59:20Z) - Combinatorial Optimization with Physics-Inspired Graph Neural Networks [0.0]
最適化問題の解法としてグラフニューラルネットワークを用いる方法を示す。
ニューラルネットワークは、既存の解法よりも優れているか、あるいは優れていることが分かりました。
論文 参考訳(メタデータ) (2021-07-02T16:54:35Z) - Good and Bad Optimization Models: Insights from Rockafellians [0.0]
このチュートリアルでは、この幅広い視点から得られる機会と洞察について説明します。
このチュートリアルでは、この幅広い視点から得られる機会と洞察について説明します。
論文 参考訳(メタデータ) (2021-05-13T04:31:42Z) - Offline Model-Based Optimization via Normalized Maximum Likelihood
Estimation [101.22379613810881]
データ駆動最適化の問題を検討し、一定の点セットでクエリのみを与えられた関数を最大化する必要がある。
この問題は、関数評価が複雑で高価なプロセスである多くの領域に現れる。
我々は,提案手法を高容量ニューラルネットワークモデルに拡張可能なトラクタブル近似を提案する。
論文 参考訳(メタデータ) (2021-02-16T06:04:27Z) - Improved Bilevel Model: Fast and Optimal Algorithm with Theoretical
Guarantee [110.16183719936629]
本稿では,現行の定式化よりも高速に収束する2レベルモデルを提案する。
実験結果から,本モデルが現行のバイレベルモデルよりも大きなマージンで優れていたことが示唆された。
論文 参考訳(メタデータ) (2020-09-01T20:52:57Z) - 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) - Combining Reinforcement Learning and Constraint Programming for
Combinatorial Optimization [5.669790037378094]
目標は、有限個の可能性の集合の中で最適解を見つけることである。
深部強化学習(DRL)はNP-ハード最適化問題を解くことを約束している。
制約プログラミング(CP)は最適化問題を解決する汎用ツールである。
本研究では,最適化問題の解法としてDRLとCPを用いた汎用ハイブリッド手法を提案する。
論文 参考訳(メタデータ) (2020-06-02T13:54:27Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
アルゴリズムの族は高い確率でほぼ最適な解を生成できないことを示す。
ブール回路の場合、回路複雑性理論で知られている最先端境界を改善する。
論文 参考訳(メタデータ) (2020-04-25T05:45:59Z) - Gumbel-softmax-based Optimization: A Simple General Framework for
Optimization Problems on Graphs [5.486093983007419]
本稿では,ディープラーニングフレームワークによって強化された高度な自動微分技術に基づく,シンプルで高速で汎用的なアルゴリズムフレームワークを提案する。
高品質なソリューションは、従来のアプローチに比べてはるかに少ない時間で得られる。
論文 参考訳(メタデータ) (2020-04-14T14:11:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。