論文の概要: Exact and approximate determination of the Pareto set using minimal correction subsets

• arxiv url: http://arxiv.org/abs/2204.06908v1
• Date: Thu, 14 Apr 2022 12:08:55 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-15 13:00:21.426603
• Title: Exact and approximate determination of the Pareto set using minimal correction subsets
• Title（参考訳）: 最小補正部分集合を用いたパレート集合の厳密かつ近似決定
• Authors: Andreia P. Guerreiro, Jo\~ao Cortes, Daniel Vanderpooten, Cristina Bazgan, In\^es Lynce, Vasco Manquinho, Jos\'e Rui Figueira
• Abstract要約: 我々はMOBO問題を解くために最小補正サブセット(MCS)列挙を用いることが可能であることを示す。 また,MSS列挙を用いたパレートフロンティアの (1 + varepsilon)-近似を求める2つの新しいアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Recently, it has been shown that the enumeration of Minimal Correction Subsets (MCS) of Boolean formulas allows solving Multi-Objective Boolean Optimization (MOBO) formulations. However, a major drawback of this approach is that most MCSs do not correspond to Pareto-optimal solutions. In fact, one can only know that a given MCS corresponds to a Pareto-optimal solution when all MCSs are enumerated. Moreover, if it is not possible to enumerate all MCSs, then there is no guarantee of the quality of the approximation of the Pareto frontier. This paper extends the state of the art for solving MOBO using MCSs. First, we show that it is possible to use MCS enumeration to solve MOBO problems such that each MCS necessarily corresponds to a Pareto-optimal solution. Additionally, we also propose two new algorithms that can find a (1 + {\varepsilon})-approximation of the Pareto frontier using MCS enumeration. Experimental results in several benchmark sets show that the newly proposed algorithms allow finding better approximations of the Pareto frontier than state-of-the-art algorithms, and with guaranteed approximation ratios.
• Abstract（参考訳）: 近年、ブール公式の最小補正部分集合(MCS)の列挙により、MOBO(Multi-Objective Boolean Optimization)の定式化が可能であることが示されている。 しかし、このアプローチの大きな欠点は、ほとんどの MCS がパレート最適解に対応していないことである。 実際、与えられた MCS がすべての MCS が列挙されたとき、パレート最適解に対応することが分かる。 さらに、全ての MCS を列挙できない場合、パレートフロンティアの近似の品質を保証することは不可能である。 本稿では,mcssを用いたmobo解法の現状について述べる。 まず,各MCSがパレート最適解に対応するようなMOBO問題の解決にMCS列挙を用いることが可能であることを示す。 さらに,mcs列挙法を用いてパレートフロンティアの近似値(1 + {\varepsilon})を求めることができる2つの新しいアルゴリズムを提案する。 いくつかのベンチマークセットによる実験結果から,提案アルゴリズムは最先端のアルゴリズムよりもパレートフロンティアの近似の精度が向上し,近似比が保証された。

関連論文リスト

• Alternating Minimization Schemes for Computing Rate-Distortion-Perception Functions with $f$-Divergence Perception Constraints [10.564071872770146]
  離散メモリレスソースに対するRDPF(Ralse-Distortion-Perception Function)の計算について検討した。 最適パラメトリック解を特徴付ける。 歪みと知覚制約について十分な条件を提供する。
  論文  参考訳（メタデータ） (2024-08-27T12:50:12Z)
• FIMP-HGA: A Novel Approach to Addressing the Partitioning Min-Max Weighted Matching Problem [13.431192456490987]
  本稿では,PMMWM に対する高速反復マッチング分割ハイブリッド遺伝的アルゴリズム (FIMP-HGA) を提案する。 マッチング段階では、漸進的な調整によりマッチング複雑性を低減するKM-Mアルゴリズムを提案する。 分割段階では、エリート戦略を取り入れたHybrid Genetic Algorithm (HGA)を導入し、Greedy Partition Crossover (GPX) 演算子を設計する。
  論文  参考訳（メタデータ） (2024-05-06T05:57:46Z)
• Moreau Envelope ADMM for Decentralized Weakly Convex Optimization [55.2289666758254]
  本稿では,分散最適化のための乗算器の交互方向法(ADMM)の近位変種を提案する。 数値実験の結果,本手法は広く用いられている手法よりも高速かつ堅牢であることが示された。
  論文  参考訳（メタデータ） (2023-08-31T14:16:30Z)
• On the Global Solution of Soft k-Means [159.23423824953412]
  本稿では,ソフトk-平均問題の解法を全世界で提案する。 ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
  論文  参考訳（メタデータ） (2022-12-07T12:06:55Z)
• Faster One-Sample Stochastic Conditional Gradient Method for Composite Convex Minimization [61.26619639722804]
  滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。 提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
  論文  参考訳（メタデータ） (2022-02-26T19:10:48Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Effective multi-view registration of point sets based on student's t mixture model [15.441928157356477]
  本稿では,学生のt混合モデル(StMM)に基づく効果的な登録手法を提案する。 NNサーチ法により全てのt分布セントロイドが得られるため、マルチビュー登録を実現するのがより効率的である。 実験結果は,最先端手法よりも優れた性能と精度を示す。
  論文  参考訳（メタデータ） (2020-12-13T08:27:29Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Exact and Approximation Algorithms for Sparse PCA [1.7640556247739623]
  本稿では,MISDP(MISDP)とMISDP(MISDP)について述べる。 次に、それらの連続緩和値の理論的最適性ギャップを分析し、それらが最先端の値よりも強いことを証明する。 市販の解法は一般にMISDPを解くのが難しいため,MISDPと同等の大きさのMILP(mixed-integer linear program)を用いてSPCAを任意の精度で近似する。
  論文  参考訳（メタデータ） (2020-08-28T02:07:08Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Halpern Iteration for Near-Optimal and Parameter-Free Monotone Inclusion and Strong Solutions to Variational Inequalities [14.848525762485872]
  非拡張写像、単調リプシッツ作用素、近位写像の間の接続を利用して、単調包含問題に対する準最適解を得る。 これらの結果は、変分不等式問題に対する強い解の近似、凸凸凹 min-max 最適化問題の近似、および min-max 最適化問題における勾配のノルムの最小化について、ほぼ最適に保証される。
  論文  参考訳（メタデータ） (2020-02-20T17:12:49Z)

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

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