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

5.3 선형계획법 문제와 이차계획법 문제

5.1절과 5.2절에서는 일반적인 최적화 문제를 다루었다. 하지만 데이터 분석에서는 목적함수나 제한조건이 특정한 수식은 최적화 문제가 많이 등장한다. 이 절에서는 그 중 선형 계획법과 이차계획법을 소개한다.

선형계획법 문제

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

선형계획법 문제의 목적함수는

$$ \begin{align} \arg\min_x c^Tx \tag{5.3.1} \end{align} $$

이고 선형 연립방정식으로 된 등식 제한조건

$$ \begin{align} Ax = b \tag{5.3.2} \end{align} $$

과 변수값이 모두 음수가 아니어야하는 부등식 제한조건

$$ \begin{align} x \geq 0 \tag{5.3.3} \end{align} $$

를 동시에 가진다.

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

$$ \begin{align} \arg\min_x c^Tx \tag{5.3.1} \end{align} $$$$ \begin{align} Ax \leq b \tag{5.3.2'} \end{align} $$$$ \begin{align} x \geq 0 \tag{5.3.3} \end{align} $$

예제

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

  • 제품 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{aligned} -x_1 & & &\leq& -100 \\ & & -x_2 &\leq& -100 \\ x_1 &+& 2 x_2 &\leq& 500 \\ 4x_1 &+& 5 x_2 &\leq& 9800 \\ \end{aligned} $$$$ x_1 \geq 0, \;\; x_2 \geq 0 $$

이를 정규형 선형계획법 문제로 표현하면 다음과 같다.

$$ \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 명령을 사용하면 선형계획법 문제를 풀 수 있다. 사용법은 다음과 같다.

linprog(c, A, b)
  • c: 목적함수의 계수 벡터
  • A: 등식 제한조건의 계수 행렬
  • b: 등식 제한조건의 상수 벡터

예제

다음 코드는 위 예제 선형계획법 문제를 사이파이로 계산하는 코드다.

In [1]:
import scipy.optimize

A = np.array([[-1, 0], [0, -1], [1, 2], [4, 5]])
b = np.array([-100, -100, 500, 9800])
c = np.array([-3, -5])

result = sp.optimize.linprog(c, A, b)
result
Out:
     con: array([], dtype=float64)
     fun: -1400.0
 message: 'Optimization terminated successfully.'
     nit: 3
   slack: array([ 200.,    0.,    0., 8100.])
  status: 0
 success: True
       x: array([300., 100.])

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

CVXPY를 이용한 선형계획법 문제 계산

CVXPY 또는 PuLP와 같은 파이썬 패키지를 사용하면 선형계획법 문제의 계수 행렬 $A$, $b$, $c$를 직접 숫자로 정의하지 않고 심볼로 정의하여 더 직관적인 파이썬 코드를 만들 수 있다. 다음 코드는 위에서 풀었던 예제를 CVXPY로 다시 계산한 것이다. 다만 이 방법은 변수나 조건의 수가 아주 많을 경우에는 심볼릭 연산으로 인해 속도가 느려질 수 있다.

In [2]:
import cvxpy as cp

# 변수의 정의
a = cp.Variable()  # A의 생산량
b = cp.Variable()  # B의 생산량

# 조건의 정의
constraints = [
    a >= 100,  # A를 100개 이상 생산해야 한다.
    b >= 100,  # B를 100개 이상 생산해야 한다. 
    a + 2 * b <= 500, # 500시간 내에 생산해야 한다.
    4 * a + 5 * b <= 9800,  # 부품이 9800개 밖에 없다.
]

# 문제의 정의
obj = cp.Maximize(3 * a + 5 * b)
prob = cp.Problem(obj, constraints)

# 계산
prob.solve() 

# 결과
print("상태:", prob.status)
print("최적값:", a.value, b.value)
상태: optimal
최적값: 299.99999999999983 100.00000000000001

이차계획법 문제

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

이차계획법 문제의 목적함수는

$$ \begin{align} \dfrac{1}{2}x^TQx + c^Tx \tag{5.3.4} \end{align} $$

이고 등식 제한조건과 부호 제한조건은 선형계획법 문제와 같다.

$$ \begin{align} Ax = b \tag{5.3.5} \end{align} $$$$ \begin{align} x \geq 0 \tag{5.3.6} \end{align} $$

잔차 제곱합을 최소화하는 예측 모형에 추가적인 제한조건이 있으면 이차계획법 문제가 된다.

예제

앞 절에서 풀었던 등식 제한조건이 있는 최적화 문제도 사실은 이차계획법 문제다.

$$ \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를 이용한 이차계획법 문제 계산

CvxOpt라는 패키지를 사용하면 이차계획법 문제를 풀 수 있다. CvxOpt를 쓸 때는 NumPy의 ndarray 배열을 CvxOpt 전용의 matrix 자료형으로 바꿔야 한다. 또 정수 자료형을 사용하지 못하므로 항상 부동소수점 실수가 되도록 명시해야 한다.

In [3]:
from cvxopt import matrix, solvers

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]])

연습 문제 5.3.1

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

$$ \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 $$

질문/덧글

