다운로드
작성자: admin 작성일시: 2017-06-09 12:11:09 조회수: 4602 다운로드: 230
카테고리: 기초 수학 태그목록:

제한조건이 있는 최적화 문제

등식 제한조건이 있는 최적화 문제

현실의 최적화 문제에서는 여러가지 제한조건이 있는 최적화(constrained optimization) 문제가 많다. 가장 간단한 경우는 다음과 같이 등식 제한조건이 있는 경우이다.

$$ x^{\ast} = \text{arg} \min_x f(x) \;\; (x \in \mathbf{R}^N) \\ g_j(x)=0 \;\; (j=1, \ldots, M) $$

이 때는 단순히 $f(x)$를 가장 작게 하는 $x$값을 찾는게 아니라 $g_1(x) = 0, g_2(x) = 0, \cdots, g_M(x) = 0$을 모두 만족시키면서 $f(x)$를 가장 작게 하는 $x$값을 찾아야 한다.

예를 들어 목적 함수와 제한조건이 다음과 같은 경우를 생각하자.

$$ f(x_1, x_2) = x_1^2 + x_2^2 $$$$ g(x_1, x_2) = x_1 + x_2 - 1 = 0 $$

이 문제는 다음 그림처럼 $g(x_1, x_2)=0$으로 정의되는 직선상에서 가장 $f(x_1, x_2)$ 값이 작아지는 점 $(x_1^{\ast}, x_2^{\ast})$를 찾는 문제가 된다.

In [1]:
# objective function f(x) = x1^2 + x2^2
def f1(x1, x2):
    return x1 ** 2 + x2 ** 2
In [2]:
x1 = np.linspace(-5, 5, 100)
x2 = np.linspace(-3, 3, 100)
X1, X2 = np.meshgrid(x1, x2)
Y = f1(X1, X2)

# constraint function g(x) = x1 + x2 - 1 = 0
x2_g = 1 - x1
In [3]:
plt.contour(X1, X2, Y, colors="gray", levels=[0.5, 2, 8, 32])
plt.plot(x1, x2_g, 'g-')

plt.plot([0], [0], 'rP')
plt.plot([0.5], [0.5], 'ro', ms=10)

plt.xlim(-5, 5)
plt.ylim(-3, 3)
plt.xticks(np.linspace(-4, 4, 9))
plt.xlabel("$x_1$")
plt.ylabel("$x_2$")
plt.title("등식 제한조건이 있는 최적화 문제")
plt.show()

이렇게 등식 제한조건이 있는 최적화 문제는 라그랑주 승수법(Lagrange multiplier)을 사용하여 최적화 할 수 있다.

라그랑주 승수 방법에서는 $f(x)$가 아니라 제한조건인 등식에 $\lambda$라는 새로운 변수를 곱해서 더한 함수

$$h(x, \lambda) = f(x) + \sum_{j=1}^M \lambda_j g_j(x)$$

를 목적함수로 간주하여 최적화한다. 제한조건 등식 하나마다 새로운 $\lambda_i$를 추가해주어야 하므로 만약 제한조건이 $M$개이면 $\lambda_1, \cdots , \lambda_M$개의 변수가 새로 생긴 것과 같다.

확장된 목적함수 $h(x_1, x_2, \ldots , x_N, \lambda_1, \ldots , \lambda_M)$는 입력변수가 더 늘어났기 때문에 그레디언트 벡터를 영벡터로 만드는 조건이 다음처럼 $N+M$개가 된다.

$$ \begin{eqnarray} \dfrac{\partial h(x, \lambda)}{\partial x_1} &=& \dfrac{\partial f}{\partial x_1} + \sum_{j=1}^M \lambda_j\dfrac{\partial g_j}{\partial x_1} = 0 \\ \dfrac{\partial h(x, \lambda)}{\partial x_2} &=& \dfrac{\partial f}{\partial x_2} + \sum_{j=1}^M \lambda_j\dfrac{\partial g_j}{\partial x_2} = 0 \\ \vdots & & \\ \dfrac{\partial h(x, \lambda)}{\partial x_N} &=& \dfrac{\partial f}{\partial x_N} + \sum_{j=1}^M \lambda_j\dfrac{\partial g_j}{\partial x_N} = 0 \\ \dfrac{\partial h(x, \lambda)}{\partial \lambda_1} &=& g_1 = 0 \\ \vdots & & \\ \dfrac{\partial h(x, \lambda)}{\partial \lambda_M} &=& g_M = 0 \end{eqnarray} $$

