自己 一致関数とは、ある 微分不等式 を満たす関数であり、 ニュートン法 [1] を用いた 最適化 が特に容易になります 。6.2.4.2節 自己 一致障壁 とは、特定の自己一致関数であり、 特定の凸集合に対する 障壁関数でもあります。自己一致障壁は、最適化における 内点法 の重要な要素です。
自己一致関数
多変量自己一致関数 自己一致関数の一般的な定義は以下の通りである。 [2] : 定義2.0.1
C を R n の凸非空 開集合 とする 。f を C 上で定義される3回連続微分可能な関数とする。f が以下の性質を満たすとき、 f は C 上で自己一致的である と言う。
1. 障壁特性: C の境界点に収束する C 内の任意の点の列上で 、 f は ∞に収束します。
2. 微分不等式： C 内の 任意の点 x と R n 内の任意の方向h に対して、 g h を 方向 h に制限された関数 f とします。すなわち、 g h ( t ) = f ( x + t* h ) です。このとき、1次元関数 g h は次の微分不等式を満たします。
| g h ‴ ( x ) | ≤ 2 g h ″ ( x ) 3 / 2 {\displaystyle |g_{h}'''(x)|\leq 2g_{h}''(x)^{3/2}} 。
同様に: [3]
d d α ∇ 2 f ( x + α y ) | α = 0 ⪯ 2 y T ∇ 2 f ( x ) y ∇ 2 f ( x ) {\displaystyle \left.{\frac {d}{d\alpha }}\nabla ^{2}f(x+\alpha y)\right|_{\alpha =0}\preceq 2{\sqrt {y^{T}\nabla ^{2}f(x)\,y}}\,\nabla ^{2}f(x)}
一変量自己一致関数 関数 が 自己一致となるのは、次の 場合です。 f : R → R {\displaystyle f:\mathbb {R} \rightarrow \mathbb {R} } R {\displaystyle \mathbb {R} }
| f ‴ ( x ) | ≤ 2 f ″ ( x ) 3 / 2 {\displaystyle |f'''(x)|\leq 2f''(x)^{3/2}} 同様に、次の 条件が満たされる場合は、 f ″ ( x ) > 0 {\displaystyle f''(x)>0}
| d d x 1 f ″ ( x ) | ≤ 1 {\displaystyle \left|{\frac {d}{dx}}{\frac {1}{\sqrt {f''(x)}}}\right|\leq 1} 他の部分も満足します 。 f ‴ ( x ) = 0 {\displaystyle f'''(x)=0}
例 線形関数と凸二次関数は、3 次導関数が 0 であるため自己一致します。 が定義され、すべての に対して凸であり 、が成り立つ ことを検証する 任意の関数は 、その定義域 上で自己一致します 。いくつかの例を以下に示します。 f ( x ) = − log ( − g ( x ) ) − log x {\displaystyle f(x)=-\log(-g(x))-\log x} g ( x ) {\displaystyle g(x)} x > 0 {\displaystyle x>0} | g ‴ ( x ) | ≤ 3 g ″ ( x ) / x {\displaystyle |g'''(x)|\leq 3g''(x)/x} { x ∣ x > 0 , g ( x ) < 0 } {\displaystyle \{x\mid x>0,g(x)<0\}} g ( x ) = − x p {\displaystyle g(x)=-x^{p}} のために 0 < p ≤ 1 {\displaystyle 0<p\leq 1} g ( x ) = − log x {\displaystyle g(x)=-\log x} g ( x ) = x p {\displaystyle g(x)=x^{p}} のために − 1 ≤ p ≤ 0 {\displaystyle -1\leq p\leq 0} g ( x ) = ( a x + b ) 2 / x {\displaystyle g(x)=(ax+b)^{2}/x} 条件を満たす任意の関数については、 を持つ 関数 も条件を満たします。 g {\displaystyle g} g ( x ) + a x 2 + b x + c {\displaystyle g(x)+ax^{2}+bx+c} a ≥ 0 {\displaystyle a\geq 0} 自己一致しないいくつかの関数:
f ( x ) = e x {\displaystyle f(x)=e^{x}} f ( x ) = 1 x p , x > 0 , p > 0 {\displaystyle f(x)={\frac {1}{x^{p}}},x>0,p>0} f ( x ) = | x p | , p > 2 {\displaystyle f(x)=|x^{p}|,p>2}
自己一致障壁 自己一致障壁（SCB）の一般的な定義は以下の通りである。 [2] : 定義3.1.1
C をR n 内の凸閉集合とし、 その 内部は空でないものとする。f をinterior( C ) から R への関数とする。M >0 を実パラメータとする。f が 以下の式を満たすとき、 fは Cに対して M -自己一致障壁 である という。
1. fは内部( C )上の自己一致関数である 。
2. interior( C )内の
任意の点 x と R n 内の任意の方向h に対して、 g h を 方向 h に制限した関数 f とする。すなわち、 g h ( t ) = f ( x + t* h )とする。このとき、1次元関数 g h は次の微分不等式を満たす。
| g h ′ ( x ) | ≤ M 1 / 2 ⋅ g h ″ ( x ) 1 / 2 {\displaystyle |g_{h}'(x)|\leq M^{1/2}\cdot g_{h}''(x)^{1/2}} 。
SCBの構築 内点法における SCB の重要性のため、さまざまなドメインに対して SCB を構築する方法を知ることが重要です。
理論的には、R n内の任意の 閉凸 領域は、パラメータ O( n )を持つ自己一致障壁を持つ ことが証明できる 。しかし、この「普遍障壁」は多変数積分によって与えられ、実際の計算には複雑すぎる。したがって、主な目標は、効率的に計算可能な自己一致障壁を構築することである。 [4] : 9.2.3.3節
SCB はいくつかの基本的な SCB から構築することができ、いくつかの 組み合わせ規則 を使用して、より複雑なドメインの SCB を生成するために組み合わせられます 。
基本的なSCB 全ての定数は、パラメータM=0のR n に対して自己一致障壁となる 。これは空間全体に対して唯一の自己一致障壁であり、 M < 1の場合にのみ自己一致障壁となる。 [2] ：例3.1.1 [線形関数と二次関数は自己一致関数であるが、自己一致障壁では ないこと に注意]。
正の半直線 ( ) に対して、 はパラメータ を持つ自己一致障壁である 。これは定義から直接証明できる。 R + {\displaystyle \mathbb {R} _{+}} x > 0 {\displaystyle x>0} f ( x ) = − ln x {\displaystyle f(x)=-\ln x} M = 1 {\displaystyle M=1}
置換ルール Gを R n の閉凸領域とし 、 g を Gの M -SCB とする 。 x = Ay + bを R k からR n へのアフィン写像とし、その像は G の内部と交差するものとする 。 H を、 H = { y in R k | Ay+b in G }の 写像による G の逆像とする。 h を合成関数 h ( y ) := g( Ay + b ) とする。このとき、 hは Hの M -SCB となる 。 [2] : Prop.3.1.1
例えば、 n = 1、 G を 正の半直線、 とします 。任意の k に対して、 a を k 元ベクトル、 b をスカラーとします。H = { y in R k | a T y+b ≥ 0} = a k 次元半空間とします 。 置換 規則 により 、 は H に対して 1 - SCB です 。 より 一般 的な形式は H = { x in R k | a T x ≤ b} で、この場合の SCB は です 。 g ( x ) = − ln x {\displaystyle g(x)=-\ln x} h ( y ) = − ln ( a T y + b ) {\displaystyle h(y)=-\ln(a^{T}y+b)} h ( y ) = − ln ( b − a T y ) {\displaystyle h(y)=-\ln(b-a^{T}y)}
置換規則は、アフィン写像から特定のクラスの「適切な」写像 [2] : Thm.9.1.1 および二次写像[2] : Sub.9.3 に拡張することができる。
デカルト積の法則 1,..., mに属するすべての i に対し 、 G i を R ni に属する閉凸領域とし 、 g i をG i のM i -SCB とする 。G を すべての G i の直積 とする。g (x 1 ,...,x m ) := sum i g i ( x i )とする 。すると、 gは G の SCB であり 、パラメータ sum i M i を持つ。 [2] : Prop.3.1.1
例えば、すべての G i を 正の半直線とすると、 G は正の直交座標 となります 。Gの m -SCB を とします 。 R + m {\displaystyle \mathbb {R} _{+}^{m}} g ( x ) = − ∑ i = 1 m ln x i {\displaystyle g(x)=-\sum _{i=1}^{m}\ln x_{i}}
ここで置換規則を適用できます。1 ,..., mにおける j に対して線型不等式 a j T x ≤ b j で定義される多面体に対して、 スレーターの条件 を満たす場合 、 は m -SCB となります。線型関数は 二次関数 に置き換えることができます 。 f ( x ) = − ∑ i = 1 m ln ( b j − a j T x ) {\displaystyle f(x)=-\sum _{i=1}^{m}\ln(b_{j}-a_{j}^{T}x)} b j − a j T x {\displaystyle b_{j}-a_{j}^{T}x}
交差ルール G 1 ,..., G m を R n の閉凸領域とする 。1 ,..., mの各 i に対し 、 g i を G i のM i -SCB とし 、 r i を 実数とする。G をすべての G i の共通集合とし 、その内部は空でないとする。g := sum i r i *g i とする 。 すると 、 g は G の SCB で あり 、 パラメータ sum i r i *M i を持つ。 [2] : Prop.3.1.1
したがって、 G が 制約のリストによって定義されている場合は、制約ごとに SCB を個別に見つけて、それらを合計するだけで G の SCB を取得できます。
例えば、ドメインが a j T x ≤ b j （ j は1,..., m の範囲）という形式の m個の線形制約によって定義されているとします。この場合、交差規則を用いて m -SCB （これは以前に直積規則を用いて計算したものと同じものです） を構築できます。 f ( x ) = − ∑ i = 1 m ln ( b j − a j T x ) {\displaystyle f(x)=-\sum _{i=1}^{m}\ln(b_{j}-a_{j}^{T}x)}
碑文のSCB 関数 f ( x ) のエピグラフ は 、関数のグラフ上の領域、すなわち である 。f のエピグラフが 凸集合と なるのは、 f が 凸関数 である 場合に限る。以下の定理は 、エピグラフが SCB を持つ 関数 f のいくつかを示す。 { ( x , t ) ∈ R 2 : t ≥ f ( x ) } {\displaystyle \{(x,t)\in \mathbb {R} ^{2}:t\geq f(x)\}}
g ( t )を t >0上の 3回連続微分可能な 凹関数 とし、 すべての t >0に対して 定数（ 3* bと表記）で有界とします。G を 2次元凸領域とします。 すると、関数 f ( x , t ) = -ln(f(t)-x) - max[1,b 2 ]*ln(t) は G に対して自己一致障壁となり 、パラメータは (1+max[1,b 2 ]) となります。 [2] : Prop.9.2.1 t ⋅ | g ‴ ( t ) | / | g ″ ( t ) | {\displaystyle t\cdot |g'''(t)|/|g''(t)|} G = closure ( { ( x , t ) ∈ R 2 : t > 0 , x ≤ g ( t ) } ) . {\displaystyle G={\text{closure}}(\{(x,t)\in \mathbb {R} ^{2}:t>0,x\leq g(t)\}).}
例:
g ( t ) = t 1/ p （任意のp ≥ 1に対して） とし 、 b =(2 p -1)/(3 p ) とします。すると 、 は2-SCB を持ちます。同様に、 は2-SCB を持ちます。交差則を用いると、 は 4-SCB を持ちます。 G 1 = { ( x , t ) ∈ R 2 : ( x + ) p ≤ t } {\displaystyle G_{1}=\{(x,t)\in \mathbb {R} ^{2}:(x_{+})^{p}\leq t\}} G 2 = { ( x , t ) ∈ R 2 : ( [ − x ] + ) p ≤ t } {\displaystyle G_{2}=\{(x,t)\in \mathbb {R} ^{2}:([-x]_{+})^{p}\leq t\}} G = G 1 ∩ G 2 = { ( x , t ) ∈ R 2 : | x | p ≤ t } {\displaystyle G=G_{1}\cap G_{2}=\{(x,t)\in \mathbb {R} ^{2}:|x|^{p}\leq t\}} g ( t )=ln( t )、 b =2/3と すると、 2-SCBが成り立ちます。 G = { ( x , t ) ∈ R 2 : e x ≤ t } {\displaystyle G=\{(x,t)\in \mathbb {R} ^{2}:e^{x}\leq t\}} p ノルムを最小化する問題に対する SCB を構築できるようになりました 。 ここで、 v j は定数スカラー、 u j は定数ベクトル、 p >0 は定数です。まず、これを線形目的関数の最小化に変換します。 ここで、制約条件は [ m ] 内のすべての j に対して次のとおりです。各制約条件について、アフィン置換規則により 4-SCB が得られます。交差規則を用いると、実行可能領域全体に対して
(4 n )-SCB が得られます。 min x ∑ j = 1 n | v j − x T u j | p {\displaystyle \min _{x}\sum _{j=1}^{n}|v_{j}-x^{T}u_{j}|^{p}} min x ∑ j = 1 n t j {\displaystyle \min _{x}\sum _{j=1}^{n}t_{j}} t j ≥ | v j − x T u j | p {\displaystyle t_{j}\geq |v_{j}-x^{T}u_{j}|^{p}}
同様に、 gを x >0の射線上の3回連続微分可能な凸関数とし 、 x >0の任意の値に対して次が成り立つものとする。G を 2 次元凸定義域とする：closure({(t,x)inR2:x>0,t≥g ( x ) } ) 。 この とき 、関数 f ( x , t )=-ln(tf(x))-max[1,b2 ] *ln( x )はGの自己一致障壁であり、パラメータは(1+max[1,b2])である 。 [ 2] ：Prop.9.2.2 x ⋅ | g ‴ ( x ) | / | g ″ ( x ) | ≤ 3 b {\displaystyle x\cdot |g'''(x)|/|g''(x)|\leq 3b}
例:
g ( x ) = x − p （ある p >0 ）とし、b=(2+ p )/3と する。このとき 2-SCBが成り立つ。 G 1 = { ( x , t ) ∈ R 2 : x − p ≤ t , x ≥ 0 } {\displaystyle G_{1}=\{(x,t)\in \mathbb {R} ^{2}:x^{-p}\leq t,x\geq 0\}} g ( x )= x ln( x )、 b =1/3 とすると、 2-SCBが成り立ちます。 G = { ( x , t ) ∈ R 2 : x ln x ≤ t , x ≥ 0 } {\displaystyle G=\{(x,t)\in \mathbb {R} ^{2}:x\ln x\leq t,x\geq 0\}}
コーン用SCB 2 次円錐 の場合 、関数 は自己一致バリアです。 { ( x , y ) ∈ R n − 1 × R ∣ ‖ x ‖ ≤ y } {\displaystyle \{(x,y)\in \mathbb {R} ^{n-1}\times \mathbb {R} \mid \|x\|\leq y\}} f ( x , y ) = − log ( y 2 − x T x ) {\displaystyle f(x,y)=-\log(y^{2}-x^{T}x)} m*m 対称行列の半正定値 円錐の場合 、関数は 自己一致障壁です。 f ( A ) = − log det A {\displaystyle f(A)=-\log \det A} が 半正 定値対称行列 である二次関数 領域 で定義される領域では 、対数障壁は 次式と自己一致する。 ϕ ( x ) > 0 {\displaystyle \phi (x)>0} ϕ ( x ) = α + ⟨ a , x ⟩ − 1 2 ⟨ A x , x ⟩ {\displaystyle \phi (x)=\alpha +\langle a,x\rangle -{\frac {1}{2}}\langle Ax,x\rangle } A = A T ≥ 0 {\displaystyle A=A^{T}\geq 0} f ( x ) = − log ϕ ( x ) {\displaystyle f(x)=-\log \phi (x)} M = 2 {\displaystyle M=2} 指数円錐の場合 、関数は 自己一致障壁です。 { ( x , y , z ) ∈ R 3 ∣ y e x / y ≤ z , y > 0 } {\displaystyle \{(x,y,z)\in \mathbb {R} ^{3}\mid ye^{x/y}\leq z,y>0\}} f ( x , y , z ) = − log ( y log ( z / y ) − x ) − log z − log y {\displaystyle f(x,y,z)=-\log(y\log(z/y)-x)-\log z-\log y} パワーコーン の場合 、関数 は自己一致バリアです。 { ( x 1 , x 2 , y ) ∈ R + 2 × R ∣ | y | ≤ x 1 α x 2 1 − α } {\displaystyle \{(x_{1},x_{2},y)\in \mathbb {R} _{+}^{2}\times \mathbb {R} \mid |y|\leq x_{1}^{\alpha }x_{2}^{1-\alpha }\}} f ( x 1 , x 2 , y ) = − log ( x 1 2 α x 2 2 ( 1 − α ) − y 2 ) − log x 1 − log x 2 {\displaystyle f(x_{1},x_{2},y)=-\log(x_{1}^{2\alpha }x_{2}^{2(1-\alpha )}-y^{2})-\log x_{1}-\log x_{2}}
歴史 1994年の著書 [6 ]の「参考文献コメント」 [5] で述べられているように、自己一致関数は1988年に ユーリ・ネステロフ [7] [8]によって導入され、 アルカディ・ネミロフスキー [9] によってさらに発展させられました 。 [10] で説明されているように 、彼らの基本的な観察は、ニュートン法がアフィン不変であるということでした。つまり、関数に対して ニュートンステップが存在する場合、 関数に対して 非退化線形変換から始めて、 再帰的に示せる ニュートンステップが存在するという ことです。 f ( x ) {\displaystyle f(x)} x k + 1 = x k − [ f ″ ( x k ) ] − 1 f ′ ( x k ) {\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k})} ϕ ( y ) = f ( A y ) {\displaystyle \phi (y)=f(Ay)} A {\displaystyle A} y 0 = A − 1 x 0 {\displaystyle y_{0}=A^{-1}x_{0}} y k = A − 1 x k {\displaystyle y_{k}=A^{-1}x_{k}}
y k + 1 = y k − [ ϕ ″ ( y k ) ] − 1 ϕ ′ ( y k ) = y k − [ A T f ″ ( A y k ) A ] − 1 A T f ′ ( A y k ) = A − 1 x k − A − 1 [ f ″ ( x k ) ] − 1 f ′ ( x k ) = A − 1 x k + 1 {\displaystyle y_{k+1}=y_{k}-[\phi ''(y_{k})]^{-1}\phi '(y_{k})=y_{k}-[A^{T}f''(Ay_{k})A]^{-1}A^{T}f'(Ay_{k})=A^{-1}x_{k}-A^{-1}[f''(x_{k})]^{-1}f'(x_{k})=A^{-1}x_{k+1}} 。 しかし、ニュートン法の標準的な解析では、 のヘッセ行列がリプシッツ連続、つまりある定数 に対して であると仮定する 。 が 3 回 連続微分可能である と仮定すると、これは次式と等価である。 f {\displaystyle f} ‖ f ″ ( x ) − f ″ ( y ) ‖ ≤ M ‖ x − y ‖ {\displaystyle \|f''(x)-f''(y)\|\leq M\|x-y\|} M {\displaystyle M} f {\displaystyle f}
| ⟨ f ‴ ( x ) [ u ] v , v ⟩ | ≤ M ‖ u ‖ ‖ v ‖ 2 {\displaystyle |\langle f'''(x)[u]v,v\rangle |\leq M\|u\|\|v\|^{2}} すべての人のために u , v ∈ R n {\displaystyle u,v\in \mathbb {R} ^{n}} ここで 、上記の不等式の左辺はアフィン変換に対して不変です が、右辺はそうではありません。 f ‴ ( x ) [ u ] = lim α → 0 α − 1 [ f ″ ( x + α u ) − f ″ ( x ) ] {\displaystyle f'''(x)[u]=\lim _{\alpha \to 0}\alpha ^{-1}[f''(x+\alpha u)-f''(x)]} f ( x ) → ϕ ( y ) = f ( A y ) , u → A − 1 u , v → A − 1 v {\displaystyle f(x)\to \phi (y)=f(Ay),u\to A^{-1}u,v\to A^{-1}v}
著者らは、ユークリッド計量を のヘッセ行列によって 定義 されるスカラー積で置き換えることで、右辺も不変にできることを指摘している 。そして、自己一致関数の定義を以下のように導く。 f {\displaystyle f} ‖ w ‖ f ″ ( x ) = ⟨ f ″ ( x ) w , w ⟩ 1 / 2 {\displaystyle \|w\|_{f''(x)}=\langle f''(x)w,w\rangle ^{1/2}} w ∈ R n {\displaystyle w\in \mathbb {R} ^{n}}
| ⟨ f ‴ ( x ) [ u ] u , u ⟩ | ≤ M ⟨ f ″ ( x ) u , u ⟩ 3 / 2 {\displaystyle |\langle f'''(x)[u]u,u\rangle |\leq M\langle f''(x)u,u\rangle ^{3/2}} 。
プロパティ
線形結合 および が定数 および および と 自己一致している 場合、 は 定数 と自己一致します 。 f 1 {\displaystyle f_{1}} f 2 {\displaystyle f_{2}} M 1 {\displaystyle M_{1}} M 2 {\displaystyle M_{2}} α , β > 0 {\displaystyle \alpha ,\beta >0} α f 1 + β f 2 {\displaystyle \alpha f_{1}+\beta f_{2}} max ( α − 1 / 2 M 1 , β − 1 / 2 M 2 ) {\displaystyle \max(\alpha ^{-1/2}M_{1},\beta ^{-1/2}M_{2})}
が定数 と自己一致し 、 が のアフィン変換である 場合 、 は パラメータ とも自己一致します 。 f {\displaystyle f} M {\displaystyle M} A x + b {\displaystyle Ax+b} R n {\displaystyle \mathbb {R} ^{n}} ϕ ( x ) = f ( A x + b ) {\displaystyle \phi (x)=f(Ax+b)} M {\displaystyle M}
凸共役 が自己一致 ならば、その 凸共役 も自己一致である。 [6] [11] f {\displaystyle f} f ∗ {\displaystyle f^{*}}
非特異ヘッセ行列 が自己一致し、 の定義域に直線が含まれない 場合 （両方向に無限）、 は 特異ではありません。 f {\displaystyle f} f {\displaystyle f} f ″ {\displaystyle f''}
逆に、 の領域にあるいくつか に対して が 成り立つ場合 、 が の領域にあるすべての に対して が成り立ち 、 は 線形 で あり、最大値を持つことはできないので、 はすべて の 領域にあります。また、 は その領域内に最小値を持つことはできない ことにも注意してください。 x {\displaystyle x} f {\displaystyle f} u ∈ R n , u ≠ 0 {\displaystyle u\in \mathbb {R} ^{n},u\neq 0} ⟨ f ″ ( x ) u , u ⟩ = 0 {\displaystyle \langle f''(x)u,u\rangle =0} ⟨ f ″ ( x + α u ) u , u ⟩ = 0 {\displaystyle \langle f''(x+\alpha u)u,u\rangle =0} α {\displaystyle \alpha } x + α u {\displaystyle x+\alpha u} f {\displaystyle f} f ( x + α u ) {\displaystyle f(x+\alpha u)} x + α u , α ∈ R {\displaystyle x+\alpha u,\alpha \in \mathbb {R} } f {\displaystyle f} f {\displaystyle f}
アプリケーション 自己一致関数は、ニュートン法 の解析において特に有用である 。自己一致 バリア関数は、凸最適化および非線形最適化のため の内点法 で使用される バリア関数の 開発に用いられる 。バリア関数の2次導関数はリプシッツ連続でないため、ニュートン法の通常の解析は適用できない。そうでない場合、バリア関数は の任意のコンパクト部分集合上で有界となるためである 。 R n {\displaystyle \mathbb {R} ^{n}}
自己一致バリア関数
制約付き最適化手法において障壁として使用できる関数のクラスである。 通常の場合と同様に、ニュートンアルゴリズムを使用して最小化できる（ただし、これらの結果を導くのはやや難しい） 上記の両方を満たすには、関数の3次導関数の通常の定数境界（ニュートン法の通常の収束結果を得るために必要）をヘッセ行列に対する境界に置き換える。
自己一致関数の最小化 自己一致関数は、収束に必要なステップ数に上限がある修正ニュートン法を用いて最小化できます。ここでは、 が 標準 的な 自己一致関数、つまりパラメータ と自己一致であると仮定します 。 f {\displaystyle f} M = 2 {\displaystyle M=2}
における ニュートン減衰を 、 における ヘッセ行列によって定義される局所ノルムにおける ニュートンステップの大きさとして 定義する。 λ f ( x ) {\displaystyle \lambda _{f}(x)} f {\displaystyle f} x {\displaystyle x} [ f ″ ( x ) ] − 1 f ′ ( x ) {\displaystyle [f''(x)]^{-1}f'(x)} f {\displaystyle f} x {\displaystyle x}
λ f ( x ) = ⟨ f ″ ( x ) [ f ″ ( x ) ] − 1 f ′ ( x ) , [ f ″ ( x ) ] − 1 f ′ ( x ) ⟩ 1 / 2 = ⟨ [ f ″ ( x ) ] − 1 f ′ ( x ) , f ′ ( x ) ⟩ 1 / 2 {\displaystyle \lambda _{f}(x)=\langle f''(x)[f''(x)]^{-1}f'(x),[f''(x)]^{-1}f'(x)\rangle ^{1/2}=\langle [f''(x)]^{-1}f'(x),f'(x)\rangle ^{1/2}} の領域において 、 の場合、 ニュートン反復法が証明可能である。 x {\displaystyle x} f {\displaystyle f} λ f ( x ) < 1 {\displaystyle \lambda _{f}(x)<1}
x + = x − [ f ″ ( x ) ] − 1 f ′ ( x ) {\displaystyle x_{+}=x-[f''(x)]^{-1}f'(x)} も の領域に含まれます 。これは、 の自己一致に基づいて 、 の値に有限の境界を与えることができるためです 。さらに、 f {\displaystyle f} f {\displaystyle f} f ( x + ) {\displaystyle f(x_{+})}
λ f ( x + ) ≤ ( λ f ( x ) 1 − λ f ( x ) ) 2 {\displaystyle \lambda _{f}(x_{+})\leq {\Bigg (}{\frac {\lambda _{f}(x)}{1-\lambda _{f}(x)}}{\Bigg )}^{2}} そしてもし私たちが
λ f ( x ) < λ ¯ = 3 − 5 2 {\displaystyle \lambda _{f}(x)<{\bar {\lambda }}={\frac {3-{\sqrt {5}}}{2}}} となることが保証されるので 、収束するまでニュートン法を使い続けることができます。 ある に対してが 0 に 2次収束することに注意しましょう。これは 、 が に 、 が に 2次収束することを与えます。 ここで 、 は次の定理により、 となります。そして 、 λ f ( x + ) < λ f ( x ) {\displaystyle \lambda _{f}(x_{+})<\lambda _{f}(x)} λ f ( x + ) < β {\displaystyle \lambda _{f}(x_{+})<\beta } β ∈ ( 0 , λ ¯ ) {\displaystyle \beta \in (0,{\bar {\lambda }})} λ f {\displaystyle \lambda _{f}} λ f ( x + ) ≤ ( 1 − β ) − 2 λ f ( x ) 2 {\displaystyle \lambda _{f}(x_{+})\leq (1-\beta )^{-2}\lambda _{f}(x)^{2}} f ( x k ) {\displaystyle f(x_{k})} f ( x ∗ ) {\displaystyle f(x^{*})} x {\displaystyle x} x ∗ {\displaystyle x^{*}} x ∗ = arg min f ( x ) {\displaystyle x^{*}=\arg \min f(x)} λ f ( x ) < 1 {\displaystyle \lambda _{f}(x)<1}
ω ( λ f ( x ) ) ≤ f ( x ) − f ( x ∗ ) ≤ ω ∗ ( λ f ( x ) ) {\displaystyle \omega (\lambda _{f}(x))\leq f(x)-f(x^{*})\leq \omega _{*}(\lambda _{f}(x))} ω ′ ( λ f ( x ) ) ≤ ‖ x − x ∗ ‖ x ≤ ω ∗ ′ ( λ f ( x ) ) {\displaystyle \omega '(\lambda _{f}(x))\leq \|x-x^{*}\|_{x}\leq \omega _{*}'(\lambda _{f}(x))} 以下の定義に従う
ω ( t ) = t − log ( 1 + t ) {\displaystyle \omega (t)=t-\log(1+t)} ω ∗ ( t ) = − t − log ( 1 − t ) {\displaystyle \omega _{*}(t)=-t-\log(1-t)} ‖ u ‖ x = ⟨ f ″ ( x ) u , u ⟩ 1 / 2 {\displaystyle \|u\|_{x}=\langle f''(x)u,u\rangle ^{1/2}} ニュートン法をある値 から始める場合、次のよう に定義される 減衰ニュートン法 から始める必要がある。 x 0 {\displaystyle x_{0}} λ f ( x 0 ) ≥ λ ¯ {\displaystyle \lambda _{f}(x_{0})\geq {\bar {\lambda }}}
x k + 1 = x k − 1 1 + λ f ( x k ) [ f ″ ( x k ) ] − 1 f ′ ( x k ) {\displaystyle x_{k+1}=x_{k}-{\frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})} これについては、前述の定義の通り、 が となることが示せます。 は の 増加 関数 であり、 任意の に対して となる ので 、 の値は 各反復で一定量減少することが保証されます。これは が の領域内にあることも証明しています 。 f ( x k + 1 ) ≤ f ( x k ) − ω ( λ f ( x k ) ) {\displaystyle f(x_{k+1})\leq f(x_{k})-\omega (\lambda _{f}(x_{k}))} ω {\displaystyle \omega } ω ( t ) {\displaystyle \omega (t)} t > 0 {\displaystyle t>0} ω ( t ) ≥ ω ( λ ¯ ) {\displaystyle \omega (t)\geq \omega ({\bar {\lambda }})} t ≥ λ ¯ {\displaystyle t\geq {\bar {\lambda }}} f {\displaystyle f} x k + 1 {\displaystyle x_{k+1}} f {\displaystyle f}
参考文献 ^ NemirovskyとBen-Tal (2023). 「最適化III：凸最適化」 （PDF） . ^ abcdefghij Arkadi Nemirovsky (2004). 「凸計画法における内点多項式時間法」 ^ Boyd, Stephen P.; Vandenberghe, Lieven (2004). 凸最適化 (PDF) . Cambridge University Press. ISBN 978-0-521-83378-3 . 2011年 10月15日 閲覧 。 ^ NemirovskyとBen-Tal (2023). 「最適化III：凸最適化」 （PDF） . ^ネステロフ、ユーリ、ネミロフスキー、アルカディ（1994年1 月 ）。凸計画法における内点多項式アルゴリズム（参考文献コメント）。応用数学協会。doi : 10.1137 /1.9781611970791.bm。ISBN 978-0-89871-319-0 。 ^ ab Nesterov, Yurii; Nemirovskii, Arkadii (1994). 凸計画法における内点多項式アルゴリズム . 応用数学と数値数学の研究. 第13巻. doi :10.1137/1.9781611970791. ISBN 978-0-89871-319-0 . OCLC 29310677。 [ ページが必要 ] ^ ゆ。 E. NESTEROV、線形および二次計画法における多項式時間法、Izvestija AN SSSR、Tekhnitcheskaya kibernetika、No. 3、1988、324-326 ページ。 (ロシア語で。) ^ Yu. E. NESTEROV, 線形計画法と二次計画法における多項式時間反復法, Voprosy kibernetiki, モスクワ, 1988, pp. 102-125. (ロシア語) ^ YE Nesterov と AS Nemirovski、「凸計画法における自己一致関数と多項式時間法」、技術レポート、ソ連科学アカデミー中央経済数学研究所、モスクワ、ソ連、1989 年。 ^ Nesterov, I︠U︡. E. (2013年12月). 凸最適化入門講義：基礎コース . ボストン. ISBN 978-1-4419-8853-9 . OCLC 883391994。 {{cite book }}: CS1 maint: location missing publisher (link )^ Sun, Tianxiao; Tran-Dinh, Quoc (2018). 「一般化自己一致関数：ニュートン型法のレシピ」. 数理計画 ：命題6. arXiv : 1703.04599 . 
![{\displaystyle G_{2}=\{(x,t)\in \mathbb {R}^{2}:([-x]_{+})^{p}\leq t\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e99958b9b0f09e9639e83e5389792850771ab8d6)
![{\displaystyle x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b245be5eaf43c895ecbf35ac63b40f8bec01c5dd)
![{\displaystyle y_{k+1}=y_{k}-[\phi ''(y_{k})]^{-1}\phi '(y_{k})=y_{k}-[A^{T}f''(Ay_{k})A]^{-1}A^{T}f'(Ay_{k})=A^{-1}x_{k}-A^{-1}[f''(x_{k})]^{-1}f'(x_{k})=A^{-1}x_{k+1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2df3f5c8b059191e6dcf59392a108ceea7d34e9c)
![{\displaystyle |\langle f'''(x)[u]v,v\rangle |\leq M\|u\|\|v\|^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74a78be152f1db6516a4fc96859cec5b955325b9)
![{\displaystyle f'''(x)[u]=\lim _{\alpha \to 0}\alpha ^{-1}[f''(x+\alpha u)-f''(x)]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1be966179e3181d99a56918315085324cdfb0808)
![{\displaystyle |\langle f'''(x)[u]u,u\rangle |\leq M\langle f''(x)u,u\rangle ^{3/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2cd02fb992e681dfb6d072b3ed75665265a8e48a)
![{\displaystyle [f''(x)]^{-1}f'(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2cba2421b936cb79d5ab8c68d8aca828ae028a3)
![{\displaystyle \lambda _{f}(x)=\langle f''(x)[f''(x)]^{-1}f'(x),[f''(x)]^{-1}f'(x)\rangle ^{1/2}=\langle [f''(x)]^{-1}f'(x),f'(x)\rangle ^{1/2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ebdbe02bad547b15d7693147b0318bc981a97e8d)
![{\displaystyle x_{+}=x-[f''(x)]^{-1}f'(x)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/322071437533f8751f1457a642861d1afd834280)
![{\displaystyle x_{k+1}=x_{k}-{\frac {1}{1+\lambda _{f}(x_{k})}}[f''(x_{k})]^{-1}f'(x_{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ca8d4a1ca3d9fac68d5fb62ba65cff0b40a11a54)
