최적화 문제
보통 f(x)를 최소화하는 문제로 주어지며, 제약조건이 주어진다. (h(x)=0,g(x)<=0와 같은)
최소화하는 함수를 보통 objective function이라고 한다.
제약조건을 만족하는 x를 feasible solutions라고 하며 이 x들을 모아놓은 집합을 feasible set이라고 한다.
feasible set 중에서 f(x)를 최소화하는 해를 optimal solution이라고 한다.
optimal solution = argminxf(x)
Local minimum
어떤 값 주변에서 함수를 가장 작게 만드는 점이 극솟점 (즉, 꼭 미분이 0이 아니어도 된다. 하지만 미분 가능한 지점이라면 미분의 값은 0이 될 것이다.)
극솟값 중 제일 작은 것을 global minimum이라고 한다. (즉, 전역에서 가장 작은값)
Local maximum
이와 반대로 주변에서 함수를 가장 크게 만드는 점이 극댓값, 극댓값 중 제일 큰 것을 global maximum이라고 한다.
Convex Optimization Problem
f(x)가 convex고 feasible set이 convex한 것을 convex optimization problem이라고 한다.
(Convex란 볼록한 것을 말한다.)
feasible set이 convex하다는 것을 수식으로 나타낸다면,
x1,x2∈S 일때, αx1+(1−α)x2∈S,α∈[0,1]을 만족할 때 convex set이라고 한다.
f(x)가 convex하다는 것을 수식으로 나타낸다면
x1,x2∈X(정의역), α∈[0,1]일 때,
f(αx1+(1−α)x2)≤αf(x1)+(1−α)f(x2)을 만족할 때 f(x) 는 convex하다고 한다.
미분가능할 때는 f’’(x)>=0 이라면 convex function이다.
하지만, 독립변수가 다변수일 때에는 Hessian Matrix가 Positive semidefinite를 만족한다면 convex function이다.
Convex Optimization Problem이라면 Local minima = global minima인 이유
x∗ 가 local minimum이라고 하고 f(x′)<f(x∗)인 x′ 가 존재한다고 가정하자
x′,x∗∈feasibleset 이므로 αx∗+(1−α)x′∈feasibleset일 것이다.
또한,
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∗)
=(1−α)(f(x′)−f(x∗))+f(x∗)
(1−α)(f(x′)−f(x∗)) 은 0보다 작기 때문에 우변은 f(x∗)보다는 작게 된다.
f(αx∗+(1−α)x′)<f(x∗)를 만족해야 하는데
limα→1f(αx∗+(1−α)x′)<limα→1f(x∗)
x∗ 는 local minimum이라고 정의했기 때문에 모순이 된다.
f(x′)<f(x∗)를 만족하는 x′ 가 있다는 전제가 모순이 되므로 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