Main Content

제약 조건이 없는 비선형 최적화 알고리즘

제약 조건이 없는 최적화 정의

제약 조건이 없는 최소화는 스칼라 함수 f(x)에 대한 국소 최솟값인 벡터 x를 구하는 문제입니다.

minxf(x)

제약 조건이 없는이라는 용어는 x의 범위에 어떠한 제한도 적용되지 않았다는 것을 의미합니다.

fminunctrust-region 알고리즘

비선형 최소화를 위한 Trust-Region 방법

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

최적화에 대한 trust-region 접근법을 이해하기 위해 제약 조건이 없는 최소화 문제를 살펴보고, f(x)를 최소화해 보겠습니다. 여기서 함수는 벡터 인수를 받고 스칼라를 반환합니다. n 공간에서 점 x에 있고 향상, 즉 더 낮은 함수 값을 가지는 점으로 이동하기를 원한다고 가정해 보겠습니다. 기본적인 발상은 점 x 주위에 있는 이웃 N에서 함수 f의 동작을 잘 반영하는 더 간단한 함수 q를 사용하여 f를 근사하는 것입니다. 이 이웃을 신뢰 영역이라고 합니다. 시행 스텝 sN에 대한 최소화(또는 근사 최소화)를 수행하여 계산됩니다. 이를 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차 근삿값 qx에서 F에 대한 테일러 근사의 처음 두 항으로 정의되며, 이웃 N은 일반적으로 구면 또는 타원 형태입니다. 수학적으로 trust-region 하위 문제는 대개 다음과 같이 표기됩니다.

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

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

1Δ1s=0.

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

2차원 부분공간 S는 아래에 설명되어 있는 선조건 적용 켤레 기울기법 과정을 통해 결정됩니다. 솔버는 Ss1s2에 의해 생성되는 선형 공간으로 정의합니다. 여기서 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에 대한 근사해입니다. 어느 경우이든 p비선형 최소화를 위한 Trust-Region 방법에 설명된 trust-region 접근법에 사용되는 2차원 부분공간을 정의하는 데 도움이 됩니다.

fminuncquasi-newton 알고리즘

제약 조건이 없는 최적화 관련 기본 사항

제약 조건이 없는 최적화를 위한 다양한 방법이 존재하지만, 크게는 사용되거나 사용되지 않는 도함수 정보를 기준으로 분류될 수 있습니다. 함수 실행만 사용하는 탐색 방법(예: 넬더-미드 심플렉스(Nelder-Mead Simplex) 탐색 [30])은 매끄럽지 않거나 여러 개의 불연속 지점을 갖는 문제에 가장 적합합니다. 기울기 방법은 일반적으로 최소화하려는 함수가 1계 도함수에서 연속인 경우에 더욱 효율적입니다. 뉴턴의 방법과 같이 차수가 높은 방법일수록 2차 정보가 순조롭고 쉽게 계산되는 경우에만 적합합니다. 그 이유는 수치 미분을 사용하는 2차 정보 계산은 많은 계산량을 요하기 때문입니다.

기울기 방법은 최솟값이 있다고 여겨지는 곳의 탐색 방향을 정하기 위해 함수의 기울기에 대한 정보를 사용합니다. 그중 가장 단순한 방법은 탐색이 –∇f(x) 방향으로 수행되는 최속강하법입니다. 여기서 f(x)는 목적 함수의 기울기입니다. 이 방법은 최소화하려는 함수가 길고 좁은 밸리를 가지는 경우 매우 비효율적입니다. 예를 들어, 다음과 같은 로젠브록 함수가 이에 해당됩니다.

f(x)=100(x2x12)2+(1x1)2.(5)

이 함수의 최솟값은 x = [1,1]에 있습니다. 여기서 f(x) = 0입니다. 이 함수의 등고선 지도는 점 [–2,2]에서 시작하여 최속강하법 구현에서의 최솟값에 이르는 해의 경로와 함께 아래 Figure에 표시되어 있습니다. 400회의 반복 실행 후 최적화가 종료되었으며, 여전히 최솟값과는 거리가 상당히 떨어져 있습니다. 검은색 영역은 이 방법이 밸리의 한쪽에서 다른 쪽으로 연속적으로 지그재그 방향으로 움직이는 부분을 나타냅니다.

Level curves of the Rosenbrock function are close to the parabola y = x^2

 Figure 생성에 사용된 코드

바나나 함수라고도 하는 이 함수는 곡률이 원점을 중심으로 구부러지는 형태 때문에 제약 조건이 없는 예제 중 잘 알려진 함수입니다. 로젠브록 함수는 다양한 최적화 기법 사용을 보여주기 위해 이 섹션 전체에 걸쳐 차용됩니다. 등고선은 U자 모양의 밸리 주변 기울기의 경사도로 인해 지수적 증분 단위로 플로팅되었습니다.

반복 점을 생성하는 스크립트를 포함하여 위 Figure에 대한 더 자세한 설명을 보려면 바나나 함수 최소화 항목을 참조하십시오.

