黄金分割探索

黄金分割探索は、指定された区間内で関数の極値（最小値または最大値）を見つける手法です。区間内に極値を持つ厳密に単峰性の関数の場合はその極値を見つけますが、区間に複数の極値（区間の境界を含む可能性あり）がある場合は、そのうちの 1 つに収束します。区間上の唯一の極値が区間の境界上にある場合は、その境界点に収束します。この方法は、指定された区間の値の範囲を順次狭めていくことで動作します。そのため、比較的低速ですが、非常に堅牢です。この手法の名前は、3 つの区間幅がφ :1: φの比率にある 4 つの点の関数値を維持するアルゴリズムに由来しています。ここで、 φは黄金比です。これらの比率は各反復で維持され、最大限に効率的です。境界点を除き、最小値を検索する場合、中心点は常に外側の点以下であり、外側の点の間に最小値が含まれることが保証されます。最大値を検索する場合は逆のことが当てはまります。このアルゴリズムは、多くの関数評価におけるフィボナッチ検索の限界です (以下でも説明します)。フィボナッチ検索と黄金分割検索は、Kiefer (1953) によって発見されました (Avriel と Wilde (1966) も参照)。

ここでの議論は、単峰性関数の最小値の検索（最大値の検索も同様）という観点から提起されています。ゼロの検索では、反対の符号を持つ 2 つの関数評価で根を囲むのに十分ですが、最小値の検索では 3 つの値が必要です。黄金分割検索は、最小値を見つける間隔を徐々に狭める効率的な方法です。重要なのは、評価された点の数に関係なく、最小値は、これまでに評価された最小値を持つ点に隣接する 2 つの点によって定義される間隔内にあることに気付くことです。

上の図は、最小値を見つける手法の 1 つのステップを示しています。 の機能値は垂直軸上にあり、水平軸はxパラメータです。 の値は、、、の3 つのポイントですでに評価されています。 はまたはのどちらよりも小さいため、最小値はからまでの区間内にあることは明らかです。 ${\displaystyle f(x)}$${\displaystyle f(x)}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle x_{3}}$${\displaystyle f_{2}}$${\displaystyle f_{1}}$${\displaystyle f_{3}}$${\displaystyle x_{1}}$${\displaystyle x_{3}}$

最小化プロセスの次のステップは、関数をxの新しい値、つまりで評価して「プローブ」することです。最も効率的なのは、最大区間内のどこか、つまりと の間を選択することです。図から、関数が を生成する場合、最小値はと の間にあり、新しい 3 つのポイントは 、、および になることは明らかです。ただし、関数が値 を生成する場合、最小値はと の間にあり、新しい 3 つのポイントは、、および になります。したがって、どちらの場合でも、関数の最小値を確実に含む、より狭い新しい検索区間を構築できます。 ${\displaystyle x_{4}}$${\displaystyle x_{4}}$${\displaystyle x_{2}}$${\displaystyle x_{3}}$${\displaystyle f_{4a}>f(x_{2})}$${\displaystyle x_{1}}$${\displaystyle x_{4}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle x_{4}}$${\displaystyle f_{4b} <f(x_{2})}$${\displaystyle x_{2}}$${\displaystyle x_{3}}$${\displaystyle x_{2}}$${\displaystyle x_{4}}$${\displaystyle x_{3}}$

上の図から、新しい検索間隔は、長さがa  +  cのと の間、または長さがbのとの間のいずれかになることがわかります。黄金分割検索では、これらの間隔が等しくなければなりません。等しくない場合、「不運」が続くと、より広い間隔が何度も使用され、収束速度が遅くなる可能性があります。b = a + cを確実にするために、アルゴリズムは を選択する必要があり ます 。 ${\displaystyle x_{1}}$${\displaystyle x_{4}}$${\displaystyle x_{2}}$${\displaystyle x_{3}}$${\displaystyle x_{4}=x_{1}+(x_{3}-x_{2})}$

しかし、を およびに対してどこに配置するかという問題がまだ残っています。黄金分割探索では、これらの点の間隔が、後続の 3 つのまたはと同じ間隔の割合になるように選択します。アルゴリズム全体で同じ間隔の割合を維持することで、が またはに非常に近くなる状況を回避し、各ステップで区間幅が同じ一定の割合で縮小することを保証します。 ${\displaystyle x_{2}}$${\displaystyle x_{1}}$${\displaystyle x_{3}}$${\displaystyle x_{1},x_{2},x_{4}}$${\displaystyle x_{2},x_{4},x_{3}}$${\displaystyle x_{2}}$${\displaystyle x_{1}}$${\displaystyle x_{3}}$

