최적화 문제관련 용어

5050·2021년 9월 10일
0

최적화

목록 보기
1/1

최적화 문제

보통 f(x)f(x)를 최소화하는 문제로 주어지며, 제약조건이 주어진다. (h(x)=0,g(x)<=0h(x) = 0, g(x) <= 0와 같은)
최소화하는 함수를 보통 objective function이라고 한다.
제약조건을 만족하는 xxfeasible solutions라고 하며 이 xx들을 모아놓은 집합을 feasible set이라고 한다.
feasible set 중에서 f(x)f(x)를 최소화하는 해를 optimal solution이라고 한다.
optimal solution = argminxf(x)argmin_x f(x)

Local minimum

어떤 값 주변에서 함수를 가장 작게 만드는 점이 극솟점 (즉, 꼭 미분이 0이 아니어도 된다. 하지만 미분 가능한 지점이라면 미분의 값은 0이 될 것이다.)
극솟값 중 제일 작은 것을 global minimum이라고 한다. (즉, 전역에서 가장 작은값)

Local maximum

이와 반대로 주변에서 함수를 가장 크게 만드는 점이 극댓값, 극댓값 중 제일 큰 것을 global maximum이라고 한다.

Convex Optimization Problem

f(x)f(x)가 convex고 feasible set이 convex한 것을 convex optimization problem이라고 한다.
(Convex란 볼록한 것을 말한다.)
feasible set이 convex하다는 것을 수식으로 나타낸다면,
x1,x2Sx_1,x_2∈S 일때, αx1+(1α)x2S,α[0,1]αx_1+(1- α) x_2 ∈S ,α∈[0,1]을 만족할 때 convex set이라고 한다.

f(x)f(x)가 convex하다는 것을 수식으로 나타낸다면
x1,x2X(정의역)x_1,x_2 ∈X(정의역), α[0,1]α ∈[0,1]일 때,
f(αx1+(1α)x2)αf(x1)+(1α)f(x2)f(αx_1+(1- α) x_2 ) ≤ αf(x_1 )+(1-α)f(x_2 )을 만족할 때 f(x)f(x) 는 convex하다고 한다.

미분가능할 때는 f’’(x)>=0f’’(x) >= 0 이라면 convex function이다.
하지만, 독립변수가 다변수일 때에는 Hessian Matrix가 Positive semidefinite를 만족한다면 convex function이다.

Convex Optimization Problem이라면 Local minima = global minima인 이유

xx^* 가 local minimum이라고 하고 f(x)<f(x)f(x' ) < f(x^* )xx' 가 존재한다고 가정하자
x,xfeasiblesetx',x^* ∈ feasible\,set 이므로 αx+(1α)xfeasiblesetαx^*+(1- α) x'∈feasible\,set일 것이다.
또한,
f(αx+(1α)x)αf(x)+(1α)f(x)f(αx^*+(1- α) x' )≤αf(x^* )+(1- α)f(x' ) 를 만족해야 한다. (Convex Optimization Problem이므로)

αf(x)+(1α)f(x)=αf(x)+(1α)f(x)+f(x)f(x)αf(x^* )+(1-α)f(x')= αf(x^* )+(1-α)f(x' )+f(x^* )-f(x^* )
=(1α)(f(x)f(x))+f(x)=(1- α)(f(x')-f(x^* ))+f(x^* )
(1α)(f(x)f(x))(1- α)(f(x' )-f(x^* )) 은 0보다 작기 때문에 우변은 f(x)f(x^* )보다는 작게 된다.

f(αx+(1α)x)<f(x)f(αx^*+(1- α) x' ) <f(x^* )를 만족해야 하는데
limα1f(αx+(1α)x)<limα1f(x)lim_{α→1}⁡f(αx^*+(1- α) x' )< lim_{α→1}⁡f(x^*)
xx^* 는 local minimum이라고 정의했기 때문에 모순이 된다.
f(x)<f(x)f(x' )<f(x^* )를 만족하는 xx' 가 있다는 전제가 모순이 되므로 local minimum보다 작은 x'는 없기 때문에
local minimum = global minimum이 된다.

참고 내용 : https://www.youtube.com/watch?v=E-INcQ4rRVk&ab_channel=%ED%98%81%ED%8E%9C%ED%95%98%EC%9E%84

이미지 참조 : https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=sw4r&logNo=221495616715

profile
하이

0개의 댓글