최적설계 | 카루시-쿤-터커 KKT 최적성 조건(1)

1. 카루시-쿤-터커 최적성 조건

   카루시-쿤-터커(Karush-Kuhn-Tucker, KKT) 최적성 조건은 등호제약조건과 부등호제약조건을 가진 목적함수의 국소적 최소점 후보군을 찾기 위한 필요조건이다. 등호제약조건과 부등호제약조건을 모두 만족하는 설계변수벡터 중에서 라그랑주 함수가 국소적 최소가 되는 설계변수벡터가 있다면, 해당 설계변수벡터에 대한 라그랑주 승수 벡터가 존재한다. 우선 아래와 같이 등호제약조건과 부등호제약조건을 포함한 최적화 문제를 고려해보자.

 

$$ \begin{align} f\left ( \mathbf{x} \right ) &= f\left ( x_1,x_2,\cdots ,x_n \right )\\\\ h_i\left ( \mathbf{x} \right ) &= 0;~~~~i=1~to~p\\\\ g_j\left ( \mathbf{x} \right ) &\leq 0;~~~~j=1~to~m \end{align}$$

 

   위와 같은 최적화 문제는 다음과 같은 라그랑주 함수로 나타낼 수 있다.

 

$$ \begin{align} L\left ( \textbf{x},\textbf{v},\textbf{u},\textbf{s} \right ) &= f\left ( \textbf{x} \right)+\sum_{i=1}^{p}v_{i}h_i\left( \textbf{x} \right)+\sum_{j=1}^{m}u_{j} \left[ g_{j}\left ( \textbf{x} \right )+s_{j}^{2} \right]\\\\ &=f\left ( \textbf{x} \right ) + \textbf{v}^{T}\mathbf{h}\left ( \textbf{x} \right ) + \textbf{u}^{T} \left[ \mathbf{g}\left ( \textbf{x} \right ) + \mathbf{s}^{2} \right] \end{align}$$

 

   라그랑주 함수를 이용해 국소적 최소점 후보군이 되기 위한 필요조건을 표현하면 다음과 같다.

 

$$ \begin{align} \triangledown L \left ( \mathbf{x^*}, \mathbf{v^*}, \mathbf{u^*}, \mathbf{s^*} \right )=0 \end{align}$$

 

$$ \begin{align} \frac{\partial L \left ( \mathbf{x^*},\mathbf{v^*},\mathbf{u^*},\mathbf{s^*} \right )}{\partial x_k}&=0;~~~~k=1~to~n\\\\ \frac{\partial L \left ( \mathbf{x^*},\mathbf{v^*},\mathbf{u^*},\mathbf{s^*} \right )}{\partial v_i}&=h_i \left( \textbf{x*} \right)=0;~~~~i=1~to~p\\\\ \frac{\partial L \left ( \mathbf{x^*},\mathbf{v^*},\mathbf{u^*},\mathbf{s^*} \right )}{\partial u_j}&=g_j \left( \textbf{x*} \right)+s_j^{2} = 0;~~~~j=1~to~m\\\\ \frac{\partial L \left ( \mathbf{x^*},\mathbf{v^*},\mathbf{u^*},\mathbf{s^*} \right )}{\partial s_j}&=2u_j^*s_j =0;~~~~j=1~to~m \end{align}$$

 

   라그랑주 승수는 제약조건 앞에 붙어 선형결합의 스칼라 계수 역할을 하며, 등호제약조건 앞에 있는 승수는 부호에 제한이 없는 반면, 부등호제약조건 앞에 있는 승수는 음이 아니어야 한다. 

 

$$ \begin{align} u_{j}^{*} \geq 0 \end{align}$$

 

2. 라그랑주 승수의 물리적 의미

   최적해에서 라그랑주 함수를 구성하는 라그랑주 승수는 목적함수에 대한 해당 활성제약조건의 영향력으로 해석할 수 있다. 비교적 큰 값의 승수를 갖는다는 것은 이 승수에 해당하는 활성제약조건이 변할 경우 목적함수에 지대한 영향을 준다는 것을 의미한다. 라그랑주 승수의 값이 클수록 이에 대응하는 활성제약조건을 완화시키면 이익이 더욱 많아지게 되거나, 이에 대응하는 활성제약조건을 엄격하게 하면 더 많은 손해를 보게 된다는 것이다. 이처럼 라그랑주 승수를 보고, 목적함수에 지대한 영향을 미치는 활성제약조건을 선택하여, 이 조건들을 완화했을 때 목적함수가 얼마나 개선되는지 살펴볼 수 있다.

 

3. 주의사항

   제약조건을 포함한 최적화 문제의 해는 존재하지 않을 수 있다. 이러한 경우는 목적함수를 과도하게 제약하면 발생할 수 있는데, 제약조건이 서로 대립하여 이를 모두 만족하는 설계를 구성할 수 없는 것이다. 이러한 경우에는 해당 문제의 정식화를 다시 검토하여 제약조건을 완화해야 한다.

 

4. 예제

   부등호제약조건을 고려하여 아래 목적함수의 후보 최대점을 찾아보자.
 

$$ \begin{align} F\left ( \textbf{x} \right ) &= 2x_1+2x_2-x_1^{2}-x_2^{2}-2\\\\ G_1\left ( \textbf{x} \right ) &= 2x_1+x_2 \geq 4\\\\ G_2\left ( \textbf{x} \right ) &= x_1+2x_2 \geq 4 \end{align} $$

 

