최적설계 | 이차계획법

1. 이차계획법

   이차계획법(Quadratic Programming, QP)은 선형계획법과는 다르게 이차목적함수와 선형제약조건을 갖는다. 실제 응용에서도 많이 찾아볼 수 있으며, 일반적인 비선형계획 알고리즘은 매 반복마다 이차계획문제의 해를 요구한다. 이차계획문제는 다음과 같이 정의한다.
 

$$ \begin{align} \mathrm{minimize}~~~~&f \left( \mathbf{x} \right) = \frac{1}{2}\mathbf{x}^T\mathbf{H}\mathbf{x}+\mathbf{c}^T\mathbf{x} \\\\ \mathrm{subject~to}~~~~&\mathbf{N}^T\mathbf{x} = \mathbf{e} \\\\ &\mathbf{A}^T\mathbf{x} \leq \mathbf{b} \\\\ &\mathbf{x} \geq \mathbf{0} \end{align}$$

 

2. 이차계획문제의 KKT 필요조건

   이차계획문제를 풀기 위해서는 해당 문제에 KKT 필요조건을 사용하고, 이를 심플렉스법을 적용할 수 있는 형태로 변환시킨다. KKT 필요조건을 사용하기 위해 부등호제약조건은 이완변수를 도입하여 다음의 등식으로 변환한다.
 

$$ \begin{align} \mathbf{A}^T\mathbf{x} + \mathbf{s} = \mathbf{b};~~~~\mathbf{s} \geq \mathbf{0} \end{align}$$

 
   이차계획문제를 라그랑주 함수로 나타내면 아래와 같다. 첫 번째 항은 목적함수, 두 번째 항은 부등호제약조건, 세 번째 항은 설계변수가 음이 아닐 조건, 네 번째 항은 등호제약조건에 해당한다.
 

$$ \begin{align} L\left ( \mathbf{x} \right ) &= f\left ( \mathbf{x} \right ) + \mathbf{u}^{T} \left( \mathbf{A}^T \mathbf{x} + \mathbf{s} - \mathbf{b} \right ) - \mathbf{\xi}^T \mathbf{x} + \mathbf{v}^T \left ( \mathbf{N}^T \mathbf{x} - \mathbf{e} \right ) \\\\ &= \mathbf{c}^T \mathbf{x} + \frac{1}{2} \mathbf{x}^T \mathbf{H} \mathbf{x} + \mathbf{u}^{T} \left( \mathbf{A}^T \mathbf{x} + \mathbf{s} - \mathbf{b} \right ) - \mathbf{\xi}^T \mathbf{x} + \mathbf{v}^T \left ( \mathbf{N}^T \mathbf{x} - \mathbf{e} \right ) \end{align}$$

 
   위 식에 KKT 필요조건을 적용하여 다시 나타내면 다음과 같다.
 

$$ \begin{align} \frac{\partial L \left( \mathbf{x} \right) }{\partial \mathbf{x}} = \mathbf{c}+\mathbf{H}\mathbf{x} + \mathbf{A}\mathbf{u} - \mathbf{\xi} + \mathbf{N}\mathbf{v} &= \mathbf{0}\\\\ \mathbf{A}^T \mathbf{x} + \mathbf{s} - \mathbf{b} &= \mathbf{0} \\\\ \mathbf{N}^T \mathbf{x} - \mathbf{e} &= \mathbf{0} \\\\ u_i s_i \left( \mathbf{x} \right) &= 0;~~~~s_i \geq 0,~~~u_i \geq 0~~~~for~~i=1~~to~~m \\\\ \xi_i x_i \left( \mathbf{x} \right) &= 0;~~~~x_i \geq 0,~~~\xi_i \geq 0~~~~for~~i=1~~to~~n \end{align}$$

 
   등호제약조건에 해당하는 라그랑지 승수는 부호의 제약이 없으므로 다음과 같이 분해한다.
 

$$ \begin{align} \mathbf{v} = \mathbf{y} - \mathbf{z};~~~~\mathbf{y} \geq \mathbf{0},~~\mathbf{z} \geq \mathbf{0} \end{align}$$

 
   위 식들을 종합하여 행렬식으로 나타내면 아래와 같다. 이차계획문제에 KKT 필요조건을 적용함으로써, 이차계획문제가 제약조건을 만족하는 선형방정식의 해를 구하는 문제로 축약된다.
 

