최적화 문제

곡선 적합

보간법(Interpolation)

개념

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

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

보간법은 좀 제한적인 개념이다.

즉, 해당 $n$개의 점들을 만족하는 다항함수가 없을 수도 있다.

만약 있다면, 이는 유일하다는 의미이다.  

 

사례

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

$$ f(x)=a_0+a_1x+a_2x^2+a_3x^3 $$

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

 

① $\begin{pmatrix}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{pmatrix}\begin{pmatrix}a_0\\a_1\\a_2\\a_3\end{pmatrix}=\begin{pmatrix}y_1\\y_2\\y_3\\y_4\end{pmatrix}$  

 

② 네 점을 대입하고 augmented matrix(첨가행렬)을 만든다.

$\begin{pmatrix}1&1&1&1&3\\1&2&4&8&-2\\1&3&9&27&-5\\1&4&16&64&0\end{pmatrix}$  

 

③ 첨가행렬을 가우스-조던 소거법을 이용해 푼다.

$\begin{pmatrix}1&1&1&1&3\\1&2&4&8&-2\\1&3&9&27&-5\\1&4&16&64&0\end{pmatrix}\Rightarrow\begin{pmatrix}1&0&0&0&4\\0&1&0&0&3\\0&0&1&0&-5\\0&0&0&1&1\end{pmatrix}$  

 

④ $a_0=4,\,\,a_1=3,\,\,a_2=-5,\,\,a_3=1$ 이므로 $f(x)=4+3-5x^2+x^3$ 이다.

 

앞에서도 설명했지만 보간법의 치명적인 단점은, 유연성이 부족하다.

즉, 머신러닝 용어로 overfitting의 위험이 높다.  

  

최소제곱법(Least squares)

개념

특정 점들을 포함하는 함수를 특정 지을 수 없을 때,

실제 해와의 오차 제곱 합이 최소가 되는 근사적인 해를 구하는 방법.

(보간법처럼 딱 맞을 필요가 없으니 유연성이 좋다)

💡 방정식 $A\text{x}=B$ 을 변형한 방정식 $A^TA\text{x}=A^TB$ (정규방정식)의 모든 해는 $A\text{x}=B$의 최소제곱해이다.

  

사례

네 점 $(0,1),(1,3), (2,4), (3,4)$ 에 근사하는 일차함수

$$ f(x)=a_0+a_1x $$

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

 

① $A\text{x}=B$

$\begin{pmatrix}1&x_1\\1&x_2\\1&x_3\\1&x_4\end{pmatrix}\begin{pmatrix}a_0\\a_1\end{pmatrix}=\begin{pmatrix}y_1\\y_2\\y_3\\y_4\end{pmatrix}$  

 

② 네 점을 대입하고 정규방정식 $A^TA\text{x}=A^TB$로부터 방정식 $\text{x}=(A^TA)^{-1}A^TB$을 구성한다.

$A^TA=\begin{pmatrix}4&6\\6&14\end{pmatrix}$ 이므로

$(A^TA)^{-1}=\begin{pmatrix}4&6\\6&14\end{pmatrix}^{-1}=\dfrac{1}{10}\begin{pmatrix}7&-3\\-3&2\end{pmatrix}$

$\therefore\quad\text{x}=\dfrac{1}{10}\begin{pmatrix}7&-3\\-3&2\end{pmatrix}\begin{pmatrix}1&1&1&1\\0&1&2&3\end{pmatrix}\begin{pmatrix}1\\3\\4\\4\end{pmatrix}$  

 

③ $\text{x}=\begin{pmatrix}a_0\\a_1\end{pmatrix}=\begin{pmatrix}\frac{3}{2}\\1\end{pmatrix}$ 이므로 구하고자 하는 함수는 $f(x)=\dfrac{3}{2}+x$ 이다.

 

$n$차 일반화

$m$개의 자료점 $(x_1,y_1),\cdots,(x_m,y_m)$에 대해 $n$차 다항식 $y=a_0+a_1x+\cdots+a_nx^n$을 최소제곱법으로 이용하여 근사하기 위해서는 $A\text{x}=B$를

