본문 바로가기
AI 수학/최적화

함수의 최소화 또는 최대화의 조건

by 깊은대학 2020. 10. 20.

다음과 같이 제약조건이 없는 일반적인 최적화 문제가 있다.

 

minxf(x)        maxxf(x)

 

여기서 xRn은 최적화 변수이고, f(x)은 목적함수(objective function)이다. 이 목적함수를 최소화 또는 최대화하기 위한 조건은 무엇일까.

 

 

x의 독립적 변화에 의해 유도된 함수 f(x)의 변화량을 계산해 보자. x의 변화량을 Δx라고 하면, 함수의 증분(increment) Δf는 다음 식으로 주어진다.

 

Δf=f(x+Δx)f(x)

 

변화량이 매우 작을 때, 즉 Δx0일 때는 미분(differential) dx로 표기하고 함수의 증분도 미분 df로 표기한다. 미분 df와 미분 dx의 비율 dfdx를 도함수(derivative)라고 한다 (흔히 이것도 미분이라고 번역한다).

다음 그림은 최적화 변수가 스칼라일때의 함수의 증분과 미분 사이의 관계를 보여준다. 증분 Δfx의 변화량이 dx=Δx일 때 함수 f(x)의 변화량인 반면 dfx점에서 계산한 접선(도함수)을 따라 생긴 변화량을 나타낸다. 즉 df=dfdxdx이다. 그래서 미분 df를 1차(first-order) 증분 또는 선형 증분이라고 한다.

 

 

다음 그림은 최적화 변수가 2차원 벡터 x=[x1x2]T일 때의 함수의 증분과 미분 사이의 관계를 보여준다. 증분 Δfx1x2의 변화량이 각각 dx1=Δx1dx2=Δx2일 때 함수 f(x)의 변화량인 반면, dfx1x2점에서 계산한 접면(도함수)을 따라 생긴 변화량을 나타낸다. 즉

 

df=fx1dx1+fx2dx2

 

 

함수의 변수가 일반적인 n-차원 벡터 x일 때의 함수의 미분 df는 다음과 같이 계산된다.

 

df=fx1dx1+fx2dx2++fxndxn=(dfdx)Tdx

 

 

만약 x을 기준으로 xx<ϵ을 만족하는 모든 x에 대해서 Δf=f(x)f(x)0인 어떤 값 ϵ>0가 존재한다면, f(x)를 로컬 최소값이라고 하고, Δf=f(x)f(x)0이라면 f(x)를 로컬 최대값이라고 한다. 만약 ϵ값을 임의의 큰 값으로 정할 수 있다면 각각 글로벌 최소값, 글로벌 최대값이라고 한다. 그리고 이 때의 x를 정류점(stationary point) 또는 극점(extremal point)이라고 한다.

 

 

정류점에서는 함수의 미분이 0이 된다. 즉. df(x)=0 이다. 이 말은 어떤 함수가 어떤 값 x에서 (로컬) 최소값 또는 최대값을 갖는다면 그 값이 바로 정류점이고 그 때 함수의 미분은 0이라는 뜻이다. 즉, 함수 f(x)가 (로컬) 최소값 또는 최대값을 갖기 위한 필요조건은 다음과 같다.

 

df(x)=0

 

증명해 보자.
먼저 함수가 x에서 로컬 최소값을 갖는다면, x=x+αdx 일 때 함수의 미분은 다음 식을 만족해야 한다.

 

df(x)=f(x+αdx)f(x)=α(dfdx)xTdx0

 

여기서 α>0이고 ]|αdx0 이며, (dfdx)xx=x에서 계산한 x에 대한 f의 그래디언트(gradient)이다. 또한 함수가 x에서 로컬 최소값을 갖는다면, x=xαdx 일 때도 다음 식을 만족해야 한다.

 

df(x)=f(xαdx)f(x)=α(dfdx)xTdx0

 

위 두 식에 의하면 동시에 (dfdx)xTdx0(dfdx)xTdx0을 만족해야 하므로, 함수가 x에서 로컬 최소값을 갖는다면 (dfdx)xTdx=0 또는 df(x)=0이 되야 한다.
동일한 방법을 사용하면 함수가 x에서 로컬 최대값을 갖을 때에도 df(x)=0이 돼야 함을 증명할 수 있다.

정리하면, 함수 f(x)x에서 (로컬) 최소값 또는 최대값을 갖기 위한 필요조건은 다음과 같다.

 

df=(dfdx)Tdx=fx1dx1+fx2dx2++fxndxn=0

 

만약 x의 성분이 모두 독립이라면, stationary point x는 다음 식으로 계산할 수 있다.

 

fxi=0,    i=1,2,...,n

 

 

 

 

'AI 수학 > 최적화' 카테고리의 다른 글

최소화의 필요조건과 충분조건  (0) 2021.01.10
SGD에서 데이터를 무작위로 추출해야 하는 이유  (1) 2021.01.04
라그랑지 곱수법의 증명  (0) 2020.10.01
라그랑지 곱수법  (0) 2020.10.01
경사하강법  (0) 2020.09.30

댓글