Main Content

방정식 풀이 알고리즘

방정식 풀이 정의

n개의 비선형 함수 Fi(x) 집합이 있다고 가정할 경우(여기서 n은 벡터 x의 성분 개수임) 방정식 풀이의 목적은 모든 Fi(x)를 0으로 만드는 벡터 x를 구하는 것입니다.

fsolve는 성분의 제곱합을 최소화하여 연립방정식을 풀려고 시도합니다. 제곱합이 0이면 연립방정식의 해가 구해집니다. fsolve에는 다음과 같이 세 가지 알고리즘이 있습니다.

  • Trust-region

  • Trust-region-dogleg

  • Levenberg-Marquardt

모든 알고리즘은 대규모입니다. 대규모 알고리즘과 중간 규모 알고리즘 비교 항목을 참조하십시오.

fzero 함수는 하나의 1차원 방정식을 풉니다.

mldivide 함수는 선형 연립방정식을 풉니다.

Trust-Region 알고리즘

Optimization Toolbox™ 솔버에 사용되는 대부분의 방법이 최적화의 단순하지만 강력한 개념인 신뢰 영역을 기반으로 합니다.

최적화에 대한 trust-region 접근법을 이해하기 위해 제약 조건이 없는 최소화 문제를 살펴보고, f(x)를 최소화해 보겠습니다. 여기서 함수는 벡터 인수를 받고 스칼라를 반환합니다. 현재 점은 n-공간에 있는 점 x이고, 더 낮은 함수 값을 가지는 점으로 이동하여 향상하기를 원한다고 가정해 보겠습니다. 이를 위해 알고리즘은 점 x 주위에 있는 이웃 N에서 함수 f의 동작을 잘 반영하는 더 간단한 함수 q를 사용하여 f를 근사합니다. 이 이웃을 신뢰 영역이라고 합니다. 솔버는 N에 대한 최소화(또는 근사 최소화)를 수행하여 시행 스텝 s를 계산합니다. trust-region 하위 문제는 다음과 같습니다.

mins{q(s), sN}.

솔버는 f(x + s) < f(x)인 경우 현재 점을 x + s로 업데이트합니다. 그렇지 않은 경우 현재 점은 변경되지 않고 그대로 유지되며 솔버가 N(신뢰 영역)을 축소하고 시행 스텝 계산을 반복합니다.

f(x)를 최소화하기 위한 특정 trust-region 접근법을 정의할 때 고려해야 할 핵심 질문은 근삿값 q(현재 점 x에서 정의됨)를 선택하고 계산하는 방법은 무엇인가, 신뢰 영역 N을 선택하고 수정하는 방법은 무엇인가, 그리고 trust-region 하위 문제를 얼마나 정확하게 풀 수 있는가입니다.

표준 trust-region 방법([48])에서는 2차 근삿값 q가 x에서 F에 대한 테일러 근사의 처음 두 항으로 정의됩니다. 이웃 N은 일반적으로 구면 또는 타원 형태입니다. 수학적으로 trust-region 하위 문제는 대개 다음과 같이 표기됩니다.

min{12sTHs+sTg  such that  DsΔ},(1)

여기서 g는 현재 점 x에서 f의 기울기이고, H는 헤세 행렬(2계 도함수의 대칭 행렬)이고, D는 대각 스케일링 행렬이고, Δ는 양의 스칼라이며, ‖ . ‖는 2-노름입니다. 수식 1을 풀기 위해 알고리즘([48] 참조)은 H의 모든 고유값을 계산한 후 다음과 같은 고유방정식에 뉴턴 과정을 적용할 수 있습니다.

1Δ1s=0.

이러한 알고리즘은 수식 1에 대한 정확한 해를 제공합니다. 하지만, 이 알고리즘을 사용하려면 H에 대한 여러 행렬 분해에 비례하는 시간이 필요합니다. 따라서, trust-region 문제에는 다른 접근법이 필요합니다. 수식 1 기반한 여러 근사법과 발견법 전략이 참고 문헌([42][50])에서 제안되었습니다. Optimization Toolbox 솔버는 trust-region 하위 문제를 2차원 부분공간 S([39][42])로 제한하는 근사 접근법을 따릅니다. 솔버가 부분공간 S를 계산하고 나면 수식 1을 푸는 방법은 간단합니다. 부분공간에서는 문제가 2차원뿐이기 때문입니다. 이제 수행해야 하는 주된 작업은 부분공간을 결정하는 것입니다.

솔버는 선조건 적용 켤레 기울기법(다음 섹션에서 설명)의 도움을 받아 2차원 부분공간 S를 결정합니다. 솔버는 S를 s1 및 s2에 의해 생성되는 선형 공간으로 정의합니다. 여기서 s1은 기울기 g의 방향이고 s2는 근사 뉴턴 방향, 즉 다음 수식의 해이거나,

Hs2=g,

