論文の概要: A Generic Branch-and-Bound Algorithm for $\ell_0$-Penalized Problems with Supplementary Material

• arxiv url: http://arxiv.org/abs/2506.03974v1
• Date: Wed, 04 Jun 2025 14:05:49 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-06-05 21:20:14.367194
• Title: A Generic Branch-and-Bound Algorithm for $\ell_0$-Penalized Problems with Supplementary Material
• Title（参考訳）: 補助材料を用いた$\ell_0$-Penalized問題に対する分岐境界法
• Authors: Clément Elvira, Théo Guyard, Cédric Herzet,
• Abstract要約: L0-penalized optimization 問題を解くために,汎用的なブランチ・アンド・バウンド法を提案する。 本手法は, より広範な損失関数のクラスに対応し, 一般のペナルティ項による緩和設計の柔軟性を高める。 我々は,L0ペナル化問題におけるユーザ定義の損失と罰則を可能にする,プラグイン・アンド・プレイワークフローを備えたオープンソースのPythonソルバであるEl0psを紹介した。
• 参考スコア（独自算出の注目度）: 10.960289997471083
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We present a generic Branch-and-Bound procedure designed to solve L0-penalized optimization problems. Existing approaches primarily focus on quadratic losses and construct relaxations using "Big-M" constraints and/or L2-norm penalties. In contrast, our method accommodates a broader class of loss functions and allows greater flexibility in relaxation design through a general penalty term, encompassing existing techniques as special cases. We establish theoretical results ensuring that all key quantities required for the Branch-and-Bound implementation admit closed-form expressions under the general blanket assumptions considered in our work. Leveraging this framework, we introduce El0ps, an open-source Python solver with a plug-and-play workflow that enables user-defined losses and penalties in L0-penalized problems. Through extensive numerical experiments, we demonstrate that El0ps achieves state-of-the-art performance on classical instances and extends computational feasibility to previously intractable ones.
• Abstract（参考訳）: L0-penalized optimization 問題を解くために,汎用的なブランチ・アンド・バウンド法を提案する。 既存のアプローチは主に二次的損失に焦点を当て、"Big-M"制約と/またはL2-ノルム罰を用いて緩和を構築する。 対照的に,本手法はより広範な損失関数を許容し,既存の手法を特殊な事例として含む一般ペナルティ項による緩和設計の柔軟性を高める。 本研究では, 分岐境界実装に必要なすべての鍵量に対して, 一般のスクラッチ仮定の下での閉形式表現が認められることを保証する理論的な結果を確立する。 このフレームワークを活用したオープンソースのPythonソルバEl0psを紹介します。 大規模な数値実験により,El0psは従来型のインスタンス上での最先端性能を実現し,従来より難易度の高いインスタンスに計算能力を拡張できることが実証された。

関連論文リスト

• Efficient QAOA Architecture for Solving Multi-Constrained Optimization Problems [3.757262277494307]
  本稿では,量子近似最適化アンサッツのための制約符号化手法の新たな組み合わせを提案する。 ワンホット制約は、検索空間を実現可能なサブ空間に自然に制限する$XY$-mixerによって強制される。 確立されたQUBOの定式化と組み合わせた手法をベンチマークし、最適解をサンプリングする確率と解の質を向上した。
  論文  参考訳（メタデータ） (2025-06-03T17:46:53Z)
• A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions [0.0]
  線形ノルムバウンド制約の問題は、ポートフォリオ最適化、機械学習、機能選択など、さまざまなアプリケーションで発生する。 本稿では,これらの問題をグローバルに解決するための新しいグラフベース手法を提案する。
  論文  参考訳（メタデータ） (2025-05-06T18:09:54Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  本稿では、目的関数と制約関数の両方が弱凸である問題の重要な部分集合について検討する。 既存の手法では、収束速度の遅さや二重ループ設計への依存など、しばしば制限に直面している。 これらの課題を克服するために,新しい単一ループペナルティに基づくアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-04-21T17:15:48Z)
• Learning Adversarial MDPs with Stochastic Hard Constraints [37.24692425018]
  我々は,制約付きマルコフ決定過程(CMDP)におけるオンライン学習について,敵対的損失と厳しい制約を伴って検討した。 我々の研究は、敵の損失と厳しい制約の両方にかかわるCMDPを初めて研究した。
  論文  参考訳（メタデータ） (2024-03-06T12:49:08Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  ポートフォリオ最適化からロジスティクスに至るまで、制約付き最適化問題は業界に多い。 これらの問題の解決における主要な障害の1つは、有効な検索空間を制限する非自明なハード制約の存在である。 本研究では、Ax=bという形の任意の整数値等式制約をU(1)対称ネットワーク(TN)に直接エンコードし、それらの適用性を量子に着想を得た生成モデルとして活用する。
  論文  参考訳（メタデータ） (2022-11-16T18:59:54Z)
• Universal Online Convex Optimization Meets Second-order Bounds [74.0120666722487]
  ユニバーサルオンライン凸最適化のための簡単な戦略を提案する。 主要なアイデアは、オリジナルのオンライン機能を処理するための専門家のセットを構築し、線形化された損失に対してメタアルゴリズムをデプロイすることである。 このようにして、私たちはブラックボックスの専門家として、既成のオンライン問題解決者をプラグインして、問題依存の後悔の限界を提供することができます。
  論文  参考訳（メタデータ） (2021-05-08T11:43:49Z)
• An Integer Linear Programming Framework for Mining Constraints from Data [81.60135973848125]
  データから制約をマイニングするための一般的なフレームワークを提案する。 特に、構造化された出力予測の推論を整数線形プログラミング(ILP)問題とみなす。 提案手法は,9×9のスドクパズルの解法を学習し,基礎となるルールを提供することなく,例からツリー問題を最小限に分散させることが可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-18T20:09:53Z)
• Polynomial-Time Exact MAP Inference on Discrete Models with Global Dependencies [83.05591911173332]
  ジャンクションツリーアルゴリズムは、実行時の保証と正確なMAP推論のための最も一般的な解である。 本稿では,ノードのクローン化による新たなグラフ変換手法を提案する。
  論文  参考訳（メタデータ） (2019-12-27T13:30:29Z)

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

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