4.5 선형 최소제곱 문제

다음 함수를 최소화 하는x 의 값을 구한다고 하자.

경사 하강법 기반 최적화 기법으로 해당 문제를 풀어본다.

우선 기울기 벡터를 구해야 한다.

이제 이 기울기르 ㄹ따라 작은 단계만큼 언덕을 내려가는 과정을 반복하면 해가 나온다.

이 문제를 뉴턴법으로 풀 수도 있다. 지금 예에서는 목적함수가 실제로 이차함수이므로 뉴턴법은 단 한 번의 반복으로 전역 최솟값에 수렴한다. 

 

같은 함수를 최소화하되, x^T x <= 1 이라는 제약이 있다고 하자. 이를 풀기 위해 다음과 같은 라그랑주 함수를 도입한다.

이제 다음과 같은 최적화 문제를 풀면 된다. 

제약 없는 최소제곱 문제의 최소 노름 해를 무어-펜로즈 유사역행렬로 풀 수 있다. 이 경우 x = A^4+ b 이다. 만일 이 점이 실현가능 점이면, 이 점은 제약 있는 문제의 해가 된다. 

실현가능 점이 아니면 제약이 활성인 해를 찾아야 한다. 

라그랑주 함수를 x 에 대해 미분하면 다음과 같은 방정식이 나온다.

이로부터 문제의 해가 다음과 같은 형식임을 알 수 있다. 

이제 해가 제약을 위반하지 않게 하는 lambda 값을 구하면 되는데 lambda 에 대해 경사 상승법을 적용해서 구할 수 있다.

이를 위해 다음 관계에 주목한다.

x 의 노름이 1보다 크면 이 미분이 양수이므로, 미분 방향으로 언덕을 올라가서 lambda 에 대한 라그랑주 함수를 증가하면 lambda 가 증가한다. 

벌점에 해당하는 x^T x 의 계수가 증가하므로 x 에 대한 연립방정식을 풀면 노름이 더 작은 해가 나온다. 

연립방정식을 풀고 lambda 를 조정하는 괒엉르 x 의 노름이 원하는 크기가 되고 lambda 에 대한 미분이 0이 될때까지 반복한다.