[수치해석 09] 비구속 최적화

비구속 최적화(Unconstrained Optimization) 는 특정 독립변수가 가질 수 있는 범위가 제한되지 않은 상태에서 이루어지는 최적화 방식을 의미한다. 반대의 개념으로 구속 최적화(Constrained Optimization) 이 있다.

 

최적화(Optimization)

최적화는 함수의 최소값 및 최대값을 구하는 것이다. 

특정 함수에서의 최적점은 곡선 위의 평탄한 점으로, 도함수 f'(x) = 0 이 되는 지점에 해당한다.

이때 2차 도함수 f''(x) < 0 이면 최대값, f''(x) > 0 이면 최소값이 된다.

 

따라서, 최적화를 위해서는 미분 함수인 f'(x) = 0 의 근을 구해 최적점을 얻어야 한다.

 

도함수와 원 함수의 관계

 

1차원 및 다차원에서의 최적화 문제

1차원의 문제는 한 개의 독립변수에 의존하는 함수에 관한 문제이고,

다차원의 문제는 여러개의 독립변수에 의존하는 함수에 관한 문제이다.

 

동일 함수 f에 대해 f(x) 의 최소화 및 -f(x) 의 최대화 문제는 동일하다.

2차원에서의 최적화의 경우, 등고선 형태를 띄는데, 이를 통해 최대 혹은 최소를 찾을 수 있다.

 

 

비구속 최적화

최적화라는 것은 함수의 최소값(global minimum) 혹은 최대값(global maximum)을 찾는 것으로,

이러한 값들은 극대값(local maximum) 이나 극소값(local minimum)과 헷갈릴 수 있다.

이때 local optimum인지, global optimum인지 구별하기 위해 3가지 방법을 사용할 수 있다.

1. 저차원 함수의 경우 그래프를 그려서 시각적으로 구분한다.
2. 광범위, 다양한 시작값을 기반으로 최적값들을 찾고, 그중 가장 크거나 작은 값을 선택한다.
3. 지역 최적점과 관련된 시작점을 교란, 해당 값이 항상 같은 값에 도달하는지, 더 좋은 값을 찾아가는지 판단한다.

황금 분할 탐색법 : 하나의 최적값에 대해 초기 추측값들을 황금비를 이용해 추정해나가는 구간법.

2차 보간법 : 2차 다항식을 이용하여 추정하는 정교한 구간법.

Newton법: 최대 최소값을 f'(x) = 0을 통해 구하는 개구간법

황금분할탐색법

황금비

과거 오래전부터 서구 문명에서 미학적으로 보기 좋다고 여겨진 비율.

 

Euclid 정의에 의하면 황금비란,

 

"선분을 나눌 때 전체 선분 (l₁+l₂) 에 대한 긴 선분의 비(l₁)가 

긴 선분(l₁)에 대한 짧은 선분(l₂)의 비와 같도록" 나누는 것이다.

 

이때 황금비 R = 짧은 선분의 비/긴 선분의 비 =  l₂ / l₁ ≃ (-1 + √5)/2 이다. 

 

 

황금비의 계산

 

황금분할탐색법(Golden-Section Search)

하나의 최적값(unimodal) 만 포함하는 구간에서 최적값을 탐색하는 방법.

이분법에 대해 한개의 중간값을 사용한다. 최적값의 발생여부를 알기 위해 2개의 중간 함수 값을 필요로 하며,

효율적인 중간값들을 선택하여, 이분법처럼 이전 값을 새로운 값으로 치환하여 함수 계산 횟수를 최소화한다.

x_l 및 x_u에 대해 중간값 x₁, x₂를 생성하고, 함수 값에 따라 x_l, x_u 중 하나의 값을 선택해 구간을 줄여나간다.

 

 

 

이때, 반복 전후 구간의 길이 비율이 항상 황금비를 이룬다.

 

 

최대값 기준의 황금분할탐색법

하나의 최적값을 포함하는 두개의 초기값 x_l 및 x_u로부터 시작한다.

R = (√5 - 1)/2=0.618

d=𝑅(x_𝑢 - x_𝑙)

x₁ = x_𝑙 + d, x₂ = x_𝑢− d

 

• f(x₁) > f(x₂) : x_l = x₂,  x₂ = x₁
• f(x₁) < f(x₂) : x_u = x₁, x₁ = x₂

1번 반복할 때마다 구간은 황금비 비율(0.618..)로 줄어든다.

4개의 값 중 3개는 이전 값을 사용하므로 각 반복 단계에서 하나의 함수값만 계산하면 된다.

 

 

예제

황금분할 탐색법의 오차

반복 완료 이후, 최적 값은 [xl, x1] 또는 [x2, xu] 에 존재한다. 상부구간을 이용하여 오차를 추정할 때,

• f(x₁) > f(x₂) : [x_l,x₁,x₂] 구간 최대
• f(x₁) < f(x₂) : [x₂,x₁,x_u] 구간 최대

이때 상부 구간을 기준으로 값을 추정하자.

 

왼쪽 끝 참값. 

 

오른쪽 끝 참값.

 

 

추정 최적값에 의한 정규화 (최대오차 기반으로 추정)

 

 

알고리즘

이 알고리즘에서는 함수의 값을 미리 저장해두고, 반복할 때마다 1번의 추가 함수 연산만 수행한다.

 

 

 

2차 보간법

2차 다항식은 때때로 최적값 근처에서 f(x)의 형상을 근사한다.

이때 최적값을 둘러싸는 3개의 점이 주어질 때 세 점을 연결하는 포물선을 구한다.

 

 

 

새로운 추정 해를 구하는 공식

 

 

 

Newton 법

 

 

f(x)의 최적값을 구하기 위해 f'(x) = 0 인 점을 추정하는 방식.

Newton 법은 "개구간법" 이며, 발산할 수도 있기 때문에 최적 값에 근접했을 때 사용한다.