최적화와 볼록최적화(Optimization and Convex Optimization)

최적화 기본 요소

1. 목적함수 (Object function) 무엇을 최소화, 최대화 하는가?

2. 변수 (decision variable or unknown) 목적함수를 최소화하는 변수를 찾는것.

3. 제약 조건 (Constraints) 

 

최적화 과정 

1. 주어진 문제. 문제에서 목적함수가 무엇인지, 결정변수가 무엇인지, 제약조건이 무엇인지를 identify하는 것 = 모델링

2. 모델링 끝이 나면, 최적화 해를 찾는다. 다양한 옵티마이제이션 알고리즘을 사용함.

 

최적화 수학 모델

$ \min f(x) $ 

$ subject\,\,to\,\, g_{i}(x) \leq 0, \, i=1,2, ... , m $  (제약조건이 1개일 수도.. m개 일수도 있다)

최적화에서는 수학적 표준 모델이라 한다. 

 

x는 decision variable이다. n개면 벡터로 나타낸다. n차원의 칼럼의 형태이다.

x를 input으로 하는 함수가 있다. 이 함수는 objective function이라 하고. 이 function을 최소화하는 것으로 귀결이 된다.

 

x가 아무값을 가질 수 있지만 contraint가 있으면 feasible region이라 하고, 부등식의 형태로 이것을 만족하는 집합 내에서 최소화하는 x를 찾는 것.

 

솔루션은 $ x^{*} $ 옵티멀 솔루션이라 한다.

 

 

 

최대화 할 경우 등가변환

 

표준 모델 만드는 이유?

 

모델링하고

모델링한 것 최적화 어떻게 푸느냐 하는 문제

 

표준화된 모양으로 바꿀 수 있으면...

표준화된 문제에 대한 해법만을 고민하면 된다.

 

 

최적화 종류

 

제약조건이 없는 최적화 문제 vs 제약 조건이 있는 최적화 문제

 

 

또 다른 최적화의 종류가 볼록 최적화(Convex Optimization)이다. 

 

objective function이 convex function이고,

feasible region C가 convex set일 때... 2가지 조건이 있을 때 Convex Optimization이라 부른다.

 

Convex Optimization이 왜 좋으냐?

local한 솔루션이 global한 솔루션이 되기 때문이다.

 

만약 최적화의 문제가 Convex Optimization의 문제이면 해를 찾는데 있어서

직접 계산하지 않고 Convex Optimization Solver인 CVX(CVXPY)를 사용할 수 있다.

머신러닝 문제에서 데이터를 해석 할 때, 최적화의 관점에서 문제를 바라볼 것.

많은 경우에 해당 문제가 Convex Optimization으로 모델링이 가능함.

 

Convex가 되었다면 CVXPY를 사용하여 Approximate된 solution을 찾을 것.

 

 

 

 

Convex function에 대해 설명하기 전에...

 

두 점이 주어졌을 때 linear interpolation을 어떻게 하는지 알아보자 (선형보간법)

원점이라고 가정하면...

$ \vec {z} $가 가르키고 있는 점을 추정하려면...

 

x,y의 점이 주어졌다고 하면,

그 점 사이의 데이터 포인트를 추정하자.

 

 

$ \vec {z} = \vec {y} + \theta ( \vec {x} - \vec {y}) $

 

세타는 알파

1-세타는 베타

 

알파 + 베타는 둘다 양수이고 

알파 + 베타 = 1 일 때.

 

이러한 수식을 기하학적 의미가 있는 능력이 있어야함.

 

이걸 설명하는 이유는 다음과 같다.

 

Convex function은 볼록함수이다.

 

두 점 사이에 linear inpolation한 점 (C)

 

아래점 (B)

 

Convex하다는 게 수학적으로 정의를 하면

B점이 C점보다 작다 모든 점에서~

 

 

 

https://www.youtube.com/watch?v=QJSSWNIAPlw