KKT 최적성 조건

 

   위 최적화 문제를 정규화하면 다음과 같다.

 

$$ \begin{align} f\left ( \textbf{x} \right ) &= x_1^{2}+x_2^{2}-2x_1-2x_2+2\\\\ g_1\left ( \mathbf{x} \right ) &= -2x_1-x_2+4 \leq 0 \\\\ g_2\left ( \mathbf{x} \right ) &= -x_1-2x_2+4 \leq 0 \end{align}$$

   위 최적화 문제를 라그랑주 함수 형태로 표현하면 다음과 같다.
 

$$ \begin{align} L\left ( \textbf{x},\textbf{u},\textbf{s} \right ) &= f\left( \textbf{x} \right) +u_1\left[g_1\left( \textbf{x} \right)+s_1^2\right] +u_2\left[g_2\left( \textbf{x} \right)+s_2^2\right]\\\\ &=x_1^{2}+x_2^{2}-2x_1-2x_2+2 + u_1 \left( -2x_{1}-x_{2}+4+s_1^2 \right) + u_2 \left( -x_{1}-2x_{2}+4+s_2^2 \right) \end{align}$$

 
   목적함수가 국소적 최소를 가진다면 한 설계변수벡터와 라그랑지 승수에 대해서 라그랑주 함수의 도함수가 0이어야 한다. 라그랑주 함수의 도함수를 계산하고, 경우의 수를 나누어 연립방정식을 풀면 다음과 같다.
 

$$ \begin{align} \triangledown L\left ( \mathbf{x^*}, \mathbf{u^*}, \mathbf{s^*} \right )= \begin{bmatrix} 2x_1-2-2u_1-u_2 \\ 2x_2-2-u_1-2u_2 \\ -2x_1-x_2+4+s_1^2 \\ -x_1-2x_2+4+s_2^2 \\ 2u_1s_1 \\ 2u_2s_2 \end{bmatrix} = \begin{bmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{bmatrix} \end{align} $$

 

$$ \begin{flalign} ①~u_1=0,~u_2=0: && \end{flalign} $$

 

$$ \begin{align} &2x_1-2 = 0~~~~\left( x_1=1 \right)\\\\ &2x_2-2 = 0~~~~\left( x_2=1 \right)\\\\\ &1+s_1^2 = 0~~~~\left( not feasible \right)\\\\ &1+s_2^2 = 0~~~~\left( not feasible \right) \end{align} $$

 

$$ \begin{flalign} ②~u_1=0,~s_2=0: && \end{flalign} $$

 

$$ \begin{align} & 2x_1-2-u_2 = 0~~~~\left(x_1=\frac{1}{2}u_2+1 \right)\\\\ & 2x_2-2-2u_2 = 0~~~~\left(x_2=u_2+1 \right)\\\\ & -2x_1-x_2+4+s_1^2 = 0\\\\ & -x_1-2x_2+4 = 0\\\\ \\\\ & -2u_2+1+s_1^2=0\\\\ & -\frac{5}{2}u_2+1 = 0~~~~\left( u_2=\frac{2}{5} \right)\\\\ \\\\ & \frac{1}{5}+s_1^2 = 0~~~~\left( not feasible \right) \end{align} $$

 

$$ \begin{flalign} ③~s_1=0,~u_2=0: && \end{flalign} $$

 

$$ \begin{align} & 2x_1-2-u_2 = 0~~~~\left(x_1=\frac{1}{2}u_2+1 \right)\\\\ & 2x_2-2-2u_2 = 0~~~~\left(x_2=u_2+1 \right)\\\\ & -2x_1-x_2+4+s_1^2 = 0\\\\ & -x_1-2x_2+4 = 0\\\\ \\\\ & -2u_2+1+s_1^2=0\\\\ & -\frac{5}{2}u_2+1 = 0~~~~\left( u_2=\frac{2}{5} \right)\\\\ \\\\ & \frac{1}{5}+s_1^2 = 0~~~~\left( not feasible \right) \end{align} $$

 

$$ \begin{flalign} ④~s_1=0,~s_2=0: && \end{flalign} $$

 

$$ \begin{align} & 2x_1-2-2u_1-u_2 = 0\\\\ & 2x_2-2-u_1-2u_2 = 0\\\\ & -2x_1-x_2+4 = 0\\\\ & -x_1-2x_2+4 = 0\\\\ \\\\ & \frac{2}{3}-2u_1-u_2 = 0\\\\ & \frac{2}{3}-u_1-2u_2 = 0\\\\ & x_1 = \frac{4}{3},~~~~x_2=\frac{4}{3}\\\\ \\\\ & u_1 = \frac{2}{9} \geq 0,~~~~u_2=\frac{2}{9} \geq 0 \end{align} $$

 

$$ \begin{align} \therefore~ u_1^{*}=\frac{2}{9},~~~~s_1^{*}=0,~~~~ u_2^{*}=\frac{2}{9},~~~~s_2^{*}=0,~~~~ x_{1}^{*}=\frac{4}{3},~~~~x_{2}^{*}=\frac{4}{3} \end{align} $$

 

 

 

 

 

[함께 읽으면 좋은 페이지]

 

최적설계 | 등호제약조건 문제

최적설계 | 부등호제약조건 문제

최적설계 | 카루시-쿤-터커 KKT 최적성 조건(2)

 

 

 

 

 

참고문헌
- Arora, J. S. (2016). Introduction to optimum design. Elsevier.