論文の概要: Multiplying poles to avoid unwanted points in root finding and
optimization
- arxiv url: http://arxiv.org/abs/2309.11475v1
- Date: Wed, 20 Sep 2023 17:20:41 GMT
- ステータス: 処理完了
- システム内更新日: 2023-09-21 15:21:23.265352
- Title: Multiplying poles to avoid unwanted points in root finding and
optimization
- Title(参考訳): ルート探索と最適化における不要点回避のための極の乗算
- Authors: Tuyen Trung Truong
- Abstract要約: ルート探索と最適化では、閉集合 $A$ 1 が A に収束しない場合が多い。
そこで本稿では,距離関数の適切なパワーによってコスト関数を$A$に分割する手法を提案する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: In root finding and optimization, there are many cases where there is a
closed set $A$ one does not the sequence constructed by one's favourite method
will converge to A (here, we do not assume extra properties on $A$ such as
being convex or connected). For example, if one wants to find roots, and one
chooses initial points in the basin of attraction for 1 root $x^*$ (a fact
which one may not know before hand), then one will always end up in that root.
In this case, one would like to have a mechanism to avoid this point $z^*$ in
the next runs of one's algorithm.
In this paper, we propose a new method aiming to achieve this: we divide the
cost function by an appropriate power of the distance function to $A$. This
idea is inspired by how one would try to find all roots of a function in 1
variable. We first explain the heuristic for this method in the case where the
minimum of the cost function is exactly 0, and then explain how to proceed if
the minimum is non-zero (allowing both positive and negative values). The
method is very suitable for iterative algorithms which have the descent
property. We also propose, based on this, an algorithm to escape the basin of
attraction of a component of positive dimension to reach another component.
Along the way, we compare with main existing relevant methods in the current
literature. We provide several examples to illustrate the usefulness of the new
approach.
- Abstract(参考訳): ルート探索と最適化では、閉じた集合 $a$ が存在して、自分の好きな方法で構築された列が a に収束しないケースが多数存在する(ここでは、凸または連結のような$a$ 上の追加のプロパティを仮定しない)。
例えば、もしルートを見つけたいとすると、1つのルート$x^*$(手元が知らないかもしれない事実)のアトラクションの流域の初期点を選ぶと、必ずそのルートに現れる。
この場合、アルゴリズムの次の実行において、このポイント$z^*$を避けるメカニズムを持つ必要がある。
本稿では,距離関数の適切なパワーによってコスト関数を$A$に分割する手法を提案する。
この考えは 1 変数の関数のすべての根を見つける方法に着想を得たものである。
まず、コスト関数の最小値がちょうど 0 である場合にこの方法のヒューリスティックを説明し、最小値が 0 でない場合(正値と負値の両方が許容できる)にどのように進むかを説明する。
この手法は降下特性を持つ反復アルゴリズムに非常に適している。
また, これに基づいて, 正次元成分のアトラクションを回避し, 別の成分に到達するためのアルゴリズムを提案する。
その過程で,現在の文献における既存手法との比較を行った。
新しいアプローチの有用性を説明するために、いくつかの例を挙げる。
関連論文リスト
- ADMM for Structured Fractional Minimization [7.9047096855236125]
我々は、数値化器が微分可能な関数を含むような、構造化された分数問題のクラスを考える。
本稿では,このクラスの問題に対して,最初の乗算器の交換法であるsf FADMMを紹介する。
論文 参考訳(メタデータ) (2024-11-12T02:50:12Z) - Mutually unbiased bases as a commuting polynomial optimisation problem [0.0]
我々は、実数に対する最適化問題として、相互に偏りのない基底の問題を考察する。
最適化手法を多数組み合わせた2つの手法を用いる。
このようなアルゴリズムが最終的に有限メモリで次元6に関するオープンな問題を解くことを実証する。
論文 参考訳(メタデータ) (2023-08-03T17:14:22Z) - An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue
Optimization Problems [76.2042837251496]
相補的な合成条件に基づく2つの難解なミラー降下アルゴリズムを導入する。
注目すべきは、どちらのアルゴリズムも、目的関数のリプシッツ定数や滑らかさに関する事前の知識なしで機能する。
本稿では,大規模半確定プログラム上での手法の効率性とロバスト性を示す。
論文 参考訳(メタデータ) (2023-06-30T08:34:29Z) - Explicit Second-Order Min-Max Optimization Methods with Optimal Convergence Guarantee [86.05440220344755]
我々は,非制約のmin-max最適化問題のグローバルなサドル点を求めるために,不正確な正規化ニュートン型手法を提案し,解析する。
提案手法は有界集合内に留まるイテレートを生成し、その反復は制限関数の項で$O(epsilon-2/3)$内の$epsilon$-saddle点に収束することを示す。
論文 参考訳(メタデータ) (2022-10-23T21:24:37Z) - Submodular + Concave [53.208470310734825]
第一次最適化法が凹関数の最大目的値に収束できることはよく確立されている。
本研究では、滑らかな函数凸体(英語版)の行列式を$F(x) = G(x) +C(x)$で始める。
このクラスの函数は、保証がないような凹凸函数と連続DR-部分モジュラ函数の両方の拡張である。
論文 参考訳(メタデータ) (2021-06-09T01:59:55Z) - Bayesian Algorithm Execution: Estimating Computable Properties of
Black-box Functions Using Mutual Information [78.78486761923855]
多くの現実世界では、T関数の評価の予算を考えると、高価なブラックボックス関数 f の性質を推測したい。
本稿では,アルゴリズムの出力に対して相互情報を最大化するクエリを逐次選択する手法InfoBAXを提案する。
これらの問題に対してInfoBAXは、元のアルゴリズムで要求されるより500倍少ないクエリをfに使用する。
論文 参考訳(メタデータ) (2021-04-19T17:22:11Z) - Saddle Point Optimization with Approximate Minimization Oracle [8.680676599607125]
サドル点最適化に対する主要なアプローチである$min_xmax_y f(x, y)$は、GAN(Generative Adversarial Network)によって一般化される勾配に基づくアプローチである。
対照的に、最小化問題を解くオラクルのみに依存する代替手法を解析する。
我々のアプローチでは、近似解 $x'$ と $y'$ to $min_x'f(x', y)$ を与えられた点 $(x, y)$ に配置し、これらの近似解 $(x', y)$ に更新する。
論文 参考訳(メタデータ) (2021-03-29T23:03:24Z) - Finding Global Minima via Kernel Approximations [90.42048080064849]
関数評価のみに基づく滑らかな関数のグローバル最小化を考える。
本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
論文 参考訳(メタデータ) (2020-12-22T12:59:30Z) - Unconstrained optimisation on Riemannian manifolds [0.0]
本稿では, (Local-) Backtracking Gradient Descent と New Q-Newton の手法について記述する。
また、対称正方行列の最小固有値を計算するための明示的な計算を行う。
論文 参考訳(メタデータ) (2020-08-25T15:10:21Z) - Gradient-Free Methods for Saddle-Point Problem [125.99533416395765]
我々はGasnikov et al., 2017のアプローチを一般化し、不正確な勾配のないオラクルで(確率的な)凸最適化問題を解けるようにした。
我々のアプローチは、$fracnlog n$ の要求するオラクル呼び出しの回数を削減します。
論文の後半では、そのような仮定ができない場合を分析し、この問題を解決する方法の近代化方法に関する一般的なアプローチを提案する。
論文 参考訳(メタデータ) (2020-05-12T16:44:27Z) - Riemannian Stochastic Proximal Gradient Methods for Nonsmooth
Optimization over the Stiefel Manifold [7.257751371276488]
R-ProxSGDとR-ProxSPBは、近位SGDと近位SpiderBoostの一般化である。
R-ProxSPBアルゴリズムは、オンラインの場合で$O(epsilon-3)$ IFOs、有限サムの場合は$O(n+sqrtnepsilon-3)$ IFOsである。
論文 参考訳(メタデータ) (2020-05-03T23:41:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。