論文の概要: On the convex hull of convex quadratic optimization problems with indicators

• arxiv url: http://arxiv.org/abs/2201.00387v1
• Date: Sun, 2 Jan 2022 18:04:52 GMT
• ステータス: 処理完了
• システム内更新日: 2022-01-04 15:14:31.681223
• Title: On the convex hull of convex quadratic optimization problems with indicators
• Title（参考訳）: 指標付き凸二次最適化問題の凸包について
• Authors: Linchuan Wei, Alper Atamt\"urk, Andr\'es G\'omez, Simge K\"u\c{c}\"ukyavuz
• Abstract要約: 二次変数の2次数を持つ拡張空間における関連する混合整数集合の凸包記述は、単一の正の半定値制約と線形制約からなることを示す。 ここで提示された新しい理論は、混合整数非線形集合の凸殻を解析するために多面体法を利用するための道を開く。
• 参考スコア（独自算出の注目度）: 2.867517731896504
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the convex quadratic optimization problem with indicator variables and arbitrary constraints on the indicators. We show that a convex hull description of the associated mixed-integer set in an extended space with a quadratic number of additional variables consists of a single positive semidefinite constraint (explicitly stated) and linear constraints. In particular, convexification of this class of problems reduces to describing a polyhedral set in an extended formulation. We also give descriptions in the original space of variables: we provide a description based on an infinite number of conic-quadratic inequalities, which are "finitely generated." In particular, it is possible to characterize whether a given inequality is necessary to describe the convex-hull. The new theory presented here unifies several previously established results, and paves the way toward utilizing polyhedral methods to analyze the convex hull of mixed-integer nonlinear sets.
• Abstract（参考訳）: 我々は、指標変数と指標に対する任意の制約を伴う凸二次最適化問題を考える。 二次変数の2次数を持つ拡張空間において、関連する混合整数集合の凸包記述が、1つの正半定値制約(明示的記述)と線形制約からなることを示す。 特に、この種類の問題の凸化は、拡張定式化における多面体集合の記述に還元される。 また、変数の元の空間に記述を与える: 無限個の円錐四次不等式に基づいて記述を与えるが、これは「有限生成」である。 特に、与えられた不等式が凸ハルを記述するのに必要かどうかを特徴付けることができる。 ここで提示される新しい理論は、いくつかの既定の結果を統一し、混合整数非線形集合の凸包を解析するために多面体法を利用する道を開く。

関連論文リスト

• Constrained Optimization of Rank-One Functions with Indicator Variables [0.0]
  様々な機械学習アプリケーションに現れる決定変数のサポートに関する制約をモデル化する制約よりも、ランクワン凸関数が関与する最適化問題である。 本稿では、視点関数によって誘導される隠れ円錐構造を利用する構成的アプローチを提案する。 これにより、非線形可分あるいは非可分な目的関数を持つ集合の凸包記述に対する視点記述を体系的に与え、連続変数の制約にサインし、指標変数の制約を与えることができる。
  論文  参考訳（メタデータ） (2023-03-31T15:51:56Z)
• Hessian Based Smoothing Splines for Manifold Learning [0.228438857884398]
  多様体学習における多次元平滑化スプラインアルゴリズムを提案する。 平らな多様体のソボレフ空間上の二次形式に、薄板スプラインの曲げエネルギーペナルティを一般化する。 解の存在と一意性は、ヒルベルト空間を再現する理論を適用することによって示される。
  論文  参考訳（メタデータ） (2023-02-10T02:49:05Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。 また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
  論文  参考訳（メタデータ） (2023-01-16T10:30:04Z)
• Learning Graphical Factor Models with Riemannian Optimization [70.13748170371889]
  本稿では,低ランク構造制約下でのグラフ学習のためのフレキシブルなアルゴリズムフレームワークを提案する。 この問題は楕円分布のペナルティ化された最大推定値として表される。 楕円モデルによく適合する正定行列と定ランクの正半定行列のジオメトリを利用する。
  論文  参考訳（メタデータ） (2022-10-21T13:19:45Z)
• Lifting the Convex Conjugate in Lagrangian Relaxations: A Tractable Approach for Continuous Markov Random Fields [53.31927549039624]
  断片的な離散化は既存の離散化問題と矛盾しないことを示す。 この理論を2つの画像のマッチング問題に適用する。
  論文  参考訳（メタデータ） (2021-07-13T12:31:06Z)
• Supermodularity and valid inequalities for quadratic optimization with indicators [3.8073142980733]
  階数 1 の二次数の基底集合関数は線形時間で最小化できることを示す。 凸殻の明示的な形式は、元の空間変数と、円錐二次表現可能な不等式による拡張公式の両方で与えられる。 実験により、円錐二次形式における昇降超モジュラー不等式は、インジケータによる二次最適化の積分ギャップを低減するのに非常に効果的であることが示されている。
  論文  参考訳（メタデータ） (2020-12-29T07:03:09Z)
• Optimal oracle inequalities for solving projected fixed-point equations [53.31620399640334]
  ヒルベルト空間の既知の低次元部分空間を探索することにより、確率観測の集合を用いて近似解を計算する手法を検討する。 本稿では,線形関数近似を用いた政策評価問題に対する時間差分学習手法の誤差を正確に評価する方法について述べる。
  論文  参考訳（メタデータ） (2020-12-09T20:19:32Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Ideal formulations for constrained convex optimization problems with indicator variables [2.578242050187029]
  本研究では,指標変数と指標に対する制約を用いた凸最適化問題のクラスを凸化することを検討した。 スパース回帰問題の凸化に関する従来の研究とは異なり、非線形非分離対象、指標変数、制約を同時に検討する。 階層性,多行性,空間性制約といった問題に対する理想的な凸化を導出する。
  論文  参考訳（メタデータ） (2020-06-30T21:07:10Z)
• Convex Geometry and Duality of Over-parameterized Neural Networks [70.15611146583068]
  有限幅2層ReLUネットワークの解析のための凸解析手法を開発した。 正規化学習問題に対する最適解が凸集合の極点として特徴づけられることを示す。 高次元では、トレーニング問題は無限に多くの制約を持つ有限次元凸問題としてキャストできることが示される。
  論文  参考訳（メタデータ） (2020-02-25T23:05:33Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。