이상엽/ 최적화 문제

곡선 적합

보간법

개념

주어진 특징 점들을 포함하는 함수를 구하는 방법

정리) 좌표평면에 있는 임의의 서로 다른 n 개의 점을 지나는 k 차 다항함수는 유일하게 존재한다. (단 k k < n 인 자연수)

사례

네 점 (1, 3), (2, -2), (3, -5), (4, 0) 을 모두 지나는 3차 함수

f(x) = a_{0} + a_{1} x + a_{2} x^{2} + a_{3} x^{3}

를 구하자. 우선 다음의 방정식을 세운다.

Step 1)

\left( \begin{array}{rrrr} 1 & x_{1} & x_{1}^{2} & x_{1}^{3} \\ 1 & x_{2} & x_{2}^{2} & x_{2}^{3} \\ 1 & x_{3} & x_{3}^{2} & x_{3}^{3} \\ 1 & x_{4} & x_{4}^{2} & x_{4}^{3} \end{array} \right) \left( \begin{array}{rrrr} a_{0} \\ a_{1} \\ a_{2} \\ a_{3} \end{array} \right) = \left( \begin{array}{rrrr} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{array} \right)

Step 2) 네 점을 대입하고 첨가행렬을 만든다.

\left( \begin{array}{rrrrr} 1 & 1 & 1 & 1 & 3 \\ 1 & 2 & 4 & 8 & -2 \\ 1 & 3 & 9 & 27 & -5 \\ 1 & 4 & 16 & 64 & 0 \end{array} \right)

Step 3) 첨가행렬을 가우스-조던 소거법을 이용하여 풀이한다.

\left( \begin{array}{rrrrr} 1 & 1 & 1 & 1 & 3 \\ 1 & 2 & 4 & 8 & -2 \\ 1 & 3 & 9 & 27 & -5 \\ 1 & 4 & 16 & 64 & 0 \end{array} \right) \Rightarrow \left( \begin{array}{rrrrr} 1 & 0 & 0 & 0 & 4 \\ 0 & 1 & 0 & 0 & 3 \\ 0 & 0 & 1 & 0 & -5 \\ 0 & 0 & 0 & 1 & 1 \end{array} \right)

Step 4) 

a_{0} = 4, a_{1} = 3, a_{2} = -5, a_{3} = 1 이므로 f(x) = 4 + 3 x - 5 x^{2} + x^{3} 이다.

  • 곡선 접합은 현재 가진 데이터에 대해 분석은 잘 할 수 있지만, 신규 데이터가 현재 그려 놓은 곡선 위에 존재한다는 보증이 없음. 유연성이 매우 떨어진다.
    • 애초에 데이터를 모두 포함하는 함수가 존재하지 않는 경우도 많음.

최소제곱법

  • 곡선 접합의 단점을 보완할 수 있는 방법.
  • 가우스가 창안한 방법으로 가우스는 이 방법을 통해 소행성 ‘세레스’ 의 궤도를 정확히 예측해 냄.

개념

특징 점들을 포함하는 함수를 특정 지을 수 없을 때, 실제 해와의 오차 제곱 합이 최소가 되는 근사적인 해를 구하는 방법

정리) 방정식 Ax = B 을 변형한 방정식 A^{T}Ax = A^{T}B (정규방정식)의 모든 해는 Ax = B 의 최소제곱해이다.

  • 요게 결국 선형회귀이다.
  • A^{T}Ax = A^{T}B (정규방정식)의 모든 해는 Ax = B 의 최소제곱해이라는 부분은 증명이 복잡하므로 강의 상에서는 생략.

사례

네 점 (0, 1), (1, 3), (2, 4), (3, 4) 에 근사하는 일차 함수 f(x) = a_{0} + a_{1} x 을 구하자. 우선 다음의 방정식을 세운다.

Step 1) Ax = B

\Leftrightarrow \left( \begin{array}{rrrr} 1 & x_{1} \\ 1 & x_{2} \\ 1 & x_{3} \\ 1 & x_{4} \end{array} \right) \left( \begin{array}{rr} a_{0} \\ a_{1} \end{array} \right) = \left( \begin{array}{rrrr} y_{1} \\ y_{2} \\ y_{3} \\ y_{4} \end{array} \right)

Step 2) 네 점을 대입하고 정규방정식 A^{T}Ax = A^{T}B 으로부터 방정식 x = (A^{T}A)^{-1} A^{T}B 을 구성한다.

A^{T}A = \left( \begin{array}{rr} 4 & 6 \\ 6 & 14  \end{array} \right) 이므로

(A^{T}A)^{-1} = \left( \begin{array}{rr} 4 & 6 \\ 6 & 14  \end{array} \right)^{-1} = {1 \over 10} \left( \begin{array}{rr} 7 & -3 \\ -3 & 2  \end{array} \right)  

\therefore x = {1 \over 10} \left( \begin{array}{rr} 7 & -3 \\ -3 & 2  \end{array} \right) \left( \begin{array}{rrrr} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 3  \end{array} \right) \left( \begin{array}{rrrr} 1 \\ 3 \\ 4 \\ 4  \end{array} \right)

Step 3) x = \left( \begin{array}{rr} a_{0} \\ a_{1}  \end{array} \right) = \left( \begin{array}{rr} {2 \over 3} \\ 1 \end{array} \right) 이므로 구하고자 하는 함수는 f(x) = {3 \over 2} + x 이다.

n차 일반화