数学的には、評価後の間隔がその評価前の間隔に比例することを保証するには、がであり、新しい3つの点が、、およびである場合、次のようにします。 ${\displaystyle f(x_{4})}$${\displaystyle f(x_{4})}$${\displaystyle f_{4a}}$${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle x_{4}}$

${\displaystyle {\frac {c}{a}}={\frac {a}{b}}.}$

しかし、がであり、新しい3つの点が、、およびである場合、 ${\displaystyle f(x_{4})}$${\displaystyle f_{4b}}$${\displaystyle x_{2}}$${\displaystyle x_{4}}$${\displaystyle x_{3}}$

${\displaystyle {\frac {c}{bc}}={\frac {a}{b}}.}$

これら2つの同時方程式から cを消去すると、

${\displaystyle \left({\frac {b}{a}}\right)^{2}-{\frac {b}{a}}=1,}$

または

${\displaystyle {\frac {b}{a}}=\varphi ,}$

ここでφは黄金比です。

${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}=1.618033988\ldots }$

評価ポイントの比例間隔に黄金比が現れることから、この検索アルゴリズムの名前が付けられています。

アプリケーションに応じて、任意の数の終了条件を適用できます。区間 Δ X = X ₄ − X _{1は、最小値}Xの推定における絶対誤差の尺度であり、アルゴリズムを終了するために使用できます。 Δ Xの値は、各反復でr = φ − 1の係数で減少するため、 Δ Xの絶対誤差に達するまでの反復回数は、約 ln(Δ X /Δ X ₀ ) / ln( r ) です。ここで、 Δ X _{0は Δ} Xの初期値です。

滑らかな関数は最小値の近くでは平坦（1次導関数がゼロに近い）なので、最小値を見つける際にあまり高い精度を期待しないように注意する必要があります。Numerical Recipes in Cで提供される終了条件は、、、および間のギャップをテストし、相対精度の境界内にあるときに終了することに基づいています。 ${\displaystyle x_{1}}$${\displaystyle x_{2}}$${\displaystyle x_{3}}$${\displaystyle x_{4}}$

${\displaystyle |x_{3}-x_{1}|<\tau {\big (}|x_{2}|+|x_{4}|{\big )},}$

ここで、 はアルゴリズムの許容パラメータであり、は の絶対値です。 チェックは、 の相対誤差が典型的なケースでは の絶対誤差の二乗にほぼ比例するため、その中心値に対する括弧サイズに基づきます。 同じ理由から、Numerical Recipes のテキストでは を推奨しています。ここで、 はの必要な絶対精度です。 ${\displaystyle \tau}$${\displaystyle |x|}$${\displaystyle x}$${\displaystyle x}$${\displaystyle f(x)}$${\displaystyle \tau ={\sqrt {\varepsilon }}}$${\displaystyle \epsilon }$${\displaystyle f(x)}$

注意!ここでの例では、関数の 最小値を見つけるためのアルゴリズムについて説明しています。最大値の場合は、比較演算子を逆にする必要があります。

1. 最小化${\displaystyle f(x)}$する関数、検索する区間を{ X ₁、X ₄ }として指定し、その関数値F ₁とF _4を指定します。
2. 内部点とその関数値 F ₂を計算します。2 つの区間の長さの比はc : rまたはr : cです。ここでr = φ − 1、c = 1 − rであり、φは黄金比です。
3. 3 つ組を使用して、収束基準が満たされているかどうかを判断します。満たされている場合は、その 3 つ組から最小値の X を推定して返します。
4. 3つ組から、他の内部点とその関数値を計算します。3つの区間の比率は⁠ ⁠${\displaystyle c:cr:c}$になります。
5. 次の反復の 3 つのポイントは、F が最小値となるポイントと、X 内でそれに最も近い 2 つのポイントになります。
6. ステップ3に進みます。

"""
黄金分割探索用の Python プログラム。この実装では
関数の評価を再利用せず、最小値は c
または d (a または b のエッジではない) であると想定します。 
"""

インポート 数学

