최적화

공학도를 위한 수치해석 : Steven C. Chapra, Raymond P. Canale 저, 김철.김태국.나양.신동신.이승배 공역, McGraw-Hill Korea, 2002 (원서 : Numerical Method for Engineers, 4th ed), Page 328~335

1. 동기부여

근 (Root) 구하기 와 최적화 (Optimization) 는 둘 다 함수 위의 한 점을 추측하거나 찾는다는 점에서 관련성이 있다. 두 방법의 근본적인 차이점은 그림 1 에서 찾아볼 수 있으며, 근 구하기는 함수 혹은 함수들의 근들을 구하는 반면 최적화는 최소값 혹은 최대값을 찾는 것이다.

그림 1  근과 최적점 사이의 차이점을 보여주는 단일변수의 함수.

최적점은 곡선의 평탄한 점으로, 수학적 용어로 나타내면 도합수 f'(x) 가 0 이 되는 점에 해당한다. 또한 2 차 도함수인 f''(x) 는 최적점이 최소값인지 최대값인지를 나타낸다. 만일 f''(x) 가 0 보다 작으면 최대값을, 그리고 0 보다 크면 최소값을 나타낸다.

근과 최적점 사이의 관계를 이해하면 최적점을 찾는 방법에 대한 전략을 세우는데 도움이 된다. 즉, 주어진 함수를 미분한 다음, 새로 구한 함수의 근을 구하는 것이다. 사실 몇 가지의 최적화 방법들은 f'(x) = 0 의 근을 구해서 최적점을 찾게 된다. f'(x) 가 손쉽게 구해지지 않는 경우 이러한 최적화 방법은 종종 복잡해지게 된다. 이러한 경우 도함수를 조사하기 위해 유한차분 근사법을 사용해야 한다.

최적화는 근 구하는 방법 이상으로 단순한 근 구하기가 아닌 다른 수학적 접근이 포함된다. 이러한 접근은 다차원의 최적화를 더욱 가능하게 한다.

1. 컴퓨터를 사용하지 않는 방법

앞서 언급한 바와 같이 미분을 이용한 방법은 최적해를 구하기 위해 지금도 사용되고 있으며, 공학계열 및 자연계열의 학생들은 수학 과목 시간에 함수의 1 차 도함수를 구하여 최대-최소 문제를 풀었던 것을 기억할 것이다. Bernoulli, Euler, Lagrange 및 그 외의 많은 수학자들은 함수값의 최소화를 다루는 변분수학의 기초를 만들었다. Largrange multiplier 방법은 변수들의 범위가 정해진 문제를 최적화하도록 개발되었다.

수치적 접근에서 최초의 중요한 진보는 제 2 차 세계대전 이후 디지털 컴퓨터의 개발로 가능해 졌다. 영국의 Koopmans 와 구소련의 Kantorovich 가 독립적으로 공급물자나 생산물의 최소비용 분배의 문제를 연구하였다. 1947 년 Koopmans 의 제자인 Dantzig 는 선형 프로그래밍인 Simplex 법을 개발하였으며, 이 방법은 Charnes 및 많은 연구자들에 의한 구속 최적화 문제의 기초가 되었다. 또한, 비구속 최적화 방법도 컴퓨터가 널리 보급되면서부터 급속도로 개발되어 왔다.

2. 최적화와 공학적 적용

지금까지 다루어 온 대부분의 공학적 모델들은 서술적 (descriptive) 모델이었다. 즉, 공학적 장치나 시스템의 거동을 모사하기 위해 유도된 모델이다. 반면에 최적화는 문제의 "최상의 결과", 혹은 최적해를 구하는 것을 다루는 일련의 과정, 혹은 가장 좋은 설계를 설정하게 되는 설정적 (prescriptive) 모델이라는 용어를 사용한다.