$$ A=\begin{pmatrix}1&x_1&\cdots&x_1^n\\1&x_2&\cdots&x_2^n\\\vdots&\vdots&\ddots&\vdots\\1&x_m&\cdots&x_m^n\end{pmatrix},\,\,\text{x}=\begin{pmatrix}a_0\\a_1\\\vdots\\a_n\end{pmatrix},\,\,B=\begin{pmatrix}y_1\\y_2\\\vdots\\y_m\end{pmatrix} $$

로 설정하면 된다.  

 

사실, 위와 같은 꼴의 다항식이 아니라 만약 식이 $xy, \log x, \sin x$ 등의 항이 있다 하더라도 똑같이 적용가능하므로 굉장히 유용하다.  

 

두 방법의 비교

  

 

---

이차형식의 최적화

이차형식(Quadratic form)

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

$\forall k,l\in K,\,\,\forall u,v,w\in V,$

1. $Q(kv)=k^2Q(v)$
2. $Q(u+v+w)=Q(u+v)+Q(v+w)+Q(u+w)-Q(u)-Q(v)-Q(w)$
3. $Q(ku+lv)=k^2Q(u)+l^2Q(v)+klQ(u+v)-klQ(u)-klQ(v)$  

 

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

$$ a_1x_1^2+a_2x_2^2+2a_3x_1x_2\Leftrightarrow\begin{pmatrix}x_1&x_2\end{pmatrix}\begin{pmatrix}a_1&a_2\\a_3&a_2\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix} $$  

 

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

$$ a_1x_1^2+a_2x_2^2+a_3x_3^2+2a_4x_1x_2+2a_5x_1x_3+2a_6x_2x_3\\\Leftrightarrow\begin{pmatrix}x_1&x_2&x_3\end{pmatrix}\begin{pmatrix}a_1&a_4&a_5\\a_4&a_2&a_6\\a_5&a_6&a_3\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} $$  

 

제약된 극값

개념

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

💡 $n\times n$ 행렬 $A$의 eigenvalue를 큰 순서대로 $\lambda_1,\cdots,\lambda_n$ 이라 하자. 이 때 $\|\text{v}\|=1$ 제약 하에 $\text{v}^TA\text{v}$ 의 최댓(솟)값은 $\lambda_1(\lambda_n)$에 대응하는 단위고유벡터에서 존재한다.

  

사례

제약 $x^2+y^2=1$ 하에서 $z=5x^2+5y^2+4xy$ 의 최댓값과 최솟값을 구하자.

우선 $z$를 이차형식 $\text{v}^TA\text{v}$ 형태로 변환한다.  

 

① $a_1x^2+a_2y^2+2a_3xy\\\Leftrightarrow\begin{pmatrix}x_1&x_2\end{pmatrix}\begin{pmatrix}a_1&a_2\\a_3&a_2\end{pmatrix}\begin{pmatrix}x_1\\x_2\end{pmatrix}=\text{v}^TA\text{v}$

즉, $z=\begin{pmatrix}x&y\end{pmatrix}\begin{pmatrix}5&2\\2&5\end{pmatrix}\begin{pmatrix}x\\y\end{pmatrix}$  

 

② 행렬 $A=\begin{pmatrix}5&2\\2&5\end{pmatrix}$ 의 eigenvalue와 eigenvector를 구한다.

$\lambda_1=7,\quad\text{v}_1=(1,1)\\\lambda_2=3,\quad\text{v}_2=(-1,1)$  

 

③ Eigenvector를 정규화한다.

$\lambda_1=7,\quad\text{v}_1=(\dfrac{1}{\sqrt{2}},\dfrac{1}{\sqrt{2}})\\\lambda_2=3,\quad\text{v}_2=(-\dfrac{1}{\sqrt{2}},\dfrac{1}{\sqrt{2}})$  

 

④ 따라서 $(x,y)=(\dfrac{1}{\sqrt{2}},\dfrac{1}{\sqrt{2}})$ 일 때 $z$는 최댓값 $7$을 갖고,

$(x,y)=(-\dfrac{1}{\sqrt{2}},\dfrac{1}{\sqrt{2}})$ 일 때 $z$는 최솟값 $3$을 갖는다.  

 

※ 물론 nomalize안해도 최대 최소값은 변함없다.