가우스-뉴턴 알고리즘

가우스-뉴턴 알고리즘은 함수 값 제곱의 합을 최소화하는 것과 동일한 비선형 최소 제곱 문제를 해결하는 데 사용됩니다. 그것은 비선형 함수의 최소값을 찾기 위한 뉴턴의 방법의 확장입니다. 제곱의 합은 음수가 아니어야 하므로 알고리즘은 뉴턴의 방법을 사용하여 합의 성분의 0을 반복적으로 근사하고 따라서 합을 최소화하는 것으로 볼 수 있습니다. 이러한 의미에서 알고리즘은 과도하게 결정된 방정식 시스템을 해결하는 데 효과적인 방법이기도 합니다. 계산이 어려울 수 있는 2차 도함수가 필요 없다는 장점이 있습니다.^[1]

비선형 최소 제곱 문제는 예를 들어 비선형 회귀 분석에서 발생하며, 여기서 모델의 매개 변수는 모델이 사용 가능한 관측치와 잘 일치하도록 모색됩니다.

이 방법은 수학자 칼 프리드리히 가우스와 아이작 뉴턴의 이름을 따서 명명되었으며, 가우스의 1809년 작품인 Sectionibus conicis solem ambientum에서 처음 등장했습니다.^[2]

묘사

Given ${\displaystyle m}$ functions ${\displaystyle {\textbf {r}}=(r_{1},\ldots ,r_{m})}$ (often called residuals) of ${\displaystyle n}$ variables ${\displaystyle {\boldsymbol {\beta }}=(\beta _{1},\ldots \beta _{n}),}$ with ${\displaystyle m\ge n,}$${\displaystyle m\geqn,}$ 가우스-뉴턴 알고리즘은$$ 제곱의^[3] 합을 최소화하는 변수의 값을 반복적으로 찾습니다.

