ラグランジュの未定乗数法～不等式制約条件

1 概要
2 例題
- 2.1 停留点が制約条件の範囲内の場合
- 2.2 停留点が制約条件の範囲外の場合
3 λの符号について
- 3.1 有界でない例
4 KKT条件
5 参考サイト

概要

不等式制約条件を持つLagrangeの未定乗数法は以下のように表示される(等式条件の場合はこちらを参照)。

(1) $\begin{align*} & \mathrm{maximize/minimize} \quad f(\boldsymbol{x}) \\ & \mathrm{subject~to} \quad g(\boldsymbol{x}) \le 0 \end{align*}$

この場合、停留点が制約条件の範囲外にあれば等式条件と同じ問題となり、範囲内にあれば制約条件なしの通常の極値問題となる。

例題

停留点が制約条件の範囲内の場合

停留点が制約条件の境界内にある次のような問題を考える。

(2) $\begin{align*} & \mathrm{minimize} \quad f(x, y) = \left(x - \frac{1}{2} \right)^2 + \left(y - \frac{1}{2} \right)^2 +10 \\ & \mathrm{subject~to} \quad g(x, y) =x^2 + y^2 - 4\le 0 \\ &L(x, y, \lambda) = (x - 1)^2 + (y - 1)^2 + 10 - \lambda (x^2 + y^2 - 4) \end{align*}$

この問題を解くのに、まず停留点が制約条件の範囲内にあるかをチェックする。上の式で $\lambda=0$ と置いて最適化問題を解く。

(3) $\begin{gather*} \frac{\partial f}{\partial x} = 2\left(x - \frac{1}{2} \right) = 0 \\ \frac{\partial f}{\partial y} = 2\left(y - \frac{1}{2} \right) = 0 \\ \Downarrow \\ x = y = \frac{1}{2} \end{gather*}$

上記の解は制約条件 $g(x, y) \le 0$ を満足する。この停留点が極値だということが分かっていれば、これが問題の解ということになる。

import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D

def f(x, y, a, b):
    return (x - a)**2 + (y - b)**2 + 10

a, b = 1/2, 1/2
x = np.linspace(-3, 6)
y = np.linspace(-3, 6)
x, y = np.meshgrid(x, y)

t = np.linspace(-np.pi, np.pi)
xg = 2 * np.cos(t)
yg = 2 * np.sin(t)

x4min = 6 / np.sqrt(13)
y4min = 4 / np.sqrt(13)
fmin = f(x4min, y4min, a, b)
x4max = - 6 / np.sqrt(13)
y4max = - 4 / np.sqrt(13)
fmax = f(x4max, y4max, a, b)

fig = plt.figure()
ax = fig.add_subplot(111, projection='3d')

ax.plot_surface(x, y, f(x, y, a, b), alpha=0.5)
ax.plot(xg, yg, 0, c='r')
ax.plot(xg, yg, f(xg, yg, a, b), c='r', linestyle='dashed')

ax.scatter(a, b, 10, c='b')
ax.scatter(a, b, 0, c='b')
ax.plot([a, a], [b, b], [0, 10], c='b', linestyle='dotted')

ax.plot([x4min, x4min], [y4min, y4min], [0, fmin], c='r', linestyle='dotted')
ax.plot([x4max, x4max], [y4max, y4max], [0, fmax], c='r', linestyle='dotted')

ax.set_xlabel("x")
ax.set_ylabel("y")

print("f_max={:8.4f}, for x={:7.4f}, y={:7.4f}".format(fmax, x4max, y4max))
print("f_min={:8.4f}, for x={:7.4f}, y={:7.4f}".format(fmin, x4min, y4min))

plt.show()

import numpy as np

import matplotlib.pyplot as plt

from mpl_toolkits.mplot3d import Axes3D

def f(x, y, a, b):

return (x - a)**2 + (y - b)**2 + 10

a, b = 1/2, 1/2

x = np.linspace(-3, 6)

y = np.linspace(-3, 6)

x, y = np.meshgrid(x, y)

t = np.linspace(-np.pi, np.pi)

xg = 2 * np.cos(t)

yg = 2 * np.sin(t)

x4min = 6 / np.sqrt(13)