$$ \begin{align} \begin{bmatrix} \mathbf{H} & \mathbf{A} & \mathbf{-I}_{\left(n\right)} & \mathbf{0}_{\left(n \times m\right)} & \mathbf{N} & -\mathbf{N} \\ \mathbf{A}^T & \mathbf{0}_{\left(m \times m\right)} & \mathbf{0}_{\left(m \times n\right)} & \mathbf{I}_{\left(m\right)} & \mathbf{0}_{\left(m \times p\right)} & \mathbf{0}_{\left(m \times p\right)} \\ \mathbf{N}^T & \mathbf{0}_{\left(p \times m\right)} & \mathbf{0}_{\left(p \times n\right)} & \mathbf{0}_{\left(p \times m\right)} & \mathbf{0}_{\left(p \times p\right)} & \mathbf{0}_{\left(p \times p\right)} \\ \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ \mathbf{u} \\ \mathbf{\xi} \\ \mathbf{s} \\ \mathbf{y} \\ \mathbf{z} \end{bmatrix} = \begin{bmatrix} \mathbf{-c} \\ \mathbf{b} \\ \mathbf{e} \end{bmatrix} \end{align}$$

 

$$ \begin{align} \mathbf{B}\mathbf{X} = \mathbf{D} \end{align}$$

 

3. 이차계획문제와 심플렉스법

   심플렉스법을 적용하기 위해, 등호제약에 인위변수를 정의하고 인위가격함수를 만들어 초기 기저유용해를 결정한다. 등호제약조건에 인위변수를 도입하여 나타내면 아래와 같다. 이렇게 하여 모든 설계변수를 비기저변수로, 인위변수를 기저변수로 선택한다. 초기 기저해가 유용해가 되기 위해서는 우변에 있는 모든 요소가 양의 값을 가져야 한다.
 

$$ \begin{align} \mathbf{B}\mathbf{X} + \mathbf{Y} = \mathbf{D} \end{align}$$

 
   선형계획법에서의 심플렉스법과 마찬가지로, 인위가격함수는 인위변수의 합으로 정의된다.  이때 인위가격함수는 다음과 같이 비기저변수의 항으로만 나타내야 한다.
 

$$ \begin{align} \omega &= \sum_{i=1}^{n+m+p}Y_i \\\\ &= \sum_{i=1}^{n+m+p}D_i - \sum_{j=1}^{2\left(n+m+p\right)}\sum_{i=1}^{n+m+p}B_{ij}X_j \\\\ &= \omega_0 + \sum_{j=1}^{2\left(n+m+p\right)}C_{j}X_j \end{align}$$

 

4. 예제

이차계획법

   아래에 주어진 비선형·제약조건 문제에 이차계획법을 적용하여 최적화해보자.
 

$$ \begin{align} \mathrm{minimize}~~~~&f = \left( x_1-3 \right)^2 + \left( x_2-3 \right)^2 \\\\ \mathrm{subject~to}~~~~&x_1 + x_2 \leq 4 \\\\ &x_1 - 3x_2 = 1 \\\\ &x_1 \geq 0,~~x_2 \geq 0 \end{align}$$

 
   주어진 목적함수를 전개하여 행렬식으로 나타내면 다음과 같다. 연산의 편의를 위해 목적함수의 상수는 무시한다.
 

$$ \begin{align} f &= x_1^2+x_2^2-6x_1-6x_2 \\\\ &= \mathbf{c}^T \mathbf{x} + \frac{1}{2} \mathbf{x}^T \mathbf{H} \mathbf{x} \\\\ &= \begin{bmatrix} -6 & -6 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} + \frac{1}{2} \begin{bmatrix} x_1 & x_2 \\ \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 2 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \end{align}$$

 

$$ \begin{align} \mathbf{N}^T\mathbf{x} &= \mathbf{e} \\\\ \begin{bmatrix} 1 & -3 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} &= \begin{bmatrix} 1 \end{bmatrix} \end{align}$$

 

$$ \begin{align} \mathbf{A}^T\mathbf{x} &\leq \mathbf{b} \\\\ \begin{bmatrix} 1 & 1 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} &\leq \begin{bmatrix} 4 \end{bmatrix} \end{align}$$

 
   이차계획문제에 KKT 필요조건을 적용하여 행렬식으로 나타내면 다음과 같다.
 

$$ \begin{align} \mathbf{B} \mathbf{X} &= \mathbf{D} \end{align}$$

 

$$ \begin{align} \begin{bmatrix} \mathbf{H} & \mathbf{A} & \mathbf{-I}_{\left(2\right)} & \mathbf{0}_{\left(2 \times 1\right)} & \mathbf{N} & -\mathbf{N} \\ \mathbf{A}^T & \mathbf{0}_{\left(1 \times 1\right)} & \mathbf{0}_{\left(1 \times 2\right)} & \mathbf{I}_{\left(1\right)} & \mathbf{0}_{\left(1 \times p\right)} & \mathbf{0}_{\left(1 \times p\right)} \\ \mathbf{N}^T & \mathbf{0}_{\left(p \times 1\right)} & \mathbf{0}_{\left(p \times 2\right)} & \mathbf{0}_{\left(p \times 1\right)} & \mathbf{0}_{\left(p \times p\right)} & \mathbf{0}_{\left(p \times p\right)} \\ \end{bmatrix} \begin{bmatrix} \mathbf{x} \\ \mathbf{u} \\ \mathbf{\xi} \\ \mathbf{s} \\ \mathbf{y} \\ \mathbf{z} \end{bmatrix} &= \begin{bmatrix} \mathbf{-c} \\ \mathbf{b} \\ \mathbf{e} \end{bmatrix} \\\\ \begin{bmatrix} 2 & 0 & 1 & -1 & 0 & 0 & 1 & -1 \\ 0 & 2 & 1 & 0 & -1 & 0 & -3 & 3 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & -3 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ u_1 \\ \xi_1 \\ \xi_2 \\ s_1\\ y_1 \\ z_1 \end{bmatrix} &= \begin{bmatrix} 6 \\ 6 \\ 4 \\ 1 \end{bmatrix} \end{align}$$

 
   심플렉스법을 적용하기 위해 인위변수와 인위가격함수를 도입하여 행렬식로 나타내면 다음과 같다.
 