invphi  =  (数学.sqrt ( 5 ) -1 ) / 2 # 1/ phi      


def  gss ( f ,  a ,  b ,  tolerance = 1e-5 ): 
"""     [a,b]上の f の最小値を見つけるための    黄金分割検索    



    * f: [a,b]上の厳密に単峰性の関数

    例: 
    >>> def f(x): return (x - 2) ** 2 
    >>> x = gss(f, 1, 5) 
    >>> print(f"{x:.5f}") 
    2.00000

    """ 
    b - a >許容値の場合 : c = b - ( b - a ) * invphi d = a + ( b - a ) * invphi f ( c ) < f ( d )の場合: b = dそれ以外の場合: # f(c) > f(d) 最大値を見つけるにはa = c    
                
                
           
              
          
              

     （b  +  a ） /  2を返す

// a と c は検索範囲を定義します
// func(x) は最小化される x での関数の値を返します
function goldenSection ( a , c , func ) { function split ( x1 , x2 ) { return x1 + 0.6180339887498949 * ( x2 - x1 ); } var b = split ( a , c ); var bv = func ( b ); while ( a != c ) { var x = split ( a , b ); var xv = func ( x ); if ( xv < bv ) { bv = xv ; c = b ; b = x ; } else { a = c ; c = x ; } } return b ; } function test ( x ) { return - Math . sin ( x ); } console . log ( goldenSection ( 0 , 3 , test )); // PI/2 を出力します    
          
      
     
      
        
       
        
        
        
        
    
     
        
        
    
  
   

     
   

"""
黄金分割探索用の Python プログラム。この実装では
関数の評価を再利用せず、最小値は c
または d (a または b のエッジではない) であると想定します。 
"""

インポート 数学

invphi  =  ( math . sqrt ( 5 )  -  1 )  /  2   # 1 / phi 
invphi2  =  ( 3  -  math . sqrt ( 5 ))  /  2   # 1 / phi^2


def  gss ( f ,  a ,  b ,  tolerance = 1e-5 ): 
"""    黄金分割探索。    



    区間 [a,b]
    内に単一の局所最小値を持つ関数 f が与えられた場合、gss は    、dc <= 許容値の最小値を含むサブセット区間 [c,d] を返します。

    例: 
    >>> def f(x): return (x - 2) ** 2 
    >>> print(*gss(f, a=1, b=5, tolerance=1e-5)) 
    1.9999959837979107 2.0000050911830893 
    """ 
    a ,  b  =  min ( a ,  b ),  max ( a ,  b ) 
    h  =  b  -  a 
    if  h  <=  tolerance : 
        return  ( a ,  b )

    # 許容範囲を達成するために必要な手順
    n  =  int ( math . ceil ( math . log ( tolerance  /  h )  /  math . log ( invphi )))

    c ,  d  =  a  +  invphi2  *  h ,  a  +  invphi  *  h 
    yc ,  yd  =  f ( c ),  f ( d )

     _が 範囲( n - 1 )の 場合: h *= invphi yc < ydの場合: b 、d = d 、c yd = yc c = a + invphi2 * h yc = f ( c ) else : # yc > yd 最大値を求めるa 、c = c 、d yc = yd d = a + invphi * h yd = f ( d )  
          
           
                
              
                  
              
          
                
              
                  
              

     yc < ydの場合は( a ,  d ) を返し、そうでない場合は( c , b )を返す      