준뉴턴(Quasi-Newton) 방법

기울기 정보를 사용하는 방법 중에서 가장 선호되는 방법이 바로 준뉴턴 방법입니다. 이 방법은 각 반복에서 곡률 정보를 생성하여 다음 형식의 2차 모델 문제를 정식화합니다.

minx12xTHx+cTx+b,(6)

여기서 헤세 행렬 H는 양의 정부호 대칭 행렬이고, c는 상수 벡터이고, b는 상수입니다. 이 문제의 최적해는 x의 편도함수가 0이 될 때 발생합니다. 즉, 다음과 같습니다.

f(x*)=Hx*+c=0.(7)

최적해에 해당하는 점 x*는 다음과 같이 작성할 수 있습니다.

x*=H1c.(8)

뉴턴 유형 방법은 (준뉴턴 방법과는 다르게) 여러 반복 후 H를 직접 계산하고 하강 방향으로 진행하여 최솟값을 찾습니다. H를 수치적으로 계산하는 과정에는 많은 양의 계산이 수반됩니다. 준뉴턴 방법은 f(x)와 f(x)의 관측된 동작을 사용하여 곡률 정보를 생성함으로써 적합한 업데이트 기법으로 H에 대한 근삿값을 구하는 방식으로 이를 방지합니다.

많은 수의 헤세 행렬 업데이트 방법이 개발되었습니다. 그러나, 브로이든(Broyden) [3], 플레처(Fletcher) [12], 골드파브(Goldfarb) [20], 샤노(Shanno) [37](BFGS)의 식이 일반적인 용도의 방법에 사용하는 데 가장 효과적인 것으로 평가됩니다.

BFGS 식은 다음과 같습니다.

Hk+1=Hk+qkqkTqkTskHkskskTHkTskTHksk,(9)

여기서

sk=xk+1xk,qk=f(xk+1)f(xk).

시작점으로 H0은 임의의 양의 정부호 대칭 행렬(예:단위 행렬 I)로 설정될 수 있습니다. 헤세 행렬 H의 역이 발생하지 않도록, 사용자는 각 업데이트마다 헤세 행렬의 역행렬인 H–1의 근삿값을 구하는 식을 사용하여 H에 대한 직접적인 역이 발생하지 않도록 하는 업데이트 방법을 도출해낼 수 있습니다. 잘 알려진 절차는 데이비든(Davidon) [7], 플레처(Fletcher), 파월(Powell)[14]의 DFP 식입니다. 이 절차는 BFGS 방법(수식 9)과 동일한 식을 사용합니다. 단, qksk 대신 사용된다는 점만 다릅니다.

기울기 정보는 해석적으로 계산된 기울기를 통해 제공되거나 유한 차분을 통한 수치 미분 방법을 사용하여 편도함수에 의해 도출됩니다. 이 과정에는 각 설계 변수 x에 차례로 섭동을 추가하고 목적 함수의 변화율을 계산하는 작업이 수반됩니다.

주요 반복인 k번마다 다음 방향으로 직선 탐색이 수행됩니다.

d=Hk1f(xk).(10)

준뉴턴 방법의 예가 로젠브록 함수에 대한 해의 경로로 표시되어 있습니다. 이 방법은 밸리의 형태를 따라갈 수 있으며 유한 차분 기울기만 사용하여 약 150회의 함수 평가 후 최솟값으로 수렴합니다.

Level curves of the Rosenbrock function are close to the parabola y = x^2. The iterative steps go from upper-left, down around the parabola, to upper-right.

 Figure 생성에 사용된 코드

반복 점을 생성하는 스크립트를 포함하여 위 Figure에 대한 더 자세한 설명을 보려면 바나나 함수 최소화 항목을 참조하십시오.

직선 탐색

직선 탐색은 규모가 큰 최적화 알고리즘의 일부로 사용되는 탐색 방법입니다. 주 알고리즘의 각 단계마다 직선 탐색 방법은 주 알고리즘이 결정하는 벡터인 탐색 방향과 평행하게 현재 점 xk를 포함하는 선을 따라 탐색을 수행합니다. 즉, 이 방법은 아래 형식의 다음 반복 xk+1을 찾습니다.

xk+1=xk+α*dk,(11)

여기서 xk는 현재 반복을 나타내고, dk는 탐색 방향이며, α*는 스칼라 스텝 길이 파라미터입니다.

직선 탐색 방법은 목적 함수의 다항식 보간 모델을 반복적으로 최소화하여 직선 xk + α*dk를 따라 목적 함수를 줄이려고 시도합니다. 직선 탐색 절차는 다음과 같은 두 가지 주요 단계로 구성됩니다.

  • 탐색 구간 설정(bracketing) 단계에서는 탐색하려는 직선 xk+1=xk+α*dk 위에 있는 점의 범위를 결정합니다. 탐색 구간(bracket)α의 값 범위를 지정하는 구간에 해당합니다.

  • 분할(sectioning) 단계에서는 탐색 구간을 하위 구간으로 분할합니다. 이 하위 구간에서 다항식 보간에 의해 목적 함수 최솟값에 대한 근삿값이 구해집니다.

