이 페이지의 최신 내용은 아직 번역되지 않았습니다. 최신 내용은 영문으로 볼 수 있습니다.

방정식 풀이 알고리즘

방정식 풀이 정의

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

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

  • Trust-region

  • Trust-region dogleg

  • Levenberg-Marquardt

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

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

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

fsolve의 Trust-Region 알고리즘

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

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

mins{q(s), sN}.(1)

현재 점은 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Δ},(2)

여기서 g는 현재 점 x에서 f의 기울기이고, H는 헤세 행렬(2계 도함수의 대칭 행렬)이고, D는 대각 스케일링 행렬이고, Δ는 양의 스칼라이며, ∥ . ∥는 2-노름입니다. 수식 2를 푸는 데 사용할 수 있는 좋은 알고리즘이 있습니다([48] 참조). 이러한 알고리즘은 일반적으로 다음과 같은 고유방정식에 적용되는 뉴턴 과정 및 비희소(Full) 고유 시스템에 대한 계산을 포함합니다.

1Δ1s=0.

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

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

Hs2=g,(3)

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

s2THs2<0.(4)

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

trust-region 알고리즘을 사용한 제약 조건이 없는 최소화 과정은 이제 다음과 같이 간단하게 요약할 수 있습니다.

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

  2. 수식 2를 풀어서 시행 스텝 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에 대한 근사해(tol이 근사 정도를 제어함)입니다. 어느 경우이든 비선형 최소화를 위한 Trust-Region 방법에 설명된 trust-region 접근법에 사용되는 2차원 부분공간을 정의하는 데 도움이 되도록 p가 사용됩니다.

Trust-Region Dogleg 방법

선형 연립방정식을 풀어 탐색 방향을 구하는 또 다른 접근법, 즉 뉴턴의 방법(Newton's Method)은 다음을 충족하는 탐색 방향 dk를 구합니다.

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

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

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.(5)

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

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

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

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

Trust-Region Dogleg 구현

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

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

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

여기서 α는 수식 5를 최소화하도록 선택됩니다.

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

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

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

스텝 d는 다음이 충족되도록 선택됩니다.

d = dC + λ(dGN – dC),

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

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

Levenberg-Marquardt 방법

Levenberg-Marquardt [25][27] 방법은 다음과 같은 선형 방정식 세트

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

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

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

여기서 스칼라 λk는 dk의 크기와 방향을 모두 제어합니다. 옵션 ScaleProblem'none'으로 설정하여 수식 7을 선택하고 ScaleProblem'Jacobian'으로 설정하여 수식 8을 선택할 수 있습니다.

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

\ 알고리즘

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

fzero 알고리즘

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

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

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