9. 등식 제약조건

김재희·2021년 9월 17일
0

최적화 이론

목록 보기
8/9

지금까지는 주어진 목적함수에 대해 최소화하는 다양한 방법들을 살펴보았다. 하지만 실제로는 단순히 목적함수만 주어지지 않는다. 선형회귀에서도 랏소나 릿지와 같이 가중치들에 대한 제약식이 주어진다. 이렇게 제약식이 주어졌을 때, 어떻게 문제를 해결할 수 있는지 알아보자.

1. 예시

다음과 같은 최적화 문제 수식을 생각해보자.

minimizexf(x)subject to x∈X(1)minimize_\textbf{x} f(\textbf{x})\\ \text{subject to } \textbf{x} \in X \tag{1}

위 문제를 풀 때, 제약조건이 없다면 가능한 집합 XX는 RnR^n로 실수 전체가 될 것이다. 하지만 제약 조건이 있는 문제에서는 RnR^n의 부분집합이 된다. 가중치에 대한 상한 혹은 하한이 있는 제약식을 생각해보자. 이는 아래 그림과 같이 일변수 문제에선 가중치의 범위를 제한하는 꼴이다.

minimizexf(x)subject to x∈[a,b](2)minimize_x f(x) \\ \text{subject to } x \in [a, b] \tag{2}

만약 다변량 목적함수에 대해 위와 같은 제약식이 있다면, 이는 아래 그림과 같이 초사각형 내에서 최적해를 찾는 문제가 될 것이다.

2. 제약조건의 형태

제약조건은 보통 부분집합으로 직접 주어지지 않고, 두가지 형태로 주어진다.

  1. 등식 제약조건 h(x)=0h(x) = 0
  2. 부등식 제약조건 g(x)≤0g(x) \leq 0

이때, 이러한 제약조건은 다음처럼 표현할 수 있을 것이다.