또는 다음과 같은 음의 곡률 방향입니다.

s2THs2<0.

이러한 S 선택의 바탕이 되는 철학은 (최속강하법 방향 또는 음의 곡률 방향을 통해) 전역 수렴을 강제 적용하고 (존재하는 경우 뉴턴 스텝을 통해) 신속하게 국소 수렴을 달성한다는 것입니다.

trust-region 접근법을 사용한 제약 조건이 없는 최소화 과정은 이제 다음과 같이 간단하게 지정할 수 있습니다.

  1. 2차원 trust-region 하위 문제를 정식화합니다.

  2. 수식 1를 풀어서 시행 스텝 s를 결정합니다.

  3. f(x + s) < f(x)이면 x = x + s입니다.

  4. Δ를 조정합니다.

솔버는 표준 규칙에 따라 trust-region 차원 Δ를 조정해 가면서 수렴이 이루어질 때까지 이 네 단계를 반복합니다. 특히, 솔버가 시행 스텝을 받아들이지 않을 경우, 즉 f(x + s) ≥ f(x)인 경우에는 trust-region 크기를 줄입니다. 이 사항에 대한 자세한 내용은 [46] 항목과 [49] 항목을 참조하십시오.

Optimization Toolbox 솔버는 비선형 최소제곱, 2차 함수, 선형 최소제곱 등의 특화된 함수를 사용하여 f에 대한 중요한 사례를 처리합니다. 하지만, 기반이 되는 알고리즘적 발상은 일반적인 사례와 동일합니다.

선조건 적용 켤레 기울기법(Preconditioned Conjugate Gradient Method)

선조건 적용 켤레 기울기법(PCG)은 대규모 양의 정부호 대칭 선형 연립방정식 Hp = –g를 푸는 데 자주 사용되는 방법입니다. 이 반복적인 접근법을 사용하려면 H·v 형식의 행렬-벡터 곱을 계산할 수 있어야 합니다. 여기서 v는 임의 벡터입니다. 양의 정부호 대칭 행렬 M 은 H에 대한 선조건자입니다. 즉, M = C2입니다. 여기서 C–1HC–1은 조건이 좋은 행렬이거나 서로 다른 고유값이 모여 있는 행렬입니다.

최소화의 맥락에서는 헤세 행렬 H가 대칭 행렬이라고 간주할 수 있습니다. 하지만, H는 강력한 최소점의 이웃인 경우에만 양의 정부호 행렬 여부가 보장됩니다. 알고리즘 PCG는 음의 곡률(또는 영곡률) 방향이 발생한 경우, 즉 dTHd ≤ 0인 경우에 종료됩니다. PCG 출력값 방향 p는 음의 곡률 방향이거나 뉴턴 시스템 Hp = –g에 대한 근사해입니다. 어느 경우이든 p는 비선형 최소화를 위한 Trust-Region 방법에 설명된 trust-region 접근법에 사용되는 2차원 부분공간을 정의하는 데 도움이 됩니다.

Trust-Region-Dogleg 알고리즘

또 다른 접근법은 선형 연립방정식을 풀어 탐색 방향을 구하는 것입니다. 뉴턴의 방법은 다음을 충족하는 탐색 방향 dk를 구합니다.

J(xk)dk = –F(xk)
xk + 1 = xk + dk,

여기서 J(xk)는 다음과 같이 n×n 야코비 행렬입니다.

J(xk)=[F1(xk)TF2(xk)TFn(xk)T].

뉴턴의 방법에는 문제가 있을 수 있습니다. J(xk)가 특이 행렬일 수 있는데 그럴 경우에는 뉴턴 스텝 dk가 정의되지 않습니다. 또한, 정확한 뉴턴 스텝 dk는 계산하는 데 시간이 많이 걸릴 수 있습니다. 뿐만 아니라, 시작점이 해와 거리가 먼 경우 뉴턴의 방법이 수렴되지 않을 수 있습니다.

trust-region 기법(비선형 최소화를 위한 Trust-Region 방법에서 소개됨)을 사용하면 J(xk)가 특이 행렬인 경우가 처리되고 시작점이 해와 거리가 먼 경우 견고성이 향상됩니다. trust-region 전략을 사용하려면 xk + 1이 xk보다 더 좋은지 아니면 더 나쁜지를 결정하기 위해 이득 함수가 필요합니다. 가능한 선택은 다음과 같습니다.

mindf(d)=12F(xk+d)TF(xk+d).

하지만 f(d)의 최솟값이 반드시 F(x)의 근이 되지는 않습니다.

뉴턴 스텝 dk는 다음에 대한 근이고

M(xk + d) = F(xk) + J(xk)d,

또한 m(d)의 최솟값이기도 합니다. 여기서는 다음이 성립됩니다.

