Optimization

Optimzation은 4개의 기준으로 나눌 수 있다.

1. Continuous / Discrete

2. Unconstrained / Constrained

3. None, One or Many objective functions

4. Deterministic / Stochastic

 

나머지 이름은 objective function의 형태에 따라 결정된다.

Linear, Quadratic, Nonlinear 등등.

 

최적해를 찾는 과정에서 local minima에 빠지는 경우가 생길 수 있다.

그러나 objective function이 convex하다면 local minimum이 global minimum이 되어 이 문제를 해결할 수 있다.

함수가 convex한 지 확인하기 위해서는 아래 식을 활용하면 된다.

 

 

그래프로 최적화를 생각해보면 gradient descent method와 같은 방법을 생각할 수 있다.

 

 

Objective fuction과 함께 contraints가 제시되는 경우도 있다.

만약 x가 모든 constraints를 만족하면 x가 feasible하다고 한다.

모든 optimal solution은 feasible 하지만, feasible solution이 optimal 하지는 않다는 점을 주의하자.

 

 

Linear programing의 경우에는 아래와 같은 형태로 제시된다.

이 때 objective function과 모든 constraints는 모두 x에 대한 linear function이며, LP 문제는 모두 convex 이다.

Constraints에 의해 아래와 같은 feasible region이 나올 경우, 이 feasible polygon region의 꼭지점에 optima가 있다.

 

 

Quadratic programming(QP)는 다음과 같은 형태를 취할 수 있다.

 

 

Linear Least Sqaures 같은 경우는 아래와 같은 objective fuction을 갖는다.

이 때 A가 full rank이냐, 아니냐에 따라 풀이 방법이 달라진다.

 

A가 full rank인 경우는 다음의 풀이를 따른다.

기본 풀이는 같으나 full rank가 아닌 경우는 마지막 부분에서 차이가 생긴다.

 

 

Unconstrained Nonlinear Least Squares의 경우에는 자코비안을 사용해서 선형화를 한다고 생각하면 된다.

f(x)가 objective functoin일 때 다음과 같이 생각할 수 있다.