y4min = 4 / np.sqrt(13)

fmin = f(x4min, y4min, a, b)

x4max = - 6 / np.sqrt(13)

y4max = - 4 / np.sqrt(13)

fmax = f(x4max, y4max, a, b)

fig = plt.figure()

ax = fig.add_subplot(111, projection='3d')

ax.plot_surface(x, y, f(x, y, a, b), alpha=0.5)

ax.plot(xg, yg, 0, c='r')

ax.plot(xg, yg, f(xg, yg, a, b), c='r', linestyle='dashed')

ax.scatter(a, b, 10, c='b')

ax.scatter(a, b, 0, c='b')

ax.plot([a, a], [b, b], [0, 10], c='b', linestyle='dotted')

ax.plot([x4min, x4min], [y4min, y4min], [0, fmin], c='r', linestyle='dotted')

ax.plot([x4max, x4max], [y4max, y4max], [0, fmax], c='r', linestyle='dotted')

ax.set_xlabel("x")

ax.set_ylabel("y")

print("f_max={:8.4f}, for x={:7.4f}, y={:7.4f}".format(fmax, x4max, y4max))

print("f_min={:8.4f}, for x={:7.4f}, y={:7.4f}".format(fmin, x4min, y4min))

plt.show()

停留点が制約条件の範囲外の場合

今度は目的関数の停留点が制約条件の境界の範囲外にある問題を考えてみる。

(4) $\begin{align*} & \mathrm{minimize} \quad f(x, y) = (x - 3)^2 + (y-2)^2 +10 \\ & \mathrm{subject~to} \quad g(x, y) =x^2 + y^2 - 4\le 0 \\ &L(x, y, \lambda) = (x - 3)^2 + (y - 2)^2 + 10 - \lambda (x^2 + y^2 - 4) \end{align*}$

まず停留点が境界条件の範囲内にあるとして、 $\lambda = 0$ として問題を解いてみる。

(5) $\begin{gather*} \frac{\partial f}{\partial x} = 2(x - 3) = 0 \\ \frac{\partial f}{\partial y} = 2(y - 2) = 0 \\ \Downarrow \\ x = 3 , \; y = 2 \end{gather*}$

ところがこの解は制約条件 $g(x, y) \le 0$ を満足しない。解は制約条件の境界上にあることになるので、 $\lambda \ne 0$ の条件でLagrangeの未定乗数法によって解く。

