[설계 최적화 이론] Gradient Method - Steepest Descent Method, Conjugate Gradient Method
이번 포스팅은 최적화문제(Optimization Problem)의 Unconstrained Optimization method 중에서도 Gradient method의 다섯 가지 method에 대해 하나씩 공부해보겠습니다.
잠깐 다시 짚어보자면, 최적해를 찾기 위한 방법은 Starting point부터 점차적으로 최적해를 찾아가도록 수많은 iteration을 통해 point를 improve해 나가는 Direct한 방법과 소위 최적조건(Optimality Condition)을 만족하는 어떠한 방정식을 풀어나가는 Indirect한 방법이 있습니다. Indirect한 방법은 iteration이나 starting point가 필요없고, 최적해를 만족하는 조건이 방정식으로 정의될 수 있어야 합니다.
자, 그럼 본격적으로 공부해보겠습니다.
1. Steepest Descent Method
방법은 간단합니다.
Step 1. 목적함수(f)의 음의 미분 값으로 탐색 방향을 설정합니다.
Step 2. 최적해까지 iteration을 반복하면서 point를 업데이트해 나갑니다.
iteration을 무한히 반복할 수 없기 때문에, stop 조건을 정의해줍니다.
너무 쉽죠?
미지수가 하나일 때에도 두 개 이상일 때에도 동일합니다.
2. Conjugate Gradient Method
이 방법은 1번 Steepest descent method를 살짝 좋아진 방법으로, 이전의 iteration에서 사용된 scaled direction을 더해줌으로써 수렴률(Convergence rate)을 개선시켰습니다.
처음은 똑같습니다.
Step 1. 목적함수(f)의 음의 미분 값으로 탐색 방향을 설정합니다.
Step 2. 최적해까지 iteration을 반복하면서 point를 업데이트해 나갑니다.
Step 3. 새로운 탐색 방향을 계산해줍니다.
Step 4. iteration에서 사용되는 step size를 계산합니다.
Step 5. design point를 업데이트 해줍니다. 그리고 다시 Step 2로 돌아갑니다.
예제로 풀어볼까요?
목적함수와 starting point(여기서는 0,0으로 하겠습니다) 를 정의합니다.
첫 번째 iteration입니다. x_1 point를 찾아보겠습니다.
두 번째 iteration입니다. x_2 point를 찾아보겠습니다.
두 번의 iteration으로 최적해를 찾을 수 있었습니다. 이미지로 보면 아래와 같습니다.
첫 번째로 Gradient method의 다섯가지 방법론 중에서 가장 간단한 Steepest Descent Method와 Conjugate Gradient Method에 대해 알아보았습니다. 다음 포스팅은 Gradient method의 남은 방법론에 대해 공부해보겠습니다.