다운로드
작성자: admin 작성일시: 2018-01-27 10:06:38 조회수: 1603 다운로드: 133
카테고리: 기초 수학 태그목록:

LP 문제와 QP 문제

Linear Programming 문제

방정식이나 부등식 제한 조건을 가지는 선형 모형(linear model, linear combination)의 값을 최소화하는 문제를 LP(Linear Programming) 문제라고 한다.

$$ \begin{eqnarray} \min_x c^Tx \\ Ax = b \\ x \geq 0 \end{eqnarray} $$

LP문제는 여러가지 형태가 존재하는데 위와 같은 형태를 LP 문제의 기본형(standard form)이라고 한다. 마지막 부등식 제한 조건은 벡터 $x$의 모든 원소가 양수거나 0이 되어야 한다는 것을 의미한다.

표준형을 확장한 정규형(canonical form)은 부등식 조건을 허용한다.

$$ \begin{eqnarray} \min_x c^Tx \\ Ax \leq b \\ x \geq 0 \end{eqnarray} $$

어떤 공장에서 두가지 제품을 생상해야 한다고 하자.

  • 제품 A와 제품 B 각각 100개 이상 생산해야 한다.
  • 시간은 500시간 밖에 없다.
  • 제품 A는 생산하는데 1시간이 걸리고 제품 B는 2시간이 걸린다.
  • 특정 부품이 9800개밖에 없다.
  • 제품 A는 생산하는데 특정 부품을 4개 필요로 하고 제품 B는 생산하는데 특정 부품을 5개 필요로 한다.
  • 제품 A의 이익은 하나당 3만원이고 제품 B의 이익은 하나당 5만원이다.

제품 A와 제품 B의 생산량을 각각 $x_1, x_2$라고 하면 최소화하려는 목적함수는

$$ -3x_1 -5x_2 $$

이고 제한 조건은 다음과 같다.

$$ \begin{eqnarray} -x_1 & & &\leq& -100 \\ & & -x_2 &\leq& -100 \\ x_1 &+& 2 x_2 &\leq& 500 \\ 4x_1 &+& 5 x_2 &\leq& 9800 \\ \end{eqnarray} $$$$ x_1 \geq 0, \;\; x_2 \geq 0 $$

이를 정규형 LP문제로 표현하면 다음처럼 된다.

$$ \min_x \begin{bmatrix} -3 & -5 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} $$$$ \begin{bmatrix} -1 & 0 \\ 0 & -1 \\ 1 & 2 \\ 4 & 5 \\ \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} \leq \begin{bmatrix} -100 \\ -100 \\ 500 \\ 9800 \end{bmatrix} $$$$ \begin{bmatrix} x_1 \\ x_2 \end{bmatrix}\geq \begin{bmatrix} 0 \\ 0 \end{bmatrix} $$

scipy.optimize 패키지의 linprog 명령을 사용하면 LP 문제를 풀 수 있다. 사용법은 다음과 같다.

In [1]:
A = np.array([[-1, 0], [0, -1], [1, 2], [4, 5]])
b = np.array([-100, -100, 500, 9800])
c = np.array([-3, -5])
In [2]:
import scipy.optimize
result = sp.optimize.linprog(c, A, b)
result
Out:
     fun: -1400.0
 message: 'Optimization terminated successfully.'
     nit: 4
   slack: array([ 200., 8100.,    0.,    0.])
  status: 0
 success: True
       x: array([300., 100.])

제품 A를 300개, 제품 B를 100개 생산할 때 이익이 1400으로 최대가 됨을 알 수 있다.

Quadratic Programming 문제

방정식이나 부등식 제한 조건을 가지는 일반화된 이차형식(quadratic form)의 값을 최소화하는 문제를 QP(Quadratic Programming) 문제라고 한다.

$$ \begin{eqnarray} \arg\min_x \dfrac{1}{2}x^TQx + c^Tx \\ Ax = b \\ x \geq 0 \end{eqnarray} $$

잔차 제곱합을 최소화하기 위한 데이터 분석 모형은 부가 조건이 있는 경우 대부분 QP 문제가 된다.

사실 앞 절에서 풀었던 등식조건이 있는 최적화 문제도 사실은 QP 문제였다.

$$ \arg\min_x x_1^2 + x_2^2 $$$$ x_1 + x_2 - 1 = 0 $$

이 문제를 QP 형식으로 바꾸면 다음과 같다.

$$ \arg\min_x \dfrac{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} + \begin{bmatrix} 0 & 0 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} $$$$ \begin{bmatrix} 1 & 1 \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \end{bmatrix} = 1 $$

파이썬에서는 cvxopt라는 패키지를 사용해서 QP문제를 풀 수 있다. cvxopt를 쓸 때는 numpy 배열을 cvxopt의 matrix 자료형으로 바꿔야 하고 자료값이 정수가 아니라 부동소수점 실수가 되도록 명시해야 한다.

In [3]:
from cvxopt import matrix, solvers
In [4]:
Q = matrix(np.diag([2.0, 2.0]))
c = matrix(np.array([0.0, 0.0]))
A = matrix(np.array([[1.0, 1.0]]))
b = matrix(np.array([[1.0]]))
sol = solvers.qp(Q, c, A=A, b=b)
np.array(sol['x'])
Out:
array([[0.5],
       [0.5]])

연습 문제 6.2.6

다음 문제가 QP 문제임을 보이고 $N=3$인 경우에 대해 QP 문제의 $Q$, $c$, $A$, $b$를 각각 구하라.(문제에서 $x$는 벡터이다.)

$$ \arg\min_{a_i} \left( \sum_{i=1}^N a_i - \dfrac{1}{2}\sum_{i=1}^N\sum_{j=1}^N a_i a_j y_i y_j x_i^T x_j \right) $$$$ \sum_{i=1}^N a_i y_i = 0 $$$$ a_i \geq 0 $$

질문/덧글

아직 질문이나 덧글이 없습니다. 첫번째 글을 남겨주세요!