(6) $\begin{gather*} \left\{ \begin{array}{c} \dfrac{\partial L}{\partial x} = 2(x - 3) - 2\lambda x = 0\\ \\ \dfrac{\partial L}{\partial y} = 2(y - 2) - 2\lambda y = 0\\ \\ \dfrac{\partial L}{\partial \lambda} = -(x^2 + y^2 - 4) = 0 \end{array} \right. \quad \Rightarrow \quad \left\{ \begin{array}{c} (1 - \lambda) x = 3\\ (1 - \lambda) y = 2\\ x^2 + y^2 = 4 \end{array} \right. \end{gather*}$

$\lambda \ne 1$ として、

(7) $\begin{gather*} x = \frac{3}{1 - \lambda} , \; y = \frac{2}{1 - \lambda} , \; 1 - \lambda = \pm \frac{\sqrt{13}}{2} \\ \left\{ \begin{array}{rll} \lambda &= 1 \mp \dfrac{\sqrt{13}}{2} & \fallingdotseq -0.8028 , \; 2.8028 \\ x &= \pm \dfrac{6}{\sqrt{13}} & \fallingdotseq 1.6641 , \; -1.6641 \\ y &= \pm \dfrac{4}{\sqrt{13}} & \fallingdotseq 1.1094 , \; -1.1094 \\ f(x, y) &= 17 \pm \dfrac{52}{\sqrt{13}} & \fallingdotseq 12.5778 , \; 41.4222 \end{array} \right. \end{gather*}$

いずれの解も制約条件 $g(x, y)=0$ を満たしており、このうち最小値となる解と目的関数の値は以下の通り。

(8) $\begin{gather*} (x, y, f(x, y)) = \left( \frac{6}{\sqrt{13}} , \frac{4}{\sqrt{13}} , 17 - \dfrac{52}{\sqrt{13}} \right) \fallingdotseq (1,6641, 1.1094, 12.5778) \end{gather*}$

λの符号について

有界でない例

以下、制約条件が $g(x, y) \le 0$ で有界でない場合を考える。

最小化問題でgradientが逆向き(極値が制約条件外)

まず、目的関数を最小化する場合を考える。以下の問題では目的関数fの極値が制約条件の範囲外にあり、fとgのgradientがgの境界上で逆向きになる。

(9) $\begin{align*} &\mathrm{minimize} \quad f(x, y) = (x - 1)^2 + (y - 1)^2 \\ &\mathrm{subject~to} \quad g(x, y) = x + y \le 0 \\ &L(x, y, z) = (x - 1)^2 + (y - 1)^2 - \lambda(x + y) \end{align*}$

停留点は制約条件の境界上となることから、λ≠0として未定乗数法で解いて以下を得る。λ<0となり、gradientが逆向きであることが現れている(∇f = λ∇g)。

(10) $\begin{equation*} x = 0, \; y = 0, \; \lambda = -2 \end{equation*}$

最小化問題でgradientが同じ向き(極値が制約条件内)

次の問題では極値が制約条件の範囲内にあり、fとgのgradientがgの境界上で同じ向きとなる。

(11) $\begin{align*} &\mathrm{minimize} \quad f(x, y) = (x + 1)^2 + (y + 1)^2 \\ &\mathrm{subject~to} \quad g(x, y) = x + y \le 0 \\ &L(x, y, z) = (x + 1)^2 + (y + 1)^2 - \lambda(x + y) \end{align*}$

この場合、fの極値は制約条件(緑色)の範囲内にあり、fとgのgradientがgの境界上で同じ向きになる。停留点は制約条件内にあることから、λ=0として制約条件の効果をなくし、単純にfの極値問題を解いて以下を得る(∇f =0)。

(12) $\begin{equation*} x = -1, \; y = -1, \; \lambda = 0 \end{equation*}$

最大化問題でgradientが同じ向き(極値が制約条件範囲外)

次に目的関数を最大化する場合を考える。以下の問題では目的関数fの極値が制約条件の範囲外にあり、fとgのgradientがgの境界上で同じ向きになる。

(13) $\begin{align*} &\mathrm{minimize} \quad f(x, y) = - (x - 1)^2 - (y - 1)^2 \\ &\mathrm{subject~to} \quad g(x, y) = x + y \le 0 \\ &L(x, y, z) = - (x - 1)^2 - (y - 1)^2 - \lambda(x + y) \end{align*}$

停留点は制約条件の境界上となることから、λ≠0として未定乗数法で解いて以下を得る。λ>0となり、gradientが同じ向きであることが現れている(∇f = λ∇g)。

(14) $\begin{equation*} x = 0, \; y = 0, \; \lambda = 2 \end{equation*}$

最大化問題でgradientが逆向き(極値が制約条件範囲内)

次の問題では極値が制約条件の範囲内にあり、fとgのgradientがgの境界上で逆向きとなる。

(15) $\begin{align*} &\mathrm{minimize} \quad f(x, y) = - (x + 1)^2 - (y + 1)^2 \\ &\mathrm{subject~to} \quad g(x, y) = x + y \le 0 \\ &L(x, y, z) = - (x + 1)^2 - (y + 1)^2 - \lambda(x + y) \end{align*}$

この場合、fの極値は制約条件(緑色)の範囲内にあり、fとgのgradientがgの境界上で逆向きになる。停留点は制約条件内にあることから、λ=0として制約条件の効果をなくし、単純にfの極値問題を解いて以下を得る(∇f =0)。

(16) $\begin{equation*} x = -1, \; y = -1, \; \lambda = 0 \end{equation*}$

λの符号について

以上の4つのパターンをまとめると、以下のようになる。

	∇fと∇gが同方向	∇fと∇gが逆方向
fを最小化	制約条件内 λ = 0, g(x, y) < 0	制約条件外(境界上) λ < 0, g(x, y) = 0
fを最大化	制約条件外(境界上) λ > 0, g(x, y) = 0	制約条件内 λ = 0, g(x, y) < 0

たとえばfを最大化する場合の条件をまとめて書くと、

(17) $\begin{equation*} g(x, y) \le 0 , \quad \lambda \ge 0 , \quad \lambda g(x, y) = 0 \end{equation*}$

これがKKT条件と呼ばれるもの。

ただし上記の場合分けは、最小化問題か最大化問題かによってλの符号が異なっている。さらに未定乗数を求める関数をここではL = f − λgとしたが、L = f + λgとしている場合もあり、このときはまたλの不等号が逆になってややこしい。

KKT条件では、一般にλ ≥ 0とされるが、元の問題が最小化か最大化か、不等式制約条件を正とするか負とするか、未定乗数法の関数形がf − λgかf + λgか、設定条件によってこの符号が反転する。逆に言えば、もともとのKKT条件がλ ≥ 0と示されているので、最小化(あるいは最大化)に対して−∇gとしたり、L = f ± gを使い分けたり、g ⋚ 0の設定を選んだりしている節がある。

KKT条件

不等式制約条件付きの最適化問題において、Lagrangeの未定乗数法を適用する場合の条件は、一般にKKT条件(Karush-Kuhn-Tucker condition)として示されるが、問題設定の形式を明示する必要がある(あるいは最小化問題と最大化問題でλの不等号を反転させた形で示す)。

最大化問題を基本とし、不等式制約条件は0又は負とする。ラグランジュ関数の制約条件項の符号はマイナスとする。

(18) $\begin{align*} &\mathrm{maximize} \quad f(\boldsymbol{x}) \\ &\mathrm{subject~to} \quad g(\boldsymbol{x}) \le 0 \\ &\rightarrow \; \mathrm{maximize} \quad L(\boldsymbol{x}, \lambda) = f(\boldsymbol{x}) - \lambda g(\boldsymbols{x}) \end{align*}$

この時、ラグランジュ関数を最大化するKKT条件は

(19) $\begin{gather*} g(x, y) \le 0 \\ \lambda \ge 0\\ \lambda g(x, y) = 0 \end{gather*}$

最小化問題の場合には、最大化問題となるように目的関数を反転する。

(20) $\begin{align*} &\mathrm{minimize} \quad f(\boldsymbol{x}) \\ &\mathrm{subject~to} \quad g(\boldsymbol{x}) \le 0 \\ &\rightarrow \; \mathrm{maximize} \quad L(\boldsymbol{x}, \lambda) = - f(\boldsymbol{x}) - \lambda g(\boldsymbols{x}) \end{align*}$

あるいは元のままの関数形として、最小化問題とKKT条件を以下のように設定してもよい。

(21) $\begin{gather*} \mathrm{minimize} \quad L(\boldsymbol{x}, \lambda) = f(\boldsymbol{x}) - \lambda g(\boldsymbols{x}) \\ g(x, y) \le 0 \\ \lambda \le 0\\ \lambda g(x, y) = 0 \end{gather*}$

参考サイト

本記事をまとめるにあたって、下記サイトが大変参考になったことに感謝したい。

TauStation

ラグランジュの未定乗数法～不等式制約条件

概要

例題

停留点が制約条件の範囲内の場合

停留点が制約条件の範囲外の場合

λの符号について

有界でない例

最小化問題でgradientが逆向き(極値が制約条件外)

最小化問題でgradientが同じ向き(極値が制約条件内)

最大化問題でgradientが同じ向き(極値が制約条件範囲外)

最大化問題でgradientが逆向き(極値が制約条件範囲内)

λの符号について

KKT条件

参考サイト

コメントを残すコメントをキャンセル

概要

例題

停留点が制約条件の範囲内の場合

停留点が制約条件の範囲外の場合

λの符号について

有界でない例

最小化問題でgradientが逆向き(極値が制約条件外)

最小化問題でgradientが同じ向き(極値が制約条件内)

最大化問題でgradientが同じ向き(極値が制約条件範囲外)

最大化問題でgradientが逆向き(極値が制約条件範囲内)

λの符号について

KKT条件

参考サイト

コメントを残す コメントをキャンセル

コメントを残すコメントをキャンセル