$${\displaystyle S({\boldsymbol {\beta })=\sum _{i=1}^{m}r_{i}({\boldsymbol {\beta })^{2}}$$

최소 초기 추측 $\beta {\displaystyle {\mathit{}}^{}}$($)$ {\$displaystyle${\$boldsymbol${\$beta }}^{(0)}}$부터 시작하여 반복으로 방법을 진행합니다.

$${\displaystyle {\boldsymbol {\beta }^{(s+1)}={\boldsymbol {\beta }^{(s)}-\left(\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {J_{r}\right)^{-1}\mathbf {J_{r} ^{\mathsf {T}\r} \left ({\boldsymbol {\beta }^{(s)}\right,}$$

여기서, r과 β가 열 벡터일 경우, 야코비안 행렬의 원소는

$${\displaystyle \left(\mathbf {J_{r}} \right)_{ij}={\frac {\partial r_{i}\left({\boldsymbol {\beta }^{(s)}\right)}{\partial \beta _{j}}}$$

그리고 기호 ${\displaystyle {}^{\mathsf{}}}$ ${\$는 행렬 전치를 나타냅니다$$.

각 반복에서 업데이트 δ = β (s ${\displaystyle {+}^{}}$ ) - β (s ) {\displaystyle \Delta ={\boldsymbol {\beta }^{(s+1)}-{\boldsymbol {\beta }^{(s))}는 다음 두 단계에서 이전 방정식을 재정렬하여 찾을 수 있습니다.

• ${\displaystyle \Delta =-\left(\mathbf {J_{r}} ^{\mathsf {T}\mathbf {J_{r}\r}\right)^{-1}\mathbf {J_{r} ^{\mathsf {T}\r}\left beta \bold 기호 {\({}^{(s)}\right)}$
• ${\displaystyle \mathbf {J_{r}} ^{\mathsf {T}\mathbf {J_{r}} \델타 =-\mathbf {J_{r} ^{\mathsf {T}\mathbf {r} \left ({\bold 기호 {\beta }^{(s)}\right)}$

$치환$ A = ${{Jr}_{}}^{}$ $Jr {\$textstyle A =\$mathbf {J_${r}} $^{\mathsf {T}\mathbf${J_${r$}}, b = - Jr Tr(β(s)) {\displaystyle \mathbf {b} =-\mathbf {J_{r} ^{\mathsf {T}\mathbf {r} \left ({\boldsymbol {\beta }^{(s)}\right)}, 그리고 $x$ =${\displaystyle }$δ {\displaystyle$\mathbf$ {x} =$\backslash$$Delta$ }, 이는 A x = b {\displaystyle A\mathbf {x} =\mathbf {b} 형태의 기존 행렬 방정식으로 바뀌며, 이후 다양한 방법으로 해결할 수 있습니다(참고 참조).

m = n이면 반복은 다음과 같이 단순화됩니다.

$${\displaystyle {\boldsymbol {\beta }^{(s+1)}={\boldsymbol {\beta }^{(s)}-\left(\mathbf {J_{r}\right)^{-1}\mathbf {r} \left ({\boldsymbol {\beta }^{(s)}\right),}$$

그것은 뉴턴의 방법을 1차원에서 직접적으로 일반화한 것입니다.

$주어진{\displaystyle \mathit{}}$ 모델 함수 $f{\displaystyle \mathbf{}}$(${\displaystyle x\mathbf{},}$ ${\displaystyle \beta \mathit{})}$ ${\displaystyle \mathbf {f}(\mathbf {x}, {\boldsymbol {\beta}}}$가 일부 데이터 점$({\displaystyle x_{}}$ i${\displaystyle {}_{}}$ ${\displaystyle y_{}}$) ${\displaystyle (x_{i}, y_{i})}$에 가장 잘 맞도록 매개 변수 β$$ ${\$를 찾는 것이 목표인 데이터 피팅에서$,$ ${\displaystyle {함수}_{}}$ r ${\$은 잔차입니다.

$${\displaystyle r_{i}({\boldsymbol {\beta })=y_{i}-f\left(x_{i}, {\boldsymbol {\beta }\right)}.$$

그러면 가우스-뉴턴 방법은 함수 f {\displaystyle \mathbf {${\displaystyle f_{}}$$}$의 Jacobian J f =${\displaystyle }$- ${\displaystyle {Jr}_{}}$ ${\displaystyle$\$mathbf$ {J_{f}} =-\mathbf {J_{r}}를 $다음$과 같이 표현할 수 있습니다.

$${\displaystyle {\boldsymbol {\beta }^{(s+1)}={\boldsymbol {\beta }^{(s)}+\left(\mathbf {J_{f}}^{\mathsf {T}}\mathbf {J_{f}\right)^{-1}\mathbf {J_{f}^{\mathsf {T}\r}\left ({\boldsymbol {\beta }^{(s)}\right)}}$$

$({\displaystyle {J{{\mathbf{}}_{}}^{}}^{}}$ ${\displaystyle {{{f\mathbf{}}_{}}^{}}^{}}$ ${\displaystyle {{{}_{}}^{\mathsf{}}}^{}}$ ${\displaystyle {J^{}{\mathbf{}}_{}}^{}}$ ${\displaystyle {{f\mathbf{}}_{}}^{}}$)${\displaystyle {}^{}}$- 1 ${\displaystyle {\mathrm{J}}^{}}$ ${\displaystyle {}^{}{{\mathbf{}}_{}}^{}}$ ${\displaystyle {{}_{}}^{\mathsf{}}}$ ${\$는 J ${\displaystyle {f\mathbf{}}_{}}$ ${\$의 왼쪽 의사 역입니다$.$

메모들

알고리즘 문에서 가정 m ≥ n은 필요합니다. 그렇지 않으면 ${\displaystyle {}^{}}$ ${\displaystyle {Jr}_{}}$T $Jr {\displaystyle \mathbf {J_{$r}} ^{$T}\mathbf${J_{r}}는 가역적이지 않고 정규 방정식을 풀 수 없습니다(적어도 유일하게).

가우스-뉴턴 알고리즘은 함수 r의_i 벡터를 선형적으로 근사함으로써 유도될 수 있습니다. 테일러의 정리를 사용하면 모든 반복에서 다음과 같이 쓸 수 있습니다.

$${\displaystyle \mathbf {r}({\boldsymbol {\beta}})\ 근사 \mathbf {r} \left({\boldsymbol {\beta}}^{(s)}\right)+\mathbf {J_{r} \left({\boldsymbol {\beta}}^{(s)}\right)\Delta }$$

δ =${\displaystyle {}^{}}$β -$$β (s) {\displaystyle \Delta ={\boldsymbol {\beta }-{\boldsymbol}}-{\beta }^{(s))}}. 우변의 제곱의 합을 최소화하는 δ {\displaystyle \Delta }를 찾는 작업; 즉,

$${\displaystyle \min \left\ \mathbf {r} \left({\boldsymbol {\beta}}^{(s)}\right)+\mathbf {J_{r} \left({\boldsymbol {\beta}}^{(s)}\right)\Delta \right\ _{2}^{2},}$$

는 선형 최소 squares 문제로, 알고리즘에서 정규 방정식을 산출하며 명시적으로 풀 수 있습니다.

정규 방정식은 알 수 없는 증분$$δ${\$displaystyle$$\Delta$\}$의 n개의 동시 선형 방정식입니다. $이들$은$$ 분해를 사용하거나 Jr {\$displaystyle \mathbf {J_{r}}$의 QR 인수분해를 사용하여 한 단계로 해결할 수 있습니다$.$ 대규모 시스템의 경우 공액 구배법과 같은 반복적인 방법이 더 효율적일 수 있습니다. J의_r 열 사이에 선형 의존성이 있으면 $Jr{\displaystyle {{\mathbf{}}_{}}^{}}$ T ${\displaystyle {Jr\mathbf{}}_{}}$ ${\$가 단수가 되므로$$ 반복이 실패합니다.

When ${\displaystyle \mathbf {r} }$ is complex ${\displaystyle \mathbf {r} :\mathbb {C} ^{n}\to \mathbb {C} }$ the conjugate form should be used: ${\displaystyle \left({\overline {\mathbf {J_{r}} }}^{\mathsf {T}}\mathbf {J_{r}}$$\right)^{-1}{\overline {\mathbf {J_{r}}}}^{\mathsf {T$

예

이 예제에서는 가우스-뉴턴 알고리즘을 사용하여 데이터와 모형 예측 사이의 오차 제곱의 합을 최소화하여 모형을 일부 데이터에 적합시킵니다.

효소 매개 반응에서 기질 농도[S]와 반응 속도의 관계를 연구하는 생물학 실험에서 다음 표의 데이터를 얻었습니다.

형식의 곡선(모델 함수)을 찾는 것이 좋습니다.

$${\displaystyle {\text{rate}}={\frac {V_{\text{max}}\cdot [S]}{K_{M}+[S]}}$$

$매개변수{\displaystyle {}_{}}$ ${\displaystyle {\text{V}}_{}}$max {\$displaystyle V_{\text${max$}}$ 및$$ ${\displaystyle {KM}_{}}${\$displaystyle$K_${M$}}가 결정된$$ 상태에서 최소 제곱 의미의 데이터에 가장 적합합니다.

Denote by ${\displaystyle x_{i}}$ and ${\displaystyle y_{i}}$ the values of [S] and rate respectively, with ${\displaystyle i=1,\dots ,7}$. Let ${\displaystyle \beta _{1}=V_{\text{max}}}$ and ${\displaystyle \beta _{2}=K_{M}}$. 잔차의 제곱의 합이 되도록$$ $\beta {\displaystyle {}_{}}$ ${\displaystyle {1\mathrm{}}_{}}$ ${\$과 $\beta {\displaystyle {}_{}}$ ${\displaystyle {2\mathrm{}}_{}}$ ${\$를 구합니다.

$${\displaystyle r_{i}=y_{i}-{\frac {\beta _{1}x_{i}}{\beta _{2}+x_{i}}},\quad (i=1,\dots ,7)}$$

최소화됩니다.

The Jacobian ${\displaystyle \mathbf {J_{r}} }$ of the vector of residuals ${\displaystyle r_{i}}$ with respect to the unknowns ${\displaystyle \beta _{j}}$ is a ${\displaystyle 7\times 2}$ matrix with the ${\displaystyle i}$-th row having the entries

$${\displaystyle {\frac {\partial r_{i}}{\partial \beta _{1}}=-{\frac {x_{i}}{\beta _{2}+x_{i}}};\quad {\frac {\partial r_{i}}{\partial \beta _{2}}}={\frac {\beta _{1}\cdot x_{i}}{\left(\beta _{2}+x_{i}\right)^{2}}}$$

Starting with the initial estimates of ${\displaystyle \beta _{1}=0.9}$ and ${\displaystyle \beta _{2}=0.2}$, after five iterations of the Gauss–Newton algorithm, the optimal values ${\displaystyle {\hat {\beta }}_{1}=0.362}$ and ${\displaystyle {\hat{\beta }}_2=0.}$${\displaystyle 556}$ ${\displaystyle {\hat {\${2}${\displaystyle \mathrm{=}}$0.556}을(를) 얻습니다. 잔차의 제곱합은 초기값 1.445에서 다섯 번째 반복 후 0.00784로 감소했습니다. 오른쪽 그림의 그림은 관측된 데이터를 사용하여 최적 모수에 대해 모형에 의해 결정된 곡선을 보여줍니다.

수렴속성

가우스-뉴턴 반복은 다음 ^[4]4가지 조건에서$$ 로컬 최소점 $\beta {\displaystyle \hat{}}$ ${\$로 수렴됩니다. 함수 ${\displaystyle r_{}}$ 1${\displaystyle {}_{}\dots ,}$ ${\displaystyle r_{}}$ m ${\displaystyle r_{1},\ldots, r_{m}}$는 열린 볼록 집합 ${\displaystyle D}$ ∋ β^ ${\displaystyle$ D\n에서 연속적으로 두 번 미분 가능합니다.$i {\hat {\beta$ $\}\},$ Jacobian ${\displaystyle {\mathbf{}}_{}}$(${\displaystyle \beta \stackrel{}{}^)}$ ${\displaystyle \mathbf {J} _{\mathbf {r} ({\hat {\beta$})}는$$ 전체 열 순위입니다. 초기 반복 $\beta {\displaystyle {}^{}}$(${\displaystyle {0)}^{}}$ ${\$^{($0)}}$는 β ${\displaystyle \stackrel{}{^}}${\$displaystyle {\hat {\beta }}$ 근처이고$,$ 로컬 최소값 ${\displaystyle S}$(${\displaystyle \beta \stackrel{}{}\stackrel{}{^)}}$ $displaystyle S({\hat {\beta }}) }$는 작습니다$$. 수렴은 ${\displaystyle S(\beta \stackrel{}{}^)}$ = ${\displaystyle 0}$ ${\$displaystyle S({\hat {\beta }}) = 0}인 경우 2차입니다.

증가분 δ는 S에 대한 하강 방향이며, 알고리즘이 수렴하면 한계는 S의 정지점임을 알 수 있습니다. 그러나 큰 최소값 ${\displaystyle S(\beta \stackrel{}{}^)}$ $displaystyle$ S$({\hat {\beta$}})$$}의 경우 수렴이 보장되지 않으며, 뉴턴의 방법과 같은 로컬 수렴이나 일반적인 울프 조건에서의 수렴도 보장되지 않습니다.^[6]

가우스-뉴턴 알고리즘의 수렴 속도는 이차적으로 접근할 수 있습니다.^[7] 초기 추측이 최소값과 거리가 멀거나 행렬$$ {\$displaystyle$ \$mathbf {J_${r$}^{\mathsf$ {$T}J_{r}}$가 잘못된 조건일 경우 알고리즘은 천천히 수렴하거나 전혀 수렴하지 않을 수 있습니다. 예를 들어, 다음과 같이 주어진 $m$= 2 {\displaystyle m=2} ${\displaystyle \mathrm{방정식}}$과 n = 1 {\displaystyle n=1} 변수에 대한 문제를 생각해 보십시오.

$${\displaystyle {\begin{aligned}r_{1}(\beta)&=\beta +1,\r_{2}(\beta)&=\lambda \beta ^{2}+\beta -1.\end{align}}}$$

The optimum is at ${\displaystyle \beta =0}$. (Actually the optimum is at ${\displaystyle \beta =-1}$ for ${\displaystyle \lambda =2}$, because ${\displaystyle S(0)=1^{2}+(-1)^{2}=2}$, but ${\displaystyle S(-1)=0}$.) λ =$0 {\$displaystyle \ lambda =0}인 경우 문제는 실제로 선형적이며 이 방법은 한 번의 반복에서 최적을 찾습니다. λ < 1인 경우, 방법은 선형적으로 수렴되고 오차는 반복될 때마다 요인 λ에 따라 점근적으로 감소합니다. 그러나 λ > 1이면 메서드가 로컬로 수렴되지도 않습니다.

과도하게 결정된 방정식 체계 풀기

가우스-뉴턴 반복

$${\displaystyle \mathbf {x} ^{(k+1)}=\mathbf {x} ^{(k)}-J(\mathbf {x} ^{(k)})^{\mathbf {f}(\mathbf {x} ^{(k)})\,\quad k=0,1,\ldots }$$

$${\displaystyle \mathbf {f} (\mathbf {x} )={\begin{bmatrix}f_{1}(x_{1},\ldots ,x_{n})\\\vdots \\f_{m}(x_{1},\ldots ,x_{n})\end{bmatrix}}}$$

and ${\displaystyle m>n}$ where ${\displaystyle J(\mathbf {x} )^{\dagger }}$ is the Moore-Penrose inverse (also known as pseudoinverse) of the Jacobian matrix${\displaystyle J(\mathbf {x} )}$ of ${\displaystyle \mathbf {f} (\mathbf {x} )}$. 뉴턴 방법의 확장으로 간주될 수 있으며 고립된 정규 해를 향한 동일한 로컬 2차 수렴을 즐깁니다.

If the solution doesn't exist but the initial iterate ${\displaystyle \mathbf {x} ^{(0)}}$ is near a point ${\displaystyle {\hat {\mathbf {x} }}=({\hat {x}}_{1},\ldots ,{\hat {x}}_{n})}$ at which the sum of squares $\sum _{i=1}^m{f}_i(x_1,\dots ,$$x_{}$ $n_{}$) ${\mathrm{2\; \equiv }}_{}$ ‖ $f$( ${}_{}^{}$ ${)}_{}$ ‖ $22 {\textstyle$ \$sum$ _$i=1$}^{m} f_{$i}(x_{1},\ldots,x_${n$})$^{$2}\equiv \mathbf {f}(\mathbf {x$})\_{2}^{2}} 작은 로컬 최소값에 도달하면 가우스-뉴턴 반복은 x ^ ${\displaystyle {\hat$ $\{\backslash$mathbf {x}}}로 선형$수렴$됩니다. 점 $x{\displaystyle \stackrel{}{\mathbf{}}}$ ${\$은 종종 과잉 결정된 시스템의 최소 제곱 해라고 불립니다$$.

뉴턴 방법에 의한 유도

다음은 근사를 통해 함수 최적화를 위한 뉴턴의 방법에서 가우스-뉴턴 알고리즘을 유도할 것입니다. 결과적으로, 가우스-뉴턴 알고리즘의 수렴 속도는 특정 규칙성 조건에서 이차적일 수 있습니다. 일반적으로 (약한 조건에서) 수렴 속도는 선형입니다.^[9]

파라미터 $\beta {\displaystyle \mathit{}}$ ${\$의 함수 S를 최소화하기 위한 뉴턴의 방법에 대한 반복 관계는 다음과$$ 같습니다.

$${\displaystyle {\boldsymbol {\beta }^{(s+1)}={\boldsymbol {\beta }^{(s)}-\mathbf {H}^{-1}\mathbf {g},}$$

여기서 g는 S의 기울기 벡터를 나타내고, H는 S의 헤센 행렬을 나타냅니다.

$\underset{}{\overset{}{S}}$ = ∑ $i_{}^{}\underset{}{\overset{}{}}$= 1$m$r 2 {\textstyle S =\sum _{i=1}^{m}r_{i}^{2}} 이므로 구배는 다음과 같이 주어집니다.

$${\displaystyle g_{j}=2\sum _{i=1}^{m}r_{i}{\frac {\partial r_{i}}{\partial \beta _{j}}}$$

헤센의 요소는 ${\displaystyle {\beta }_{}}$ k ${\$ _${k}}$에$$대해 기울기 요소 ${\displaystyle {gj}_{}}${\$displaystyle g_{j}}$를 미분하여 계산됩니다$.$

$${\displaystyle H_{jk}=2\sum _{i=1}^{m}\left ({\frac {\partial r_{i}}{\partial \beta _{j}}{\frac {\partial r_{i}}{\partial \beta _{k}}+r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}\right)}}$$

가우스-뉴턴 방법은 2차 도함수 항(이 식에서 두 번째 항)을 무시함으로써 얻어집니다. 즉, 헤시안은 다음과 같이 근사됩니다.

$${\displaystyle H_{jk}\approx 2\sum _{i=1}^{m}J_{ij}J_{ik}}$$

$여기$서 ${Jij}_{}$ = ∂$ri$ / ∂ βj {\textstyle J_{$ij$}={\partial r_{i}}/{\beta \partial _{j}}는 야코비안 J의 항목입니다. 정확한 헤센을 정확한 적합도에 가깝게 평가할 때 우리는 거의 0에 가까운 ri {\display r_{i}를 가지므로 두 번째 항도 거의 0에 가까워지므로 근사를 정당화합니다. 기울기와 근사 헤시안은 행렬 표기법으로 다음과 같이 쓸 수 있습니다.

$${\displaystyle \mathbf {g} =2{\mathbf {J} _{\mathbf {r}} ^{\mathsf {T}}\mathbf {r},\quad \mathbf {H} \approx 2{\mathbf {J} _{\mathbf {r}} ^{\mathsf {T}\mathbf {J_{r}}.$$

이 식을 위의 순환 관계에 대입하여 연산 방정식을 구합니다.

$${\displaystyle {\boldsymbol {\beta }^{(s+1)}={\boldsymbol {\beta }^{(s)}+\Delta;\quad \Delta =-\left(\mathbf {J_{r}} ^{\mathsf {T}}\mathbf {J_{r}\r}\right)^{-1}\mathbf {J_{r} ^{\mathsf {T}\r}.$$

가우스-뉴턴 방법의 수렴은 모든 경우에 보장되지 않습니다. 어림셈

$${\displaystyle \left r_{i}{\frac {\partial ^{2}r_{i}}{\partial \beta _{j}\partial \beta _{k}}\ll \left {\partial r_{i}}{\partial \beta _{j}}}\ll \left {\frac {\partial r_{i}}{\partial r_{i}}{\beta \beta _{k}}\right}$$

2차 도함수 항들을 무시할 수 있도록 유지되어야 하는 것은 수렴이 예상되는 두 가지 경우에서 유효할 수 있습니다.^[10]

1. 함수 값 ${\displaystyle r_{}}$ ${\$의 크기는 최소값 정도로 작습니다.
2. $\frac{{함수}_{}}{}$는 "순한" $\frac{{비선형}_{}}{}$이므로 ∂ $\frac{2_{}}{}$ r$\frac{{}_{}}{}$∂$$β j ∂$β$ k ${\textstyle {\$frac {\$partial$^{$2}r_{i}}{\partial \beta$ _${$j}\partial \beta _{k}}}는 크기가 상대적으로 작습니다.

개선된 버전

가우스-뉴턴 방법에서는 잔차 S의 제곱합이 반복될 때마다 감소하지 않을 수 있습니다. 그러나 δ는 하강 방향이므로 S$β$s) ${\displaystyle$S\$left({\boldsymbol {\beta$}}^{$s}\$right)}가 정지점이 ${\displaystyle {}^{}}$ s+ αδ) < S$($β s)${\displaystyle$ S\left$({\boldsymbol {\beta$}}^{$s}+\alpha$ \Delta \right)<$충분히$ 작은 > ${\displaystyle \alpha >0}$ 모두에 대해 S\left$({\boldsymbol {\beta}}^{s$}\$right$ 따라서, 발산이 발생하는 경우, 한 가지 해결책은 업데이트 공식에 증가 벡터 δ의 분수 $\alpha${\$displaystyle$ \$alpha}$를 사용하는 것입니다.

$${\displaystyle {\boldsymbol {\beta }^{s+1}={\boldsymbol}^{s}+\alpha \Delta.}$$

즉, 증가 벡터는 너무 길지만 여전히 "아래쪽 언덕"을 가리키므로 일부만 이동하면 목적 함수 S가 감소합니다. α ${\displaystyle \alpha}$에 대한 최적의 값은$$ line search 알고리즘, 즉, $\alpha {\displaystyle }$ ${\displaystyle \alpha}$의 크기는$$ 일반적으로 0< < 1 ${\displaystyle$ 0 $<\alpha$< $1}$에서 직접 검색 방법 또는 Armijo-line 검색과 같은 역추적 라인 검색을 사용하여 S를 최소화하는 값을 찾음으로써 결정됩니다. 일반적으로 $\alpha {\displaystyle }$ ${\displaystyle \alpha}$는 Wolf 조건 또는 Goldstein 조건을 만족하도록 선택해야$$ 합니다.^[11]

시프트 벡터의 방향이 최적의 분수 α가 0에 가까울 정도인 경우, 발산을 처리하기 위한 대안적인 방법은 신뢰 영역 방법인 Levenberg-Marquardt 알고리즘을 사용하는 것입니다.^[3] 정규 방정식은 증가 벡터가 가장 가파른 하강 방향으로 회전하는 방식으로 수정됩니다.

$${\displaystyle \left(\mathbf {J^{\mathsf {T}}J+\lambda D} \right)\Delta =-\mathbf {J} ^{\mathsf {T}}\mathbf {r} ,}$$

여기서 D는 양의 대각선 행렬입니다. D가 항등 행렬 I이고 λ → +$$∞ {\$displaystyle$ \lambda \to +\infty}일 때, then ${\displaystyle \lambda \Delta =\lambda \left(\mathbf {J^{\mathsf {T}}J} +\lambda \mathbf {I} \right)^{-1}\left(-\mathbf {J} ^{\mathsf {T}}\mathbf {r} \right)=\left(\mathbf {I}$$-\mathbf {J^{\mathsf {T}} /\lambda +\cdots \right)\left(-\mathbf {J} ^{\mathsf {T}}\mathbf$ {$r} \right)\$to-$\mathbf {$J}^{\$mathsf {T}\mathbf$ {$r}$따라서 $δ$ 방향은 음의 ${\displaystyle {기울기}^{}}$ $-{\displaystyle }$J Tr ${\displaystyle$ -$\mathbf {J$} $^{\mathsf$ {$T}\mathbf$ $\{$r} 방향에 접근합니다.

이른바 Marquardt 매개 변수$$λ ${\$displaystyle$$\lambda }도 라인 검색으로 최적화할 수 있지만 λ ${\displaystyle$ \lambda }이(가) 변경될$때$마다 시프트 벡터를 다시 계산해야 하므로 비효율적입니다. 보다 효율적인 전략은 다음과 같습니다. 발산이 발생하면 S가 감소할 때까지 Marquardt 파라미터를 증가시킵니다. 그런 다음 한 반복에서 다음 반복으로 값을 유지하되 가능하면 컷오프 값에 도달할 때까지 값을 줄인다. 마르콰르트 매개변수를 0으로 설정할 수 있을 때 S의 최소화는 표준 가우스-뉴턴 최소화가 됩니다.

대규모 최적화

대규모 최적화를 위해, 가우스-뉴턴 방법은 행렬 ${\displaystyle {\mathbf{}}_{}}$ ${\$$displaystyle \mathbf {J}_{\mathbf {r}}$이 대략 헤센 ${\displaystyle {Jr\mathbf{}}_{}}$ Tr {\$displaystyle \mathbf {J}_{\mathbf {r}}^{\mathsf {T}\mathbf {J_{r$}}\mathbf {J_{r$}}$보다 더 희소하기 때문에 특별한 관심이 있습니다$.$ 이러한 경우 단계 계산 자체는 일반적으로 공액 구배법과 같이 크고 희박한 문제에 적합한 대략적인 반복 방법으로 수행되어야 합니다.

이러한 종류의 접근 방식이 작동하려면 적어도 제품을 계산하는 효율적인 방법이 필요합니다.

$${\displaystyle {\mathbf {J} _{\mathbf {r}}}^{\mathsf {T}}\mathbf {J_{r}} \mathbf {p} }$$

어떤 벡터 p에 대하여. 희소 행렬 저장의 경우 $일반적$으로 ${\displaystyle {\mathbf{}}_{}}${\$displaystyle \mathbf {J}$ _${\mathbf {r}}$ 행을 압축된 형태$$(예: 0 항목 없음)로 저장하여 전치로 인해 위의 제품을 직접 계산하는 것이 까다롭습니다. 그러나 행렬 ${\displaystyle {\mathbf{}}_{}}$ ${\$의 c를_i 행 i로 정의하면 다음과 같은 단순 관계가 성립합니다$.$

$${\displaystyle {\mathbf {J} _{\mathbf {r}}}^{\mathsf {T}}\mathbf {J_{r}}\mathbf {p} =\sum _{i}\mathbf {c} _{i}\left(\mathbf {c} _{i}\cdot \mathbf {p} \right),}$$

모든 행이 제품에 부가적으로 독립적으로 기여하도록 합니다. 이 표현식은 실제적인 희소 저장 구조를 존중할 뿐만 아니라 병렬 계산에 매우 적합합니다. 모든 행 c는_i 해당 잔차 r의_i 기울기이므로 위의 공식은 잔차가 서로 독립적으로 문제에 기여한다는 사실을 강조합니다.

관련 알고리즘

준뉴턴 방식으로, 예를 들어 데이비드슨, 플레처, 파월 또는 브로이든에 의한 것과 같은 방식으로,플레처-골드파브-샤노(BFGS 방법) 전체 $\frac{{}_{}}{}$ ∂ 2$\frac{{}_{}{S}_{}}{}$ ∂ β j ∂ β k {\$textstyle${\$frac$ ${\partial$^{2}S}{\partial \beta _{j}\partial \beta _{k}}}는 1차 도함수 ∂ r β j {\textstyle {\frac {\partial r_{i}}{\partial \beta _{j}}}를 사용하여 수치화됩니다. n번의 정제 사이클 후에 그 방법은 성능 면에서 뉴턴의 방법과 거의 유사합니다. 준뉴턴 방법은 일반적인 실수 값 함수를 최소화할 수 있는 반면, 가우스-뉴턴, 레벤버그-마르콰르트 등은 비선형 최소 제곱 문제에만 적합합니다.

1차 도함수만을 사용하여 최소화 문제를 해결하기 위한 또 다른 방법은 구배 하강법입니다. 그러나 이 방법은 2차 도함수를 대략적으로 고려하지도 않습니다. 결과적으로 매개변수가 강한 교호작용을 갖는 경우 많은 함수에서 매우 비효율적입니다.

구현 예

줄리아.

Julia의 다음 구현은 제공된 Jacobian을 사용하는 한 가지 방법과 자동 미분이 가능한 또 다른 컴퓨팅을 제공합니다.

"""     gaussnewton(r,J,β₀,maxiter,tol)  'β ₀'에서 시작하는 Jacobian 'J'로 잔차 함수 'r'을 최소화하기 위해 Gauss-Newton 최적화를 수행합니다. 알고리즘은 단계의 norm이 tol보다 작거나 maxiter를 반복한 후에 종료됩니다. """ 기능. 가우스뉴턴(r,J,β,맥시미터,톨)     β = 알았다.(β)     위해서 _ 안에 1:맥시미터         Jβ = J(β);         Δ  = -(Jβ'*Jβ) \ (Jβ'*r(β))          β += Δ         한다면 sqrt(합(abs2,Δ)) < 톨             브레이크.         끝.     끝.     돌아가다 β 끝.  수입품 추상미분 ~하듯이 AD, 지고테 백엔드의 = AD.자이고트 백엔드() # 다른 백엔드를 사용할 수 있습니다.  """     gaussnewton (r,β ₀,maxiter,tol)  'β ₀'에서 시작하는 잔차 함수 'r'을 최소화하기 위해 Gauss-Newton 최적화를 수행합니다. 관련 Jacobian은 부호 자동 미분을 사용하여 계산됩니다. 알고리즘은 단계의 norm이 tol보다 작거나 maxiter를 반복한 후에 종료됩니다. """ 기능. 가우스뉴턴(r,β,맥시미터,톨)     β = 알았다.(β)     위해서 _ 안에 1:맥시미터         rβ, Jβ = AD.value_and_jacob의(백엔드의,r,β)         Δ  = -(Jβ[1]'*Jβ[1]) \ (Jβ[1]'*rβ)          β += Δ         한다면 sqrt(합(abs2,Δ)) < 톨             브레이크.         끝.     끝.     돌아가다 β 끝. 

메모들

참고문헌

• Björck, A. (1996). Numerical methods for least squares problems. SIAM, Philadelphia. ISBN 0-89871-360-9.
• Fletcher, Roger (1987). Practical methods of optimization (2nd ed.). New York: John Wiley & Sons. ISBN 978-0-471-91547-8..
• Nocedal, Jorge; Wright, Stephen (1999). Numerical optimization. New York: Springer. ISBN 0-387-98793-2.

외부 링크

• 확률, 통계 및 추정 이 글에서 예로 든 생물학 실험에 알고리즘을 상세하게 설명하고 적용합니다(추정치의 불확실성과 함께 84페이지).

구현

• Artelys Nitro는 Gauss-Newton 방법을 구현한 비선형 솔루션입니다. C로 작성되었으며 C++/C#/Java/Python/MATLAB/R에 대한 인터페이스가 있습니다.