[ML/DL 스터디] <Optimization - 1> Optimization, Convex Optimization

Reference

https://iai.postech.ac.kr/teaching/machine-learning
https://iai.postech.ac.kr/teaching/deep-learning
위 링크의 강의 내용에 기반하여 중요하거나 이해가 어려웠던 부분들을 정리하여 작성하였고,
모든 강의 슬라이드의 인용은 저작권자의 허가를 받았습니다.

또한, 모든 내용은 아래 Notion에서 더 편하게 확인하실 수 있습니다.
>>노션 링크<<

 

Key Point:

** 결국 Convex Optimization이 중요한 이유는, local한 minimum(optimal solution)이 global한 minimum이기 때문.

 

Optimization

Optimization 문제는 이러한 수학적 모델로 정의할 수 있음.

⇒ f(x)라는 objective function(목적 함수)를 최소화하는 x인 decision variable을 찾는 문제.
단, decision variable은 C라는 $g_i(x)\leq0$ constraint를 만족하는 x들의 feasible region(실현가능영역) 내에 존재해야 함.

(사진 내 마지막 줄에 의해 optimal solution 정의)

 

물론 min optimization 문제를 반대로 max optimization으로 바꿔도 동일.

 

Convex Optimization

Optimization 문제들 중 Convex Optimization 문제가 중요한 이유:

⇒ local solution이 global solution으로 치환될 수 있음. (한 지역적 해가 global한 해이다.)

이러한 Convex Optimization이 되기 위한 조건은,

• objective function이 convex function이며,
• Feasible region이 convex set이어야 함.

이 때 convex function과 convex set의 정의는 다음과 같음.

 

convex function이라는 것은, 함수 위의 임의의 두 점 x, y에서,

x, y를 선형 보간한 어떤 수의 함수값보다 ≤ (x, f(x)), (y, f(y))를 선형 보간한 점이 항상 커야 한다는 것.

⇒ 간단히 말하면, x, y 직선 사이의 어떤 점이든 함수 위에 존재해야 한다는 것.

 

convex set이라는 것은, set 내의 임의의 두 element를 택했을 때,

그 두 element를 선형보간한 결과 또한 set의 element로 포함되어야 한다는 것.

그림을 보면 쉽게 이해할 수 있을 것이다.

 

** 결국 Convex Optimization이 중요한 이유는, local한 minimum(optimal solution)이 global한 minimum이기 때문.