論文の概要: Supermodularity and valid inequalities for quadratic optimization with
indicators
- arxiv url: http://arxiv.org/abs/2012.14633v1
- Date: Tue, 29 Dec 2020 07:03:09 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-18 20:28:59.997658
- Title: Supermodularity and valid inequalities for quadratic optimization with
indicators
- Title（参考訳）: 指標付き二次最適化のための超モジュラリティと有効不等式
- Authors: Alper Atamturk and Andres Gomez
- Abstract要約: 階数 1 の二次数の基底集合関数は線形時間で最小化できることを示す。
凸殻の明示的な形式は、元の空間変数と、円錐二次表現可能な不等式による拡張公式の両方で与えられる。
実験により、円錐二次形式における昇降超モジュラー不等式は、インジケータによる二次最適化の積分ギャップを低減するのに非常に効果的であることが示されている。
- 参考スコア（独自算出の注目度）: 3.8073142980733
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the minimization of a rank-one quadratic with indicators and show
that the underlying set function obtained by projecting out the continuous
variables is supermodular. Although supermodular minimization is, in general,
difficult, the specific set function for the rank-one quadratic can be
minimized in linear time. We show that the convex hull of the epigraph of the
quadratic can be obtaining from inequalities for the underlying supermodular
set function by lifting them into nonlinear inequalities in the original space
of variables. Explicit forms of the convex-hull description are given, both in
the original space of variables and in an extended formulation via conic
quadratic-representable inequalities, along with a polynomial separation
algorithm. Computational experiments indicate that the lifted supermodular
inequalities in conic quadratic form are quite effective in reducing the
integrality gap for quadratic optimization with indicators.
- Abstract（参考訳）: 階数 1 の二次化を指標付きで最小化し、連続変数を射影して得られる基底集合関数が超モジュラーであることを示す。
超モジュラル最小化は一般に難しいが、階数 1 の二次の特定の集合関数は線形時間で最小化できる。
二次のエピグラフの凸包は、変数の原空間の非線形不等式へ持ち上げることによって、基礎となる超モジュラー集合函数の不等式から得ることができる。
凸-ハル記述の明示的な形式は、変数の原空間と円錐二次表現可能不等式による拡張定式化の両方において、多項式分離アルゴリズムとともに与えられる。
計算実験により、円錐二次形式における昇降超モジュラー不等式は、2次最適化と指標との積分性ギャップを低減するのに非常に効果的であることが示されている。
関連論文リスト
- Structured model selection via $\ell_1-\ell_2$ optimization [1.933681537640272]
構造化力学系を同定する学習手法を開発した。
候補関数の集合が有界系を成すとき、その回復は安定で有界であることを示す。
論文 参考訳（メタデータ） (2023-05-27T12:51:26Z) - Constrained Optimization of Rank-One Functions with Indicator Variables [0.0]
様々な機械学習アプリケーションに現れる決定変数のサポートに関する制約をモデル化する制約よりも、ランクワン凸関数が関与する最適化問題である。
本稿では、視点関数によって誘導される隠れ円錐構造を利用する構成的アプローチを提案する。
これにより、非線形可分あるいは非可分な目的関数を持つ集合の凸包記述に対する視点記述を体系的に与え、連続変数の制約にサインし、指標変数の制約を与えることができる。
論文 参考訳（メタデータ） (2023-03-31T15:51:56Z) - Multiple Convex Objects Image Segmentation via Proximal Alternating
Direction Method of Multipliers [2.294014185517203]
前述した凸形状は、各対象に関連付けられた二項指示関数上の単純な二次不等式制約であることが判明した。
凸形状を予め確率ベースに組み込んだ画像分割モデルを提案する。
自然画像と医用画像の数値実験により,提案手法は既存の方法よりも優れていることが示された。
論文 参考訳（メタデータ） (2022-03-22T00:05:19Z) - On the convex hull of convex quadratic optimization problems with
indicators [2.867517731896504]
二次変数の2次数を持つ拡張空間における関連する混合整数集合の凸包記述は、単一の正の半定値制約と線形制約からなることを示す。
ここで提示された新しい理論は、混合整数非線形集合の凸殻を解析するために多面体法を利用するための道を開く。
論文 参考訳（メタデータ） (2022-01-02T18:04:52Z) - Reinforcement Learning in Linear MDPs: Constant Regret and
Representation Selection [136.4014229319618]
線形構造を持つ有限水平マルコフ決定過程(MDPs)における後悔最小化における状態-作用値関数の表現の役割について検討する。
まず,線形報酬関数を持つ任意のMDPにおいて,一貫した後悔を実現するために,Universally spaning optimal features (UNISOFT) と呼ばれる表現に必要条件を導出する。
論文 参考訳（メタデータ） (2021-10-27T22:07:08Z) - Sparse Quadratic Optimisation over the Stiefel Manifold with Application
to Permutation Synchronisation [71.27989298860481]
二次目的関数を最大化するスティーフェル多様体上の行列を求める非最適化問題に対処する。
そこで本研究では,支配的固有空間行列を求めるための,単純かつ効果的なスパーシティプロモーティングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-09-30T19:17:35Z) - Principal Component Hierarchy for Sparse Quadratic Programs [27.812191030127618]
本稿では,濃度制約付き凸2次プログラムに対する新しい近似階層を提案する。
提案手法は,現在のスパース回帰において既存のスクリーニング手法と競合することを示す。
論文 参考訳（メタデータ） (2021-05-25T15:45:16Z) - Square Root Bundle Adjustment for Large-Scale Reconstruction [56.44094187152862]
QR分解によるランドマーク変数のnullspace marginalizationに依存するバンドル調整問題の新たな定式化を提案する。
平方根束調整と呼ばれる私たちのアプローチは、一般的に使用されるSchur補完トリックと代数的に等価です。
BALデータセットを用いた実世界での実験では、提案されたソルバが単一の精度でも平均的等しく正確なソリューションで達成できることを示す。
論文 参考訳（メタデータ） (2021-03-02T16:26:20Z) - Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。
本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
論文 参考訳（メタデータ） (2020-12-09T20:19:32Z) - Non-parametric Models for Non-negative Functions [48.7576911714538]
同じ良い線形モデルから非負関数に対する最初のモデルを提供する。
我々は、それが表現定理を認め、凸問題に対する効率的な二重定式化を提供することを証明した。
論文 参考訳（メタデータ） (2020-07-08T07:17:28Z) - Effective Dimension Adaptive Sketching Methods for Faster Regularized
Least-Squares Optimization [56.05635751529922]
スケッチに基づくL2正規化最小二乗問題の解法を提案する。
我々は、最も人気のあるランダム埋め込みの2つ、すなわちガウス埋め込みとサブサンプリングランダム化アダマール変換(SRHT)を考える。
論文 参考訳（メタデータ） (2020-06-10T15:00:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。