$$ \begin{align} \mathbf{B} \mathbf{X} + \mathbf{Y} &= \mathbf{D} \end{align}$$

 

$$ \begin{align} \begin{bmatrix} 2 & 0 & 1 & -1 & 0 & 0 & 1 & -1 \\ 0 & 2 & 1 & 0 & -1 & 0 & -3 & 3 \\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & -3 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{bmatrix} \begin{bmatrix} X_1 \\ X_2 \\ X_3 \\ X_4 \\ X_5 \\ X_6 \\ X_7 \\ X_8 \end{bmatrix} + \begin{bmatrix} Y_1 \\ Y_2 \\ Y_3 \\ Y_4 \end{bmatrix} &= \begin{bmatrix} 6 \\ 6 \\ 4 \\ 1 \end{bmatrix} \end{align}$$

 

$$ \begin{align} \omega &= \sum_{i=1}^{n+m+p}Y_i \\\\ &= Y_1 + Y_2 + Y_3 + Y_4 \\\\ &= -4X_1 -2X_3 + X_4 + X_5 - X_6 + 2X_7 - 2X_8 + 17 \end{align}$$

 

   이제 위 이차계획문제를 첨가행렬로 정리하면 다음과 같다.

 

$$ \begin{align} \begin{bmatrix} 2 & 0 & 1 & -1 & 0 & 0 & 1 & -1 & 1 & 0 & 0 & 0 & 6\\ 0 & 2 & 1 & 0 & -1 & 0 & -3 & 3 & 0 & 1 & 0 & 0 & 6\\ 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 4\\ 1 & -3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1\\ -4 & 0 & -2 & 1 & 1 & -1 & 2 & -2 & 0 & 0 & 0 & 0 & \omega-17 \end{bmatrix} \end{align}$$

 

   모든 인위변수를 비기저변수로 만들기 위해 심플렉스법을 따라 연산을 4회 수행하면 아래와 같은 첨가행렬을 얻을 수 있다. 이때 인위가격함수의 값은 0이 된다.

 

$$ \begin{align} \begin{bmatrix} 0 & 1 & 0 & 0 & 0 & \frac{1}{4} & 0 & 0 & 0 & 0 & \frac{1}{4} & -\frac{1}{4} & \frac{3}{4}\\ 0 & 0 & 1 & -\frac{3}{4} & -\frac{1}{4} & -\frac{5}{4} & 0 & 0 & \frac{3}{4} & \frac{1}{4} & -\frac{5}{4} & -\frac{1}{4} & \frac{3}{4}\\ 0 & 0 & 0 & \frac{1}{4} & -\frac{1}{4} & \frac{1}{4} & -1 & 1 & -\frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{1}{4} & \frac{5}{4}\\ 1 & 0 & 0 & 0 & 0 & \frac{3}{4} & 0 & 0 & 0 & 0 & \frac{3}{4} & \frac{1}{4} & \frac{13}{4}\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & \omega \end{bmatrix} \end{align}$$

   위 결과로부터 최적해와 해당 최적해에서 가격함수의 값을 도출하면 다음과 같다.

 

$$ \begin{align} x_1 &= \frac{13}{4},~~~~x_2 = \frac{3}{4} \\\\ u_1 &= \frac{3}{4},~~~~\xi_1 = 0,~~~~\xi_2 = 0,~~~~s_1 = 0,~~~~y_1 = 0,~~~~z_1 = \frac{5}{4} \end{align}$$

 

$$ \begin{align} f &= \left( x_1-3 \right)^2 + \left( x_2-3 \right)^2 \\\\ &= \left( \frac{13}{4}-3 \right)^2 + \left( \frac{3}{4}-3 \right)^2 \\\\ \therefore~~f &= \frac{41}{8} \end{align}$$

 
 

 

 

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

 

최적설계 | 선형계획법

최적설계 | 파이썬 기반 이차계획문제 알고리즘 qpsolvers.solve_qp

최적설계 | 제약조건 문제 수치해법(3): 순차 이차계획법 SQP

 

 

 

 

 

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