論文の概要: Optimization of Sums of Bivariate Functions: An Introduction to Relaxation-Based Methods for the Case of Finite Domains

• arxiv url: http://arxiv.org/abs/2511.20607v1
• Date: Tue, 25 Nov 2025 18:35:14 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-11-26 17:37:04.615428
• Title: Optimization of Sums of Bivariate Functions: An Introduction to Relaxation-Based Methods for the Case of Finite Domains
• Title（参考訳）: 双変数関数の和の最適化:有限領域の場合の緩和法入門
• Authors: Nils Müller,
• Abstract要約: 我々は、$n>2$引数を持つ関数の最適化を、それぞれ$n$引数の2ドルしか持たないいくつかの関数の和として表現する。 線形計画法、座標昇華法、閉形式解法で解けるいくつかのトラクタブル問題の定式化を導出する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the optimization of functions with $n>2$ arguments that have a representation as a sum of several functions that have only $2$ of the $n$ arguments each, termed sums of bivariates, on finite domains. The complexity of optimizing sums of bivariates is shown to be NP-equivalent and it is shown that there exists free lunch in the optimization of sums of bivariates. Based on measure-valued extensions of the objective function, so-called relaxations, $\ell^2$-approximation, and entropy-regularization, we derive several tractable problem formulations solvable with linear programming, coordinate ascent as well as with closed-form solutions. The limits of applying tractable versions of such relaxations to sums of bivariates are investigated using general results for reconstructing measures from their bivariate marginals. Experiments in which the derived algorithms are applied to random functions, vertex coloring, and signal reconstruction problems provide insights into qualitatively different function classes that can be modeled as sums of bivariates.
• Abstract（参考訳）: 我々は、それぞれ$n>2$の引数の2ドルしか持たないいくつかの関数の和としての表現を持つ$n>2$の引数を持つ関数の最適化について、有限領域上の双変数の和と呼ばれる。 二変数の和を最適化する複雑さはNP等価であることが示され、二変数の和の最適化に自由ランチが存在することが示されている。 対象関数の測度値拡張、いわゆる緩和、$\ell^2$-approximation、エントロピー正則化に基づいて、線形計画法、座標昇華法および閉形式解で解けるいくつかのトラクタブル問題の定式化を導出する。 このような緩和のトラクタブルバージョンを二変量和に適用する限界について, 一般結果を用いて検討した。 導出アルゴリズムがランダム関数、頂点色、信号再構成問題に適用される実験は、二変数の和としてモデル化できる定性的に異なる関数クラスに対する洞察を与える。

関連論文リスト

• Non-linear Multi-objective Optimization with Probabilistic Branch and Bound [6.305913808037513]
  多重目的確率分岐と単観察境界(MOPBnB(so))と呼ばれる多目的シミュレーション最適化アルゴリズムを提案する。 その結果、MOPBnB(so)と比較すると、複数の複製を持つ変種は計算資源の面で極めて集中的であることが明らかとなった。 さらに,MOPBnB(so) は遺伝子アルゴリズムNSGA-II よりも高い性能を示した。
  論文  参考訳（メタデータ） (2025-06-05T02:01:08Z)
• Stochastic Momentum Methods for Non-smooth Non-Convex Finite-Sum Coupled Compositional Optimization [68.22688819802622]
  我々は、(ほぼ)$レベルのKKTソリューションを見つけるために、$O(/epsilon)$の最先端の複雑さを新たに提案する。 O(/epsilon)$ の(ほぼ) $ レベルの KKT ソリューションを見つけるための技術的複雑さを適用することで、(ほぼ) $ レベルの KKT ソリューションを見つけるための $O(/epsilon)$ の最先端の複雑さを新たに達成する。
  論文  参考訳（メタデータ） (2025-06-03T06:31:59Z)
• Decomposed Global Optimization for Robust Point Matching with Low-Dimensional Branching [41.05165517541873]
  部分重なり合う点集合を整列する新しい大域的最適化手法を提案する。 本手法は非剛性変形, 位置雑音, 外れ値に優れた強靭性を示す。 2次元および3次元合成および実世界のデータを用いた実験により,本手法は最先端の手法と比較して,外れ値に対して優れた強靭性を示すことが示された。
  論文  参考訳（メタデータ） (2024-05-14T13:28:57Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  非滑らかな非最適化問題は、機械学習とビジネス製造に現れる。 2つのコア課題は、有限収束を保証する効率的な方法の開発を妨げる。 GFMとSGFMの2相版も提案され, 改良された大規模評価結果が得られた。
  論文  参考訳（メタデータ） (2022-09-12T06:53:24Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  部分観察決定過程(POMDP)の無限観測および状態空間を用いた強化学習について検討した。 線形構造をもつPOMDPのクラスに対する部分可観測性と関数近似の最初の試みを行う。
  論文  参考訳（メタデータ） (2022-04-20T21:15:38Z)
• A Granular Sieving Algorithm for Deterministic Global Optimization [6.01919376499018]
  リプシッツ連続関数に対する大域的最適化問題を解くために、勾配のない決定論的手法を開発した。 この方法は、目的関数の領域と範囲の両方で同期解析を行うグラニュラーシービングとみなすことができる。
  論文  参考訳（メタデータ） (2021-07-14T10:03:03Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• Ridge regression with adaptive additive rectangles and other piecewise functional templates [0.0]
  関数線形回帰モデルに対する$L_2$ベースのペナル化アルゴリズムを提案する。 提案アルゴリズムは,適切なテンプレートの近似と凸リッジのような問題の解法とを交互に行う方法を示す。
  論文  参考訳（メタデータ） (2020-11-02T15:28:54Z)
• Efficient algorithms for multivariate shape-constrained convex regression problems [9.281671380673306]
  最小二乗推定器は、制約付き凸プログラミング(QP)問題を$(n+1)d$変数と少なくとも$n(n-1)$線形不等式制約で解くことで計算可能であることを証明している。 一般に非常に大規模な凸QPを解くために、我々は2つの効率的なアルゴリズムを設計する。1つは対称ガウス・シーデルに基づく乗算器の交互方向法(tt sGS-ADMM)であり、もう1つは半滑らかニュートン法(tt)によって解かれる部分プロブレムを持つ近似拡張ラグランジアン法(tt pALM)である。
  論文  参考訳（メタデータ） (2020-02-26T11:18:43Z)
• Complexity of Finding Stationary Points of Nonsmooth Nonconvex Functions [84.49087114959872]
  非滑らかで非滑らかな関数の定常点を見つけるための最初の非漸近解析を提供する。 特に、アダマール半微分可能函数(おそらく非滑らか関数の最大のクラス)について研究する。
  論文  参考訳（メタデータ） (2020-02-10T23:23:04Z)

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

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