엔지니어들은 계속해서 효율적인 방법으로 임무를 수행하는 장치나 제품을 설계해야 한다. 그 과정 중에 실제 문제들에 의한 물리적 제약이 존재하게 된다. 또한 비용을 계속적으로 줄여야만 한다. 따라서, 성능과 제약조건 사이의 균형을 구하는 최적화 문제에 항상 부딪치게 된다.

일반적으로 부딪치는 예들을 표 1 에 예시하였다. 다음의 예제는 그러한 문제들을 수식화하는 방법에 대해 도와줄 것이다.

표 1  공학에서 최적화 문제의 적용 사례들.

..............

2. 수학적 기초지식

최적화 문제는 많은 수학적 개념과 연산들을 포함한다. 수학적 개념들과 관련된 연산들은 당분간 필요한 시점까지 미루기로 한다. 예를 들면, 중요한 수학적 개념인 구배 (gradient) 와 헤시안 (Hessian) 은 다차원 변분 비구속 최적화 문제를 다루는 제 13 장 후반부에서 설명한다. 여기서는 최적화 문제가 어떻게 분류되는지의 좀더 일반적인 주제를 살펴보기로 한다.

최적화 (optimiation) 혹은 수학적 프로그래밍 (mathematical programming) 문제는 일반적으로 다음과 같이 표현된다.

f(x) 를 최소화 혹은 최대화하며 다음의 조건을 만족하는 변수 x 를 구한다.

d_i(x) ≤ a_i    i = 1, 2, ..., m                        (1)

e_i(x) = b_i     i = 1, 2, ..., p                         (2)

여기서 x 는 n 차원의 설계 벡터이고, f(x) 는 목적함수이며, d_i(x) 는 부등식 구속조건, e_i(x) 는 등식 구속조건, 그리고 a_i 와 b_i 는 상수들이다.

최적화 문제들은 f(x) 의 형태에 따라 다음과 같이 분류된다.

• f(x) 와 구속조건이 선형적이면, 선형 프로그래밍 문제이다.
• f(x) 가 2 차 함수이고 구속조건이 선형적이면, 2 차 프로그래밍 문제이다.
• f(x) 가 선형도 2 차 함수도 아니거나, 혹은 구속조건이 비선형이면 비선형 프로그래밍 문제이다.

또한 식 1 과 식 2 가 포함되면 구속 최적화 문제이며, 그렇지 않으면 비구속 최적화 문제이다.

구속적 문제의 경우 자유도는 n-p 로 주어진다. 일반적으로 해를 얻기 위해서는 p 가 n 보다 작거나 같아야 한다. 만일 p 가 n 보다 크면, 과구속 (overconstrained) 문제가 된다.

그림 1  (a) 1 차원 최적화. 이 그림은 f(x) 의 최소화가 -f(x) 의 최대화와 같음을 보여준다.
(b) 2 차원 최적화. 이 그림은 최대값 (함수의 등고선값이 산처럼 정상에서 최대값) 혹은 최소값 (함수의 등고선값이 계곡처럼 최소값) 을 나타낸다.

최적화 문제를 분류하는 또 다른 방법은 차원에 따른 분류이다. 이 방법은 종종 1 차원 문제와 다차원 문제로 분류한다. 말 그대로 1 차원 문제는 함수가 한개의 종속변수에 의존하는 경우다. 그림 1a 에서처럼 이 탐색은 1 차원의 정상들과 계곡들을 오르내리게 된다. 다차원 문제는 두 개, 혹은 그 이상의 종속변수들에 의존하는 함수들을 포함한다. 2 차원 최적화도 정상들과 계곡들을 탐색하는 것으로 표현되나, 실제 등산하는 것처럼 한 방향으로만 걸어가도록 구속되지 않고, 목적지에 효과적으로 도달하기 위해 지형을 탐사하게 된다 (그림 1b).

마지막으로 최소값을 찾는 과정은 최대값을 찾는 과정과 동일하다 왜냐하면, f(x) 를 최소화하는 x^*값은 -f(x) 를 최대화하기 때문이다. 이러한 동등성은 그림 1a 의 1 차원 함수에 그래프로 표현된다.

3. 소개

..............