(선형대수학) 부록 2-1. Beginning of Optimization Problem

***** 추가적으로 "최적화 문제"에 대한 카테고리를 만들 예정입니다!!!

 

지금부턴 우리가 배웠던 내용들을 이용해서 최적화 문제(Optimization Problem)의 기본적인 내용들을 생각해보자.

 

먼저, 최적화 문제(Optimization Problem)이 무엇인지 알아보자.

 

ex) 재료 A와 B를 이용해서 제품 1과 2를 만들 수 있다고 하자.

다음은 각각 제품 1, 2 1kg를 만들기 위해서 필요한 재료 A, B의 무게를 나타낸 것이다. 

	재료 A	재료 B
제품 1	5	1
제품 2	1	6

 

재료 A의 재고는 100kg, B의 재고는 60kg 남아있다고 하자.

그리고 제품 1을 1kg를 팔면 5만원, 제품 2를 1kg를 팔면 8만원을 벌 수 있다고 하자.

그러면, 가장 수익을 많이 내기 위해서는 각각 제품 1,2를 몇 kg씩 만들면 될까???

 

(풀이)

1. 제품 1을 x kg을 만들고, 제품 2를 y kg를 만든다고 하자.

2. 수익 : J=5x+8y (만원)

3. 조건: 5x+y<=100, x+6y<=60

4. 조건2: x>=0, y>=0

이 때, 3,4번은 다음과 같은 영역 S로 나타낼 수 있다.

즉, S 안에서 J의 최댓값을 찾고, 이 때의 x,y를 찾으면 된다!!

미분에 찌들어있다면 이마저도 미분하고 싶을 수 있겠지만, 사실 이 문제는 그냥 좌표평면에 그림을 그려보면 어디가 최댓값으로 나올지 바로 감이 잡힌다!! => 좌표평면에 그려보면 알겠지만 S가 이루는 도형의 꼭짓점에서 최댓값을 가진다! -> 아래 사각형의 오른쪽 위 꼭짓점에서 최댓값을 가진다!

-> 5x+y=100, x+6y=60의 교점이 x=540/29, y=200/29이므로

-> 제품 1을 540/29kg, 제품 2를 200/29kg을 만들 때, 최댓값 4300/29만원을 벌 수 있다!

 

(NOTE)

조금 더 들어가보면 영역 S가 Closed Set인 경우

1.

인 S의 점 (x,y)에서 극값을 가진다!

혹은,

2. S의 Boundary에서 극값을 가지게 된다!!

(설명 -> Closed set과 연속함수에 대한 내용을 보고 와야 이해가 갑니다!)

S의 점 P에서 최댓값(혹은 최솟값) -> 극값 을 가진다고 하자.

1. P가 S의 Boundary가 아닌 경우

P는 S의 Interior Point이기 때문에, P를 중심으로 S에 포함되는 아주 작은 Open Ball을 잡을 수 있다. 이 경우에는 이 Open Ball에서 미분이 가능하기 때문에, 우리가 미분에서 배운 내용을 그대로 써버릴 수 있다!

 

2. P가 S의 Boundary인 경우

이 경우에는 1과 같은 Open Ball을 잡을 수 없다. 이 말인 즉슨, 유클리드 공간에서 어떤 방향으로는 더 이상 미분이 불가능하다는 것을 말하고, 이는 결국 그 방향으로는 J값이 더 증가하거나 감소할 수 없다. -> 그러므로 Boundary에서 J가 극값을 가진다!

위의 예시를 적용시켜본다면 -> x, y로 미분했을 때 J가 0이 되지 않으므로, 항상 S의 Boundary에서 극값을 가지는 것을 알 수 있다!!

 

---

이렇게 어떤 조건을 가진 영역(S) 안에서 Cost Function J의 최댓값 혹은 최솟값을 찾는, 그리고 그 때의 x를 찾는 문제를 최적화 문제(Optimization Problem)라고 한다!!!

 

물론 J가 S 안에서 미분가능하다면, 위의 Note에서 본 것처럼 그냥 미분하면 된다. 그러나, 미분불가능하다면 얘기가 복잡해진다.

=> 그러므로, 최적해(Optimized Solution) x의 존재여부는

1. 영역 S의 모양

2. J의 S에서의 미분가능성

에 따라서 달라질 수 있다!! 

-> 지금까진 대부분 미분가능성에 대해서만 많이 보아왔겠지만, 저 S의 모양이 상당히 중요하다!!

=> 특히 S를 Convex set으로 어떻게든 변환한다면 Convex Optimization! -> 아주아주 빠르고 편하게 최적화 문제를 풀 수 있다!

 

또한, 저 조건 영역 S를 Feasible set이라고 부른다. 또한, x가 Feasible set 안에 있으면 x를 Feasible하다고 한다.

---

그런데 선형대수학으로 잘 나가다가 갑자기 최적화 문제를 다루는 이유가 궁금할 것이다!

그 이유는 바로 Positive Definte Matrix의 Eigenvalue와 Maximum, Minimum이 관련이 있기 때문이다.

 

Symmetric(Hermitian) A의 Eigenvalue를 계산할 때 다음 식을 계속 보아왔을 것이다.

-> 이 떄, x가 Eigenvector가 아니라 그냥 아무 벡터였다면 저 값은 어떻게 될까??

이 값을 Rayleigh Quotient라고 한다!

이 때, x는 그냥 Norm=1이라고 생각해도 된다. 왜냐하면,

즉, 실수배는 아무런 의미가 없다...

 

이 떄, Rayleigh Quotient의 최댓값과 최솟값을 생각해보자.

Symmetric Matrix A는 Spectral Theorem에 따라서 다음과 같이 Diagonalization된다.

그러므로,

 

그러므로 결국 

=> Rayleigh Quotient의 최대최소는 A의 Eigenvalue의 최댓값과 최솟값!!!

=> 이러한 문제들도 결국 일종의 최적화 문제!!