이 $N+M$개의 연립 방정식을 풀면 $N+M$개의 미지수 $x_1, x_2, \ldots, x_N, , \lambda_1, \ldots , \lambda_M$를 구할 수 있다. 구한 결과에서 $x_1, x_2, \cdots, x_N$은 제한조건을 만족하는 최소값 위치를 나타낸다.

예를 들어 위에서 제시한 함수 $f$를 최소화하는 문제를 라그랑주 승수법으로 풀어보자.

$$ h = f + \lambda g = x_1^2 + x_2^2 + \lambda ( x_1 + x_2 - 1 ) $$

라그랑지 승수법을 적용하여 미분이 0인 위치를 구한다.

$$ \begin{eqnarray} \dfrac{\partial h}{\partial x_1} &=& 2{x_1} + \lambda = 0 \\ \dfrac{\partial h}{\partial x_2} &=& 2{x_2} + \lambda = 0 \\ \dfrac{\partial h}{\partial \lambda} &=& x_1 + x_2 - 1 = 0 \end{eqnarray} $$

위 방정식을 풀면

$$ x_1 = x_2 = \dfrac{1}{2}, \;\;\; \lambda = -1 $$

연습 문제 6.2.2

제한조건이

$$ x_1 + x_2 = 1 $$

일 때 목적 함수

$$ f(x) = - \log{x_1} - \log{x_2} \\ x_1, x_2 > 0 $$

를 최소화하는 $x_1$, $x_2$ 값을 라그랑주 승수법으로 계산하라.

연습 문제 6.2.3

제한조건이

$$ x_1^2 + x_2^2 = 1 $$

일 때 목적 함수

$$ f(x) = x_1 + x_2 $$

를 최소화하는 $x_1$, $x_2$ 값을 라그랑주 승수법으로 계산하라.

SciPy의 optimize 서브패키지에서는 제한조건이 있는 최적화 문제를 풀기위한 fmin_slsqp 명령을 제공한다. fmin_slsqp 명령은 목적함수와 초기값, 그리고 제한조건 함수를 인수로 받는데 함수는 배열인 인수를 받도록 구현되어야 하고 제한조건 함수의 경우에는 항상 리스트(list)로 만들어서 eqcons 인수로 넣어주어야 한다.

In [4]:
def f1array(x):
    return x[0] ** 2 + x[1] ** 2


def eq_constraint(x):
    return x[0] + x[1] - 1


sp.optimize.fmin_slsqp(f1array, np.array([1, 1]), eqcons=[eq_constraint])
Optimization terminated successfully.    (Exit mode 0)
            Current function value: 0.5000000000000002
            Iterations: 2
            Function evaluations: 8
            Gradient evaluations: 2
Out:
array([0.5, 0.5])

라그랑주 승수의 의미

만약 등식 제한조건 $g_i$이 있는가 없는가에 따라 최적화 해의 위치가 달라진다면 이 등식 제한조건에 대응하는 라그랑주 승수 $\lambda_i$는 0이 아닌 값이어야 한다.

$$ \lambda_i \neq 0 $$

$\lambda_i = 0$이라면 원래의 문제와 제한조건이 있는 문제가 같은 문제가 되어 최적화 해의 위치도 같게 나오기 때문이다.

부등식 제한조건이 있는 최적화 문제

이번에는 다음과 같이 $g(x) \leq 0$ 이라는 부등식(inequality) 제한조건이 있는 최적화 문제를 생각하자

$$ x^{\ast} = \text{arg} \min_x f(x) \;\; (x \in \mathbf{R}^N) \\ g_j(x) \leq 0 \;\; (j=1, \ldots, M) $$

이렇게 부등식 제한조건이 있는 최적화 문제도 이 경우에도 라그랑지 승수 방법과 마찬가지로 $f$가 아닌

$$h(x, \lambda) = f(x) + \sum_{j=1}^M \lambda_j g_j(x)$$

를 목적함수로 보고 최적화를 한다.

다만 이 경우, 최적화 해의 필요조건은 방정식 제한조건이 있는 최적화 문제 다르게 KKT(Karush-Kuhn-Tucker) 조건이라고 하며 다음처럼 3개의 조건으로 이루어진다.

(1) 모든 독립 변수 $x_1, x_2, \ldots , x_N$에 대한 미분값이 0

$$ \dfrac{\partial h(x, \lambda)}{\partial x_i} = 0 $$