mindm(d)=12M(xk+d)22=12F(xk)+J(xk)d22=12F(xk)TF(xk)+dTJ(xk)TF(xk)+12dTJ(xk)TJ(xk)d.(2)

이득 함수로 f(d)보다 m(d)를 선택하는 것이 더 나으며, 따라서 trust-region 하위 문제는 다음과 같이 되며,

mind[12F(xk)TF(xk)+dTJ(xk)TF(xk)+12dTJ(xk)TJ(xk)d],(3)

적용되는 조건은 ‖D·d‖ ≤ Δ입니다. 이 하위 문제는 dogleg 전략을 사용하여 효율적으로 풀 수 있습니다.

trust-region 방법에 대한 개요는 Conn의 문헌[4] 및 Nocedal의 문헌 [31]을 참조하십시오.

Trust-Region-Dogleg 구현

trust-region-dogleg 알고리즘의 주요 특징은 수식 3을 최소화하는 스텝 d를 계산하기 위해 파월(Powell)의 dogleg 절차를 사용한다는 것입니다. 자세한 설명은 파월(Powell)의 문헌 [34]을 참조하십시오.

이 알고리즘은 코시(Cauchy) 스텝(최속강하법 방향을 따르는 스텝)과 f(x)에 대한 가우스-뉴턴 스텝의 볼록 결합에서 스텝 d를 생성합니다. 코시 스텝은 다음과 같이 계산됩니다.

dC = –αJ(xk)TF(xk),

여기서 α는 수식 2를 최소화합니다.

가우스-뉴턴 스텝은 다음을 풀면 계산됩니다.

J(xk)·dGN = –F(xk),

이때 MATLAB® mldivide(행렬 왼쪽 나눗셈) 연산자를 사용합니다.

이 알고리즘은 다음을 충족하는 d를 선택합니다.

d = dC + λ(dGN – dC),

여기서 λ는 구간 [0,1]에서 ‖d‖ ≤ Δ를 충족하는 가장 큰 값입니다. Jk가 특이 행렬인 경우 (또는 특이 행렬에 가까운 경우) d는 코시 방향입니다.

trust-region-dogleg 알고리즘은 (가우스-뉴턴 스텝의 계산 시) 반복당 하나의 선형 풀이만 필요하므로 효율적입니다. 또한, 이 알고리즘이 직선 탐색에 가우스-뉴턴 방법을 사용하는 것보다 더 견고할 수 있습니다.

Levenberg-Marquardt 방법

Levenberg-Marquardt 알고리즘([25][27])은 다음 선형 방정식 세트의 해인 탐색 방향을 사용하거나,

(J(xk)TJ(xk)+λkI)dk=J(xk)TF(xk),(4)

또는, 선택적으로 다음 방정식의 해인 탐색 방향을 사용합니다.

(J(xk)TJ(xk)+λkdiag(J(xk)TJ(xk)))dk=J(xk)TF(xk),(5)

여기서 스칼라 λk는 dk의 크기와 방향을 모두 제어합니다. 수식 4를 사용하려면 fsolve 옵션 ScaleProblem'none'으로 설정하고, 수식 5를 사용하려면 이 옵션을 'jacobian'으로 설정하십시오.

λk가 0인 경우 방향 dk는 가우스-뉴턴 방법입니다. λk가 무한대로 가려 함에 따라 dk는 최속강하법 방향을 향하려 하며, 크기는 0에 가까워지려 합니다. 이는 충분히 큰 어떤 λk에 대해 항 F(xk + dk) < F(xk)가 성립한다는 것을 의미합니다. 따라서 이 알고리즘은 가우스-뉴턴 방법의 효율성을 제한하는 2차 항이 있음에도 불구하고 하강을 계속하도록 항 λk를 제어할 수 있습니다. 따라서 Levenberg-Marquardt 방법은 가우스-뉴턴 방향과 최속강하법 방향을 번갈아 이용하는 탐색 방향을 사용합니다. 자세한 내용은 최소제곱 문서에서 Levenberg-Marquardt 방법 항목을 참조하십시오.

fzero 알고리즘

fzero는 스칼라 변수 x에 대한 스칼라 함수 f의 근을 구하려고 합니다.

fzero는 f(x)의 부호가 바뀌는 구간을 초기점 주변에서 탐색합니다. 초기점 대신 초기 구간을 지정하면 fzero는 f(x)가 구간의 끝점에서 다른 부호를 갖는지를 확인합니다. 초기 구간은 유한해야 하며, ±Inf를 포함할 수 없습니다.

fzero는 f(x)의 근을 찾기 위해 구간 이분법, 선형 보간, 2차 역보간법(Inverse Quadratic Interpolation)을 조합하여 사용합니다. 자세한 내용은 fzero를 참조하십시오.

\ 알고리즘

\ 알고리즘은 mldivide에 대한 MATLAB 산술 연산자 섹션에 설명되어 있습니다.

참고 항목

|

관련 항목