m 개의 자료점 (x_{1}, y_{1}), (x_{2}, y_{2}), ... , (x_{m}, y_{m}) 에 대해 n 차 다항식 y = a_{0} + a_{1} x + ... + a_{n} x^{n} 을 최소제곱법을 이용하여 근사하기 위해서는 Ax = B

A = \left( \begin{array}{rrrr} 1 & x_{1} & ... & x_{1}^{n} \\ 1 & x_{2} & ... & x_{2}^{n} \\ ... & ... & ... & ... \\ 1 & x_{m} & ... & x_{m}^{n} \end{array} \right), x = \left( \begin{array}{rrrr} a_{0} \\ a_{1} \\ ... \\ a_{n} \end{array} \right), B = \left( \begin{array}{rrrr} y_{1} \\ y_{2} \\ ... \\ y_{m} \end{array} \right)

로 설정하면 된다.

두 방법의 비교

  보간법 최소제곱법
목표 데이터를 모두 포함하는 함수 데이터의 경향을 반영하는 함수
데이터의 수 적을 수록 좋음 많아도 무방함
정밀도 매우 높음 상대적으로 낮음
신축성 조절이 어려움 조절이 자유로움

이차형식의 최적화

이차형식

가환환 K 위의 가군 V 에 대해 다음 세 조건을 만족시키는 함수 Q : V \to K

  • \forall k, l \in K, \forall u, v, w \in V
    • Q(kv) = k^{2} Q(v)
    • Q(u + v + w) = Q(u + v) + Q(v+w) + Q(u+w) - Q(u) - Q(v) - Q(w)
    • Q(kv + lv) = k^{2} Q(u) + l^{2} Q(v) + kl Q(u+v) - klQ(u) - klQ(v)

ex 1) R^{2} 상의 일반적인 이차형식은 다음과 같다.

a_{1}x_{1}^{2} + a_{2}x_{2}^{2} + 2a_{3}x_{1}x_{2} \Leftrightarrow \left( \begin{array}{rr} x_{1} & x_{2} \end{array} \right) \left( \begin{array}{rr} a_{1} & a_{3} \\ a_{3} & a_{2} \end{array} \right) \left( \begin{array}{rr} x_{1} \\ x_{2}  \end{array} \right)

ex 2) R^{3} 상의 일반적인 이차형식은 다음과 같다.

a_{1}x_{1}^{2} + a_{2}x_{2}^{2} + a_{3}x_{3}^{2} +  2a_{4}x_{1}x_{2} + 2a_{5}x_{1}x_{3} + 2a_{6}x_{2}x_{2}

\Leftrightarrow \left( \begin{array}{rrr} x_{1} & x_{2} & x_{3} \end{array} \right) \left( \begin{array}{rrr} a_{1} & a_{4} & a_{5} \\ a_{4} & a_{2} & a_{6} \\ a_{5} & a_{6} & a_{3} \end{array} \right) \left( \begin{array}{rrr} x_{1} \\ x_{2} \\ x_{3} \end{array} \right)

제약된 극값

개념

특정 제약 하에 결정되는 원하는 식의 최댓값 또는 최솟값

정리) n \times n 행렬 A 의 고윳값을 큰 순서대로 \lambda_{1}, \lambda_{2}, ... , \lambda_{n} 이라 하자. 이때 \|v\| = 1 제약 하에 v^{T}Av 의 최댓(솟)값은 \lambda_{1} (\lambda_{n}) 에 대응하는 단위고유벡터에서 존재한다.

사례

제약 x^{2} + y^{2} = 1 하에서

  • 위 제약 조건은 \vec{v} = (x, y) 로 정한 것과 같다. \|v\| = 1 이 된다.

z = 5 x^{2} + 5 y^{2} + 4xy

의 최댓값과 최솟값을 구하자. 우선 z 를 이차형식 v^{T} Av 형태로 변환한다.

Step 1) a_{1}x^{2} + a_{2}y^{2} + 2a_{3}xy

\Leftrightarrow \left( \begin{array}{rr} x & y \end{array} \right) \left( \begin{array}{rr} a_{1} & a_{3} \\ a_{3} & a_{2} \end{array} \right) \left( \begin{array}{rr} x \\ y \end{array} \right) = v^{T} A v

즉, z = \left( \begin{array}{rr} x & y \end{array} \right) \left( \begin{array}{rr} 5 & 2 \\ 2 & 5 \end{array} \right) \left( \begin{array}{rr} x \\ y \end{array} \right)

Step 2) 행렬 A = \left( \begin{array}{rr} 5 & 2 \\ 2 & 5 \end{array} \right) 의 고윳값과 고유벡터를 구한다.

\Rightarrow \begin{cases} \lambda_{1} = 7 & v_{1} = (1, 1) \\ \lambda_{2} = 3 & v_{2} = (-1, 1) \end{cases}

Step 3) 고유벡터를 정규화한다.

\Rightarrow \begin{cases} \lambda_{1} = 7 & v_{1} = ({1 \over \sqrt{2}}, {1 \over \sqrt{2}}) \\ \lambda_{2} = 3 & v_{2} = (-{1 \over \sqrt{2}}, {1 \over \sqrt{2}}) \end{cases}

Step 4) 따라서 (x, y) = ({1 \over \sqrt{2}}, {1 \over \sqrt{2}}) 일 때 z 는 최댓값 7을 갖고, (x, y) = (-{1 \over \sqrt{2}}, {1 \over \sqrt{2}}) 일 때 z 최솟값 3을 갖는다.

물론 v_{1} = (-1, -1), v_{2} = (1, -1)   등으로 설정해도 무방하며, 최댓(솟)값은 변하지 않는다.

[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.