(2) 모든 라그랑지 승수 $\lambda_1, \ldots , \lambda_M$과 제한조건 부등식($\lambda$에 대한 미분값)의 곱이 0

$$ \lambda_j \cdot \dfrac{\partial h(x, \lambda)}{\partial \lambda_j} = \lambda_j \cdot g_j = 0 $$

(3) 음수가 아닌 라그랑지 승수

$$ \lambda_j \geq 0 $$

여기에서 마지막 조건은 KKT 조건이 실제로 부등식 제한조건이 있는 최적화 문제와 같은 문제임을 보장(strong duality)하기 위한 조건이다.

첫번째 조건은 방정식 제한조건의 경우와 같다. 변수 $x$들에 대한 미분값은 0이어야 한다.

두번째 조건을 보면 확장된 목적함수를 라그랑주 승수로 미분한 값은 변수 $x$들에 대한 미분값과는 달리 반드시 0이 될 필요는 없다는 것을 알 수 있다. 미분값이 0이 되는 대신 라그랑지 승수 $\lambda$ 값 자체가 0이 되어도 된다.

다음 그림은 부등식 제한조건을 가지는 최적화의 예이다.

목적 함수는

$$ f(x_1, x_2) = x_1^2 + x_2^2 $$

왼쪽 그림은 부등식 제한조건이

$$ g(x_1, x_2) = x_1 + x_2 - 1 \leq 0 $$

오른쪽 그림은 부등식 제한조건이

$$ g(x_1, x_2) = -x_1 - x_2 + 1 \leq 0 $$

인 경우이다. 제한조건을 만족하는 영역을 어둡게 표시하였다.

In [5]:
plt.figure(figsize=(13, 7))
ax1 = plt.subplot(121)
plt.contour(X1, X2, Y, colors="gray", levels=[0.5, 2, 8])
plt.plot(x1, x2_g, 'g-')
ax1.fill_between(x1, -20, x2_g, alpha=0.5)
plt.plot([0], [0], 'ro', ms=10)
plt.xlim(-3, 3)
plt.ylim(-5, 5)
plt.xticks(np.linspace(-4, 4, 9))
plt.yticks(np.linspace(-5, 5, 11))
plt.xlabel("$x_1$")
plt.ylabel("$x_2$")
plt.title("최적해가 부등식과 관계없는 경우")
ax2 = plt.subplot(122)
plt.contour(X1, X2, Y, colors="gray", levels=[0.5, 2, 8])
plt.plot(x1, x2_g, 'g-')
ax2.fill_between(x1, 20, x2_g, alpha=0.5)
plt.plot([0.5], [0.5], 'ro', ms=10)
plt.xlabel("x_1")
plt.xlim(-3, 3)
plt.ylim(-5, 5)
plt.xticks(np.linspace(-4, 4, 9))
plt.yticks(np.linspace(-5, 5, 11))
plt.xlabel("$x_1$")
plt.ylabel("$x_2$")
plt.title("최적해가 부등식에 의해 결정되는 경우")
plt.suptitle("부등식 제한조건이 있는 최적화 문제")
plt.show()

위 예제에서 보듯이 부등식 제한조건이 있는 최적화 문제를 풀면 그 제한조건은 실제로 다음 두 가지 경우의 하나가 되어 버린다.

  • 최적화 결과에 전혀 영향을 주지 않는 쓸모없는 제한조건
  • 최적화 결과에 영향을 주는 등식(equality)인 제한조건

부등식 문제로 시작했지만 결과는 등식 문제를 푸는 것과 같아진다.

KKT조건을 좀 더 자세히 들여다 보자. $x^{\ast}, \lambda^{\ast}$는 KKT 조건을 풀어서 구한 최적해의 값이다.

$$ \lambda^{\ast} = 0 \;\; \text{또는} \;\; g(x^{\ast}) = 0 $$

만약 $g_i = 0$이면 이 조건은 부등식 제한조건이 아닌 등식 제한조건이 된다. 그리고 등식 제한조건에서 말한 바와 같이 (이 제한조건이 있으나 없으나 해가 바뀌지 않는 특수한 경우를 제외하면) 라그랑주 승수는 0이 아닌 값을 가진다. $$ g_i = 0 \;\; \rightarrow \;\; \lambda_i \neq 0 \; (\lambda_i > 0)$$

