최적화 - 1.1.1 일변수 함수의 비제약 최적화

 

이번 연재에서는 John Gregory와 Cantian Lin 저 <Constrained Optimization in the Calculus of Variations and Optimal Control Theory>를 정리해 나가면서, 제약된 최적화 관련 내용을 복습하고 학습해나갈 것이다.

필자는 경제수학 수준과 대학 미적분학 수준의 제약 최적화 내용만 알기 때문에, 새로운 내용을 배울 것이라 기대하면서 연재를 시작한다. 또한 필자의 배경지식이 빈약하므로 연습문제 풀이 등에서 오류가 많을 예정인데, 댓글 등으로 적극적인 지적이 있기를 기대한다...

 

 

 

1.1 비제약 최적화

일반적으로 최적화 문제는 정의역이 n차원 실수공간의 부분집합이고 값이 실수인 어떤 함수의 극대/극솟값을 구하는 형태로 나타난다. 여기서 여러 아종이 파생되는데, 예컨대 정의역이 볼록집합인 경우, 정의역이 특정한 조건을 만족하도록 제약되는 경우 등이 있겠다. 이러한 상황에서 문제를 푸는 수치, 해석적 방법을 살펴보는 것이 이 책의 목적이다.

 

허나 이러한 문제를 풀기 전에, n차원 실수공간 전체에서 정의역을 가지고 실수값을 가지는 함수의 극솟값과 극댓값을 구하는 문제를 먼저 살펴본다.

 

정의 1.1

 

함수

$f: D \subset \mathbb{R} ^{n} \rightarrow \mathbb{R} $

가 $f \in C^{3}(D)$ 를 만족한다 하자. 즉, f는 연속인 삼계도함수를 가진다.

 

또한 $x_{0}$가 D의 내부점이고, 다음이 성립한다 하자:

$\exists \delta >0, s.t. x\in N(\delta ,x_{0}) := \{x : ||x-x_{0}|| < \delta \} \Rightarrow f(x_{0}) \leq f(x) $

 

이제 $x_{0} \in D$를 함수 f의 극소점이라 한다. 특히, $x \in N(\delta , x_{0}) , x\neq x_{0} \Rightarrow f(x_{0}) < f(x)$가 성립하면 $x_{0} \in D$를 f의 단조 극소점이라 한다.

 

또한, $x\in D$가 함수 g:= -f 의 극소점이라면 x는 g의 극대점이라 하고, 단조 극대점 또한 동일한 방식으로 정의한다.

 

 

우선은 n=1인 경우, 즉 f가 실함수인 경우를 살펴보자.

$C^3$급 실함수의 어떤 점이 극소점/ 극대점이 되기 위한 필요조건과 충분조건을 살펴보기 위하여 다음의 정리를 이용한다:

 

 

보조정리 (테일러 정리).

열린 구간에서 정의된 함수

$f:\left(a,b\right)\rightarrow \mathbb{R}$​

가 n번 미분가능하다 하고, x는 열린구간 (a,b)에 속한다 하자.

이제 $x+\epsilon$가 (a,b)에 속하도록 하는 모든 $\epsilon >0$에 대해서, 다음이 성립한다:

$\exists \xi \in \left(x,x+\epsilon \right),\ f\left(x+\epsilon \right)=\Sigma _{i=0}^{n-1}\ \frac{f^i\left(x\right)}{i!}\epsilon ^i+\frac{f^n\left(\xi \right)}{n!}\epsilon ^n$​

이 정리에 대한 증명은 생략한다. 

 

 

그리스 문자가 매우 많아서 처음 보는 사람은 두려움에 떨 가능성이 크다 (필자도 그랬다). 조금 풀어서 설명을 하자면, 이 정리는 다음을 말한다:

 

(i) x에서 $\epsilon$ (엡실론) 만큼 옆으로 간 함숫값은, $\epsilon$의 n차 다항식으로 주어질 수 있다. (예컨대 엡실론을 입력으로 받아들이는 지수함수나 사인함수로도 주어질 수 있는데, 다항식으로 주어지며, 다른 차수가 아니라 f가 미분가능한 횟수의 차수를 차수로 가지는 다항식이다)

 

