[수치해석] Ch13. One-Dimensional Unconstrained Optimization

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

▶Optimization

근 찾기와 최적화는 함수의 점을 추측하고 검색하는 것과 관련이 있다.

• 근 찾기는 함수의 0을 검색하는 것이다.

• 최적화는 여러 변수의 함수의 최솟값 또는 최댓값을 찾는 것이다.

f'(x)를 분석적으로 사용할 수 없기 때문에 종종 복잡해진다.  

따라서, 때때로 미분을 추정하기 위해 finite-difference approximation을 사용해야 한다.

 

Difference between Roots and Optima

(a) 1차원 최적화
f(x)의 최소화가 -f(x)의 최대화와 어떻게 동일한지를 보여준다.

(b) 2차원 최적화
최대화(최대 고도까지 상승) 또는 최소화(최소 고도까지 하강)를 나타낼 수 있다.

 

▶Mathematical Background

최적화에서 objective function이란 무엇인가?

수학적 최적화 문제에서 최소화되거나 최대화되어야 하는 실제 값 함수이다. 

 

multi-modal function이란 무엇입니까?

둘 이상의 모드 또는 최적(예: 계곡)을 갖는 함수를 의미한다.

다중 모드 함수는 볼록하지 않다.

하나의 글로벌 optima와 하나 이상의 로컬 또는 deceptive optima가 있을 수 있다.

 

▶One-Dimensional Unconstrained Optimization

multimodal 함수에서는 지역 및 전역 최적화가 모두 발생할 수 있다. 
거의 모든 경우에서, 함수의 절대적인 최고 또는 최저 값을 찾는 데 관심이 있다.

 

루트 위치에서와 마찬가지로 한 차원의 최적화는 bracketing과 open method으로 나눌 수 있다. 

golden-section search는 단일 최적을 bracket 하는 초기 추측에 의존하는 괄호 방법의 한 예이다. 
대체 접근법인 parabolic interpolation은 golden-section search보다 빠르게 수렴하지만 때로는 분기된다.

다른 방법은 f'(x) = 0을 풀면 최소 또는 최대를 찾을 수 있다는 open method이다.
이 접근법의 한 가지 버전으로 Newton's method가 있다.

 

마지막으로, 고급 하이브리드 접근법인 Brent's method가 있다. 
이 접근법은 golden-section search의 신뢰성과 포물선 보간 속도를 결합한다.

 

 

global optimum과 local optimum을 어떻게 구별할까?

• 그래프를 그려본다.

• 무작위로 생성된 시작 추측을 사용하고 최적화 중 가장 큰 것을 전역으로 선택한다.

• 루틴이 더 나은 점을 반환하는지 또는 동일한 로컬 최솟값을 반환하는지 확인하기 위해 시작점을 교란한다.

세 번째는 무슨 말인지 이해하지 못했다.

728x90

▶Golden-Section Search

unimodal 함수는 주어진 구간에서 단일 최댓값 또는 최솟값을 갖는다. (max나 min이 하나만 존재한다.)

• 먼저 극치를 묶을 두 점을 고른다. [xl, xu].
• 간격 내에서 세 번째 점을 추가로 선택하여 최댓값이 발생했는지 여부를 확인한다.
• 그다음 네 번째 점을 선택하여 최댓값이 처음 세 점 내에서 발생했는지 아니면 마지막 세 점 내에서 발생했는지 확인한다.

1) l0 = l1 + l2

2) l1 / l0 = l2 / l1

첫 번째 조건 : 두 개의 서브 길이 l1과 l2는 원래 간격의 길이의 합이다.

두 번째 조건 : 길이의 비율을 동일하다.

이 방법은 f(x)의 한 local 극한을 괄호로 묶는 xl과 xu로 시작한다.

• 다음 두 내부 점 x1과 x2는 황금 비율에 따라 선택된다.

두 가지 결과가 발생할 수 있다.

• f(x1) > f(x2)면, xl에서 x2까지의 x2의 도메인은 최대치를 포함하지 않기 때문에 제거될 수 있다. 

  그러면 x2는 다음 라운드의 새로운 xl이 된다.

• f(x2) > f(x1)면, x1에서 xu까지의 도메인은 제거될 것이다.

  이 경우 x1은 다음 라운드의 새로운 xu가 된다.

 

 

Error Estimate

루트 위치에 대한 bisection과 마찬가지로, 대략적인 오차의 정확한 상한 추정을 가능하게 한다.

 

 

ex.

f(x) = 2 * sinx - x^2 / 10 interval xl = 0, xu = 4

d = (root5 - 1) / 2 * (xu - xl) = 2.472

x1 = 0 + 2.472 = 2.472

x2 = 4 - 2.472 = 1.528

 

f(x2) = 1.765

f(x1) = 0.63

 

d = (root5 - 1) / 2 * d

 

f(x2) > f(x1)

xu = x1 = 2.472

x1 = x2 = 1.528

▶Parabolic Interpolation

두 점을 연결하는 직선이 하나뿐인 것처럼, 세 점을 연결하는 이차 다항식이나 포물선은 하나뿐이다.

따라서, 최적을 공동으로 괄호로 묶는 세 개의 점이 있다면, 포물선을 그릴 수 있다.

ex.

f(x) = 2 * sinx - x^2 / 10

x0 = 0, x1 = 1, x2 = 4

 

▶Newton's Method

Newton-Rapshon 방법은 f(x) = 0과 같은 함수의 근을 찾는 open method이다.

유사한 open method을 사용하여 새로운 함수 g(x) = f'(x)를 정의하여 f(x)의 최적값을 찾을 수 있다.

따라서, 동일한 최적값 x*가 f'(x*) = g(x*) = 0을 모두 만족하기 때문에, xi+1 = xi - (f'(xi) / f''(xi))을 사용할 수 있다.

 

ex.

f(x) = 2 * sinx - x^2 / 10, x0 = 2.5

f'(x) = 2 * cosx - x / 5

f''(x) = -2 * sinx - 1 / 5

 

xi+1 = xi - (2 * cosx - x/5) / (-2 * sinx - 1/5)

x0 = 2.5

x1 = 0.99508

x2 = 1.46901

... -> 1.77385

하지만 뉴턴은 항상 수렴한다는 보장을 할 수 없다.

-> 최적점이 있다면 수렴할 가능성은 높다.

또한, 주어진 함수가 미분 가능할 때만 사용 가능하다.

 

▶Brent's Method

느리고 신뢰할 수 있는 golden-section search와 더 빠르지만 신뢰할 수 없는 parabolic interpolation을 결합한 것이다.

먼저 parabolic interpolation을 시도하고 허용 가능한 결과가 얻어지는 한 계속 적용한다.

그렇지 않으면 golden-section search를 사용하여 문제를 파악한다.