선형 계획 문제

선형 계획 문제란 목적 함수, 제약 조건이 함께 선형 형태로 표현되며, 다음과 같은 벡터 ${\bf x}$를 최소화하는 문제로 표현됩니다.

\min {\bf c}^T{\bf x}
\\subject \ \ {\bf A}{\bf x}\le {\bf b}

여기서 ${\bf x}$의 차원을 $n$, 제약 수를 $m$로 설정하면 ${\bf x}, {\bf c}, {\bf b}$는 $n$ 차원 벡터 , ${\bf A}$는 $m\times n$의 행렬입니다.

자동차 마커법

선형 계획 문제의 해법으로서 단체법 라는 것이 옛부터 있습니다만, 대규모 문제에서는 효율이 나쁘고, 그 쪽에서는 이번 소개하는 내점법이 이용되고 있습니다.
선형 계획의 내점법에서는, 커마커법이라고 하는 알고리즘이 꽤 유명합니다. 이 알고리즘은 소프트웨어계의 특허의 이야기에서도 잘 나오는 이야기로, 코드로 해도 매우 간단하게 쓸 수 있어, 아름다운 알고리즘이라고 말해지고 있습니다.
다음은 파이썬으로 작성된 커마커 방법의 함수입니다.

#!/usr/bin/python
#coding:utf-8
import numpy as np

def karmarkar_method(x, c, amat, b,
                     gamma=1.0, eps=1.0e-3, nloop=30):
    """
    Karmarkar法による線形計画問題の解法
    object  min z = c^T * x
    subject Ax <= b
    """
    for n in range(nloop):
        vk = b - amat * x
        gmat = amat.T * np.diag(1.0 / np.square(vk.A1)) * amat
        d = np.linalg.pinv(gmat) * c
        if np.linalg.norm(d) < eps:
            break
        hv = -amat * d
        if np.max(hv) <= 0:
            print("Unbounded!")
            x = None
            break
        alpha = gamma * np.min(vk[hv > 0] / hv[hv > 0])
        x -= alpha * d
        yield x
    #return x


if __name__ == "__main__":
    c = np.matrix([[-1.0],
                   [-1.0]])
    amat = np.matrix([[1.0, 1.0],
                      [1.0, -1.0]])
    b = np.matrix([[0.5],
                   [1.0]])
    # 描画
    from pylab import *
    ax = subplot(111, aspect='equal')
    x = np.arange(-3.0, 3.01, 0.15)
    y = np.arange(-3.0, 3.01, 0.15)
    X,Y = meshgrid(x, y)
    t = np.arange(-3.0, 3.01, 0.15)
    func = lambda x, y : c[0, 0] * x + c[1, 0] * y
    const = [lambda x : -amat[0, 0] / amat[0, 1] * x + b[0, 0] / amat[0, 1],
             lambda x : -amat[1, 0] / amat[1, 1] * x + b[1, 0] / amat[1, 1]]
    Z = func(X, Y)
    s = [const[i](t) for i in range(2)]
    pcolor(X, Y, Z)
    for i in range(2):
        ax.plot(t, s[i], 'k')
    for x in karmarkar_method(np.matrix([[-2.0], [-2.0]]), c, amat, b, gamma=0.5, eps=1.0e-3, nloop=30):
        print(x)
        ax.plot([x[0,0]], [x[1,0]],'ro')
        axis([-3, 3, -3, 3])
    show()

이번에는 그리기 위해 최소값뿐만 아니라 도중 경과도 반환하도록 하고 있습니다.
아래에 최소값으로 향하는 모습의 그림을 나타냅니다.



파란색 영역이 목적 함수가 작아지는 영역을 나타내고, 빨간 점이 파란색 방향으로 향하면서 제약이 되어 있는 선 앞에서 정지하고 있는 것을 알 수 있습니다.
현재, 내점법은 2차 계획 문제나 비선형 계획 문제에도 이용되고 있습니다만, 카마커법은 그 선구라고도 할 수 있는 알고리즘이군요.