(ii) 이 다항식의 계수들은, n-1차 까지는 x에서 i계 미분계수 / i!으로 주어지고, n차에서는 x와 $x+\epsilon$ 사이 어떤 $\xi$ (크사이) 에 대하여 크사이에서 n계 미분계수 / n!으로 주어진다.

 

(iii) 이 이야기를 종합하면,

 

$f(x+\epsilon)-\Sigma _{i=0}^{n-1} \frac{f^i(x)}{i!}\epsilon^i =\frac{f^n(\xi)}{n!}\epsilon^{n}$​

즉, $f(x+\epsilon)$와 계수가 잘 주어진 n-1차 다항식의 차는 $e^n$에 의존하는 항이 된다는 의미이고,

다른 말로 $\epsilon$이 0으로 접근하면 $f(x+\epsilon)$와 다항식의 오차는 $e^n$의 속도로 0에 수렴한다는 의미이다.

또 다른 말로 이야기하면, f(x) 근처의 값은 n-1차 다항식으로 잘 근사된다는 의미이다. 이러한 성질은 f의 n번 미분가능함에 의존한다.

 

 

이 문제에서는 f가 세 번 미분가능하므로, 테일러 정리에 의해 f(x+e)를 다음과 같이 표현할 수 있다:

$f\left(x+\epsilon \right)=f\left(x\right)+\epsilon f'\left(x\right)+\frac{1}{2}\epsilon ^2f''\left(x\right)+\frac{1}{6}\epsilon ^{3\ }f'''\left(\xi \right),\ \ \xi \in \left(x,x+\epsilon \right)$​

 

그런데 f는 그냥 세 번 미분 가능한 것이 아니라 삼계도함수가 연속이다. 따라서 삼계미분계수의 절댓값은 주어진 $\epsilon$에서 유계일 것이고 그 상한은 $\epsilon$이 작아질수록 같이 작아질 것이다. 