minimizexf(x)subject to {hi(x)=0    (i=1,…,l)gj(x)≤0    (j=1,…,m)\begin{aligned} &minimize_\textbf{x} f(\textbf{x})\\ &\text{subject to } \begin{dcases} h_i(\textbf{x}) = 0 \;\;(i =1, \dots, l)\\ g_j(\textbf{x}) \leq 0 \;\;(j = 1, \dots , m) \end{dcases} \end{aligned}

이 식에서 등식 제약조건은 가능한 집합을 이용해서 표현할 수도 있다

h(x)=(x∉X)h(\textbf{x}) = (\textbf{x} \not \in X)

3. 제약조건 제거

가장 간단하게 제약조건이 있을 때 어떻게 최적화할 수 있는지 생각해보자.
부등식 제약조건
예를 들어 제약식이 a≤x≤ba \leq x \leq b라고 하면, xx를 다음과 같이 변형하면 제약식을 지워도 제약식 아래에서 최적해를 찾을 수 있다.

x=ta,b(x^)=b+a2+b−a2(2x^1+x^2)x = t_{a, b}(\hat{x}) = {b+a\over 2} + {b-a \over 2}({2\hat{x} \over 1+\hat{x}^2})

xx를 위처럼 변형하면, 아래 그림에서 보는 것처럼 x^=1\hat{x} =1에서 x=ax =a고, x^=−1\hat{x} = -1에서 x=bx =b가 된다.

목적함수가 f(x)=x2+3x+1f(x) = x^2 + 3x + 1일 때, 위의 제약식에서 최적화하기 위해선, 결국 목적함수가 다음과 같이 변화한다.

minimizex^f(x^)minimizex^(b+a2+b−a2(2x^1+x^2))2+3(b+a2+b−a2(2x^1+x^2))+1minimize_{\hat{x}} f(\hat{x})\\ minimize_{\hat{x}} ({b+a\over 2} + {b-a \over 2}({2\hat{x} \over 1+\hat{x}^2}))^2 + 3({b+a\over 2} + {b-a \over 2}({2\hat{x} \over 1+\hat{x}^2})) + 1

등식 제약조건
등식 제약 조건은 더 쉽게 제거할 수 있다.
예를 들어 다음과 같은 제약 조건이 있다고 해보자.

h(x)=x12+x22+⋯+xn2−1=0h(\textbf{x}) = x_1^2 + x_2^2 + \dots + x_n^2 -1 = 0

이때, 만약 i=1,…,n−1i = 1, \dots, n-1의 값을 알고 있다면, xnx_n에 대해 다음과 같이 정리하여 풀 수 있다.

xn=±1−x12−x22−⋯−xn−12x_n = \pm \sqrt{1- x_1^2 -x_2^2-\dots-x_{n-1}^2}

이를 통해 기존의 최적화문제인

minimizexf(x)subject to h(x)=0minimize_{\textbf{x}} f(\textbf{x})\\ \text{subject to } h(\textbf{x}) = 0

를 다음처럼 이전에 다룬 방법들로 최적해를 찾을 수 있는 제약식으로 변환할 수 있다.

minimizex1,…xn−1f([x1,…,xn−1,±1−x12−x22−⋯−xn−12])minimize_{x_1, \dots x_{n-1}} f([x_1, \dots, x_{n-1}, \pm \sqrt{1- x_1^2 -x_2^2-\dots-x_{n-1}^2}])

4. 라그랑주 승수

라그랑주 승수는 등식 제약조건에서 함수를 최적화하는데 이용된다. 다음과 같이 제약식이 있는 최적화문제를 생각해보자.

minimizexf(x)=−exp(−(x1x2−32)2−(x2−32)2)subject to x1−x22=0minimize_x f(\textbf{x}) = -exp(-(x_1x_2 -{3 \over 2})^2 - (x_2 - {3 \over 2})^2)\\ \text{subject to } x_1 - x^2_2 = 0

이는 x1=x22x_1 = x_2^2으로 제약조건을 변형하여 목적함수에 대입할 수 있을 것이다.

f(x)unc=−exp(−(x23−32)2−(x2−32)2)f(\textbf{x})_{unc} = -exp(-(x^3_2 - {3 \over 2})^2 - (x_2 - {3 \over 2})^2)

위의 식은 간단히 미분이 가능하고 이를 통해 쉽게 최적해를 구할 수 있다.

∂func∂x2=6exp(−(x23−32)2−(x2−32)2)(x25−32x22+13x2−12)=0∴x2=1.165,x1=(1.165)2≈1.358{\partial f_{unc} \over \partial x_2 } =6exp(-(x^3_2 - {3 \over 2})^2 - (x_2 - {3 \over 2})^2)(x^5_2 - {3 \over 2}x^2_2 + {1 \over 3}x_2 - {1 \over 2}) =0\\ \therefore x_2 = 1.165, x_1 = (1.165)^2 \approx 1.358

최적은을 본래의 목적함수 ff의 등고선이 hh가 일치하는 지점에 놓이게 될 것이다.

본래 3차원 공간에서 표현되겠지만, 간단하게 표현하고자, 위에서 내려다보는 2차원으로 표현해보면 위와 같은 상황이다.

ff는 등고선을 통해 색으로 표현되어 있고, hh는 곡선으로 검은 선으로 표현되어 있다. 이때 hh역시 3차원 공간에서 선이 아니라 사실은 수직으로 서 있는 평면이 될 것이다. 결국 우리는 제약식 hh 위의 점들 중에 ff 등고선 중 가장 아래에 있는 점이 최적해로 간주할 수 있다. 그때의 등고선은 hh와 접하는 등고선일 것이다.

이때 중요한 점은 등고선과 그래디언트는 서로 수직이라는 점이다. 높이가 cc인 등고선을 r(t)r(t) (tt는 매개변수)로 나타내보면, f(r(t))=cf(r(t)) = c 가 될 것이다. 등고선의 어떤 지점이든 높이가 똑같기 때문이다. 이때, 만약 지점을 t=at = a로 고정하고 등고선과 그래디언트를 내적해보면 다음과 같을 것이다.

∇f(r(t))r(t)=∇cr(t)=0r(t)=0\nabla f(r(t))r(t) = \nabla c r(t) = 0 r(t) = 0

이 된다.

즉, 등고선과 그래디언트의 내적은 항상 0이 되므로 수직임을 알 수 있다.

이를 이용하면 ff의 등고선과 hh가 접하는 점에서 ff의 그래디언트는 당연히 수직일 것이다. 또한, hh가 ff의 등고선에 접하고 있다면, 해당 점에서 등고선 h(x)=0h(\textbf{x}) = 0의 방향의 hh의 방향도 함수 값은 당연수 0일 것이다.

이를 종합하면 우리는 등식 제약조건에서 최적해를 찾을 때, ff의 등고선과 h(x)=0h(\textbf{x}) = 0의 등고선과 일치하는 점을 찾는 문제가 된다. 이를 라그랑주 승수법이라 한다.

자 이제 수식으로 정리해보자.
우선 다음 제약식을 만족해야 한다.

h(x)=0h(\textbf{x}) = 0

이때, 그래디언트가 다음 식처럼 어떤 계수(라그랑주 승수)λ\lambda에 대해 일치하는 x\textbf{x}를 구하면 된다.

∇f(x)=λ∇h(x)\nabla f(\textbf{x}) = \lambda \nabla h(\textbf{x})

이때 λ\lambda는 두 그래디언트가 방향은 같으나 크기가 같다는 보장이 없기 때문에 보정을 위해 들어간다.

가중치와 승수의 함수인 라그랑지안의 공식은 다음과 같아진다.

L(x,λ)=f(x)−λh(x)L(\textbf{x}, \lambda) = f(\textbf{x}) - \lambda h(\textbf{x})

결국 라그랑지안 공식의 그래디언트를 푸는 문제로 전환되는데, ∇L(x,λ)=0\nabla L(\textbf{x}, \lambda) = 0의 해는 두가지로 나뉘게 된다. 첫번째로, ∇xL=0\nabla_{\textbf{x}} L = 0는 ∇f(x)=λ∇h(x)\nabla f(\textbf{x}) = \lambda \nabla h(\textbf{x})의 조건을 제공하게 되고, ∇λL=0\nabla_{\lambda} L = 0은 h(x)=0h(\textbf{x}) = 0의 조건을 제공한다. 이렇게 구해진 해는 모두 critical point이다.

이해가 잘 가지 않으니, 전에 풀던 문제로 돌아가보자.
라그랑주 승수법으로 식을 다시 구성하면 다음과 같다.

L(x1,x2,λ)=−exp(−(x1x2−3/2)2−(x2−3/2)2)−λ(x1−x22)L(x_1, x_2, \lambda) = -exp(-(x_1x_2 - 3/2)^2 - (x_2 - 3/2)^2) - \lambda(x_1 - x_2^2)

위 식의 그래디언트를 계산하면 다음과 같다.

∂L∂x1=∂f∂x1×∂h∂x1=−2x2(x1x2−3/2)×f(x)−λ∂L∂x2=∂f∂x2×∂h∂x2=2λx2+f(x)(−2x1(x1x2−3/2)−2(x2−3/2))∂L∂λ=x22−x1\begin{aligned} {\partial L \over \partial x_1} &= {\partial f \over \partial x_1} \times {\partial h \over \partial x_1}\\ &= -2x_2(x_1x_2 - {3/2})\times f(\textbf{x}) - \lambda\\ {\partial L \over \partial x_2} &= {\partial f \over \partial x_2} \times {\partial h \over \partial x_2}\\ &= 2\lambda x_2 + f(\textbf{x})(-2x_1(x_1x_2-3/2)-2(x_2 - 3/2))\\ {\partial L \over \partial \lambda} &= x_2^2 - x_1 \end{aligned}

우리는 라그랑주 공식의 그래디언트가 0인 지점을 찾는 것이므로 0으로 설정하고 해를 구하게 되면, x≈1.358,x2≈1.165,λ≈0.170x \approx 1.358, x_2 \approx 1.165, \lambda \approx 0.170인 것을 확인할 수 있다.

라그랑주 승수법은 하나의 등식 제약조건만 풀 수 있는 것이 아니라 복수의 등식 제약조건이 주어진 경우에도 사용이 가능하다. 2개의 등식 제약조건이 있다면 아래와 같이 풀 수 있을 것이다.

minimizexf(x)subject to {h1(x)=0h2(x)=0minimize_{\textbf{x}} f(\textbf{x})\\ \text{subject to } \begin{dcases} h_1(\textbf{x}) = 0\\ h_2(\textbf{x}) = 0 \end{dcases}

위 식에서 두 제약조건을 하나로 합치는 것은 어려운 일이 아니다.

hnew(x)=h1(x)2+h2(x)2=0h_{new}(\textbf{x}) = h_1(\textbf{x})^2 + h_2(\textbf{x})^2 = 0

으로 구성하면 된다. 이렇게 제약조건을 변경한다 하더라도, 이전과 동일한 점들을 만족하기 때문에 해는 변하지 않고, 기존의 라그랑주 승수법을 그대로 이용할 수 있다. 다만 그래디언트 계산시 조금 조심할 부분이 있다. 우선 위의 식으로 그래디언트를 계산하면 다음과 같을 것이다.

∇f−λ∇hnew=0∇f−2λ(h1∇h1+h2∇h2)=0\begin{aligned} \nabla f - \lambda \nabla h_{new} &= 0\\ \nabla f - 2\lambda(h_1 \nabla h_1 + h_2 \nabla h_2) &= 0 \end{aligned}

하지만 새로운 제약조건을 만드는 것은 꼭 위와 같이 이루어질 필요가 없다. 임의의 스칼라 c>0c > 0를 삽입하여 제약조건을 구성하여도 전혀 문제될 것은 없을 것이다.

hnew(x)=h1(x)2+c×h2(x)2=0h_{new}(\textbf{x}) = h_1(\textbf{x})^2 + c\times h_2(\textbf{x})^2 = 0

이때의 그래디언트는 다음과 같이 계산된다.

∇f−λ∇hnew=0∇f−2λ(h1∇h1+c×h2∇h2)=0∇f−2λh1∇h1+2cλ h2∇h2=0∇f−λ1h1∇h1+λ2 h2∇h2=0\begin{aligned} \nabla f - \lambda \nabla h_{new} &= 0\\ \nabla f - 2\lambda(h_1 \nabla h_1 + c \times h_2 \nabla h_2) &= 0\\ \nabla f - 2\lambda h_1 \nabla h_1 + 2c\lambda \ h_2 \nabla h_2 &= 0\\ \nabla f - \lambda_1 h_1 \nabla h_1 + \lambda_2 \ h_2 \nabla h_2 &= 0 \end{aligned}

즉, n개의 등식 제약조건이 있을 때, n개의 λ\lambda를 생성하여 다음과 같이 라그랑주 승수를 가진 라그랑지안으로 정의할 수 있다. 마지막 식의 λ\lambda는 스칼라가 아닌, nn개의 스칼라로 구성된 벡터임을 유의하자.

L(x,L)=f(x)−∑i=1nλihi(x)=f(x)−λTh(x)L(\textbf{x}, L) = f(\textbf{x}) - \sum^n_{i=1} \lambda_i h_i(\textbf{x}) = f(\textbf{x}) - \lambda^Th(\textbf{x})

참고

공돌이의 수학노트 등고선에 대한 설명

profile
김재희
이전 포스트

8. 2계 도함수법(뉴턴법 등)

다음 포스트

10. 부등식 제약 조건(KKT) & 쌍대성

0개의 댓글