준뉴턴법

준뉴턴 방법은 뉴턴의 방법의 대안으로 함수의 영점이나 국소 맥시마와 미니마를 찾는 데 사용되는 방법이다.Jacobian 또는 Hessian이 사용할 수 없거나 너무 비싸서 반복할 때마다 계산하지 못할 경우 이 매개변수를 사용할 수 있다."완전한" 뉴턴의 방법은 0을 찾기 위해 자코비안이나, 극단성을 찾기 위해 헤시안을 필요로 한다.

0 검색: 루트 찾기

Newton's method to find zeroes of a function ${\displaystyle g}$ of multiple variables is given by ${\displaystyle x_{n+1}=x_{n}-[J_{g}(x_{n})]^{-1}g(x_{n})}$, where ${\displaystyle [J_{g}(x_{n})]^{-1}}$ is the left inverse of t$x{\displaystyle {}_{}}$ ${\displaystyle n_{}}$ ${\$$displaystyle g}$의 Jacobian 행렬 J$g$ ( x n ) {\displaystyle J_${g}(x_{n})$에 대해 평가된$$ g {\$displaystyle x_{n$

엄밀히 말하면, 정확한 Jacobian $J{\displaystyle {}_{}}$ ${\displaystyle g_{}}$( x ${\displaystyle n_{}}$) ${\displaystyle J_{g}(x_{n})$을 근사치로$$ 대체하는 모든 방법은 준뉴턴 방법이다.^[1]예를 들어 코드 방법(J ${\displaystyle g_{}}$( ${\displaystyle x_{}}$ n${\displaystyle {}_{}}$) ${\displaystyle J_{g}(x_{n})$이 모든 반복에 $대해$ ${\displaystyle J_{}}$ g${\displaystyle {}_{}}$( ${\displaystyle {}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$) ${\displaystyle J_{g}(x_{0})$로 대체되는$$ 경우)은 간단한 예다.최적화를 위해 아래에 제시된 방법은 준뉴턴 방법의 중요한 하위 분류인 세컨트 방법을 참조한다.^[2]

0을 찾기 위해 개발된 방법을 사용하는 것이 항상 좋은 생각은 아니다. 극단성을 찾는데 사용되는 방법의 대다수는 사용되는 행렬이 대칭이어야 하기 때문이다.이것은 극단성을 찾는 맥락에서 유지되지만, 0을 찾을 때는 거의 유지되지 않는다.브로이든의 '좋은' 방법과 '나쁜' 방법은 0을 찾는 데도 적용할 수 있는 극단성을 찾는 데 흔히 쓰이는 두 가지 방법이다.그 밖에 사용할 수 있는 방법으로는 칼럼업데이트법, 역기둥업데이트법, 준뉴턴최소제곱법, 준뉴턴최소제곱법 등이 있다.

더 최근에 준 뉴턴 방법은 복수 결합 방정식 시스템(예: 유체-구조 상호작용 문제 또는 물리학의 상호작용 문제)의 해결책을 찾기 위해 적용되었다.그들은 (글로벌 시스템보다 더 간단한) 각 구성 시스템을 각각 분리하여 (글로벌 시스템보다) 순환적이고 반복적인 방식으로 해결함으로써 글로벌 시스템의 해결책이 발견될 때까지 해결책을 찾을 수 있도록 한다.^[2][3]

극단값 검색: 최적화

스칼라 값 함수의 최소값 또는 최대값 검색은 해당 함수의 그라데이션 0에 대한 검색에 불과하다.따라서 준뉴턴 방법은 함수의 극단성을 찾기 위해 쉽게 적용할 수 있다.즉, $g{\displaystyle }$ ${\displaystyle g}$이(가) $f{\displaystyle }$ ${\displaystyle f}$의 그라데이션인$$ 경우$,$ 벡터 값 $함수{\displaystyle }$ g$${\$displaystyle$$g$}의 0 검색은 스칼라 값 $함수{\displaystyle }$ f$${\$displaystyle$ f$}$의 $극단$ 검색에 해당하며$,$ $g{\displaystyle }$ ${\dis$가 된다$$$.$$[\displaystyle$ f$}$의 a$.$가장 큰 차이점은 헤시안 행렬이 0을 검색할 때 자코비안 행렬과 달리 대칭 행렬이라는 점이다.최적화에 사용되는 대부분의 준뉴턴 방법은 이 속성을 이용한다.

최적화에서 준뉴턴 방법(변수금속 방법의 특수한 경우)은 함수의 국소 최대값과 최소값을 찾기 위한 알고리즘이다.준뉴턴 방법은 뉴턴이 함수의 정지점을 찾는 방법에 근거한 것으로, 경사가 0이다.뉴턴의 방법은 함수가 최적점을 중심으로 부위에서 2차적인 것으로 국소적으로 근사할 수 있다고 가정하고, 제1차 및 제2차 파생상품을 사용하여 정지점을 찾는다.더 높은 치수에서 뉴턴의 방법은 최소화할 기능의 두 번째 파생상품의 구배와 헤시안 매트릭스를 사용한다.

준 뉴턴 방법에서는 헤시안 매트릭스를 계산할 필요가 없다.헤시안은 대신 연속적인 그라데이션 벡터를 분석하여 업데이트된다.준뉴턴법은 다차원적 문제에 대한 첫 번째 파생상품의 뿌리를 찾기 위해 제2차적 방법을 일반화한 것이다.다차원에서는 세컨트 방정식이 충분히 결정되지 않으며, 준 뉴턴 방법은 일반적으로 헤시안의 현재 추정치에 간단한 하위 순위 업데이트를 추가함으로써 해결책을 제약하는 방법에 따라 다르다.

최초의 준 뉴턴 알고리즘은 윌리엄 C에 의해 제안되었다. Argonne National Laboratory에서 일하는 물리학자 Davidon.그는 1959년 최초의 준뉴턴 알고리즘인 DFP 업데이트 공식을 개발했는데, 이후 1963년 플레처와 파웰에 의해 대중화되었지만 오늘날에는 거의 사용되지 않는다.가장 일반적인 준뉴턴 알고리즘은 현재 SR1 공식('대칭 순위 1'을 위한)과 BHHHH 방법, 널리 보급된 BFGS 방법(Broyden, Fletcher, Goldfarb, Shanno, 1970년 독립적으로 제안), 저메모리 확장 L-BFGS이다.브로이든의 클래스는 DFP와 BFGS 방법의 선형 결합이다.

SR1 공식은 양의 정의를 유지하기 위해 업데이트 매트릭스를 보장하지 않으며 무기한 문제에 사용할 수 있다.브로이든의 방법은 업데이트 매트릭스가 대칭적일 것을 요구하지 않으며 (경사가 아닌) 야코비안(헤시안보다)을 업데이트함으로써 (경사가 아닌) 방정식의 일반 시스템의 뿌리를 찾는 데 사용된다.

뉴턴의 방법에 비해 준뉴턴의 방법의 주요 장점 중 하나는 헤시안 매트릭스(또는 준뉴턴 방법의 경우 그 근사치) $B{\displaystyle }$ ${\디스플레이 스타일$ B$}$을(를) 반전시킬 필요가 없다는$$ 점이다.뉴턴의 방법, 그리고 내부 포인트 방법과 같은 그 파생상품은 헤시언을 뒤집도록 요구하는데, 이는 일반적으로 선형 방정식의 시스템을 풀어서 실행되며 종종 상당한 비용이 든다.이와는 대조적으로 준뉴턴 방법은 대개 ${\displaystyle {\mathrm{B}}^{}}$- 1${\$의 추정치를 직접$$ 생성한다.

뉴턴의 방법에서와 ${\displaystyle \mathrm{같이}}$, $함수{\displaystyle }$ f${\displaystyle }$( x$){\displaystyle f(x)}$의 최소값을 찾기 위해 2차 근사치를 사용한다$.$반복을 중심으로$$ 한 Taylor 시리즈 $f{\displaystyle }$( ${\displaystyle x}$) ${\displaystyle$ f$(x)}$는

${\displaystyle f(x_{k}+\Delta x)\관련 f(x_{k})+\nabla f(x_{k})^{\mathrm {T}}\\delta x+{1}{1}{1}}}}\delta x^{{{{{{}}}}\mathrmatrmatrmartrmartrmatrmerm},\B\,\delta x,\c},\c.$

여기서 ( ${\displaystyle \mathrm{}}$ ${\displaystyle f}$ ${\displaystyle \nabla f}$)는 그라데이션이고, $B{\displaystyle }$ ${\displaystyle B}$은 헤시안 행렬에 대한 근사치.^[4]이 근사치의 구배($\Delta {\displaystyle \mathrm{}}$ ${\displaystyle x}$ ${\displaystyle \Delta x}$에 대한$)$는 다음과 같다.

${\displaystyle \nabla f(x_{k}+\Delta x)\대략 \nabla f(x_{k})+B\,\Delta x,}$

그리고 이 구배를 0(최적화의 목표)으로 설정하면 뉴턴 단계가 제공된다.

${\displaystyle \Delta x=-B^{-1}\nabla f(x_{k})}$

Hesisian 근사 $B{\displaystyle }$ ${\displaystyle B}$을(를) 만족하도록 선택됨$$

${\displaystyle \nabla f(x_{k}+\Delta x)=\nabla f(x_{k})+B\,\Delta x,}$

이를 제2차 방정식(경사 자체의 테일러 시리즈)이라고 한다.둘 이상의 차원 $B{\displaystyle }$ ${\displaystyle B}$이(가) 충분히 결정되지 않음$$.한 차원에서는 $B{\displaystyle }$ ${\displaystyle B}$에 대한 해결과$$ 업데이트된 값으로 뉴턴의 단계를 적용하는 것이 제2차원의 방법과 동일하다.다양한 준 뉴턴 방법은 제2차 방정식에 대한 해법 선택에 따라 다르다(한 차원에서는 모든 변형이 동일하다).대부분의 방법(예: Broyden의 방법)은 대칭적 솔루션(${\displaystyle B}$ ${\displaystyle T^{}}$= B ${\displaystyle B^{$$T}=B}$); furthermore, the variants listed below can be motivated by finding an update ${\displaystyle B_{k+1}}$ that is as close as possible to ${\displaystyle B_{k}}$ in some norm; that is, ${\displaystyle B_{k+1}=\operatorname {argmin} _{B}\ B-B_{k}\ _{V}}$,여기서 $V{\displaystyle }$ ${\displaystyle V}$은(는) 규범을 정의하는 확실한 일부 행렬이다.대략적인 초기 값 ${\displaystyle {B\mathrm{}}_{}}$ 0${\displaystyle {}_{}}$= ${\displaystyle \beta }$ I ${\displaystyle B_{0}=\beta I}$은(는) $\beta {\displaystyle }$ ${\\displaystyle \beta }$을(를) 선택하는 일반적인 전략은 없지만 빠른 수렴을 달성하기에 충분한$$ 경우가 많다$.$^[5] B ${\displaystyle {0\mathrm{}}_{}}$ ${\$은 양정확해야 한다는$$ 점에 유의하십시오.알 수 없는 $x{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$은(는) 현재 근사 헤시안 매트릭스 ${\displaystyle B_{}}$ k ${\$를 사용하여 계산된 뉴턴의 단계를 적용하여 업데이트된다$.$

• ${\displaystyle }$$\Delta {\displaystyle }$ ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$= -${\displaystyle {}_{}^{}{\alpha k}_{}}$ B ${\displaystyle k_{}^{}}$ - ${\displaystyle 1_{}^{}\mathrm{}³}$ f${\displaystyle }$( x ${\displaystyle k_{}}$) ${\displaystyle$ $\$$Delta x_{k}=-\alpha _{k}^{$1}-1}:{-1$}\$$nabla$ $f(x_{k})$가$$Wolfe 조건을 충족하기 위해 선택됨$;$
• ${\displaystyle x_{}}$ ${\displaystyle k_{}}$+ ${\displaystyle 1_{}}$= ${\displaystyle x_{}}$ k${\displaystyle {}_{}}$+ ${\displaystyle \mathrm{\Delta }}$ ${\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$;
• 새 지점$$$\nabla {\displaystyle \mathrm{}}$ ${\displaystyle f}$( ${\displaystyle x_{}}$ ${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$) ${\displaystyle \nabla f(x_{k+1})$에서 계산된 그라데이션

${\displaystyle y_{k}=\displayla f(x_{k+1})-\displayla f(x_{k}})$

Sherman-Morrison 공식을 사용하여$$ Hesian $B{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{k}}_{}}$+ 1 ${\$또는 $Hesian{\displaystyle {}_{}}$ B ${\displaystyle k_{}}$ +${\displaystyle 1_{}}$= ${\displaystyle {\mathrm{B}}_{}^{}}$ ${\displaystyle {}_{}^{}}$+ 1 -${\displaystyle 1_{}^{}}$ ${\$1}:{-$1}$를 직접 업데이트하는 데 사용된다.

• BFGS 및 DFP 업데이트의 주요 속성은 ${\displaystyle {Bk}_{}}$ ${\$가 양의 정의로 되어$$ 있고, ${\displaystyle {\alpha k}_{}}$ ${\$가 Wolfe 조건을 만족시키기 위해 선택되어 있다면$$ ${\displaystyle {Bk}_{}}$+ ${\$}도$$양의 정의로 되어 있다는$$ 것이다.

가장 많이 사용되는 업데이트 수식은 다음과 같다.

방법	${\displaystyle \displaystyle B_{k+1}=}$	${\displaystyle H_{k+1}=B_{k+1}^{-1}=}$
BFGS	${\displaystyle B_{k}+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}-{\frac {B_{k}\Delta x_{k}(B_{k}\Delta x_{k})^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }B_{k}\,\Delta x_{k}}}}$	${\displaystyle \left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm{T}}}}}{y_{k}^{\mathrm {T}}}}}\delta x_{k}}}}\오른쪽)H_{k}\left(I-{\frac {y_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\Delta x_{k}}}\right)+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}}$
브로이든	${\displaystyle B_{k}+{\frac {y_{k}-B_{k}}\Delta x_{k}}}{\Delta x_{k}}^{}}\Delta x_{k}}}}}\Delta x_{k}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}$	${\displaystyle H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k}}})\Delta x_{k}^{\mathrm {T}{}}}H_{k}}{\Delta x_{k}^{\mathrm {T}{}}{H_{k}\H_{k}\,y_{k}}}}}}}}}}}}{k}}}}}}}}}}}}}}}}}}}}}}}}}}$
브로이든 가문	${\displaystyle(1-\varphi _{k})B_{k+1}^{\text{BFGS}+\varphi _{k}B_{k+1}^{\text{DFP},\quad \varphi \in [0,1]}$
DFP	${\displaystyle \left(I-{\frac {y_{k}\,\Delta x_{k}^{{k}^{}}}}}{y_{k}^{\mathrm {T}\}\Delta x_{k}}}\오른쪽)B_{k}\left(I-{\frac {\Delta x_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}\right)+{\frac {y_{k}y_{k}^{\mathrm {T} }}{y_{k}^{\mathrm {T} }\,\Delta x_{k}}}}$	${\displaystyle H_{k}+{\frac {\Delta x_{k}\Delta x_{k}^{\mathrm {T} }}{\Delta x_{k}^{\mathrm {T} }\,y_{k}}}-{\frac {H_{k}y_{k}y_{k}^{\mathrm {T} }H_{k}}{y_{k}^{\mathrm {T} }H_{k}y_{k}}}}$
SR1	${\displaystyle B_{k}+{\frac {(y_{k}-B_{k}\,\Delta x_{k})(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }}{(y_{k}-B_{k}\,\Delta x_{k})^{\mathrm {T} }\,\Delta x_{k}}}}$	${\displaystyle H_{k}+{\frac {(\Delta x_{k}-H_{k}y_{k})(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }}{(\Delta x_{k}-H_{k}y_{k})^{\mathrm {T} }y_{k}}}}$

다른 방법으로는 피어슨의 방법, 맥코믹의 방법, 파월 대칭 브로이든(PSB) 방법, 그린슈타트의 방법 등이 있다.^[2]

행렬 반전과의 관계

$f{\displaystyle }$ ${\displaystyle f}$이(가) 양-확정 $헤시안{\displaystyle }$ B ${\displaystyle$ $B$$}$을(를) 가진 볼록한 2차 함수인 경우$$$,$ 준뉴턴 방법으로 생성된$$ ${\displaystyle {행렬}_{}}$ H ${\$ H${\displaystyle }$= ${\displaystyle {}^{}}$- ${\displaystyle 1^{}}$ ${\$에$$수렴할 것으로 예상할 수 있다$.$최소한의 변경 업데이트에 기초한 준 뉴턴 방법의 종류는 실제로 그러하다.^[6]

주목할 만한 구현

준 뉴턴 방법의 구현은 많은 프로그래밍 언어로 이용할 수 있다.주목할 만한 구현에는 다음이 포함된다.

• GNU 옥타브는 BFGS의 형태를 사용한다.fsolve트러스트 영역 확장이 있는 기능.
• GNU 과학 도서관은 BFGS(Broyden-Fletcher-Goldfarb-Shanno) 알고리즘을 구현한다.
• 마티카에는 준뉴턴 해결사가 포함되어 있다.^[7]
• NAG 라이브러리에는 준뉴턴 알고리즘을 사용하는 함수를^[9] 최소화하거나 최대화하기 위한 몇 가지 루틴이^[8] 포함되어 있다.
• MATLAB의 Optimization Toolbox에서는fminunc함수는 (다른 방법 중) BFGS 준 뉴턴 방법을 사용한다.^[10]Optimization(최적화) 도구 상자의 제약된 방법 중 다수는 BFGS와 변종 L-BFGS를 사용한다.^[11]<
• R'soptim범용 최적화 도구 루틴은 BFGS 방법을 사용하여method="BFGS".^[12]
• Scipy.optimize에는 fmin_bfgs가 있다.Python에 대한 SciPy 확장에서는scipy.optimize.minimize기능에는 BFGS 구현이 포함된다.^[13]

참고 항목

• BFGS법
  • L-BFGS
  • 올빼미-QN
• 브로이덴의 방법
• DFP 업데이트 공식
• 뉴턴의 방법
• 뉴턴의 최적화 방법
• SR1 공식

참조

추가 읽기

• Bonnans, J. F.; Gilbert, J. Ch.; Lemaréchal, C.; Sagastizábal, C. A. (2006). Numerical Optimization : Theoretical and Numerical Aspects (Second ed.). Springer. ISBN 3-540-35445-X.
• Fletcher, Roger (1987), Practical methods of optimization (2nd ed.), New York: John Wiley & Sons, ISBN 978-0-471-91547-8.
• Nocedal, Jorge; Wright, Stephen J. (1999). "Quasi-Newton Methods". Numerical Optimization. New York: Springer. pp. 192–221. ISBN 0-387-98793-2.
• Press, W. H.; Teukolsky, S. A.; Vetterling, W. T.; Flannery, B. P. (2007). "Section 10.9. Quasi-Newton or Variable Metric Methods in Multidimensions". Numerical Recipes: The Art of Scientific Computing (3rd ed.). New York: Cambridge University Press. ISBN 978-0-521-88068-8.
• Scales, L. E. (1985). Introduction to Non-Linear Optimization. New York: MacMillan. pp. 84–106. ISBN 0-333-32552-4.