$\left|{f\left(x+\epsilon \right)-\left\{f\left(x\right)+\epsilon f'\left(x\right)+\frac{1}{2}\epsilon ^2f''\left(x\right)\right\}}\right|\le \frac{1}{6}k_{\epsilon }\epsilon ^{3\ }$​

 

 

$\epsilon$를 작게 하면 할수록 $k_{\epsilon}$는 작아질 것이므로, 충분히 작은 $\epsilon$에 대해서 $k_\epsilon < K$인 K가 존재할 것이다.

이를 표기하는 방법으로

${f\left(x+\epsilon \right)-\left\{f\left(x\right)+\epsilon f'\left(x\right)+\frac{1}{2}\epsilon ^2f''\left(x\right)\right\}=O\left(\epsilon ^3\right)}$​

이라고 표기한다.

 

 

 

이 테일러 근사로부터 다음의 결과들이 바로 얻어진다:

 

정리 1.1

f가 $x_{0}$에서 극소점을 가지기 위한 필요조건은

$\left(i\right)\ f'\left(x_{0}\right)=0$​

$\left(ii\right)\ f''\left(x_{0}\right)\ge 0$

 

증명.

실수의 삼분법에 의하여 $f'(x_{0}) > 0 , f'(x_{0}) < 0 , f'(x_{0}) = 0$ 셋 중 하나만이 성립한다.

이제 만약 $f'(x_{0}) > 0$이라 가정하자. 테일러 전개에 의하여

$\frac{f(x_{0}+\epsilon) - f(x_{0})}{\epsilon} = f'(x_{0}) + \frac{1}{2} \epsilon f''(x_{0}) + \frac{O(\epsilon ^3)}{\epsilon}$

마지막 두 항은 $\epsilon \rightarrow 0$에 따라 0으로 수렴하는 반면, $f'(x_{0})$은 상수이므로, 충분히 작은 모든 $\epsilon>0$에 대하여 우변이 0보다 커야 하고 따라서 좌변도 0보다 커야 한다.

 

그러나 이는 $f(x_{0}+\epsilon) > f(x_{0})$을 의미하므로 f가 $x_{0}$에서 극소점을 가지지 않는다.

 

마찬가지의 논리로 $f'(x_{0}) < 0$이라 가정하면, 테일러 전개와 위와 유사한 논의에 의해 절댓값이 충분히 작은 $\epsilon < 0$에 대하여 $f(x_{0}+\epsilon) > f(x_{0})$를 의미하고, 따라서 f가 $x_{0}$ 에서 극소점을 가지지 않는다.

 

이제 (i)은 성립하지만 (ii)가 성립하지 않는다 하자; 즉 $f''(x_{0}) <0$이라 가정하자.

 

테일러 전개를 다시 하면

$\frac{f(x_{0}+\epsilon) - f(x_{0})}{\epsilon}$

$= \frac{1}{2} \epsilon f''(x_{0}) + \frac{O(\epsilon^3)}{\epsilon}$

 

따라서

 

$\frac{f(x_{0}+\epsilon) - f(x_{0})}{\epsilon^2}$

 

$=\frac{1}{2} f''(x_{0}) + \frac{O(\epsilon^3)}{\epsilon^2}$

 

 

이제 두번째 항은 $\epsilon \rightarrow 0$에 따라 0으로 수렴하는 반면 $f''(x_{0})$는 음수이므로, 충분히 작은 모든 $\epsilon >0$에 대하여 우변이 음수이고 좌변도 음수이다.

그런데 이는 충분히 작은 모든 $\epsilon >0$에 대해

$f(x_{0} +\epsilon ) - f(x_{0}) < 0$임을 의미하므로, f는 $x_{0}$서 극솟값을 가질 수 없다. $\square$

 

 

정리 1.2 

f가 $x_{0}$에서 단조 극소점을 가지기 위한 충분조건은

$\left(i\right)\ f'\left(x_{0}\right)=0$​

$\left(ii\right)\ f''\left(x_{0}\right) > 0$

 

증명.

 

다시 테일러 전개를 사용하면 (i)에 의해

$\frac{f(x_{0}+\epsilon) - f(x_{0})}{\epsilon^2}$

$=\frac{1}{2} f''(x_{0}) + \frac{O(\epsilon^3)}{\epsilon^2}$

 

 

이제 두번째 항은 $\epsilon \rightarrow 0$에 따라 0으로 수렴하는 반면 $f''(x_{0})$는 양수이므로, 충분히 작은 모든 $|{\epsilon}| >0$에 대하여 우변이 양수이고 좌변도 양수이다.

따라서 그러한 모든 $\epsilon$에 대해서 어떤 양수 K가 존재하여,

$f(x_{0} +\epsilon) - f(x_{0}) > K*\epsilon^2 > 0$

따라서

$\exists \delta >0, x_0 - \delta < x < x_0 + \delta \Rightarrow f(x) \geq f(x_{0}), x\neq x_0 \Rightarrow f(x) > f(x_{0})$. $\square$

 

 

마지막으로 예제로 마무리짓고자 한다.

 

문제 1.1 

$f(x) = 2x^{2} - 12x + 25$라 하자.

a. $x_0 = 3$이 정리 1.2의 충분조건들을 만족함을 보이시오.

b. $x_0 = 3$에서 f가 전역적 최솟값을 가짐을 보이시오.

 

풀이.

f는 다항함수이므로 전역적으로 무한번 미분 가능함을 상기하자. 따라서 정리 1.2를 적용할 때 미분 가능성에 따른 제약이 없다.

a. $f(x_0) = 7, f'(x_0) = 0, f''(x_0) = 4$이며 이는 정리 1.2의 충분조건들을 만족함을 확인할 수 있다.

 

b. f를 $x_0 =3$에서 테일러 전개를 하면 모든 $\epsilon>0$에 대하여

$f(x_0 + \epsilon) = f(x_0) + \epsilon f'(x_0) + \frac{1}{2} \epsilon^2 f''(x_0) + O(\epsilon^3)$

 

그런데 f의 2차 테일러 근사다항식

$7 + 2\epsilon^2$은 $f(3 + \epsilon)$과 같음을 (직접 대입으로) 확인할 수 있다.

 

따라서 $f(3+\epsilon) = f(3)+2\epsilon^2 \geq f(3) $임을 확인할 수 있고, f는 x=3에서 전역적 최솟값을 가진다.

 

 

다음 글에서는 다변수 함수의 비제약 최적화를 다룰 예정이다.