결과로 생성되는 스텝 길이는 다음과 같은 울프(Wolfe) 조건을 충족합니다.

f(xk+αdk)f(xk)+c1αfkTdk,(12)
f(xk+αdk)Tdkc2fkTdk,(13)

여기서 c1c2는 0 < c1 < c2 < 1을 충족하는 상수입니다.

첫 번째 조건(수식 12)을 만족하려면 αk가 목적 함수를 충분히 감소시켜야 합니다. 두 번째 조건(수식 13)은 스텝 길이가 너무 작지 않도록 만들어 줍니다. 두 조건(수식 12수식 13)을 모두 충족하는 점을 수용 가능한 점이라고 합니다.

직선 탐색 방법은 [13]의 섹션 2-6에 설명되어 있는 알고리즘을 구현한 것입니다. 직선 탐색에 대한 자세한 내용을 보려면 [31]도 참조하십시오.

헤세 행렬 업데이트

다수의 최적화 함수는 BFGS 방법(수식 9)을 통해 각 반복마다 헤세 행렬을 업데이트하여 탐색 방향을 결정합니다. 함수 fminunc준뉴턴(Quasi-Newton) 방법에 주어진 DFP 방법을 사용하는 옵션도 제공합니다(DFP 방법을 선택하려면 options에서 HessUpdate'dfp'로 설정함). 탐색 방향 d가 항상 하강 방향이 되도록 헤세 행렬 H는 항상 양의 정부호 행렬로 유지됩니다. 이는 방향 d에서 일부 임의의 작은 스텝 α에 대해 목적 함수의 크기가 감소한다는 것을 의미합니다. H가 양의 정부호가 되도록 초기화된 후 qkTsk(수식 14 참조)가 항상 양수가 되도록 하여 H의 양의 정부호 특성을 충족시킬 수 있습니다. 항 qkTsk는 직선 탐색 스텝 길이 파라미터 αk와, 탐색 방향 d와 과거 및 현재 기울기 계산 결과의 조합의 곱입니다.

qkTsk=αk(f(xk+1)Tdf(xk)Td).(14)

충분히 정확한 직선 탐색을 수행하면 qkTsk가 양수여야 한다는 조건이 항상 충족됩니다. 이는 탐색 방향 d가 하강 방향이어서 αk 및 음수 기울기 –∇f(xk)Td가 항상 양수가 되도록 하기 때문입니다. 따라서, 가능한 음수 항 –∇f(xk+1)Td는 직선 탐색의 정확도를 높임으로써 필요한 만큼 크기를 작게 만들 수 있습니다.

LBFGS 헤세 행렬 근사

대규모 문제의 경우 BFGS 헤세 행렬 근사법은 상대적으로 느리고 대용량의 메모리를 사용할 수 있습니다. 이러한 문제를 방지하려면 HessianApproximation 옵션을 'lbfgs'로 설정하여 LBFGS 헤세 행렬 근사를 사용하십시오. 이와 같이 설정하면 fminunc가 Low-memory BFGS 헤세 행렬 근사를 사용합니다(아래에 설명되어 있음). 대규모 문제에 LBFGS를 사용할 경우의 이점에 대해 알아보려면 Solve Nonlinear Problem with Many Variables 항목을 참조하십시오.

Nocedal과 Wright의 문헌[31]에 설명되어 있는 것과 같이, Low-memory BFGS 헤세 행렬 근사는 준뉴턴(Quasi-Newton) 방법에 설명된 BFGS 근사와 비슷하지만, 이전 반복에 대해서는 제한된 양의 메모리를 사용합니다. 수식 9에 주어진 헤세 행렬 업데이트 식은 다음과 같습니다.

Hk+1=Hk+qkqkTqkTskHkskskTHkTskTHksk,

여기서

sk=xk+1xk,qk=f(xk+1)f(xk).

BFGS 절차에 대한 또 다른 설명은 다음과 같습니다.

xk+1=xkαkHkfk,(15)

여기서 ɑk는 직선 탐색에서 선택된 스텝 길이이고 Hk는 헤세 행렬의 역행렬 근사입니다. Hk에 대한 식은 다음과 같습니다.

Hk+1=VkTHkVk+ρkskskT,

여기서 skqk는 앞에서 정의된 바와 같고, 추가로 다음과 같이 정의됩니다.

ρk=1qkTskVk=IρkqkskT.

LBFGS 알고리즘은 직전 반복에서의 파라미터 skqk의 고정된 유한 개수 m을 유지합니다. 초기점 H0부터 시작하여, 수식 15로부터 스텝을 구하기 위해 근사 Hk를 계산합니다. Hkfk의 계산은 ρj, qj, sj의 가장 최근 m 값을 사용하여 이전 방정식부터 재귀 방식으로 진행됩니다. 자세한 내용은 Nocedal과 Wright의 문헌[31]의 Algorithm 7.4를 참조하십시오.

참고 항목

관련 항목