반대로 $g_i \neq 0 \; (g_i < 0)$이면 해가 $g_i$가 표현하는 곡선으로부터 떨어져 있기 때문에 부등식 제한조건이 아무런 의미가 없어진다. 즉, 제한조건이 있을 때와 없을 때의 해가 같다. 따라서 목적함수 $h(x, \lambda)$는 $\lambda_ig_i (g_i \neq 0)$ 항이 있으나 없으나 상관없이 같은 해를 가진다. 따라서 $\lambda_i=0$이 된다. $$ g_i \neq 0 \;\; \rightarrow \;\; \lambda_i = 0 $$

따라서 부등식 제한조건이 있는 최적화 문제는 각 제한조건에 대해 위의 두 가지 경우를 가정하여 각각 풀어보면서 최적의 답을 찾는다.

다음은 복수의 부등식 제한조건이 있는 또다른 2차원 최적화 문제의 예다.

$$ \text{arg} \min_x \; (x_1-4)^2 + (x_2-2)^2 $$$$ g_1(x) = x_1 + x_2 - 1\leq 0 $$$$ g_2(x) = -x_1 + x_2 - 1\leq 0 $$$$ g_3(x) = -x_1 - x_2 - 1\leq 0 $$$$ g_4(x) = x_1 - x_2 - 1\leq 0 $$

이 4개의 제한조건은 다음과 같은 하나의 부등식으로 나타낼 수도 있다.

$$ g(x) = \left\vert\, x_1 \right\vert + \left\vert\, x_2 \right\vert - 1 = \sum_{i=1}^{2} \left\vert\, x_i \right\vert - 1 \leq 0 $$
In [6]:
def f2plt(x1, x2):
    return np.sqrt((x1 - 4) ** 2 + (x2 - 2) ** 2)


x1 = np.linspace(-2, 5, 100)
x2 = np.linspace(-1.5, 3, 100)
X1, X2 = np.meshgrid(x1, x2)
Y = f2plt(X1, X2)

plt.contour(X1, X2, Y, colors="gray",
            levels=np.arange(0.5, 5, 0.5) * np.sqrt(2))

ax = plt.gca()
x12 = np.linspace(-1, 0, 10)
x13 = np.linspace(0, 1, 10)
ax.fill_between(x12, x12 + 1, -1 - x12, color='g', alpha=0.5)
ax.fill_between(x13, x13 - 1, 1 - x13, color='g', alpha=0.5)

plt.plot(1, 0, 'ro', ms=20)

plt.xlim(-2, 5)
plt.ylim(-1.5, 3)
plt.xticks(np.linspace(-2, 5, 8))
plt.yticks(np.linspace(-1, 3, 5))
plt.xlabel("$x_1$")
plt.ylabel("$x_2$")
plt.title("$|x_1| + |x_2| \leq 1$ 제한조건을 가지는 최적화 문제")
plt.show()

fmin_slsqp 명령은 이렇게 부등식 제한조건이 있는 경우에도 사용할 수 있다. 단 ieqcons 인수에 들어가는 부등호의 부호가 위에서 서술한 것과 달리 0 또는 양수이어야 한다. ($g \geq 0$)

In [7]:
def f2(x):
    return np.sqrt((x[0] - 4) ** 2 + (x[1] - 2) ** 2)


def ieq_constraint(x):
    return np.atleast_1d(1 - np.sum(np.abs(x)))


sp.optimize.fmin_slsqp(f2, np.array([0, 0]), ieqcons=[ieq_constraint])
Optimization terminated successfully.    (Exit mode 0)
            Current function value: 3.6055512804550336
            Iterations: 11
            Function evaluations: 77
            Gradient evaluations: 11
Out:
array([9.99999982e-01, 1.79954011e-08])

연습 문제 6.2.4

위 문제에서 최적해가

$$ x_1 = 1, \; x_2 = 0 $$

이라는 사실을 이용하여 라그랑지 승수 $\lambda_1$, $\lambda_2$, $\lambda_3$, $\lambda_4$ 중 어느 값이 0이 되는지 알아내라.

연습 문제 6.2.5

위 문제에서 제한조건을 다음과 같이 바꾼다.

$$ g(x) = \left\vert\, x_1 \right\vert + \left\vert\, x_2 \right\vert - k = \sum_{i=1}^{2} \left\vert\, x_i \right\vert - k \leq 0 $$

여기에서 $k$의 값을 0.1 부터 10까지 다양하게 변화시키면서 최적화의 해가 어떻게 달라지는지 살펴보라.

질문/덧글

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