브로이든-플레처-골드파브-샨노 알고리즘

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "브로이든-Fletcher-Goldfarb-Shanno 알고리즘" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2016년 3월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

수치적 최적화에서 브로이든-Fletcher-Goldfarb-Shanno(BFGS) 알고리즘은 구속되지 않은 비선형 최적화 문제를 해결하기 위한 반복적인 방법이다.^[1]관련 다비던처럼-Fletcher-Powell 방법, BFGS는 곡률 정보로 구배를 전제하여 하강 방향을 결정한다.일반화된 제분법을 통해 구배 평가(또는 근사 구배 평가)에서만 얻은 손실 함수의 헤시안 매트릭스에 대한 근사치를 점진적으로 개선함으로써 그렇게 한다.^[2]

BFGS 곡률 매트릭스의 업데이트는 매트릭스 역전이 필요하지 않으므로 연산 복잡성은 뉴턴의 방법에서 O${\displaystyle ({}^{}}$ ${\displaystyle {3\mathrm{}}^{}}$) ${\$$displaystyle {\mathcal {O}(n^{3$}) ${\displaystyle$ {\$mathcal$ {O$}(n^{3})}$에 비해 O$($n^2)에 $불과하다$${\displaystyle {}^{}}$또한 L-BFGS는 매우 많은 변수(예: >1000)의 문제에 특히 적합한 BFGS의 제한된 메모리 버전이다.BFGS-B 모델은 단순한 박스 구속조건을 처리한다.^[3]

이 알고리즘은 찰스 조지 브로이든, 로저 플레처, 도널드 골드파브, 데이비드 섀노의 이름을 따서 지어졌다.^[4][5][6][7]

이론적 근거

최적화 문제는 $f{\displaystyle }$( ${\displaystyle x\mathbf{}}$) ${\displaystyle$ f$(\mathbf {x} )}$을(를) 최소화하는 것이다$.$ $여기$서 x ${\$은(는) ${\displaystyle {}^{}}$ n ${\$의 벡터이고$$, $f{\displaystyle }$ ${\displaystaystystythetable$ 스칼라 $함수$.$x{\displaystyle \mathbf{}}$ ${\$이(가) 취할 수 있는$$ 값에는 제한이 없다.

알고리즘은 최적값 ${\displaystyle {\mathrm{}}_{}}$ 0 ${\$에 대한 초기 추정치에서 시작하여$$ 각 단계에서 더 나은 추정치를 얻기 위해 반복적으로 진행한다.

k단계에서 검색 방향 p는_k 뉴턴 방정식의 아날로그 해법에 의해 주어진다.

${\displaystyle B_{k}\mathbf {p} _{k}=-\nabla f(\mathbf {x} _{k}),}$

는 반복적으로 각 단계마다 업데이트됩니다는 헤시 안 행렬, 어디에 Bk{\displaystyle B_{km그리고 4.9초 만}}은 근사치고 함수 xk에서 평가되의 ∇ f()k){\displaystyle \nabla f(\mathbf{x}_{k})}은 기울기.방향 pk고 있는 선로 검색한 다음 그 다음 요지를 찾기 xk+1 f을 최소화하면서(인데에 의해 사용된다${\displaystyle {}_k}$+ ${\displaystyle {}_{}}$ p ${\displaystyle {}_{}}$) ${\displaystyle f(\mathbf {x} _{k}+\mathbf {p}$ $_$${k}}$ 스칼라 0 ${\displaystyle \gamma}$을(를) 위에$$ 놓는다$.$$}$

$B{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$ 업데이트에 부과된 준뉴턴 조건은$$

${\displaystyle B_{k+1}(\mathbf {x} _{k+1}-\mathbf {x} _{k}=\nabla f(\mathbf {x} _{k})-\mathbf {x}_{k}).}$

Let ${\displaystyle \mathbf {y} _{k}=\nabla f(\mathbf {x} _{k+1})-\nabla f(\mathbf {x} _{k})}$ and ${\displaystyle \mathbf {s} _{k}=\mathbf {x} _{k+1}-\mathbf {x} _{k}}$, then ${\displaystyle B_{k+1}}$ satisfies ${\displaystyle B_{k+1}}$${\displaystyle {}_{}}$= ${\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$ ${\$ 이것이 제2차 방정식이다.만약 전국 곡률 상태여서 km그리고 4.9초 만 ⊤ y k>0{\displaystyle \mathbf{s}_{k}^{\top}\mathbf{y}_{k}>. 0}일 경우 Bk+1{\displaystyle B_{k+1}에}은}skm그리고 4.9초 만 T{\displaystyle \mathbf{s}_{k}^{T}을 정할 방정식 pre-multiplying으로 확인해야 할 수 있는 긍정적인 확실한,. 만족해야 한다.func강하게 볼록하지 않은 상태에서 조건을 명시적으로 적용해야 한다.

$x{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$+ ${\displaystyle 1_{}}$ ${\$지점의 전체 헤시안 행렬을 $B{\displaystyle {}_{}}$ ${\displaystyle {\mathrm{k}}_{}}$+ 1 ${\$로 계산하도록 요구하는$$ 대신, 단계 k에서의 대략적인 헤시안 행렬은 다음 두 개의 행렬을 추가하여 업데이트된다$.$

${\displaystyle B_{k+1}=B_{k}+U_{k}+V_{k}}}$

$U{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$와 ${\displaystyle V_{}}$ $k{\displaystyle {}_{}}$ ${\$ 모두 대칭적인 순위 1 행렬이지만$$, 그 합계는 순위 2 업데이트 행렬이다.BFGS와 DFP 업데이트 매트릭스는 모두 2위 매트릭스에 의해 이전 매트릭스와 다르다.또 다른 간단한 순위 1 방법은 대칭 순위 1 방법으로 알려져 있는데, 이것은 양의 확정성을 보장하지 않는다.In order to maintain the symmetry and positive definiteness of ${\displaystyle B_{k+1}}$, the update form can be chosen as ${\displaystyle B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }}$. Imposing the secant condition, $$${\displaystyle B_{k+1}\mathbf {s} _{k}=\mathbf {y} _{k}}$. Choosing ${\displaystyle \mathbf {u} =\mathbf {y} _{k}}$ and ${\displaystyle \mathbf {v} =B_{k}\mathbf {s} _{k}}$, we can obtain:^[8]

${\displaystyle \alpha ={\frac {1}{\mathbf {y} _{k}^{T}\mathbf {s},}$

${\displaystyle \beta =-{\frac {1}{\mathbf {s} _{k}^{k}B_{k}\mathbf {s} _{k}}}.}$

Finally, we substitute ${\displaystyle \alpha }$ and ${\displaystyle \beta }$ into ${\displaystyle B_{k+1}=B_{k}+\alpha \mathbf {u} \mathbf {u} ^{\top }+\beta \mathbf {v} \mathbf {v} ^{\top }}$ and get the update equation of ${\displaystyle B_{k+1}}$:

${\displaystyle B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} }B_{k}^{\mathrm {T} }}{\mathbf {s} _{k}^{\mathrm {T} }B_{k}\mathbf {s} _{k}}}.}$

알고리즘.

초기 추측 $x{\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {\mathrm{}}_{}}$ ${\$ 및$$ 대략적인 헤시안 ${\displaystyle {매트릭스\mathrm{}}_{}}$ B 0$${\$displaystyle$B_${0$}}에서 $x{\displaystyle {\mathbf{}}_{}}$ k ${\$이(가) 솔루션으로 수렴되면서$$ 다음$$ 단계가 반복된다.

1. $B{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\displaystyle {}_{}}$ ${\displaystyle {}_{}{\mathbf{}}_{}}$= -${\displaystyle }$$display$ f ( x k$)$ {\${\displaystyle \mathrm{displaystyle}}$$$B_$k}\mathbf {p} _{$k} _{k} _{$k}=-\nabla$ f$(\mathbf {x} _{k}})$를 풀어서 방향$$ $p{\displaystyle {\mathbf{}}_{}}$ {$k}$을 얻으십시오$.$
2. 1차원 최적화(라인 검색)를 수행하여 첫 번째 단계에서 찾은 방향으로$$ ${\displaystyle {\alpha k}_{}}$ ${\$ 허용 가능한 단계화 α k {\displaystyle \alpha _{k}.If an exact line search is performed, then ${\displaystyle \alpha _{k}=\arg \min f(\mathbf {x} _{k}+\alpha \mathbf {p} _{k})}$ . In practice, an inexact line search usually suffices, with an acceptable ${\displaystyle \alpha _{k}}$ satisfying Wolfe conditions.
3. ${\displaystyle {}_{}}$ k${\displaystyle {}_{}}$= ${\displaystyle {\alpha k}_{}}$ p ${\displaystyle {}_{}}$ ${\$을(를) 설정하고$$ ${\displaystyle {\mathrm{x}}_{}}$ ${\displaystyle {}_{}}$+ 1${\displaystyle {}_{}}$= ${\displaystyle {\mathbf{}}_{}}$ ${\displaystyle {}_{}}$+ ${\displaystyle {}_{}}$ ${\$
4. ${\displaystyle {}_{}y}$ ${\displaystyle {}_{}}$= ${\displaystyle \nabla \mathrm{}}$ f${\displaystyle }$( ${\displaystyle {\mathrm{x}}_{}}$ ${\displaystyle {}_{}}$+ 1${\displaystyle {}_{}}$) -${\displaystyle \mathrm{\nabla }}$ ${\displaystyle f}$( x ${\displaystyle {}_{}}$) ${\$mathbf {$k$
5. ${\displaystyle B_{k+1}=B_{k}+{\frac {\mathbf {y} _{k}\mathbf {y} _{k}^{\mathrm {T} }}{\mathbf {y} _{k}^{\mathrm {T} }\mathbf {s} _{k}}}-{\frac {B_{k}\mathbf {s} _{k}\ma$$thbf {s} _{k}^{\mathrm {T}^{{$B_${k}^{\mathrm {T}}}}{{k}^{{k}^{}}\mathrm {T}}{B_{k}}\mathbf {s} _{k$

${\displaystyle f}$( ${\displaystyle x\mathbf{}}$) ${\displaystyle f(\mathbf {x} )}$은(는) 최소화할 목표 함수를 의미한다$$.수렴은 gradient의 ${\displaystyle \mathrm{규범}}$인 ${\displaystyle \nabla \mathrm{}}$ f${\displaystyle }$( x $displaystyle \nabla$ f$(\mathbf {x} _{k}}}}}$을(를) 관찰하여 확인할 수 있다$.$ ${\displaystyle {B\mathrm{}}_{}}$ ${\displaystyle {0\mathrm{}}_{}}$${\displaystyle {}_{}}$= ${\displaystyle I}$ ${\displaystyle B_{0}=I}$로 초기화된$$ 경우 첫$$번째 단계는 gradient down과 동일하지만 더 많은 단계들이다.$B{\displaystyle {}_{}}$ ${\displaystyle k_{}}$ ${\$에 의해 더 정제된 것으로,$$헤시안 근사값이다.

알고리즘의 첫 번째 단계는 $매트릭스{\displaystyle {}_{}}$ B ${\displaystyle k_{}}$ ${\${k$}$의 역순을 이용하여 수행되는데$,$ 이 매트릭스 B k {\displaystyle B_${k$}}를 알고리즘의 5단계에 적용하면 효율적으로 얻을 수 있어 다음과 같은 장점이 있다.

${\displaystyle B_{k+1}^{-1}=\왼쪽(I-{\frac {\mathbf {s} _{k}\mathbf {y} _{k}^{{k}^)T}{{\mathbf {y} _{k}^{T}\mathbf {s} _{k}\오른쪽)B_{k}^{-1}\left(I-{\frac {\mathbf {y} _{k}\mathbf {s} _{k}^{{k}^)T}{{{k}^{T}\mathbf {s} _{k}}\mathbf {s}\{k}\오른쪽)+{\frac {\mathbf {s} _{k}\mathbf {s}{k}^{k}}^{{}}}}{}}}}}}}}}}}}}}}}}}}T}{{\mathbf {y} _{k}^{T}\mathbf {s} _{k}}.}$

This can be computed efficiently without temporary matrices, recognizing that ${\displaystyle B_{k}^{-1}}$ is symmetric, and that ${\displaystyle \mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}\mathbf {y} _{k}}$ and ${\displaystyle \mathbf {s} _{k}^{\mathrm {$$T} }}\mathbf {y} _{k}}$은(는) 다음과 같은 확장을 사용하는 스칼라이다$$.

${\displaystyle B_{k+1}^{-1}=B_{k}^{-1}+{\frac {(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k}+\mathbf {y} _{k}^{\mathrm {T} }B_{k}^{-1}\mathbf {y} _{k})(\mathbf {s} _{k}\mathbf {s} _{k}^{\mathrm {T} })}{(\mathbf {s} _{k}^{\mathrm {T} }\mathbf {y} _{k})^{2}}}-{\frac {B_{k}^{-1}\mathbf {y} _{k}\mathbf {s} _{k}^{\mathrm {T} }+\mathbf {s} _{k}\mathbf{y} _{k}^{{k}^{{B_{k}^{-1}{{\mathbf {s} _{k}^{k}^{k}{k}^{k}}}\mathbf {y} _{k}}}}}}.}$

통계적 추정 문제(최대우도 또는 베이지안 추론 등)에서는 최종 헤시안 행렬의^{[citation needed]} 역행으로부터 해법에 대한 신뢰 구간이나 신뢰 구간을 추정할 수 있다.그러나 이러한 수량은 기술적으로 참 헤시안 행렬에 의해 정의되며, BFGS 근사치는 참 헤시안 행렬에 수렴되지 않을 수 있다.^[9]

주목할 만한 구현

• 대규모 비선형 최적화 소프트웨어 Artelys Nitro는 무엇보다도 BFGS와 L-BFGS 알고리즘을 구현한다.
• GSL은 BFGS를 gsl_multimina_fdfminimizer_vector_bfgs2로 구현한다.^[10]
• MATLAB Optimization Toolbox에서 fminunc 함수는^[11] 문제 크기를 "중규모"로 설정할 때 입방선 검색과 함께 BFGS를 사용한다.^[12]
• R에서 BFGS 알고리즘(및 박스 구속조건을 허용하는 L-BFGS-B 버전)은 기본 함수 최적화의 옵션으로 구현된다().^[13]
• SciPy에서 scipy.optimize.fmin_bfgs 함수는 BFGS를 구현한다.^[14]또한 파라미터 L을 매우 큰 숫자로 설정하여 L-BFGS 알고리즘 중 어떤 것을 사용하여 BFGS를 실행할 수도 있다.

참고 항목

참조

추가 읽기

• Avriel, Mordecai (2003), Nonlinear Programming: Analysis and Methods, Dover Publishing, ISBN 978-0-486-43227-4
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. (2006), "Newtonian Methods", Numerical Optimization: Theoretical and Practical Aspects (Second ed.), Berlin: Springer, pp. 51–66, 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
• Luenberger, David G.; Ye, Yinyu (2008), Linear and nonlinear programming, International Series in Operations Research & Management Science, vol. 116 (Third ed.), New York: Springer, pp. xiv+546, ISBN 978-0-387-74502-2, MR 2423726
• Kelley, C. T. (1999), Iterative Methods for Optimization, Philadelphia: Society for Industrial and Applied Mathematics, pp. 71–86, ISBN 0-89871-433-8
• Nocedal, Jorge; Wright, Stephen J. (2006), Numerical Optimization (2nd ed.), Berlin, New York: Springer-Verlag, ISBN 978-0-387-30303-1