パブリッククラスGoldenSectionSearch {パブリックstatic final double invphi = ( Math . sqrt ( 5.0 ) - 1 ) / 2.0 ;パブリックstatic final double invphi2 = ( 3 - Math . sqrt ( 5.0 )) / 2.0 ;   
              
              

    パブリックインターフェース関数{ double of ( double x ); }   
          
    

    // fの最小値を含む[a,b]の部分区間を返す

    public static double [] gss ( Function f 、double a 、double b 、double tol ) { return gss ( f 、a 、b 、tol 、b - a 、true 、0 、0 、true 、0 、0 ); } private static double [] gss ( Function f 、double a 、double b 、double tol 、double h 、boolean noC 、double c 、double fc 、boolean noD 、double d 、double fd ) { if ( Math . abs ( h ) <= tol ) { return new double [] { a 、b }; } if ( noC ) { c = a + invphi2 * h ; fc = f . of ( c ); } if ( noD ) { d = a + invphi * h ; fd = f . of ( d ); } if ( fc < fd ) { // fc > fd で最大値を求めるreturn gss ( f , a , d , tol , h * invphi , true , 0 , 0 , false , c , fc ); } else { return gss ( f ,           
                     
    
              
                                       
                                      
            
                  
        
          
                  
              
        
          
                  
              
        
              
                         
          
              c 、b 、tol 、h * invphi 、false 、d 、fd 、true 、0、0 ) ; } }​           
        
    

    public static void main ( String [] args ) { Function f = ( x ) -> Math . pow ( x - 2 , 2 ); double a = 1 ; double b = 5 ; double tol = 1e-5 ; double [] ans = gss ( f , a , b , tol ); System . out . println ( "[" + ans [ 0 ] + "," + ans [ 1 ] + "]" ); // [1.9999959837979107,2.0000050911830893] } }     
            
           
           
           
               
                
        
    

インポート 数学


invphi  =  ( math . sqrt ( 5 )  -  1 )  /  2   # 1 / phi 
invphi2  =  ( 3  -  math . sqrt ( 5 ))  /  2   # 1 / phi^2


def  gssrec ( f ,  a ,  b ,  tol = 1e-5 ,  h = None ,  c = None ,  d = None ,  fc = None ,  fd = None ): 
"""黄金分割検索、再帰的。    


    区間 [a, b]
    内に単一の局所最小値を持つ関数 f が与えられた場合、gss は    dc <= tol の最小値を含むサブセット区間 [c, d] を返します。

    例: 
    >>> f = lambda x: (x - 2) ** 2 
    >>> a = 1 
    >>> b = 5 
    >>> tol = 1e-5 
    >>> (c, d) = gssrec(f, a, b, tol) 
    >>> print (c, d) 
    1.9999959837979107 2.0000050911830893 
    """

    ( a ,  b )  =  ( min ( a ,  b ),  max ( a ,  b )) 
    hがNone の場合 : h = b - a h <= tol の場合: return ( a , b ) cがNone の場合: c = a + invphi2 * h dがNone の場合: d = a + invphi * h fcがNone の場合: fc = f ( c ) fdがNone の場合: fd = f ( d ) fc < fd : # fc > fdの場合、最大値を見つけるには、gssrec ( f , a , d , tol , h * invphi , c = None , fc = None , d = c , fd = fc )を返します。そうでない場合は、gssrec ( f , c , b , tol , h * invphi , c = d , fc = fd , d = None , fd = None )を返します。  
            
       
          
       
              
       
              
       
          
       
          
         
                   
    
                   

非常によく似たアルゴリズムを使用して、単一の極小値または極大値を持つ値のシーケンスの極値(最小値または最大値)を見つけることもできます。整数シーケンス インデックスのみをプローブしながら黄金分割検索のプローブ位置を近似するために、この場合のアルゴリズムのバリアントでは通常、括弧で囲まれた区間の長さがフィボナッチ数になるソリューションの括弧が維持されます。このため、黄金分割検索のシーケンス バリアントは、フィボナッチ検索と呼ばれることがよくあります。

フィボナッチ探索は、区間内の単峰関数の最大値（最小値）を求める ミニマックス探索として、 Kiefer（1953）によって最初に考案されました。

二分法は、関数のゼロを見つけるための同様のアルゴリズムです。ゼロを囲むには、3 つの点ではなく 2 つの点だけが必要であることに注意してください。間隔比は、黄金比ではなく、各ステップで 2 ずつ減少します。

• 三項検索
• ブレント法
• バイナリ検索

• Kiefer, J. (1953)、「最大値を求める逐次ミニマックス探索」、アメリカ数学会紀要、4 (3): 502–506、doi : 10.2307/2032161、JSTOR  2032161、MR  0055639
• アヴリエル、モーデカイ、ワイルド、ダグラス J. (1966)、「対称フィボナッチ探索法の最適性証明」、フィボナッチ クォータリー、4 : 265–269、MR  0208812

• Press, WH; Teukolsky, SA; Vetterling, WT; Flannery, BP (2007)、「セクション 10.2. 1 次元での黄金分割検索」、Numerical Recipes: The Art of Scientific Computing (第 3 版)、ニューヨーク: Cambridge University Press、ISBN 978-0-521-88068-8、2011年8月11日にオリジナルからアーカイブされ、2011年8月12日に取得