LP문제에서 rlaw*** 2018년 12월 4일 8:43 오후

어떤 공장에서 두가지 제품을 "생상"해야 한다고 하자. => "생산" 같습니다.

수고하십시오.

답변: LP문제에서 dono*** 2018년 12월 5일 1:17 오후

수정하였습니다. 지적 감사합니다.

LP 문제에 대해, PuLP package의 사용을 추천합니다. skit*** 2019년 5월 10일 9:57 오전

LP 문제의 경우, 실질적인 문제 해결을 위해서는 linprog 대신 pulp를 사용하는 것을 추천합니다.

LP문제는 복잡한 제약식과 많은 변수갖는 경우가 많아,
모든 제약식을 A, b, c로 깔끔하게 관리하는 것은 무척 어려운 일입니다.

그래서, 현장에서 (주로 상용 software)들은 symbolic하게 변수생성, 목적식 추가, 제약식 추가 등의
함수를 제공하는 프로그램을 선호합니다.

LP의 사용에 가장 적합한 무료 solver로 PuLP만한 것이 없다고 생각됩니다.

답변: LP 문제에 대해, PuLP package의 사용을 추천합니다. 관리자 2019년 5월 11일 3:12 오후

학교에서 예제로 몇 십개 정도의 변수를 사용할 때는 상관없지만 실무에서는 변수의 수가 수억개 이상이 되는 경우가 많습니다.
이런 경우 pulp나 cvxpy같이 파이썬 객체로 변수나 제약조건 하나 하나 만드는 패키지는 객체 생성 시간 및 메모리 관리 때문에 사용할 수 없습니다.
실제로 1억개 수준 문제를 샘플로 만들어보시면 알 수 있습니다.

답변: 답변: LP 문제에 대해, PuLP package의 사용을 추천합니다. skit*** 2019년 5월 13일 10:55 오전

제 설명이 부족했군요.
우선 현실의 대형 문제를 풀기위해서는, pre-processing, 다양한 heuristics 및 기타 메모리 최적화가 필수적이기 때문에, 당연하게도 상용 solver를 사용해야 겠지요.
ilog가 cplex에 concert technology를 도입하기 전에, 대부분의 초기 lp solver들은 linprog() 처럼, 프로그래머가 직접, c, A, b를 관리해 주어야 했습니다.
그것도 메모리 최적화를 위해, A matrix를 nonzero coefficient만 관리해 야 하기 때문에 그 어려움은 문제가 복잡해 질 수록 더해지죠.
물론 c언어의 포인터를 사용해서 쓸사람은 다 사용했습니다만, 그 관리의 어려움은 말할 필요가 없겠죠.

요즘 lp solver들은 모두 조금씩은 다릅니다만, 사용자가 직접 A matrix를 제어하지 않습니다.
LP/IP의 문제에 있어 해찾기의 속도 만큼이나 문제 관리의 편이성이 중요하다 생각하기 때문입니다.

이점에서 python의 장점이 나타난다 봅니다.
Gurobi 와 같은 상용 solver들도 표준 interface언어로 python을 사용합니다. 물론 core logic은 c언어로 구현되어 있어 속도를 희생시키지 않으면서, interface는 선형 제약식의 표현에 편리한 python문법을 차용하는 것이죠.
PuLP를 사용하는 것도 비슷한 전략입니다. PuLP는 직접 LP/IP를 풀수도 있지만, 대형 문제를 풀 때, 주요 free/commercial LP solver들을 불러 사용할 수 있기 때문입니다.
특히, Free solver로 가장 빠르다고 알려진, GLPK, LP_Solve를 PuLP에서 불러 사용할 수 있습니다.
직접 test해보지 않았지만 scipy.optimize가 이들보다 빠르지는 않을 것이라 생각합니다.

제가 PuLP사용을 추천한 이유는, 현장에서 scipy.optimize를 사용하는 사례를 본적이 없기 때문입니다.
lp solver는 사실 프로그래머의 선호가 아닌 프로젝트의 예산, 고객의 software 유지비에 대한 생각에 따라 결정되는 것이고,
solver는 그 때 그 때 선택하여 사용할 수 있어야 하며,
이러기위해서는 symbolic하게 LP/IP Formulation을 관리하는 프로그래머의 능력이 중요합니다.

------------------------------------------------------------------------------------------------------------------------
감기 약기운이 돌아 두서없이 장황한 글이 되어버려, 원래의 취지가 뭐였는지도 모르겠네요.
이곳의 내용을 제 수업에서 학생들에 소개하면서 많은 도움을 받습니다.
그러나 보니 좀 제 입맛에 맞는 방향을 추천하게되었네요.
이곳에 글을 남겨서 저자분에게 짐을 늘릴려는 의도는 아닙니다.
최적화에 관심있는 학생들이 이곳에서 좀더 유용한 정보를 얻어기갈 바라는 마음입니다.
감사합니다.

답변: 답변: 답변: LP 문제에 대해, PuLP package의 사용을 추천합니다. 관리자 2019년 5월 14일 9:09 오전

코멘트 감사합니다. 의견을 반영하여 파이썬 객체 구조로 LP를 푸는 예제 코드를 추가하였습니다.