준뉴턴 방법
준뉴턴법뉴턴의 방법을 기반으로 한 최적화 방법으로, 주로 비선형 방정식이나 연속 함수의 영점, 최대값, 최소값 문제를 푸는 데 사용됩니다.
뉴턴의 방법에서 야코비안 행렬이 헤시안 행렬을 계산하기 어렵거나 불가능한 경우, 준뉴턴 방법이 사용됩니다. 이는 비선형 최적화 문제를 해결하는 가장 효과적인 방법 중 하나입니다. 준뉴턴 방식은 미국에서 처음 제안되었습니다. 아르곤 국립 연구소의 물리학자 WCDavidon ~에 20 세기 50 제안된 시대.
준뉴턴법의 아이디어
뉴턴의 방법은 해결된다 헤시안 행렬을 계산할 때 역행렬을 먼저 계산해야 하므로 효율성이 떨어지지만, 준뉴턴법은 양의 정부호 행렬을 사용하여 근사합니다. 헤시안 행렬의 역행렬을 구함으로써 알고리즘의 복잡도를 낮추고 효율성을 향상시킨다.
일반적인 준뉴턴 알고리즘
- DFP(Davidon-Fletcher-Powell) 알고리즘
DFP 알고리즘에서 우리는 각 반복에서 행렬이 두 개의 추가 항으로 구성된다고 가정하여 근사치로 선택합니다.
안에,
그리고
결정되지 않은 행렬입니다. 하지만
만들다
준뉴턴 조건을 만족시키면 다음과 같습니다.그리고풀다
바람직한
매트릭스반복 공식
초기 행렬이 다음과 같은 경우 증명될 수 있습니다.
양의 정부호인 경우 반복 과정의 각 행렬은
모두 긍정적입니다.
- BFGS(Broyden-Fletcher-Goldfard-Shano) 알고리즘
DFP는헤시안 행렬의 역행렬 근사화
, BFGS 알고리즘에서는
헤시안 행렬 근사
, 해당 준뉴턴 조건
각 반복에서 행렬이 다음과 같다고 가정합니다.
~이다두 가지 추가 용어가 있습니다.
안에,그리고결정되지 않은 행렬입니다. 하지만
만들다준뉴턴 조건을 만족시키면 다음과 같습니다.그리고풀다
바람직한
매트릭스반복 공식
초기 행렬이 다음과 같은 경우 증명될 수 있습니다.
양의 정부호인 경우 반복 과정의 각 행렬은모두 긍정적입니다.
- 브로이든(Broyden) 알고리즘 유형 알고리즘
BFGS 알고리즘 행렬을 얻을 수 있습니다BFGS 알고리즘의 반복 공식은 다음과 같습니다..의 반복 공식.
기억하다
Sherman-Morrison 공식을 두 번 적용하면 다음과 같습니다.
이를 BFGS 알고리즘이라고 합니다..의 반복 공식.
셔먼-모리슨 공식: 가정
n차 가역 행렬입니다.
n차원 벡터이고
가 가역행렬이라면:
DFP 알고리즘에 의해 얻어진 반복 공식은 다음과 같습니다.로 기록됨
BFGS 알고리즘의 반복 공식에 따르면당신이 얻는 것와 는 모두 준뉴턴 조건을 만족하므로 두 가지의 선형 조합은 로 표시됩니다.
또한 이는 준뉴턴 조건을 만족하며 양의 정부호입니다. 안에,
. 이런 유형의 알고리즘을 브로이든 유형 알고리즘이라고 합니다.