論文の概要: Between steps: Intermediate relaxations between big-M and convex hull
formulations
- arxiv url: http://arxiv.org/abs/2101.12708v1
- Date: Fri, 29 Jan 2021 18:03:15 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-05 00:26:02.546890
- Title: Between steps: Intermediate relaxations between big-M and convex hull
formulations
- Title(参考訳): ステップ間:big-mと凸包式の間の中間緩和
- Authors: Jan Kronqvist and Ruth Misener and Calvin Tsay
- Abstract要約: 我々は, 接点のビッグmと凸包式の間の緩和のクラスを展開する。
提案された "P-split" の定式化は凸をP分割に分割し、分節の凸体を形成する。
- 参考スコア(独自算出の注目度): 4.769747792846004
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This work develops a class of relaxations in between the big-M and convex
hull formulations of disjunctions, drawing advantages from both. The proposed
"P-split" formulations split convex additively separable constraints into P
partitions and form the convex hull of the partitioned disjuncts. Parameter P
represents the trade-off of model size vs. relaxation strength. We examine the
novel formulations and prove that, under certain assumptions, the relaxations
form a hierarchy starting from a big-M equivalent and converging to the convex
hull. We computationally compare the proposed formulations to big-M and convex
hull formulations on a test set including: K-means clustering, P_ball problems,
and ReLU neural networks. The computational results show that the intermediate
P-split formulations can form strong outer approximations of the convex hull
with fewer variables and constraints than the extended convex hull
formulations, giving significant computational advantages over both the big-M
and convex hull.
- Abstract(参考訳): この研究は、big-m と凸包式の間の緩和のクラスを発達させ、両者の利点を引き出す。
提案する「p-split」定式化は、付加的に分離可能な制約をpパーティションに分割し、分割された分節の凸包を形成する。
パラメータPはモデルサイズと緩和強度のトレードオフを表す。
新たな定式化を考察し、ある仮定の下で、緩和がビッグm同値から凸包へ収束する階層を形成することを証明した。
提案した定式化を,K平均クラスタリング,P_ball問題,ReLUニューラルネットワークを含むテストセット上で,Big-Mおよびconvexの船体定式化と比較した。
計算結果から, 中間 p-split 定式化は拡張凸包定式よりも少ない変数と制約で凸包の強い外的近似を形成できることが示され, ビッグm と凸包の両方に対して大きな計算上の優位性が得られた。
関連論文リスト
- Randomized Physics-Informed Machine Learning for Uncertainty
Quantification in High-Dimensional Inverse Problems [49.1574468325115]
本研究では,高次元逆問題における不確実性定量化のための物理インフォームド機械学習手法を提案する。
我々は解析的に、そして、ハミルトン・モンテカルロとの比較を通して、rPICKLE はベイズ則によって与えられる真の後続に収束することを示す。
論文 参考訳(メタデータ) (2023-12-11T07:33:16Z) - P-split formulations: A class of intermediate formulations between big-M
and convex hull for disjunctive constraints [3.585904984801793]
我々は,大小Mおよび凸容器の定式化と中間の解離的制約に対する混合整数定式化のクラスを開発する。
P$-split" の定式化は、凸加法的に分離可能な制約を$P$パーティションに分割するリフト変換に基づいている。
P$-split の定式化が Big-M 同値から凸包に収束する階層を形成することを示す。
論文 参考訳(メタデータ) (2022-02-10T18:02:16Z) - Partition-based formulations for mixed-integer optimization of trained
ReLU neural networks [66.88252321870085]
本稿では,訓練されたReLUニューラルネットワークのための混合整数式について紹介する。
1つの極端な場合、入力毎に1つのパーティションがノードの凸殻、すなわち各ノードの最も厳密な可能な定式化を回復する。
論文 参考訳(メタデータ) (2021-02-08T17:27:34Z) - Efficient semidefinite-programming-based inference for binary and
multi-class MRFs [83.09715052229782]
分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。
一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
論文 参考訳(メタデータ) (2020-12-04T15:36:29Z) - On the minmax regret for statistical manifolds: the role of curvature [68.8204255655161]
2つの部分のコードと最小記述長は、最高のモデルを選別するための手順を提供するのに成功している。
我々は、フィッシャー情報計量のスカラー曲率が支配的な役割を果たす複雑さによって与えられる標準表現よりも、よりシャープな表現を導出する。
論文 参考訳(メタデータ) (2020-07-06T17:28:19Z) - Ideal formulations for constrained convex optimization problems with
indicator variables [2.578242050187029]
本研究では,指標変数と指標に対する制約を用いた凸最適化問題のクラスを凸化することを検討した。
スパース回帰問題の凸化に関する従来の研究とは異なり、非線形非分離対象、指標変数、制約を同時に検討する。
階層性,多行性,空間性制約といった問題に対する理想的な凸化を導出する。
論文 参考訳(メタデータ) (2020-06-30T21:07:10Z) - Model Reduction and Neural Networks for Parametric PDEs [9.405458160620533]
無限次元空間間の入出力マップをデータ駆動で近似するフレームワークを開発した。
提案されたアプローチは、最近のニューラルネットワークとディープラーニングの成功に動機づけられている。
入力出力マップのクラスと、入力に対する適切な選択された確率測度について、提案手法の収束性を証明する。
論文 参考訳(メタデータ) (2020-05-07T00:09:27Z) - Stochastic spectral embedding [0.0]
確率スペクトル埋め込み(SSE)に基づく新しい逐次適応サロゲートモデリング法を提案する。
本手法は,複雑性と入力次元の異なるモデルの集合上で,最先端のスパースカオス展開に対して,どのように好意的に比較されるかを示す。
論文 参考訳(メタデータ) (2020-04-09T11:00:07Z) - MINA: Convex Mixed-Integer Programming for Non-Rigid Shape Alignment [77.38594866794429]
非剛体形状マッチングのための凸混合整数プログラミングの定式化。
効率的な低次元離散モデルに基づく新しい形状変形モデルを提案する。
論文 参考訳(メタデータ) (2020-02-28T09:54:06Z) - Distributed Averaging Methods for Randomized Second Order Optimization [54.51566432934556]
我々はヘッセン語の形成が計算的に困難であり、通信がボトルネックとなる分散最適化問題を考察する。
我々は、ヘッセンのサンプリングとスケッチを用いたランダム化二階最適化のための非バイアスパラメータ平均化手法を開発した。
また、不均一なコンピューティングシステムのための非バイアス分散最適化フレームワークを導入するために、二階平均化手法のフレームワークを拡張した。
論文 参考訳(メタデータ) (2020-02-16T09:01:18Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。