数理計画法

  1. 1. 第1章 序章
    1. 1.1. 最適化問題
    2. 1.2. 数理計画問題
    3. 1.3. 制約付最適化問題
      1. 1.3.1. 制約付問題のベクトル表現
    4. 1.4. 線形計画問題(Linear Programming; LP)
      1. 1.4.1. LPは行列をベクトルで表せる
      2. 1.4.2. n変数の2次関数
    5. 1.5. 2次計画問題(Quadratic Program; QP)
    6. 1.6. 無制約最適化問題
    7. 1.7. 他の問題
      1. 1.7.1. 最適化問題の例
      2. 1.7.2. 最小二乗問題
      3. 1.7.3. ポートフォリオ選択問題
  2. 2. 第2章 凸集合と凸関数
    1. 2.1. 勾配ベクトルとヘッセ行列
      1. 2.1.1. 勾配ベクトル,ヘッセ行列,ヤコビ行列
      2. 2.1.2. 多変数Taylor展開
      3. 2.1.3. 線形関数,2次関数の勾配ベクトルとヘッセ行列
    2. 2.2. 凸集合
      1. 2.2.1. 凸集合(convex set)
      2. 2.2.2. 例題(2.3.1)
      3. 2.2.3. 例题(2.3.2)
      4. 2.2.4. 例題(2.3.3)
      5. 2.2.5. 超平面,半空間
      6. 2.2.6. 凸多面集合,凸多面体
      7. 2.2.7. 端点,辺
      8. 2.2.8. 錐,凸錐
      9. 2.2.9. 射線,端線
    3. 2.3. 凸関数(convex function)
      1. 2.3.1. 凸関数,狭義凸関数
      2. 2.3.2. 凸関数であるための条件(微分可能の場合)
      3. 2.3.3. 2次関数の凸性
      4. 2.3.4. 凸関数であるための条件(2回微分可能の場合)
      5. 2.3.5. 凸関数と凸集合の関係
      6. 2.3.6. 凹関数と凸集合の関係
  3. 3. 第3章 線形計画法
    1. 3.1. 標準形
    2. 3.2. 用語の定義
      1. 3.2.1. 実行可能解と実行可能領域
      2. 3.2.2. 基底行列と基底解
      3. 3.2.3. 実行可能基底解
      4. 3.2.4. 非退化実行可能基底解
      5. 3.2.5. 単体乗数
      6. 3.2.6. 最適解
        1. 3.2.6.1. 例題(3.2.1)
        2. 3.2.6.2. 例題(3.2.2)
        3. 3.2.6.3. 例題(3.2.3)
    3. 3.3. 線形計画法の基本定理
    4. 3.4. 単体法の原理
      1. 3.4.1. アルゴリズム3.1(単体法)
    5. 3.5. 単体法の例
      1. 3.5.1. 例題(3.5.1)
    6. 3.6. 2段階法
      1. 3.6.1. 例題(3.6.1)
    7. 3.7. 単体法の収束性
      1. 3.7.1. 最小添字規則
      2. 3.7.2. 最大改善規則
      3. 3.7.3. 例題(3.7.1)
    8. 3.8. 双対性
      1. 3.8.1. 双対問題の定義
      2. 3.8.2. 弱双対定理
      3. 3.8.3. 双対定理
      4. 3.8.4. 相補性定理
      5. 3.8.5. 例題(3.8.1)
      6. 3.8.6. 例題(3.8.2)
  4. 4. 第4章 非線形計画法I(無制約最小化問題)
    1. 4.1. 最適性条件
      1. 4.1.1. 最小解
      2. 4.1.2. 最適性条件の定理
      3. 4.1.3. 例題(4.1.1)
      4. 4.1.4. 例題(4.1.2)
      5. 4.1.5. 例題(4.1.3)
      6. 4.1.6. 最小2乗問題
    2. 4.2. 反復法
      1. 4.2.1. アルゴリズム4.1(直線探索を用いた反復法)
    3. 4.3. 収束性定義
    4. 4.4. 直線探索法(line search method)
      1. 4.4.1. アルゴリズム4.2(Armijo条件に対する直線探索法)
      2. 4.4.2. 例題(4.4.1)
      3. 4.4.3. 例題(4.4.2)
      4. 4.4.4. 例題(4.4.3)
    5. 4.5. 降下法の大域的収束性
      1. 4.5.1. Zoutendijk条件
    6. 4.6. 最急降下法
      1. 4.6.1. 最急降下法の性質
      2. 4.6.2. アルゴリズム4.3(最急降下法(直線探索付き))
      3. 4.6.3. 最急降下法の大域的収束性
      4. 4.6.4. 最急降下法の収束率
    7. 4.7. 共役勾配法
    8. 4.8. ニュートン法
      1. 4.8.1. アルゴリズム4.6(ニュートン法)
      2. 4.8.2. ニュートン法の局所的2次収束性
      3. 4.8.3. 例題(4.7.1)
      4. 4.8.4. 例題(4.7.2)
      5. 4.8.5. 例題(4.7.3)
    9. 4.9. 準ニュートン法(quasi-Newton method)
      1. 4.9.1. ヘッセ行列を近似する準ニュートン法
      2. 4.9.2. アルゴリズム4.7(準ニュートン法)
      3. 4.9.3. DFP(Davidon−Fletcher−Powell)DFP(Davidon-Fletcher-Powell)DFP(Davidon−Fletcher−Powell)公式
      4. 4.9.4. BFGS(Broyden−Fletcher−Goldfarb−Shanno)BFGS(Broyden-Fletcher-Goldfarb-Shanno)BFGS(Broyden−Fletcher−Goldfarb−Shanno)公式
      5. 4.9.5. アルゴリズム4.8(準ニュートン法(BFGSBFGSBFGS公式))
      6. 4.9.6. BFGSBFGSBFGS公式を用いた準ニュートン法の性質
      7. 4.9.7. ヘッセ行列の逆行列を近似する準ニュートン法
        1. 4.9.7.1. HHH公式のBFGSBFGSBFGS公式
      8. 4.9.8. アルゴリズム4.9(準ニュートン法(HHH公式のBFGSBFGSBFGS公式))
      9. 4.9.9. 対称ランクワン公式
      10. 4.9.10. 例題(4.8.1)
      11. 4.9.11. 例題(4.8.2)
      12. 4.9.12. 例題(4.8.3)
    10. 4.10. まとめ
  5. 5. 第5章 非線形計画法II(制約付き最小化問題)
    1. 5.1. 最適性条件
      1. 5.1.1. 等式制約付き最小化問題の最適性条件
      2. 5.1.2. 不等式制約付き最小化問題の最適性条件
        1. 5.1.2.1. 有効制約式
        2. 5.1.2.2. Fritz-Johnの定理
        3. 5.1.2.3. Kuhn-Tuckerの定理
      3. 5.1.3. 例題(5.1.1)
      4. 5.1.4. 例題(5.1.2)
      5. 5.1.5. 一般の制約付き問題に対する最適性条件
      6. 5.1.6. 例題(5.1.3)
    2. 5.2. 非線形計画法の双対定理
    3. 5.3. 線形計画問題の拡張:2次錐計画問題と半正定値計画問題
    4. 5.4. 制約付き最小解問題の数値解法
      1. 5.4.1. ペナルティー関数法
      2. 5.4.2. 乗数法
      3. 5.4.3. 逐次2次計画法
      4. 5.4.4. 主双対内点法
  6. 6. 参考文献

CS专业课学习笔记

第1章 序章

最適化問題

与えられた条件の下で何らかの関数を最小または最大にする問題

数理計画問題

変数, 条件(等式, 不等式で記述される))が有限個数学的に記述された最適化問題

制約付最適化問題

min f(x)条件gi(x)=0(i=1,...,m)hj(x)0(i=1,...,l)\begin{matrix} min&\ f(\mathbf{x}) \\ \text{条件}&g_i(\mathbf{x}) &=& 0 (i = 1,...,m) \\ &h_j(\mathbf{x}) &\leq& 0 (i = 1,...,l) \end{matrix}

f: Rn\mathbb{R}^{n}R\mathbb{R} 目的関数
gi:Rng_i: \mathbb{R}^{n}R(i=1,...,m)\mathbb{R} (i = 1,...,m) 制約関数
hj:Rnh_j: \mathbb{R}^{n}R(j=1,...,l)\mathbb{R} (j = 1,...,l) 制約関数

min x12+4x223x1x2条件x1+x25=0(x11)2+(x22)250x10\begin{matrix} min&\ x_1^2 + 4x_2^2 - 3x_1x_2 \\ \text{条件}& x_1 + x_2 - 5 &=& 0 \\ & (x_1 - 1)^2 + (x_2 - 2)^2 - 5 &\leq& 0 \\ & -x_1 &\leq& 0 \end{matrix}

(n = 2, m = 1, l = 2)

制約付問題のベクトル表現

g=[g1(x)gm(x)]h=[h1(x)hl(x)]min f(x)条件gi(x)=0hj(x)0\mathbf{g}=\begin{bmatrix} g_1(\mathbf{x}) \\ \vdots \\ g_m(\mathbf{x}) \end{bmatrix} \qquad \mathbf{h}=\begin{bmatrix} h_1(\mathbf{x}) \\ \vdots \\ h_l(\mathbf{x}) \end{bmatrix} \qquad \begin{matrix} min&\ f(\mathbf{x}) \\ \text{条件}&g_i(\mathbf{x}) = 0 \\ &h_j(\mathbf{x}) \leq 0 \end{matrix}

線形計画問題(Linear Programming; LP)

f(x):線形関数gi(x),hj(x):1次関数f(\mathbf{x}): \text{線形関数} \qquad g_i(\mathbf{x}), h_j(\mathbf{x}): 1\text{次関数}

min x13x2条件x1+x2=5g1(x)=x1+x25x1x21h1(x)=x1+x21x1,x20h2(x)=x1,h3(x)=x2\begin{matrix} min & \ x_1 - 3x_2 \\ \text{条件} & x_1 + x_2 = 5 \leftrightarrow g_1(x) &=& x_1 + x_2 - 5 \\ & x_1 - x_2 \geq -1 \leftrightarrow h_1(x) &=& -x_1 + x_2 -1 \\ & x_1, x_2 \geq 0 \leftrightarrow h_2(x) &=& -x_1, h_3(x) = -x_2 \end{matrix}

LPは行列をベクトルで表せる

例の場合

C=(13)x=(x1x2)\mathbf{C} = \begin{pmatrix} 1 \\ -3 \end{pmatrix} \qquad \mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}

min CTx条件Ax=aBxb\begin{matrix} min&\ \mathbf{C}^T\mathbf{x} \\ \text{条件}&A\mathbf{x} = \mathbf{a} \\ &B\mathbf{x} \leq \mathbf{b} \end{matrix}

n変数の2次関数

f(x)={12i=1nj=1nqijxixj+i=1ncixi(qij=qji)12xTQx+cTx(QT=Q)f(x) = \begin{cases} \frac{1}{2}\sum^n_{i=1}\sum^n_{j=1}q_{ij}x_ix_j+\sum^n_{i=1}c_ix_i \quad (q_{ij} = q_{ji}) \\ \frac{1}{2}\mathbf{x}^TQ\mathbf{x} + \mathbf{c}^T\mathbf{x} \quad (Q^T = Q) \end{cases}

f(x1,x2)=x12+4x223x1x2+5x13x2=12(2x12+8x223x1x23x1x2)+5x13x2=12(x1,x2)(2338)(x1x2)+(53)(x1x2)=12xTQx+cTx(QT=Q)\begin{aligned} f(x_1,x_2) &= x_1^2 + 4x_2^2 - 3x_1x_2 + 5x_1 - 3x_2 \\ &= \frac{1}{2} (2x_1^2 + 8x_2^2 - 3x_1x_2 - 3x_1x_2) + 5x_1 - 3x_2 \\ &= \frac{1}{2} (x_1,x_2) \begin{pmatrix} 2 & -3 \\ -3 & 8 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} + \begin{pmatrix} 5 & -3 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \\ &= \frac{1}{2}\mathbf{x}^TQ\mathbf{x} + \mathbf{c}^T\mathbf{x} \quad (Q^T = Q) \end{aligned}

2次計画問題(Quadratic Program; QP)

min f(x)=12xtQx+cTx条件Ax=aBxb\begin{matrix} min&\ f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^tQ\mathbf{x} + \mathbf{c}^T\mathbf{x} \\ \text{条件}&A\mathbf{x} = \mathbf{a} \\ &B\mathbf{x} \leq \mathbf{b} \end{matrix}

Qn×mAm×nam次元cn次元Bl×nbl次元\begin{matrix} Q\text{:}n\times m & A\text{:}m\times n & \mathbf{a}\text{:}m\text{次元} \\ \mathbf{c}\text{:}n\text{次元} & B\text{:}l\times n & \mathbf{b}\text{:}l\text{次元} \end{matrix}

無制約最適化問題

min f(x)min \ f(\mathbf{x})
xRn\mathbf{x} \in \mathbb{R}^n
(f:RnR)(f: \mathbb{R}^{n} \rightarrow \mathbb{R})

他の問題

整数計画問題:「変数は整数」条件 など…

最適化問題の例

生産計画問題
原料 → 製品
利益 → max
条件 原料の供給量
それぞれ製品の生産量決定

最小二乗問題

物体の運動(時刻,位置)のデータ(t1,b1)(tp,bp)\begin{aligned} \text{物体の運動} &\begin{pmatrix} \text{時刻},& \text{位置} \end{pmatrix}& \text{のデータ} \\ &\begin{pmatrix} t_1,& b_1 \end{pmatrix}& \\ &\qquad\vdots& \\ &\begin{pmatrix} t_p, & b_p \end{pmatrix}& \end{aligned}

モデル式: bi=x0+x1ti+ei(誤差)(i=1,...,p)b_i = x_0 + x_1t_i + e_i(\text{誤差}) (i = 1,...,p)

ei2minx0,x1を推定\begin{aligned} \sum e_i^2 \rightarrow min \\ x_0, x_1\text{を推定} \end{aligned}

ポートフォリオ選択問題

Support Vector Hachineに関する問題

第2章 凸集合と凸関数

勾配ベクトルとヘッセ行列

勾配ベクトル,ヘッセ行列,ヤコビ行列

f:RnRf: \mathbb{R}^n \rightarrow \mathbb{R}
ffの勾配ベクトル(gradient vector)

f(x)=(fx1fxn)Rn\nabla f(x) = \begin{pmatrix} \frac{\partial f}{\partial x_1} \\ \frac{\partial f}{\partial x_n} \end{pmatrix} \in \mathbb{R}^n

勾配ベクトルは目的関数が最も増加する方向

ffのヘッセ行列(Hessian matrix)

2f(x)=[(i,j)成分=2fxixjであるn×n行列]\nabla^2f(\mathbf{x}) = [(i, j)\text{成分} = \frac{\partial^2 f}{\partial x_i x_j}\text{である}n\times n\text{行列}]

f(x1,x2)=12(2x12+8x226x1x2)+5x13x2f(x)=(2x13x2+58x23x13)=(2338)(x1x2)+(53)2f(x)=(2338)\begin{aligned} f(x_1,x_2) &= \frac{1}{2} (2x_1^2 + 8x_2^2 -6x_1x_2) + 5x_1 - 3x_2 \\ \nabla f(\mathbf{x}) &= \begin{pmatrix} 2x_1 - 3x_2 + 5 \\ 8x_2 - 3x_1 - 3 \end{pmatrix}= \begin{pmatrix} 2 & -3 \\ -3 & 8 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} +\begin{pmatrix} 5 \\ -3 \end{pmatrix} \\ \nabla^2 f(\mathbf{x}) &= \begin{pmatrix} 2 & -3 \\ -3 & 8 \end{pmatrix} \end{aligned}

ggヤコビ行列

g(x)=[g1(x),,gp(x)]=(g1x1...gpx1g1xngpxn)Rn×p\begin{aligned} \nabla g(\mathbf{x}) = [\nabla g_1(\mathbf{x}),\cdots,\nabla g_p(\mathbf{x})] = \begin{pmatrix} \frac{\partial g_1}{\partial x_1} & ... & \frac{\partial g_p}{\partial x_1} \\ \vdots & \ddots & \vdots \\ \frac{\partial g_1}{\partial x_n} & \cdots & \frac{\partial g_p}{\partial x_n} \end{pmatrix} \in \mathbb{R}^{n \times p} \end{aligned}

で定義し,その転置行列g(x)T\nabla g(\mathbf{x})^Tをgのヤコビ行列(Jacobian matrix)という.

多変数Taylor展開

1次:f(x+d)=f(x)+f(x)Td+残差2次:f(x+d)=f(x)+f(x)Td+12dT2f(x)d+残差1変数:f(x+d)=f(x)+f(x)d+12f(x)Td2+残差\begin{aligned} &1\text{次:}f(\mathbf{x}^* + \mathbf{d}) = f(\mathbf{x}^*) + \nabla f(\mathbf{x}^*)^T\mathbf{d} + \text{残差} \\ &2\text{次:}f(\mathbf{x}^* + \mathbf{d}) = f(\mathbf{x}^*) + \nabla f(\mathbf{x}^*)^T\mathbf{d} + \frac{1}{2}\mathbf{d}^T\nabla^2f(\mathbf{x}^*)\mathbf{d}+\text{残差} \\ &1\text{変数:}f(x + d) = f(x) + f'(x)d + \frac{1}{2}f''(x)^Td^2 + \text{残差} \end{aligned}

線形関数,2次関数の勾配ベクトルとヘッセ行列

cR,QRn×n\mathbf{c} \in \mathbb{R}, \mathbb{Q} \in \mathbb{R}^{n \times n}

  • (cTx)=c\nabla(\mathbf{c}^T\mathbf{x}) = \mathbf{c}
  • (xQTx)=Q+QTx=2Qx(QT=Q)\nabla(\mathbf{x}Q^T\mathbf{x})=Q+Q^T\mathbf{x}=2Q\mathbf{x}(Q^T = Q)
  • 2(xTQx)=Q+QT=2Q(QT=Q)\nabla^2(\mathbf{x}^TQ\mathbf{x})=Q+Q^T=2Q(Q^T = Q)

f(x)=12xTQx+cTx(QT=Q)f(x)=Qx+c 2f(x)=Q\begin{aligned} f(\mathbf{x}) &= \frac{1}{2} \mathbf{x}^TQ\mathbf{x} + \mathbf{c}^T\mathbf{x} \qquad (Q^T = Q) \\ \nabla f(\mathbf{x}) &= Q\mathbf{x}+\mathbf{c} \\ \ \nabla^2f(\mathbf{x}) &= Q \end{aligned}

凸集合

イメージ ヘコミのない集合

凸集合(convex set)

SRn,u,vSλ[0,1]\mathbf{S} \in \mathbb{R}^n, \mathbf{u},\mathbf{v} \in \mathbf{S}\text{,}^\forall\lambda \in [0, 1]に対して

λu+(1λ)vS\begin{aligned} \lambda \mathbf{u} +(1 - \lambda)\mathbf{v} \in \mathbf{S} \end{aligned}

u,vSuv\mathbf{u},\mathbf{v} \in S \Rightarrow \mathbf{u}\text{と}\mathbf{v}を結ぶ線分もSに入る.Sは凸集合という.(空集合\varnothingは凸集合である))

例: 以下を証明せよ

ARm×n,bRm,S={xRnAx=b,x0}\begin{aligned} A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, \mathbf{S} = \{x \in \mathbb{R}^n | A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}\} \end{aligned}

は凸集合である.

示すべきこと:

{u,vSλ[0,1](Au=b,u0Av=b,v0)w=λu+(1λ)vS(Aw=b,w0)Aw=A(λu+(1λ)v)=λAu+(1λ)Av=λb+(1λ)b=b\begin{aligned} \begin{cases} \mathbf{u}, \mathbf{v} \in \mathbf{S} \\ \lambda \in [0, 1] \end{cases} &\Leftrightarrow \begin{pmatrix} A\mathbf{u}=\mathbf{b}, \mathbf{u}\geq \mathbf{0} \\ A\mathbf{v}=\mathbf{b}, \mathbf{v}\geq \mathbf{0} \end{pmatrix} \\ &\Downarrow \\ \mathbf{w} = \lambda \mathbf{u} + (1 - \lambda)\mathbf{v} \in \mathbf{S} &\Leftrightarrow (A\mathbf{w} = \mathbf{b}, \mathbf{w} \geq \mathbf{0}) \\ A\mathbf{w} &= A(\lambda \mathbf{u} + (1 - \lambda) \mathbf{v}) \\ &= \lambda A \mathbf{u} + (1 - \lambda)A\mathbf{v} \\ &= \lambda\mathbf{b} + (1 - \lambda)\mathbf{b} = \mathbf{b} \end{aligned}

また, λ0,1λ0\lambda \leq 0, 1 - \lambda \leq 0であるから,λu0,(1λ)v0\lambda\mathbf{u} \geq \mathbf{0}, (1 - \lambda)\mathbf{v} \geq \mathbf{0}, よって,w=λu+(1λ)v0\mathbf{w} = \lambda \mathbf{u} + (1 - \lambda)\mathbf{v} \geq \mathbf{0}

例題(2.3.1)

次の二次関数

f(x)=f(x1,x2,x3)=3x12+x22+2x32+2x1x2+3x1x34x2x3+x14x2+6x3\begin{aligned} f(x) = f(x_1,x_2,x_3) = 3x_1^2 + x_2^2 + 2x_3^2 + 2x_1x_2 + 3x_1x_3 - 4x_2x_3 + x_1 - 4x_2 + 6x_3 \end{aligned}

f(x)=12xTQx+cTxf(x) = \frac{1}{2} x^TQx + c^Txの形で記述せよ.

f(x)=12(x1,x2,x3)(623224344)(x1x2x3)+(1,4,6)(x1x2x3)\begin{aligned} f(x) = \frac{1}{2} (x_1,x_2,x_3) \begin{pmatrix} 6 & 2 & 3 \\ 2 & 2 & -4 \\ 3 & -4 & 4 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}+ (1,-4,6) \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} \end{aligned}

例题(2.3.2)

次のそれぞれの関数の勾配ベクトルとヘッセ行列を求めよ.

  • 例題(1)の関数f(x)f(x)

f(x)=(6x1+2x2+3x3+12x2+2x14x344x3+3x14x2+6)=(623224434)(x1x2x3)+(146)2f(x)=(623224434)\begin{aligned} \nabla f(\mathbf{x}) &= \begin{pmatrix} 6x_1 + 2x_2 + 3x_3 + 1 \\ 2x_2 + 2x_1 - 4x_3 - 4 \\ 4x_3 + 3x_1 - 4x_2 + 6 \end{pmatrix}= \begin{pmatrix} 6 & 2 & 3 \\ 2 & 2 & -4 \\ 4 & 3 & -4 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}+ \begin{pmatrix} 1 \\ -4 \\ 6 \end{pmatrix} \\ \nabla^2 f(\mathbf{x}) &= \begin{pmatrix} 6 & 2 & 3 \\ 2 & 2 & -4 \\ 4 & 3 & -4 \end{pmatrix} \end{aligned}

  • f(x)=ex1x2+x12x233x1+5x2f(x) = e^{x_1x_2} + x_1^2x_2^3 - 3x_1 + 5x_2

f(x)=(x2ex1x2+2x23x13x1ex1x2+3x12x22+5)2f(x)=(x22ex1x2+2x23(1+x1x2)ex1x2+6x1x22(1+x2x1)ex1x2+6x22x1x12ex1x2+6x12x2)\begin{aligned} \nabla f(\mathbf{x}) &= \begin{pmatrix} x_2e^{x_1x_2} + 2x_2^3x_1 -3 \\ x_1e^{x_1x_2} + 3x_1^2x_2^2 + 5 \end{pmatrix} \\ \nabla^2 f(\mathbf{x}) &= \begin{pmatrix} x_2^2e^{x_1x_2} + 2x_2^3 & (1 + x_1x_2)e^{x_1x_2} + 6x_1x_2^2 \\ (1 + x_2x_1)e^{x_1x_2} + 6x_2^2x_1 & x_1^2e^{x_1x_2} + 6x_1^2x_2 \end{pmatrix} \end{aligned}

例題(2.3.3)

次の集合が凸集合であることを示せ.

S={xRnAx=a,Bxb}\begin{aligned} S = \{\mathbf{x} \in \mathbb{R}^n | A\mathbf{x} = \mathbf{a}, B\mathbf{x} \leq \mathbf{b}\} \end{aligned}

ただし,ARm×n,aRm,BRl×n,bRlA \in \mathbb{R}^{m \times n}, \mathbf{a} \in \mathbb{R}^m, B \in \mathbb{R}^{l \times n}, \mathbf{b} \in \mathbb{R}^l

{u,vSλ[0,1](Au=a,Bu0Av=a,Bv0)w=λu+(1λ)vS(Aw=a,Bwb)Aw=A(λu+(1λ)v)=λAu+(1λ)Av=λa+(1λ)a=a\begin{aligned} \begin{cases} \mathbf{u}, \mathbf{v} \in \mathbf{S} \\ \lambda \in [0, 1] \end{cases} &\Leftrightarrow \begin{pmatrix} A\mathbf{u}=\mathbf{a}, B\mathbf{u}\leq \mathbf{0} \\ A\mathbf{v}=\mathbf{a}, B\mathbf{v}\leq \mathbf{0} \end{pmatrix} \\ &\Downarrow \\ \mathbf{w} = \lambda \mathbf{u} + (1 - \lambda)\mathbf{v} \in \mathbf{S} &\Leftrightarrow (A\mathbf{w} = \mathbf{a}, B\mathbf{w} \leq \mathbf{b}) \\ A\mathbf{w} &= A(\lambda\mathbf{u} + (1 - \lambda)\mathbf{v}) \\ &= \lambda A \mathbf{u} + (1 - \lambda)A\mathbf{v} \\ &= \lambda\mathbf{a} + (1 - \lambda)\mathbf{a} = \mathbf{a} \end{aligned}

また,λ0,(1λ)0,Bub,Bvb\lambda \geq 0, (1 - \lambda) \geq 0, B\mathbf{u} \leq \mathbf{b}, B\mathbf{v} \leq \mathbf{b}であるから,よって,Bw=B(λu+(1λ)v)bB\mathbf{w} = B(\lambda\mathbf{u} + (1 - \lambda)\mathbf{v}) \leq \mathbf{b}

超平面,半空間

Rn\mathbb{R}^nの零でないベクトルa\mathbf{a}と実数α\alphaを用いて定義される集合

H={xRn  aTx=α}\begin{aligned} H = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ \mathbf{a}^T \mathbf{x} = \alpha \rbrace \end{aligned}

a\mathbf{a}α\alphaで定義される超平面(hyperplane)という. 超平面H\mathbb{H}に対して

H+={xRn  aTxα},H={xRn  aTxα}\begin{aligned} H^+ = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ \mathbf{a}^T \mathbf{x} \geq \alpha \rbrace, \quad H^- = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ \mathbf{a}^T \mathbf{x} \leq \alpha \rbrace \end{aligned}

をそれぞれ超平面Hを境界にもつ正の閉半空間, 負の閉半空間という.

凸多面集合,凸多面体

有限個の閉半空間の共通部分として表される空でない集合を凸多面集合(polyhedral convex set)という.具体的には,零でないベクトルa1,,amRn\mathbf{a}_1, \cdots, \mathbf{a}_m \in \mathbb{R}^nと実数b1,,bmb_1, \cdots, b_mを用いれば

X={xRn  aiTxbi,i=1,,m}\begin{aligned} X = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ \mathbf{a}_i^T \mathbf{x} \leq b_i, i = 1, \cdots, m \rbrace \end{aligned}

は凸多面集合になる.あるいは,aiT\mathbf{a}_i^Tを第i行ベクトルにもつ行列ARm×nA \in \mathbb{R}^{m \times n}bib_iを第i成分にもつベクトルbRmb \in \mathbb{R}^mに対して

X={xRn  Axb}\begin{aligned} X = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ A\mathbf{x} \leq \mathbf{b} \rbrace \end{aligned}

は凸多面集合になる.また,等式aiTx=bi\mathbf{a}_i^T \mathbf{x} = b_iは2つの半空間

{xRn  aiTxbi},{xRn  aiTxbi}\begin{aligned} \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ \mathbf{a}_i^T \mathbf{x} \leq b_i \rbrace, \quad \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ \mathbf{a}_i^T \mathbf{x} \geq b_i \rbrace \end{aligned}

の共通部分として表せるのでX={xRn  Ax=b}X = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ A\mathbf{x} = \mathbf{b} \rbraceも凸多面集合になる.
特に,有界な凸多面集合は凸多面体(convex polytope)と呼ばれる.

端点,辺

Rn\mathbb{R}^nの凸集合Sに属する点x\mathbf{x}が,それとは異なるSの2点u,v\mathbf{u},\mathbf{v}(ただし,uv\mathbf{u} \ne \mathbf{v})の凸結合として

x=(1λ)u+λv(0<λ<1)\begin{aligned} \mathbf{x} = (1-\lambda)\mathbf{u} + \lambda\mathbf{v} (0 < \lambda < 1) \end{aligned}

と表すことができないとき,x\mathbf{x}をSの端点(extreme point)という.

また集合Sに属する互いに異なる2点u,v\mathbf{u}, \mathbf{v}を結ぶ線分(ただし,u,v\mathbf{u}, \mathbf{v}を除く)上の任意の点がこの線分上以外のSの2点の凸結合で表すことができないとき,この線分をSの辺(edge)という.さらに,2つの端点を結ぶ線分上のいかなる点もこの2つの端点の端点の凸結合としてしか表すことができないとき,この端点は互いに隣接している(隣り合っている)という.

錐,凸錐

Rn\mathbb{R}^nの空でない部分集合Cにおいて,xC\mathbf{x} \in Cならば全ての実数λ0\lambda \geq 0に対してλxC\lambda \mathbf{x} \in Cが成り立つとき,Cを錐(cone)という(原点含まれる).特に凸集合である錐を凸錐(convex cone)という.

射線,端線

Rn\mathbb{R}^nの零でない点x\mathbf{x}に対して半直線

{λx  λ>0,λR}\begin{aligned} \lbrace \lambda \mathbf{x} \ |\ \lambda > 0, \lambda \in \mathbb{R} \rbrace \end{aligned}

x\mathbf{x}方向の射線(ray)という(始点である原点が含まれない).
Rn\mathbb{R}^nの凸錐Cのある射線に属する全ての点が,その射線上の2点以外の凸結合で表すことができないとき,その射線を凸錐Cの端線(extreme ray)という.

凸関数(convex function)

凸関数,狭義凸関数

f:RnR,fが凸関数u,vR,λ(0,1)f: \mathbb{R}^n \rightarrow \mathbb{R},f\text{が凸関数}^\forall \mathbf{u,v} \in \mathbb{R}, ^\forall \lambda \in (0,1)

(1λ)f(u)+λf(v)f((1λ)u+λv)\begin{aligned} (1 - \lambda)f(\mathbf{u}) + \lambda f(\mathbf{v}) \geq f((1 - \lambda)\mathbf{u} + \lambda \mathbf{v}) \end{aligned}

f: 狭義凸関数(strictly convex function)

(1λ)f(u)+λf(v)>f((1λ)u+λv)\begin{aligned} (1 - \lambda)f(\mathbf{u}) + \lambda f(\mathbf{v}) > f((1 - \lambda)\mathbf{u} + \lambda \mathbf{v}) \end{aligned}

凸関数: グラフ上2点を線分で結ぶと,その線分がグラフの上にある(下にならない)ような関数

f:RnRf:\mathbb{R}^n \rightarrow \mathbb{R}が凹関数(concave function),(f)(-f)が凸関数.

(1)f(x)=cTx=c1x1+c2x2+...+cnxnf(\mathbf{x}) = \mathbf{c}^T\mathbf{x} = c_1x_1 + c_2x_2 + ... + c_nx_nは凸関数かつ凹関数
(2)hi:RnRh_i:\mathbb{R}^n \rightarrow \mathbb{R} 凸関数(i=1,,li = 1,\cdots,l)S={xRn  hi(x)0(i=1,,l)}\Rightarrow S = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ h_i(\mathbf{x}) \leq 0 (i=1,\cdots,l) \rbraceは凸集合

(1)の証明
f((1λ)u+λv)=(1λ)f(u)+λf(v)f((1 - \lambda) \mathbf{u} + \lambda \mathbf{v}) = (1 - \lambda)f(\mathbf{u})+\lambda f(\mathbf{v})

補足

f,g:RnRf,g:\mathbb{R}^n \rightarrow \mathbb{R},凸,λ>0\lambda > 0

  • f + g
  • λf\lambda f
  • max(f,g)max(f,g)は全て凸関数

f:RnRf:\mathbb{R}^n \rightarrow \mathbb{R} 連続的微分可能 = C1C^1f(x)\nabla f(\mathbf{x})が定義され, 連続2回連続的微分可能 = C2C^2f(x),2f(x)\nabla f(\mathbf{x}), \nabla^2 f(\mathbf{x})が定義され,連続

凸関数であるための条件(微分可能の場合)

f,g:RnRf,g:\mathbb{R}^n \rightarrow \mathbb{R}, C1C^1

f:f:凸関数(1),(2)\Leftrightarrow (1),(2)が成り立つ

(1)x,yRn^\forall x,y \in \mathbb{R}^n
f(y)f(x)+f(x)T(yx)f(\mathbf{y}) \geq f(\mathbf{x}) + \nabla f(\mathbf{x})^T(\mathbf{y} - \mathbf{x}) (接線はグラフの下になる)

(2)x,yRn^\forall x,y \in \mathbb{R}^n
(f(x)f(y))T(xy)0(\nabla f(\mathbf{x}) - \nabla f(\mathbf{y}))^T(\mathbf{x} - \mathbf{y}) \geq 0(この性質をf\nabla f単調性という)

2次関数の凸性

f(x)=12xTQx+cTx(QRn×n,対称,cRn)\begin{aligned} f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^TQ\mathbf{x} + \mathbf{c}^T\mathbf{x} \qquad (Q \in \mathbb{R}^{n \times n},\text{対称},\mathbf{c} \in \mathbb{R}^n) \end{aligned}

(1)f:凸関数Q:半正定値dTQd0(dRn)対称n×n行列Qの固有値がすべて非負f:\text{凸関数} \Leftrightarrow Q:\text{半正定値} \Leftrightarrow \mathbf{d}^TQ\mathbf{d} \geq 0(^\forall d \in \mathbb{R}^n) \Leftrightarrow \text{対称}n \times n\text{行列}Q\text{の固有値がすべて非負}
(2)f:狭義凸関数Q:正定値dTQd>0(dRn,d0)対称n×n行列Qの固有値がすべて正f:\text{狭義凸関数} \Leftrightarrow Q:\text{正定値} \Leftrightarrow \mathbf{d}^TQ\mathbf{d} > 0(^\forall d \in \mathbb{R}^n, d \ne 0) \Leftrightarrow \text{対称}n \times n\text{行列}Q\text{の固有値がすべて正}

(1)の証明
f(x)=Qx+c\nabla f(\mathbf{x}) = Q\mathbf{x} + \mathbf{c}なので,任意のx,yRnx,y \in \mathbb{R}^nに対して

(f(x)f(y))T(xy)=(xy)TQ(xy)\begin{aligned} (\nabla f(\mathbf{x}) - \nabla f(\mathbf{y}))^T (\mathbf{x} - \mathbf{y}) = (\mathbf{x} - \mathbf{y})^TQ(\mathbf{x} - \mathbf{y}) \end{aligned}

が成り立つ.(f(x)f(y))T(xy)0(\nabla f(\mathbf{x}) - \nabla f(\mathbf{y}))^T(\mathbf{x} - \mathbf{y}) \geq 0より,ffの凸性とQの半正定値性が同値である.

(2)の証明
xy\mathbf{x} \ne \mathbf{y}ならば,ffの狭義凸性とQQの正定値性が同値である.

凸関数であるための条件(2回微分可能の場合)

f:RnRf:\mathbb{R}^n \rightarrow \mathbb{R}, C2C^2
(1)f:凸関数ヘッセ行列2f(x)f:\text{凸関数} \Leftrightarrow \text{ヘッセ行列}\nabla^2 f(\mathbf{x})が半正定値(xR)(^\forall x \in \mathbb{R})
(2)ヘッセ行列2f(x)\nabla^2 f(\mathbf{x})が半正定値(xR)f:(^\forall x \in \mathbb{R}) \Rightarrow f:狭義凸関数(逆は成立しない)

(2)の必要性の反例
f(x)=x4f(x) = x^4は狭義凸関数
f(x)=12x20f'(x) = 12x^2 \geq 0
f(0)=0f''(0) = 0

凸関数と凸集合の関係

エピグラフ(epigraph): 実数値関数ffが与えられたとき,以下の集合をffのエピグラフとよぶ:

epif={(x,y)Rn×R:yf(x)}\begin{aligned} epif = \{(\mathbf{x},y) \in \mathbb{R}^n \times \mathbb{R}: y \geq f(\mathbf{x})\} \end{aligned}

実数値関数ffのエピグラフが凸集合の時,ffは凸関数.

凹関数と凸集合の関係

ハイポグラフ (hypograph): 実数値関数ffが与えられたとき,以下の集合をffのハイポグラフとよぶ:

hypf={(x,y)Rn×R:yf(x)}\begin{aligned} hypf = \{(\mathbf{x},y) \in \mathbb{R}^n \times \mathbb{R}: y \leq f(\mathbf{x})\} \end{aligned}

実数値関数ffのハイポグラフが凸集合の時,ffは凹関数.

第3章 線形計画法

標準形

例題:

最大値5x1+4x2制約条件5x1+2x230x1+2x214x10\begin{aligned} \text{最大値} \qquad &5x_1 + 4x_2 \\ \text{制約条件} \qquad &5x_1 + 2x_2 \leq 30 \\ &x_1 + 2x_2 \leq 14 \\ &x_1 \geq 0 \end{aligned}

スラック変数x3,x4x_3,x_4を入れる

5x1+2x2+x3=30x1+2x2+x4=14x3,x40\begin{aligned} 5x_1 + 2x_2 + x_3 &= 30 \\ x_1 + 2x_2 + x_4 &= 14 \\ x_3,x_4 &\geq 0 \end{aligned}

自由変数x2x2+,x2x_2\text{を}x_2^+, x_2^-で置き換える

x2=x2+x2,x2+,x20x_2 = x_2^+ - x_2^-, \qquad x_2^+, x_2^- \geq 0

最小値5x14x2++4x2+0x3+0x4制約条件5x1+2x2+2x2+x3=30x1+2x2+2x2+x4=14x1,x2+,x2,x3,x40\begin{aligned} \text{最小値} \qquad &-5x_1 - 4x_2^+ + 4x_2^- + 0x_3 + 0x_4 \\ \text{制約条件} \qquad &5x_1 + 2x_2^+ - 2x_2^- + x_3 = 30 \\ &x_1 + 2x_2^+ - 2x_2^- + x_4 = 14 \\ &x_1, x_2^+, x_2^-, x_3, x_4 \geq 0 \end{aligned}

用語の定義

線形計画問題ARm×n,bRm,CRnA \in \mathbb{R}^{m \times n}, \mathbf{b} \in \mathbb{R}^m, \mathbb{C} \in \mathbb{R}^n

minCTxs.tAx=b,x0\begin{aligned} min \qquad &\mathbb{C}^T \mathbf{x} \\ s.t \qquad &A\mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq \mathbf{0} \end{aligned}

rankA=m(m<n)rank A = m \quad (m < n)と仮定する

実行可能解と実行可能領域

制約条件を満足する点を実行可能解(feasible solution)と呼び,さらに,そのような点の集合を実行可能領域(feasible region)という.標準形の場合には

S={xRn  Ax=b,x0}S = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ A\mathbf{x} = \mathbf{b}, \quad \mathbf{x} \geq 0 \rbrace

が実行可能領域になる.

基底行列と基底解

Aから線形独立なベクトルをm本とって作られる正方行列をBRm×mB \in \mathbb{R}^{m \times m}とおいて基底行列(basis matrix)と呼ぶ.
選んだ列に対応する変数をxB\mathbf{x}_Bとおいて基底変数(basic variable)と呼ぶ.
残りの変数をxN\mathbf{x}_Nとおいて非基底変数(nonbasic variable)と呼ぶ.

A=(BN),x=(xBxN)A = (B \quad N), \mathbf{x} = \begin{pmatrix}\mathbf{x}_B \\ \mathbf{x}_N \end{pmatrix}

と分割されて,このとき等式制約Ax=bBxB+NxN=bA\mathbf{x} = \mathbf{b}\text{は}B\mathbf{x}_B + N\mathbf{x}_N = \mathbf{b}と書ける.
特に非基底変数を零とおけば,基底変数はxB=B1b\mathbf{x}_B = B^{-1}\mathbf{b}と一意に決定される.

こうして定まる変数

x=(xBxN)=(B1b0)\begin{aligned} \mathbf{x} = \begin{pmatrix} \mathbf{x}_B \\ \mathbf{x}_N \end{pmatrix} = \begin{pmatrix} B^{-1}\mathbf{b} \\ \mathbf{0} \end{pmatrix} \end{aligned}

を基底解(basic solution)と呼ぶ.

実行可能基底解

基底解の全ての変数が非負のとき(xB=B1b0,xN=0\mathbf{x}_B = B^{-1}\mathbf{b} \geq \mathbf{0}, \mathbf{x}_N = \mathbf{0}),実行可能基底解(basic feasible solution)と呼ぶ.

非退化実行可能基底解

実行可能基底解でちょうどm個の基底変数の値が正であるとき非退化(nondegenerate)であるといい,それを非退化実行可能基底解(nondegenerate basic feasible solution)と呼ぶ(xB>0,xN=0\mathbf{x}_B > 0, \mathbf{x}_N = \mathbf{0}).そうでないとき退化(degenerate)しているという.

単体乗数

基底行列Bに対応して目的関数の係数もc=(cB,cN)T\mathbf{c} = (\mathbf{c}_B, \mathbf{c}_N)^Tと分割される.このとき(B1)TcB(B^{-1})^T \mathbf{c}_Bで定まるベクトルを単体乗数(simplex multiplier)という.

最適解

目的関数を最小に実行可能解を最適解(optimal solution)という.

例題

A=(5247112433)b=(145)\begin{aligned} A = \begin{pmatrix} 5 & 2 & 4 & 7 & 1 \\ 1 & 2 & 4 & 3 & -3 \end{pmatrix} \qquad \mathbf{b} = \begin{pmatrix} 14 \\ 5 \end{pmatrix} \end{aligned}

(1) (x1,x2x_1, x_2)を基底変数に選んだ場合

xB=B1b=(22)\begin{aligned} \mathbf{x}_B = B^{-1}\mathbf{b} = \binom{2}{2} \end{aligned}

基底解はx=(2,2,0,0,0)T\mathbf{x} = (2,2,0,0,0)^Tである.これは実行可能基底解である.

(2) (x1,x4x_1, x_4)を基底変数に選んだ場合

xB=B1b=(02)\begin{aligned} \mathbf{x}_B = B^{-1}\mathbf{b} = \binom{0}{2} \end{aligned}

基底解はx=(0,0,0,2,0)T\mathbf{x} = (0,0,0,2,0)^Tである.これは退化した基底解である.

(3) (x1,x5x_1, x_5)を基底変数に選んだ場合

xB=B1b=(31)\begin{aligned} \mathbf{x}_B = B^{-1}\mathbf{b} = \binom{3}{-1} \end{aligned}

基底解はx=(3,0,0,0,1)T\mathbf{x} = (3,0,0,0,-1)^Tである.これは実行不可能基底解である.

(4) (x2,x3x_2, x_3)を基底変数に選んだ場合

B=(2424)\begin{aligned} B = \begin{pmatrix} 2 & 4 \\ 2 & 4 \end{pmatrix} \end{aligned}

基底解が作れない.

例題(3.2.1)

次の線形計画問題を標準形に書き換えよ.

最大化3x1+4x2x3制約条件x1+x254x1+x2+2x313x1+4x2+2x3=8x1,x20\begin{aligned} \text{最大化} \qquad &-3x_1 + 4x_2 - x_3 \\ \text{制約条件} \qquad &x_1 + x_2 \geq 5 \\ &4x_1 + x_2 + 2x_3 \leq 1 \\ &3x_1 + 4x_2 + 2x_3 = 8 \\ &x_1, x_2 \geq 0 \end{aligned}

最小化3x14x2+x3+x3+0x4+0x5制約条件x1+x2x4=54x1+x2+2x3+2x3+x5=13x1+4x2+2x3+2x3=8x1,x2,x3+,x3,x4,x50\begin{aligned} \text{最小化} \qquad &3x_1 - 4x_2 + x_3^+ - x_3^- + 0x_4 + 0x_5 \\ \text{制約条件} \qquad &x_1 + x_2 - x_4 = 5 \\ &4x_1 + x_2 + 2x_3^+ - 2x_3^- + x_5 = 1 \\ &3x_1 + 4x_2 + 2x_3^+ - 2x_3^- = 8 \\ &x_1, x_2, x_3^+, x_3^-, x_4, x_5 \geq 0 \end{aligned}

例題(3.2.2)

次の線形計画問題それぞれに対し,実行可能領域と目的関数の等高線を図示せよ.さらに,最適解を持つならばそれを求めよ.

まず,標準形に書き換える.ただし,標準形は割愛する.

(1)

最小化3x1x2制約条件x1x21x1+x22x1,x20\begin{aligned} \text{最小化} \qquad &3x_1 - x_2 \\ \text{制約条件} \qquad &x_1 - x_2 \leq 1 \\ &-x_1 + x_2 \leq 2 \\ &x_1, x_2 \geq 0 \end{aligned}

最適解を持つ,最適解はx=(0,2)T\mathbf{x} = (0, 2)^Tであり,目的関数の最小値はZmin=2Z_{min} = -2である.

(2)

最小化x1x2制約条件x1x21x1+x22x1,x20\begin{aligned} \text{最小化} \qquad &-x_1 - x_2 \\ \text{制約条件} \qquad &x_1 - x_2 \leq 1 \\ &-x_1 + x_2 \leq 2 \\ &x_1, x_2 \geq 0 \end{aligned}

最適解が存在しない.

(3)

最小化x1+2x2制約条件x1+x23x1x21x1,x20\begin{aligned} \text{最小化} \qquad &x_1 + 2x_2 \\ \text{制約条件} \qquad &x_1 + x_2 \leq 3 \\ &x_1 - x_2 \leq -1 \\ &x_1, x_2 \geq 0 \end{aligned}

最適解を持つ,最適解はx=(0,1)T\mathbf{x} = (0, 1)^Tであり,目的関数の最小値はZmin=2Z_{min} = 2である.

(4)

最小化x1+2x2制約条件x1+2x223x1x23x1,x20\begin{aligned} \text{最小化} \qquad &-x_1 + 2x_2 \\ \text{制約条件} \qquad &x_1 + 2x_2 \leq 2 \\ &3x_1 - x_2 \leq -3 \\ &x_1, x_2 \geq 0 \end{aligned}

最適解が存在しない.

例題(3.2.3)

次の制約条件で定義される実行可能領域において,実行可能基底解を全て求めよ.

Ax=b,x0A\mathbf{x} = \mathbf{b}, \qquad \mathbf{x} \geq 0

A=(12241316),x=(x1x2x3x4),b=(45)\begin{aligned} A = \begin{pmatrix} 1 & 2 & 2 & 4 \\ 1 & 3 & 1 & 6 \end{pmatrix}, \mathbf{x} = \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix}, \mathbf{b} = \begin{pmatrix} 4 \\ 5 \end{pmatrix} \end{aligned}

明らかにrankA=2rank A = 2である.行列Aの4本の列ベクトルから2本選ぶ組み合わせの数は6通りある.

(1) (x1,x2x_1, x_2)を基底変数に選んだ場合

xB=B1b=(21)\begin{aligned} \mathbf{x}_B = B^{-1}\mathbf{b} = \binom{2}{1} \end{aligned}

基底解はx=(2,1,0,0)T\mathbf{x} = (2,1,0,0)^Tである.これは非退化実行可能基底解である.

(2) (x1,x3x_1,x_3)を基底変数に選んだ場合

xB=B1b=(61)\begin{aligned} \mathbf{x}_B = B^{-1}\mathbf{b} = \binom{6}{-1} \end{aligned}

基底解はx=(6,0,1,0)T\mathbf{x} = (6,0,-1,0)^Tである.これは実行不可能な基底解である.

(3) (x1,x4x_1,x_4)を基底変数に選んだ場合

xB=B1b=(212)\begin{aligned} \mathbf{x}_B = B^{-1}\mathbf{b} = \binom{2}{\frac{1}{2}} \end{aligned}

基底解はx=(2,0,0,12)T\mathbf{x} = (2,0,0,\frac{1}{2})^Tである.これは非退化実行可能基底解である.

(4) (x2,x3x_2,x_3)を基底変数に選んだ場合

xB=B1b=(3212)\begin{aligned} \mathbf{x}_B = B^{-1}\mathbf{b} = \binom{\frac{3}{2}}{\frac{1}{2}} \end{aligned}

基底解はx=(0,32,12,0)T\mathbf{x} = (0,\frac{3}{2},\frac{1}{2},0)^Tである.これは非退化実行可能基底解である.

(5) (x2,x4x_2,x_4)を基底変数に選んだ場合

行列Aの2列目と3列目は線型従属なので,(x2,x4x_2,x_4)は基底変数にはならない.

(6) (x3,x4x_3,x_4)を基底変数に選んだ場合

xB=B1b=(1234)\begin{aligned} \mathbf{x}_B = B^{-1}\mathbf{b} = \binom{\frac{1}{2}}{\frac{3}{4}} \end{aligned}

基底解はx=(0,0,12,34)T\mathbf{x} = (0,0,\frac{1}{2},\frac{3}{4})^Tである.これは非退化実行可能基底解である.

線形計画法の基本定理

定理: 線型計画問題の標準形が与られたとき,以下のことが成り立つ.
(1) 実行可能解が存在するならば,実行可能基底解が存在する.
(2) 最適解が存在するならば,実行可能基底解の中に最適解が存在する.

この定理から分かること:基底解のみを考えれば十分

単体法の原理

この節では,線型計画問題の標準形を解くための単体法(シンプレックス法,simplex method)を紹介する.単体法基本的な原理は,1組の実行可能基底解が与られた時,目的関数値がより低くなるような新しい実行可能基底解を効率よく求め,そうした実行可能基底形式を順々に求めていくことによって,最終的に最適解に到達するものである.

標準形Ax=b,x0A:Rm×n(m<n,rankA=m)A\mathbf{x} = \mathbf{b}, x \geq 0 \quad A:\mathbb{R}^{m \times n} (m < n, rank A = m)において

A=(B,N),x=(xBxN)BxB+NxN=bc=(cBcN)cTx=cBTxB+cNTxN=cBTB1b+(cNTcBTB1N)xN\begin{aligned} A &= (B, N), \mathbf{x} = \binom{x_B}{x_N} \Rightarrow B\mathbf{x}_B + N\mathbf{x}_N = \mathbf{b} \\ \mathbf{c} &= \binom{c_B}{c_N} \Rightarrow \mathbf{c}^T\mathbf{x} = \mathbf{c}_B^T \mathbf{x}_B + \mathbf{c}_N^T \mathbf{x}_N = \mathbf{c}_B^T B^{-1} \mathbf{b} + (\mathbf{c}_N^T - \mathbf{c}_B^T B^{-1}N) \mathbf{x}_N \end{aligned}

ここで,BBは基底行列,正則で,x=(B1b0)\mathbf{x} = \binom{B^{-1}\mathbf{b}}{0}である.

B1b0かつcNTcBTB1N0最適解B^{-1}\mathbf{b} \geq 0 \text{かつ} \mathbf{c}_N^T - \mathbf{c}_B^T B^{-1}N \geq 0 \Rightarrow \text{最適解}

cNTcBTB1N0\mathbf{c}_N^T - \mathbf{c}_B^T B^{-1}N \geq 0でない時,(cNTcBTB1N)k<0(\mathbf{c}_N^T - \mathbf{c}_B^T B^{-1}N)_k < 0なる,非基底変数xk:0Δx_k:0 \rightarrow \Deltaと増加

よって,目的関数値が減少,現在の基底解は最適解ではない.なら,xkx_kをどこまで大きくできるか?

  • xk:0Δ>0x_k:0 \rightarrow \Delta > 0とすると
    • 目的関数cBTB1b+(cNTcBTB1N)kΔ\mathbf{c}_B^T B^{-1} \mathbf{b} + (\mathbf{c}_N^T - \mathbf{c}_B^T B^{-1}N)_k \Deltaと減少
    • 基底変数xB=B1bxB=B1bΔB1Ak(Akは行列Aの第k)\mathbf{x}_B = B^{-1}\mathbf{b} \rightarrow \overline{\mathbf{x}_B} = B^{-1} \mathbf{b} - \Delta B^{-1} A_k (A_k\text{は行\text{列}}A\text{の第}k\text{列})

xk0\overline{\mathbf{x}_k} \geq 0でなければならないので,b=B1b,y=B1Ak\overline{\mathbf{b}} = B^{-1}\mathbf{b}, y = B^{-1}A_kとおくと

Δ=min{bi/yi  yi>0(i=i,K,m)}\Delta = \min \lbrace \overline{\mathbf{b}_i} / y_i \ |\ y_i > 0(i = i,K,m) \rbrace

まで大きくできる.

そして,xk:0Δ>0x_k:0 \rightarrow \Delta > 0とした時,

  • Δ=bi/yi\Delta = \overline{\mathbf{b}_i} / y_iに対応する基底変数xi0x_i \rightarrow 0
    • xi非基底変数\mathbf{x}_i \rightarrow \text{非基底変数}
    • xk基底変数\mathbf{x}_k \rightarrow \text{基底変数}

というピボット操作(基底変数の入れ替え)を行う.

  • xB=xBΔy0\overline{\mathbf{x}_B} = \mathbf{x}_B - \Delta y \geq 0でなければならないから,yi>0y_i > 0となるiがないなら
    • Δ:\Delta:いくらでも大きくできる.
    • 目的関数をいくらでも小さくできる,つまり,有界でない.

アルゴリズム3.1(単体法)

  • step0:初期実行可能基底解(xB,xNx_B,x_N) = (B1b,0B^{-1}b,0)を選ぶ.b=B1b\overline{b} = B^{-1}bとおく.
  • step1:cNTcBTB1N0c_N^T - c_B^T B^{-1}N \geq 0ならば終了.xBx_Bは最適解.そうでなければ,(cNTcBTB1N)k<0(c_N^T - c_B^T B^{-1}N)_k < 0なる非基底変数xkx_kを選ぶ.
  • step2:y=B1Aky = B^{-1}A_kを計算する.
  • step3:y0y \leq 0ならば終了,有界でない,そうでなければ,Δ\Deltaを計算し,Δ=bi/yi\Delta = \overline{b_i} / y_iなるiを求める.(Δ=min{bi/yi  yi>0(i=1,K,m)}\Delta = \min \lbrace \overline{b_i} / y_i \ |\ y_i > 0(i = 1,K,m) \rbrace)
  • step4:非基底変数xkΔx_k \leftarrow \Delta,そのほかの非基底変数は0のまま.基底変数xBbΔyx_B \leftarrow \overline{b} - \Delta yと更新しstep1へ.

簡単な言葉で言い換えると

  • step0:実行可能基底解を得る
  • step1:入る変数を選ぶ.wの係数 < 0の非基底変数.もし,そのような変数がない場合は\Rightarrow今の解が最適,終了
  • step2:出る変数を選ぶ.入る変数を0から増やす時,最終に0になる変数(基底変数).入る変数の列を見て,正のところの比をとって,比の最小値を選ぶ.
  • step3:もし,全ての入る変数の列が全て0以下ならば,LPは非有界と判定して,終了.そうでなければ,step1へ.

例題:以下の標準形をシンプレックス法で求める

最小化2x1+3x2制約条件2x1+x2+x3=6x1+2x2+x4=6x1,x2,x3,x40\begin{aligned} \text{最小化} \qquad &-2x_1 + 3x_2 \\ \text{制約条件} \qquad &2x_1 + x_2 + x_3 = 6 \\ &x_1 + 2x_2 + x_4 = 6 \\ &x_1, x_2, x_3, x_4 \geq 0 \end{aligned}

注意すること: 常に基底変数xBx_Bと非基底変数xNx_Nを留意し更新すること!

単体法の例

次は単体表で求める.

例題1:次の最小化問題を考える.

最小化w=5x14x2制約条件5x1+2x230x1+2x214x10,x20\begin{aligned} \text{最小化} \qquad &w = -5x_1 - 4x_2 \\ \text{制約条件} \qquad &5x_1 + 2x_2 \leq 30 \\ &x_1 + 2x_2 \leq 14 \\ &x_1 \geq 0, \quad x_2 \geq 0 \end{aligned}

標準形の形にする.

最小化w=5x14x2制約条件5x1+2x2+x3=30x1+2x2+x4=14x1,x2,x3,x40\begin{aligned} \text{最小化} \qquad &w = -5x_1 - 4x_2 \\ \text{制約条件} \qquad &5x_1 + 2x_2 + x_3 = 30 \\ &x_1 + 2x_2 + x_4 = 14 \\ &x_1, x_2, x_3, x_4 \geq 0 \end{aligned}

  • 実行可能基底解がある
  • 目的関数wにおいて基底変数の係数は全て0
  • 非基底変数のいずれかの値を0から増やす
  • 選ぶ基準:wの値が改善するもの \rightarrow wの係数<0のもの
  • 入る変数:最大係数規則 \rightarrow 係数の絶対値がmax
  • ピポット演算:表の書き換え
x1x_1 x2x_2 x3x_3 x4x_4 定数
x3x_3
5 2
1
0
30
305\frac{30}{5}
x4x_4
1 2
0
1
14
141\frac{14}{1}
w-w -5 -4
0
0
0 -

基底変数 x3,x4x_3,x_4
基底変数の値 30,14
単位行列
目的関数において基底変数の係数は全て0

ここで,非基底変数x1,x2x_1,x_2はいずれか負であるため,入る変数はx1=5,x2=4x_1 = -5, x_2 = -4の絶対値が大きいもの(x1x_1)を選ぶ.

どこまでx1x_1を大きくできるか?x3,x40x_3,x_4 \geq 0を保持する範囲内

ここで,x2x_2を0に固定する.

  • 5x1+x3=30x3=305x10x13055x_1 + x_3 = 30 \rightarrow x_3 = 30 - 5x_1 \geq 0 \rightarrow x_1 \leq \frac{30}{5}
  • x1+x4=14x4=14x10x1141x_1 + x_4 = 14 \rightarrow x_4 = 14 - x_1 \geq 0 \rightarrow x_1 \leq \frac{14}{1}

つまり,x1x_1がどんどん大きくしていくと,先に0になるのはx3x_3である.x1=6の時,x3=0x1x3の役割が交換x_1 = 6\text{の時},x_3 = 0 x_1\text{と}x_3\text{の役割が交換}

  • x1:非基底変数基底変数x_1:\text{非基底変数} \rightarrow \text{基底変数}
  • x3:基底変数非基底変数x_3:\text{基底変数} \rightarrow \text{非基底変数}
  • 出る変数:x3x_3が基底から出る

次に入る変数の列を掃き出す:

  • 基底変数の列を集めると単位行列になる
  • wの係数は0
x1x_1 x2x_2 x3x_3 x4x_4 定数
x1x_1
1
25\frac{2}{5} 15\frac{1}{5}
0
6
302\frac{30}{2}
x4x_4
0
85\frac{8}{5} 15-\frac{1}{5}
1
8
408\frac{40}{8}
w-w
0
-2 1
0
30 -

ここで,非基底変数x2,x3x_2,x_3の中でx2x_2が負であるため,入る変数はx2x_2を選ぶ.

第2反復では,入る変数はx2x_2

  • x1=625x20x2302x_1 = 6 - \frac{2}{5}x_2 \geq 0 \rightarrow x_2 \leq \frac{30}{2}
  • x4=885x20x2408x_4 = 8 - \frac{8}{5}x_2 \geq 0 \rightarrow x_2 \leq \frac{40}{8}

比はx4x_4の方が小さい,よって,x4x_4が出る変数として選ばれる.

次に入る変数x2x_2の列を掃き出すが,x2x4x_2\text{と}x_4交代するので,

x1x_1 x2x_2 x3x_3 x4x_4 定数
x1x_1
1
0
14\frac{1}{4} 14-\frac{1}{4}
4
x2x_2
0
1
18-\frac{1}{8} 58\frac{5}{8}
5
w-w
0
0
34\frac{3}{4} 54\frac{5}{4} 40

第3反復で,目的関数の非基底変数の関数0\geq 0,よって,入る変数が選べない.この解だと目的関数はこれ以上下がれないと意味する.つまり,この解は最適解である.

最適値と最適解は

x1=4,x2=5,(x3=0,x4=0)w=40x_1^* = 4, x_2^* = 5, (x_3^* = 0, x_4^* = 0) \quad w^* = -40

となる.

例題2:次の最小化問題を考える.

最小化w=5x14x23x3制約条件2x1+3x2+x354x1+x2+x3113x1+4x2+2x38x10,x20,x30\begin{aligned} \text{最小化} \qquad &w = -5x_1 - 4x_2 - 3x_3 \\ \text{制約条件} \qquad &2x_1 + 3x_2 + x_3 \leq 5 \\ &4x_1 + x_2 + x_3 \leq 11 \\ &3x_1 + 4x_2 + 2x_3 \leq 8 \\ &x_1 \geq 0, \quad x_2 \geq 0, \quad x_3 \geq 0 \end{aligned}

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
2 3 1
1
0
0
5
52\frac{5}{2}
x5x_5
4 1 1
0
1
0
11
114\frac{11}{4}
x6x_6
3 4 2
0
0
1
8
38\frac{3}{8}
w-w -5 -4 -3
0
0
0
0 -

まず,非基底変数x1,x2,x3x_1,x_2,x_3はいずれか負であるため,入る変数はx1=5,x2=4,x3=3x_1 = -5, x_2 = -4, x_3 = -3の絶対値が大きいもの(x1x_1)を選ぶ.

次に出る変数を選ぶ.比を計算すると,値が一番小さいのは52\frac{5}{2}なので,出る変数としてx4x_4が選べれる.

よって,ピボット演算をやる.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
1
32\frac{3}{2} 12\frac{1}{2} 12\frac{1}{2}
0
0
52\frac{5}{2}
51\frac{5}{1}
x5x_5
0
-5
-1
-2
1
0
1
-
x6x_6
0
12-\frac{1}{2} 12\frac{1}{2} 32-\frac{3}{2}
0
1
12\frac{1}{2}
11\frac{1}{1}
w-w
0
72\frac{7}{2} 12-\frac{1}{2} 52\frac{5}{2}
0
0
252\frac{25}{2} -

次にx3x_3が入る変数として選ばれる.比を計算する.注意が必要なところはx5=1+x3x3に制限なし(x31)x_5 = 1 + x_3 \rightarrow x_3\text{に制限なし}(x_3 \geq -1).

x6x_6の比が小さいので,x6x_6が出る変数として選ばれる.

次はピボットをする.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
1
2
0
2
0
-1
2
51\frac{5}{1}
x5x_5
0
-6
0
-5
1
2
2
-
x6x_6
0
-1
1
-3
0
2
1
11\frac{1}{1}
w-w
0
3
0
1
0
1 13 -

非基底変数x2,x4,x6x_2,x_4,x_6の係数が全部正であるから,終了.

出る変数を選ぶ時に,列を縦で見て,係数がマイナスとゼロものがいたら,それは比には参加しない.

例題3:次の最小化問題を考える.

最小化w=5x14x2制約条件4x15x2124x1+5x215x10,x20\begin{aligned} \text{最小化} \qquad &w = -5x_1 - 4x_2 \\ \text{制約条件} \qquad &4x_1 - 5x_2 \leq 12 \\ &-4x_1 + 5x_2 \leq 15 \\ &x_1 \geq 0, \quad x_2 \geq 0 \end{aligned}

x1x_1 x2x_2 x3x_3 x4x_4 定数
x3x_3
4
0
1
0
124\frac{12}{4}
x4x_4
-4
1
0
1
-
w-w -5
0
0
0
0

まず,非基底変数x1x_1は負であるため,入る変数はx1x_1を選ぶ.

次に比を計算すると一番小さいx3x_3を出る変数として選ばれる.

ピボットをやると(ピボットの点を1になる)

x1x_1 x2x_2 x3x_3 x4x_4 定数
x1x_1
1
54-\frac{5}{4} 14\frac{1}{4}
0
3
x4x_4
0
0 1
1
27
w-w
0
414-\frac{41}{4} 54\frac{5}{4}
0
15

今度入る変数を選ぶと,x2x_2しかない.この列を見ると,値が全て0以下のため

  • x2\Rightarrow x_2に対する制限なし
  • x2\Rightarrow x_2はいくらでも大きくなれる
  • \RightarrowLPは非有界,終了

入る変数を選んだ後,出る変数が選べなかったら,それは入る変数は好きなだけ大きくしていいよっていうことだから.元のLPが非有界で安定されて終了になる.

例題(3.5.1)

次の線型計画問題それぞれに対して単体法を適用せよ

(1)

最小化w=x13x22x3制約条件x1+2x2x34x1+2x2+2x32x1x2+x32x1,x2,x30\begin{aligned} \text{最小化} \qquad &w = -x_1 - 3x_2 - 2x_3 \\ \text{制約条件} \qquad &-x_1 + 2x_2 - x_3 \leq 4 \\ &-x_1 + 2x_2 + 2x_3 \leq 2 \\ &x_1 - x_2 + x_3 \leq 2 \\ &x_1, x_2, x_3 \geq 0 \end{aligned}

入る変数x2x_2, 出る変数x5x_5

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
-1 2 -1
1
0
0
4
42\frac{4}{2}
x5x_5
-1 2 2
0
1
0
2
22\frac{2}{2}
x6x_6
1
-1
1
0
0
1
2
-
w-w -1 -3 -2
0
0
0
0 -

入る変数x1x_1, 出る変数x6x_6

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
0
0
-3
1
-1
0
2
-
x2x_2
12-\frac{1}{2}
1
1
0
12\frac{1}{2}
0
1
-
x6x_6
12\frac{1}{2}
0
2
0
12\frac{1}{2}
1
3
312\frac{3}{\frac{1}{2}}
w-w 52-\frac{5}{2}
0
1
0
32\frac{3}{2}
0
3 -
x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
0
0
-3
1
-1 0
2
x2x_2
0
1
3
0
1 1
4
x1x_1
1
0
4
0
1 2
6
w-w
0
0
11
0
4 5 18

目的関数の非基底変数の関数 0\geq 0,よって,入る変数が選べない.この時,x1=6,x2=4,x3=0x_1 = 6, x_2 = 4, x_3 = 0なので,この解は最適解であり,最小値は-18である.

(2)

最小化w=x12x2制約条件x12x21x1+x22x1,x20\begin{aligned} \text{最小化} \qquad &w = -x_1 - 2x_2 \\ \text{制約条件} \qquad &x_1 - 2x_2 \leq 1 \\ &-x_1 + x_2 \leq 2 \\ &x_1, x_2 \geq 0 \end{aligned}

入る変数x2x_2,出る変数x4x_4

x1x_1 x2x_2 x3x_3 x4x_4 定数
x3x_3
1
-2
1
0
1
-
x4x_4
-1 1
0
1
2
21\frac{2}{1}
w-w -1 -2
0
0
0 -

掃き出しをすると

x1x_1 x2x_2 x3x_3 x4x_4 定数
x3x_3
-1
0
1
2
5
x2x_2
-1
1
0
1
2
w-w -3
0
0
2 4

第1列の値が全部0以下で,出る変数が選べなかったので,元のLPは非有界である.

今までの例から類推できることをまとめると次の通りである.
(1) 実行可能基底解は実行可能領域の端点に対応している.
(2) 単体法の1回の掃き出しの操作により,多面体領域のある端点から隣接した端点に移ることができる.

2段階法

初期実行可能基底が容易に分からない時(そもそも実行可能かも分からない時)に適用する方法.

第1段階は補助変数(人為変数)を加えた補助問題を作り,解く.この補助問題の特徴は元のLPが実行可能\Leftrightarrow補助問題の最適解=0である.

第2段階は補助問題最適解=0の時:最終的な単体表から元のLPの実行可能基底が作れる.この基底解を初期段階として単体表を適用する.

例題1:

最小化w=2x1+3x2制約条件4x1+x2133x1+2x216x1+2x28x1,x20\begin{aligned} \text{最小化} \qquad &w = 2x_1 + 3x_2 \\ \text{制約条件} \qquad &4x_1 + x_2 \geq 13 \\ &3x_1 + 2x_2 \geq 16 \\ &x_1 + 2x_2 \geq 8 \\ &x_1, x_2 \geq 0 \end{aligned}

明らかに実行可能ではないため,スラック変数を入れる.

最小化w=2x1+3x2制約条件4x1+x2x3=133x1+2x2x4=16x1+2x2x5=8x1,x2,x3,x4,x50\begin{aligned} \text{最小化} \qquad &w = 2x_1 + 3x_2 \\ \text{制約条件} \qquad &4x_1 + x_2 - x_3 = 13 \\ &3x_1 + 2x_2 - x_4 = 16 \\ &x_1 + 2x_2 - x_5 = 8 \\ &x_1, x_2, x_3, x_4, x_5 \geq 0 \end{aligned}

各式に補助変数viv_iを追加する.

最小化w=2x1+3x2制約条件4x1+x2x3+v1=133x1+2x2x4+v2=16x1+2x2x5+v3=8x1,x2,x3,x4,x50,v1,v2,v30\begin{aligned} \text{最小化} \qquad &w = 2x_1 + 3x_2 \\ \text{制約条件} \qquad &4x_1 + x_2 - x_3 + v_1 = 13 \\ &3x_1 + 2x_2 - x_4 + v_2 = 16 \\ &x_1 + 2x_2 - x_5 + v_3 = 8 \\ &x_1, x_2, x_3, x_4, x_5 \geq 0, v_1, v_2, v_3 \geq 0 \end{aligned}

こういう形にすると,強制的に入れたv1,v2,v3v_1,v_2,v_3を初期基底として,実行可能になるので,実行可能初期解が容易に得られる.

目的関数はu=v1+v2+v3u = v_1 + v_2 + v_3である.元のLPが実行可能u=0\Leftrightarrow u^* = 0.

最小化v1+v2+v3制約条件4x1+x2x3+v1=133x1+2x2x4+v2=16x1+2x2x5+v3=8x1,x2,x3,x4,x50,v1,v2,v30\begin{aligned} \text{最小化} \qquad &v_1 + v_2 + v_3 \\ \text{制約条件} \qquad &4x_1 + x_2 - x_3 + v_1 = 13 \\ &3x_1 + 2x_2 - x_4 + v_2 = 16 \\ &x_1 + 2x_2 - x_5 + v_3 = 8 \\ &x_1, x_2, x_3, x_4, x_5 \geq 0, v_1, v_2, v_3 \geq 0 \end{aligned}

こんなLPになるが,問題は目的関数が非基底変数であり,目的関数uをx1,,x5x_1, \cdots, x_5だけで表すことが必要である.そのため

v1=134x1x2+x3v2=163x12x2+x4v3=8x12x2+x5v1+v2+v3=378x15x2+x3+x4+x5\begin{aligned} v_1 &= 13 - 4x_1 - x_2 + x_3 \\ v_2 &= 16 - 3x_1 - 2x_2 + x_4 \\ v_3 &= 8 - x_1 - 2x_2 + x_5 \\ v_1 + v_2 + v_3 &= 37 - 8x_1 - 5x_2 + x_3 + x_4 + x_5 \end{aligned}

という準備が必要である.この準備をしとけば,単体法の要件であった目的関数は基底変数の係数が全部0というものを満たすことができる.

次に単体表を作る:

反復1

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 v1v_1 v2v_2 v3v_3 定数
v1v_1 4 1 -1 0 0
1
0
0
13 134\frac{13}{4}
v2v_2 3 2 0 -1 0
0
1
0
16 163\frac{16}{3}
v3v_3 1 2 0 0 -1
0
0
1
8 81\frac{8}{1}
-u -8 -5 1 1 1
0
0
0
-37 -
-w 2 3 0 0 0 0 0 0 0 -

表の色の部分に注目すると,基底変数v1,v2,v3v_1,v_2,v_3が単体法で見ると単位行列が出てきて,目的関数の係数が全部0である.

では,ピボット演算をする.まず,入る変数を選ぶ.入る変数は目的関数uの係数がマイナスものかつ絶対値が大きい方x1x_1を選ぶ.

次は,x1x_1列を使って,出る変数を選ぶ.比を計算し,比が一番小さいのはv1v_1なので,v1v_1は出る変数として選ばれる.

反復2

v1v_1x1x_1の役割をを入れ替わって,基底変数はx1x_1になる.

掃き出しをしたら,入る変数としてx2x_2が選ばれる.続いて,比を計算する.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 v1v_1 v2v_2 v3v_3 定数
x1x_1
1
14\frac{1}{4} 14-\frac{1}{4} 0 0 14\frac{1}{4}
0
0
134\frac{13}{4} 13
v2v_2
0
54\frac{5}{4} 34\frac{3}{4} -1 0 34-\frac{3}{4}
1
0
254\frac{25}{4} 5
v3v_3
0
74\frac{7}{4} 14\frac{1}{4} 0 -1 14-\frac{1}{4}
0
1
194\frac{19}{4} 197\frac{19}{7}
-u
0
-3 -2 1 1 2
0
0
-11 -
-w 0 52\frac{5}{2} 12\frac{1}{2} 0 0 12-\frac{1}{2} 0 0 132-\frac{13}{2} -

v3v_3が出る変数として選ばれる.続いて,ピボット演算をする.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 v1v_1 v2v_2 v3v_3 定数
x1x_1
1
0
27-\frac{2}{7} 0 17\frac{1}{7} 27\frac{2}{7}
0
17-\frac{1}{7} 187\frac{18}{7} 18
v2v_2
0
0
47\frac{4}{7} -1 57\frac{5}{7} 47-\frac{4}{7}
1
57-\frac{5}{7} 207\frac{20}{7} 4
x2x_2
0
1
17\frac{1}{7} 0
47-\frac{4}{7}
17-\frac{1}{7}
0
47\frac{4}{7} 197\frac{19}{7} -
-u
0
0
47-\frac{4}{7} 1 57-\frac{5}{7} 117\frac{11}{7}
0
127\frac{12}{7} 207-\frac{20}{7} -
-w 0 0 17\frac{1}{7} 0 107\frac{10}{7} 1514\frac{15}{14} 0 127\frac{12}{7} 937-\frac{93}{7} -

x5x_5は入る変数として選ばれ,v2v_2は出る変数として選ばれる.

また,x3v1x_3\text{と}v_1の列は反対しているので,結局分かることはv1,v2,v3v_1,v_2,v_3列として全部要らない.もし,実行可能ではなかったら,人工変数はどうでもいいので,x1,x2,x3,x4,x5x_1,x_2,x_3,x_4,x_5だけ注目して,ピボット演算をする.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 定数
x1x_1
1
0
25-\frac{2}{5} 15\frac{1}{5}
0
2
x5x_5
0
0
45\frac{4}{5} 75-\frac{7}{5}
1
4
x2x_2
0
1
35\frac{3}{5} 45-\frac{4}{5}
0
5
-u
0
0
0 0
0
0
-w 0 0 -1 2 0 -19

-uの定数のところは0になるので,元のLPは実行可能と分かった.
これが第1段階は終了である.次に第2段階に移る.

第1段階において,wを単体表に含めた意味:第1段階終了した時点で{x1,x2,x5}\lbrace x_1,x_2,x_5 \rbraceは実行可能基底である.等式制約式の部分に関してはx1,x2,x5x_1,x_2,x_5の列を見ると,単位行列になるが,続けて単体法を適用するには目的関数wからx1,x2x_1,x_2を除く必要がある.

単体表から

x1=2+25x315x4x2=535x3+45x4w=2x1+3x2=19x3+2x4\begin{aligned} x_1 &= 2 + \frac{2}{5}x_3 - \frac{1}{5}x_4 \\ x_2 &= 5 - \frac{3}{5}x_3 + \frac{4}{5}x_4 \\ w &= 2x_1 + 3x_2 = 19 - x_3 + 2x_4 \end{aligned}

今から第2段階を入る.また入る変数を選ぶ.目的関数の行を見ると,マイナスものが一つしかないので,x3x_3が入る変数として選ばれる.比を計算し,x5x_5が出る変数として選ばれる.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 定数
x1x_1
1
0
25-\frac{2}{5}
15\frac{1}{5}
0
2 -
x5x_5
0
0
45\frac{4}{5} 75-\frac{7}{5}
1
4 5
x2x_2
0
1
35\frac{3}{5} 45-\frac{4}{5}
0
5 253\frac{25}{3}
-u
0
0
0 0
0
0
-
-w 0 0 -1 2 0 -19 -

掃き出しをすると

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 定数
x1x_1
1
0
0
12-\frac{1}{2} 12\frac{1}{2} 4
x3x_3
0
0
1
74-\frac{7}{4} 54\frac{5}{4} 5
x2x_2
0
1
0
14\frac{1}{4} 34-\frac{3}{4} 2
-w
0
0
0
14\frac{1}{4} 54\frac{5}{4} -14

この時に目的関数の行を見ると,係数が全部0以上なので,終了.

例題2:実行可能解が存在しない問題

最小化w=2x1+3x2制約条件4x1+x2133x1+2x216x1+2x28x1+x23x10,x20\begin{aligned} \text{最小化} \qquad &w = 2x_1 + 3x_2 \\ \text{制約条件} \qquad &4x_1 + x_2 \geq 13 \\ &3x_1 + 2x_2 \geq 16 \\ &x_1 + 2x_2 \geq 8 \\ &x_1 + x_2 \leq 3 \\ &x_1 \geq 0, x_2 \geq 0 \end{aligned}

スラック変数と人工変数を導入する

最小化w=2x1+3x2制約条件4x1+x2x3+v1=133x1+2x2x4+v2=16x1+2x2x5+v3=8x1+x2+x6=3x1,x2,x3,x4,x5,x60,v1,v2,v30\begin{aligned} \text{最小化} \qquad &w = 2x_1 + 3x_2 \\ \text{制約条件} \qquad &4x_1 + x_2 - x_3 + v_1 = 13 \\ &3x_1 + 2x_2 - x_4 + v_2 = 16 \\ &x_1 + 2x_2 - x_5 + v_3 = 8 \\ &x_1 + x_2 + x_6 = 3 \\ &x_1, x_2, x_3, x_4, x_5, x_6 \geq 0, v_1, v_2, v_3 \geq 0 \end{aligned}

x6x_6の係数がプラスなので,この式は補助変数を入れる必要がない.v4v_4を入れてもいいが,v4v_4を基底にしなくてもx6x_6はそのまま基底変数として使えるので,x6x_6のところにv4v_4が要らない.

単体表を作る:v1,v2,v3v_1,v_2,v_3のところを書かなくてもいい

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
v1v_1 4 1 -1 0 0 0 13 134\frac{13}{4}
v2v_2 3 2 0 -1 0 0 16 163\frac{16}{3}
v3v_3 1 2 0 0 -1 0 8 8
x6x_6 1 1 0 0 0 1 3 3
-u -8 -5 1 1 1 0 -37 -
-w 2 3 0 0 0 0 0 -

入る変数x1x_1,出る変数x6x_6,掃き出す

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
v1v_1
0
-3 -1 0 0 -4 1
v2v_2
0
-1 0 -1 0 -3 7
v3v_3
0
1 0 0 -1 0 5
x1x_1
1
1 0 0 0 1 3
-u
0
3 1 1 1 0
-13
-w 0 1 0 0 0 -2 -6

-uの行を見ると,目的関数の係数が全部0以上のため,非基底変数のどれかを選んで増やしても,これ以上目的関数はよくなれない.
ここで第1段階は終了するが,u=13>0u = 13 > 0となって零ではない.この時,人工変数v1=1,v2=7,v3=5v_1 = 1, v_2 = 7, v_3 = 5が残った状態である.従って,実行可能解は存在しない.元のLPが実行不可能.

例題(3.6.1)

次の線形計画問題に対して2段階法を適用せよ.

最小化w=x1+x2x3制約条件2x1x2+2x342x1+3x2x35x1x2+2x31x10,x20,x30\begin{aligned} \text{最小化} \qquad &w = -x_1 + x_2 - x_3 \\ \text{制約条件} \qquad &2x_1 - x_2 + 2x_3 \leq 4 \\ &-2x_1 + 3x_2 - x_3 \geq 5 \\ &x_1 - x_2 + 2x_3 \geq 1 \\ &x_1 \geq 0, x_2 \geq 0, x_3 \geq 0 \end{aligned}

スラック変数x4,x5,x60x_4,x_5,x_6 \geq 0を導入し,標準形を作り,人工変数v1,v2v_1,v_2を入れる.

最小化w=x1+x2x3制約条件2x1x2+2x3+x4=42x1+3x2x3x5+v1=5x1x2+2x3x6+v2=1x1,x2,x3,x4,x5,x60,v1,v20\begin{aligned} \text{最小化} \qquad &w = -x_1 + x_2 - x_3 \\ \text{制約条件} \qquad &2x_1 - x_2 + 2x_3 + x_4 = 4 \\ &-2x_1 + 3x_2 - x_3 - x_5 + v_1 = 5 \\ &x_1 - x_2 + 2x_3 - x_6 + v_2 = 1 \\ &x_1, x_2, x_3, x_4, x_5, x_6 \geq 0, v_1, v_2 \geq 0 \end{aligned}

u=v1+v2=6+x12x2x3+x5+x6u = v_1 + v_2 = 6 + x_1 - 2x_2 - x_3 + x_5 + x_6, 次に単体表を作る.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4 2
1-1
2 1 0 0 4 -
v1v_1 -2 3 -1 0 -1 0 5 53\frac{5}{3}
v2v_2 1
1-1
2 0 0 -1 1 -
-u 1 -2 -1 0 1 1 -6 -
-w -1 1 -1 0 0 0 0 -

入る変数x2x_2,出る変数v1v_1,掃き出しをする

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4 43\frac{4}{3}
0
53\frac{5}{3}
1
13-\frac{1}{3} 0 173\frac{17}{3} 175\frac{17}{5}
x2x_2 23-\frac{2}{3}
1
13-\frac{1}{3}
0
13-\frac{1}{3} 0 53\frac{5}{3} -
v2v_2 13\frac{1}{3}
0
53\frac{5}{3}
0
13-\frac{1}{3} -1 83\frac{8}{3} 85\frac{8}{5}
-u 13-\frac{1}{3}
0
53-\frac{5}{3}
0
13\frac{1}{3} 1 83-\frac{8}{3} -
-w 13-\frac{1}{3} 0 23-\frac{2}{3} 0 13\frac{1}{3} 0 53-\frac{5}{3} -

入る変数x3x_3,出る変数v2v_2,掃き出しをする

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4 1
0
0
1
0 1 3
x2x_2 35-\frac{3}{5}
1
0
0
25-\frac{2}{5} 15-\frac{1}{5} 115\frac{11}{5}
x3x_3 15\frac{1}{5}
0
1
0
15-\frac{1}{5} 35-\frac{3}{5} 85\frac{8}{5}
-u
0
0
0
0
0
0
0
-w 15-\frac{1}{5} 0 0 0 15\frac{1}{5} 25-\frac{2}{5} 35-\frac{3}{5}

-uの定数のところは0になるので,元のLPは実行可能と分かった.
これが第1段階は終了である.次に第2段階に移る.

第1段階において,wを単体表に含めた意味:第1段階終了した時点で{x2,x3,x4}\lbrace x_2,x_3,x_4 \rbraceは実行可能基底である.等式制約式の部分に関してはx2,x3,x4x_2,x_3,x_4の列を見ると,単位行列になるが,続けて単体法を適用するには目的関数wからx2,x3x_2,x_3を除く必要がある.

x1=3x4x6x2=115+35x1+25x5+15x6x3=8515x1+15x5+35x6w=x1+x2x3=3515x1+15x525x6\begin{aligned} x_1 &= 3 - x_4 - x_6 \\ x_2 &= \frac{11}{5} + \frac{3}{5}x_1 + \frac{2}{5}x_5 + \frac{1}{5}x_6 \\ x_3 &= \frac{8}{5} - \frac{1}{5}x_1 + \frac{1}{5}x_5 + \frac{3}{5}x_6 \\ w &= -x_1 + x_2 - x_3 = \frac{3}{5} - \frac{1}{5}x_1 + \frac{1}{5}x_5 - \frac{2}{5}x_6 \end{aligned}

第2段階では,入る変数x6x_6,出る変数x4x_4,掃き出しをする

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x6x_6 1
0
0
1 0
1
3
x2x_2 25-\frac{2}{5}
1
0
15\frac{1}{5} 25-\frac{2}{5}
0
145\frac{14}{5}
x3x_3 45\frac{4}{5}
0
1
35\frac{3}{5} 15-\frac{1}{5}
0
175\frac{17}{5}
-w 15\frac{1}{5}
0
0
25\frac{2}{5} 15\frac{1}{5}
0
35\frac{3}{5}

この時,目的関数の行を見ると,係数が全て0以上なので,終了.(x1,x2,x3)=(0,145,175)(x_1, x_2, x_3) = (0, \frac{14}{5}, \frac{17}{5})で最適解を取る,wは35-\frac{3}{5}である.

単体法の収束性

アルゴリズムとして機能するためには有限回で停止必要あり(無限ループに陥ってはダメ).

  • 基底解の数は有限

mincTxs.tAx=b,x0高々(nm)=Cnm(n変数,m制約)\begin{aligned} min \qquad &\mathbf{c}^T \mathbf{x} \\ s.t \qquad &A\mathbf{x} = \mathbf{b} ,\quad \mathbf{x} \geq 0 \\ &\text{高々}\binom{n}{m} = C_n^m \text{個}(n\text{変数},m\text{制約}) \end{aligned}

全ての基底解が非退化の時

x1x_1 \cdots xnx_n 定数
全て正
全て正
全て正
-w -

入る変数は正の値として基底に入る

(1) wの値は厳密に減少
(2) 同じ基底解として2度以上通らない \Rightarrow 有限回で終了

退化した基底解があると稀に終了しないことあり,この現象を巡回(cycling)という.

例題:巡回現象が起こる例

最小化w=2x13x2+x3+12x4制約条件2x19x2+x3+9x4013x1+x213x32x402x1+3x2x312x42x10,x20,x30,x40\begin{aligned} \text{最小化} \qquad &w = -2x_1 - 3x_2 + x_3 + 12x_4 \\ \text{制約条件} \qquad &-2x_1 - 9x_2 + x_3 + 9x_4 \leq 0 \\ &\frac{1}{3}x_1 + x_2 - \frac{1}{3}x_3 - 2x_4 \leq 0 \\ &2x_1 + 3x_2 - x_3 - 12x_4 \leq 2 \\ &x_1 \geq 0, x_2 \geq 0, x_3 \geq 0, x_4 \geq 0 \end{aligned}

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 x7x_7 定数
x5x_5 -2
-9
1 9
1
0
0
0 -
x6x_6 13\frac{1}{3} 1 13-\frac{1}{3} -2
0
1
0
0 01\frac{0}{1}
x7x_7 2 3 -1 -12
0
0
1
2 23\frac{2}{3}
-w -2 -3 1 12
0
0
0
0 -

退化している.入る変数x2x_2,出る変数x6x_6

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 x7x_7 定数
x5x_5 1
0
-2 -9
1
9
0
0 01\frac{0}{1}
x2x_2 13\frac{1}{3}
1
13-\frac{1}{3} -1
0
1
0
0 013\frac{0}{\frac{1}{3}}
x7x_7 1
0
0 -6
0
-3
1
2 21\frac{2}{1}
-w -1
0
0 6
0
3
0
0 -

解自体は変化せず,入る変数x1x_1,出る変数x5x_5

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 x7x_7 定数
x1x_1
1
0
-2 -9 1 9
0
0 -
x2x_2
0
1
13-\frac{1}{3} 1 13-\frac{1}{3} -2
0
0 01\frac{0}{1}
x7x_7
0
0
2 3 -1 -12
1
2 23\frac{2}{3}
-w
0
0
-2 -3 1 12
0
0 -

解自体は変化せず,入る変数x4x_4,出る変数x2x_2

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 x7x_7 定数
x1x_1
1
9 1
0
-2 -9
0
0 01\frac{0}{1}
x4x_4
0
1 13\frac{1}{3}
1
13-\frac{1}{3} -2
0
0 013\frac{0}{\frac{1}{3}}
x7x_7
0
-3 1
0
0 -6
1
2 21\frac{2}{1}
-w
0
3 -1
0
0 6
0
0 -

解は変化せず.

基底変数x5,x6,x7x5,x2,x7x1,x2,x7x1,x4,x7x3,x4,x7x3,x6,x7x5,x6,x7\begin{aligned} &\text{基底変数} \\ &x_5,x_6,x_7 \\ &\rightarrow x_5,x_2,x_7 \\ &\rightarrow x_1,x_2,x_7 \\ &\rightarrow x_1,x_4,x_7 \\ &\rightarrow x_3,x_4,x_7 \\ &\rightarrow x_3,x_6,x_7 \\ &\rightarrow x_5,x_6,x_7 \end{aligned}

続けてやると,反復6が反復0に一致しているので,巡回現象が起きている.

最小添字規則

巡回が起きた時の対策

  • 摂動法:基底変数の0,ϵ\epsilon,ϵ\epsilon^2, 0<ϵ10 < \epsilon \leq 1
  • Blandのピボット規則(最小添字規則)

最小添字規則:

  • 入る変数:wの係数 < 0の非基底変数で添字が最小のもの
  • 出る変数:入る変数の値を増やした時,最初に0になる基底変数複数ある時は最小の添字を持つもの

続いて,巡回対策を用いた場合の単体表を作る.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 x7x_7 定数
x5x_5 -2
-9
1 9
1
0
0
0 -
x6x_6 13\frac{1}{3} 1 13-\frac{1}{3} -2
0
1
0
0 01\frac{0}{1}
x7x_7 2 3 -1 -12
0
0
1
2 23\frac{2}{3}
-w -2 -3 1 12
0
0
0
0 -

入る変数今度x1x_1,出る変数はx6x_6

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 x7x_7 定数
x5x_5
1
-3
-1
3
1
6
0
0 -
x1x_1
0
3
-1
-6
0
3
0
0 -
x7x_7
0
-3 1 0
0
-6
1
2 21\frac{2}{1}
-w
0
3 -1 6
0
6
0
0 -

入る変数x3x_3,出る変数x7x_7

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 x7x_7 定数
x5x_5
1
-6
0
-3
1
0 0 2
x1x_1
0
0
0
-6
0
-3 0 2
x3x_3
0
-3
1
0
0
-6 1 2
-w
0
0
0
0
0
0 0 2

定理:Blandの巡回対策を用いた単体法の収束性
退化をしているしていないにも関わらず,Bland巡回対策を用いた単体法は有限回の反復で終了する.

最大改善規則

他のピボット規則として,最大改善規則がある.

最大改善規則:
wの係数 < 0の各非基底変数に対して,それを入る変数に選択した時のwの改善値(減少値)を計算する.最良のものを選択する.

例題:

最小値5x14x2制約条件5x1+2x230x1+2x214x10,x20\begin{aligned} \text{最小値} \qquad &-5x_1 - 4x_2 \\ \text{制約条件} \qquad &5x_1 + 2x_2 \leq 30 \\ &x_1 + 2x_2 \leq 14 \\ &x_1 \geq 0, x_2 \geq 0 \end{aligned}

x1x_1 x2x_2 x3x_3 x4x_4 定数
x3x_3 5 2
1
0
30
x4x_4 1 2
0
1
14
-w -5 -4
0
0
0

入る変数候補:x1,x2x_1,x_2

x1x_1を選ぶと

x1x_1 定数
x3x_3 5 30
6
x4x_4 1 14 14
-w -5 - -

wの改善値 = 5×6=30-5 \times 6 = -30.

x2x_2を選ぶと

x2x_2 定数
x3x_3 2 30 15
x4x_4 2 14
7
-w -4 - -

wの改善値 = 4×7=28-4 \times 7 = -28.

30>28x1|-30| > |-28| \Rightarrow x_1を選択する.

単体法が要するピボット回数

一般には

  • 最大改善 < 最大係数 < 最小添字
  • 多くの場合は制約式に比例する.ピボット数で終了.

ただし,どのピボット規則に対してもn,mの指数回のピボットを要する例が作れる.(Klee-Minty)

\Rightarrow単体法は多項式アルゴリズムであることが示せない.

例題(3.7.1)

次の線形計画問題に対して最小添え字規則に基づく単体法を適用せよ.

最小値x13x22x3制約条件x1+2x2x34x1+2x2+2x32x1x2+x32x10,x20,x30\begin{aligned} \text{最小値} \qquad &-x_1 - 3x_2 - 2x_3 \\ \text{制約条件} \qquad &-x_1 + 2x_2 - x_3 \leq 4 \\ &-x_1 + 2x_2 + 2x_3 \leq 2 \\ &x_1 - x_2 + x_3 \leq 2 \\ &x_1 \geq 0, x_2 \geq 0, x_3 \geq 0 \end{aligned}

標準形は以下となる.

最小値x13x22x3制約条件x1+2x2x3+x4=4x1+2x2+2x3+x5=2x1x2+x3+x6=2x1,,x60\begin{aligned} \text{最小値} \qquad &-x_1 - 3x_2 - 2x_3 \\ \text{制約条件} \qquad &-x_1 + 2x_2 - x_3 + x_4 = 4 \\ &-x_1 + 2x_2 + 2x_3 + x_5 = 2 \\ &x_1 - x_2 + x_3 + x_6 = 2 \\ &x_1, \cdots, x_6 \geq 0 \end{aligned}

次の単体表を作る.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
-1
2 -1
1
0
0
4 -
x5x_5
-1
2 2
0
1
0
2 -
x6x_6 1 -1 1
0
0
1
2 2
-w -1 -3 -2
0
0
0
0 -

最小添字規則に基づいて,x1x_1が入る変数として選ばれる.比を計算し,x6x_6が出る変数として選ばれる.掃き出しをする.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
0
1
0
1
0
1 6 -
x5x_5
0
1 3
0
1
1 4 43\frac{4}{3}
x1x_1
1
-1 1
0
0
1 2 2
-w
0
-4 -1
0
0
1 2 -

最小添字規則に基づいて,x3x_3が入る変数として選ばれる.比を計算し,x5x_5が出る変数として選ばれる.掃き出しをする.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
0
1
0
1
0 1 6 6
x3x_3
0
13\frac{1}{3}
1
0
13\frac{1}{3} 13\frac{1}{3} 43\frac{4}{3} 4
x1x_1
1
43-\frac{4}{3}
0
0
13-\frac{1}{3} 23\frac{2}{3} 23\frac{2}{3} -
-w
0
113-\frac{11}{3}
0
0
13\frac{1}{3} 43\frac{4}{3} 103\frac{10}{3} -

目的関数の係数マイナスのもの一つしかないので,x2x_2が入る変数として選ばれ,比を計算し,x3x_3が出る変数として選ばれる.掃き出しをする.

x1x_1 x2x_2 x3x_3 x4x_4 x5x_5 x6x_6 定数
x4x_4
0
0
-3
1
-1 0 2
x2x_2
0
1
3
0
1 1 4
x1x_1
1
0
4
0
1 2 6
-w
0
0
11
0
4 3 18

目的関数の係数は全て0以上のため,終了.目的関数は(x1,x2,x3)=(6,4,0)(x_1,x_2,x_3) = (6, 4, 0)で最適解を取り,最適解w=18w = -18である.

双対性

双対問題の定義

線形計画問題の標準形

主問題{最小化fp=cTx(xRn)制約条件Ax=b(x0)\begin{aligned} \text{主問題} \begin{cases} \text{最小化} \quad & f_p = \mathbf{c}^T \mathbf{x} (\mathbf{x} \in \mathbb{R}^n) \\ \text{制約条件} \quad & A\mathbf{x} = \mathbf{b} (\mathbf{x} \geq 0) \end{cases} \end{aligned}

に対して,次の線形計画問題を双対問題(dual problem)という.

双対問題{最大化fd=bTy(yRm)制約条件ATyc\begin{aligned} \text{双対問題} \begin{cases} \text{最大化} \quad & f_d = \mathbf{b}^T \mathbf{y} (\mathbf{y} \in \mathbb{R}^m) \\ \text{制約条件} \quad & A^T\mathbf{y} \leq \mathbf{c} \end{cases} \end{aligned}

あるいはスラック変数zRn\mathbf{z} \in \mathbb{R}^nを導入すれば

最大化fd=bTy(y,zについて)制約条件ATy+z=c(z0)\begin{aligned} \text{最大化} \quad & f_d = \mathbf{b}^T \mathbf{y} (\mathbf{y}, \mathbf{z} \text{について}) \\ \text{制約条件} \quad & A^T\mathbf{y} + \mathbf{z} = \mathbf{c} (\mathbf{z} \geq 0) \end{aligned}

となる.双対問題に対して元の最小化問題を主問題(primal problem)という.そして変数xは主変数(primal variable),変数yz\mathbf{y} \text{と} \mathbf{z}は双対変数(dual variable)と呼ばれる.

主問題と双対問題には非常に重要な関係があり,その関係を双対性(duality)という.

例題

minw=5x14x2+0x3+0x4s.t5x1+2x2+x3=30y1x1+2x2+x4=14y2x1,,x40\begin{aligned} min \qquad & w = -5x_1 - 4x_2 + 0x_3 + 0x_4 \\ s.t \qquad & 5x_1 + 2x_2 + x_3 = 30 \cdots y_1 \\ & x_1 + 2x_2 + x_4 = 14 \cdots y_2 \\ & x_1, \cdots, x_4 \geq 0 \end{aligned}

最適値ww^*を下から見積りたい(ww^*がどのくらい小さくなれるか.LPを解かずに考えたい)

1式×(2)\times (-2)

10x14x22x3+0x4=605x14x2+0x3+0x4=w\begin{aligned} -10x_1 - 4x_2 - 2x_3 + 0x_4 &= -60 \\ -5x_1 - 4x_2 + 0x_3 + 0x_4 &= w \end{aligned}

  • x1x_1の係数105-10 \leq -5
    • x10x_1 \geq 0, だから10x15x1-10x_1 \leq -5x_1
  • x2x_2の係数44-4 \leq -4
    • x20x_2 \geq 0, だから4x24x2-4x_2 \leq -4x_2
  • x3,x4x_3,x_4に関しても
    • 2x30x3,0x40x4-2x_3 \geq 0x_3, 0x_4 \geq 0x_4

これらから,(x1x4)T(x_1 \cdots x_4)^T実行可能解なら

60=10x14x22x3+0x45x14x2+0x3+0x4=w\begin{aligned} -60 &= -10x_1 - 4x_2 - 2x_3 + 0x_4 \\ &\leq -5x_1 - 4x_2 + 0x_3 + 0x_4 = w \end{aligned}

よって,w60w^* \geq -60

1式×(1)+\times (-1) + 2式 ×(1)\times (-1)

6x14x2x3x4=445x14x2+0x3+0x4=w\begin{aligned} &-6x_1 - 4x_2 - x_3 - x_4 = -44 \\ &-5x_1 - 4x_2 + 0x_3 + 0x_4 = w \end{aligned}

同様の議論により,w44w^* \geq -44

系統的に行う. 1式×y1+\times y_1 + 2式 ×y2\times y_2

(5y1+y2)x1+(2y1+2y2)x2+y1x3+y2x4=30y1+14y2\begin{aligned} (5y_1 + y_2)x_1 + (2y_1 + 2y_2)x_2 + y_1x_3 + y_2x_4 = 30y_1 + 14y_2 \end{aligned}

この式からww^*の下界を見つけたい

y1,y2y_1,y_2の満たすべき条件

x1の係数5y1+y25x2の係数2y1+2y24x3の係数y10x4の係数y20\begin{aligned} &x_1 \text{の係数} 5y_1 + y_2 \leq -5 \\ &x_2 \text{の係数} 2y_1 + 2y_2 \leq -4 \\ &x_3 \text{の係数} y_1 \leq 0 \\ &x_4 \text{の係数} y_2 \leq 0 \end{aligned}

この時30y1+14y2w\underline{30y_1 + 14y_2} \leq w^*を大きくしたい

双対問題

max30y1+14y2s.t5y1+y252y1+2y24y10y20\begin{aligned} max \qquad & 30y_1 + 14y_2 \\ s.t \qquad & 5y_1 + y_2 \leq -5 \\ & 2y_1 + 2y_2 \leq -4 \\ & y_1 \leq 0 \\ & y_2 \leq 0 \end{aligned}

max(30,14)(y1y2)s.t(51221001)(y1y2)(5400)\begin{aligned} max \qquad & (30,14)\binom{y_1}{y_2} \\ s.t \qquad & \begin{pmatrix} 5 & 1 \\ 2 & 2 \\ 1 & 0 \\ 0 & 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} \leq \begin{pmatrix} -5 \\ -4 \\ 0 \\ 0 \end{pmatrix} \end{aligned}

例題

主問題

minfp=3x1+2x2+5x3+x4s.t2x1+x23x3+5x4=103x17x2+4x3+x4=15x1,,x40\begin{aligned} min \qquad & f_p = 3x_1 + 2x_2 + 5x_3 + x_4 \\ s.t \qquad & 2x_1 + x_2 - 3x_3 + 5x_4 = 10 \\ & 3x_1 - 7x_2 + 4x_3 + x_4 = 15 \\ & x_1, \cdots, x_4 \geq 0 \end{aligned}

が与えられた時,双対問題は次のように表される.

maxfd=10y1+15y2s.t2y1+3y23y17y223y1+4y255y1+y21\begin{aligned} max \qquad & f_d = 10y_1 + 15y_2 \\ s.t \qquad & 2y_1 + 3y_2 \leq 3 \\ & y_1 - 7y_2 \leq 2 \\ & -3y_1 + 4y_2 \leq 5 \\ & 5y_1 + y_2 \leq 1 \end{aligned}

(y1,y2y_1,y_2に非負制約なし)

標準形に書き換える

min10(y1+y1)15(y2+y2)s.t2(y1+y1)+3(y2+y2)+z1=3x1(y1+y1)7(y2+y2)+z2=2x23(y1+y1)+4(y2+y2)+z3=5x35(y1+y1)+(y2+y2)+z4=1x4y1+,y1,y2+,y2,z1,,z40\begin{aligned} min \qquad & -10(y_1^+ - y_1^-) - 15(y_2^+ - y_2^-) \\ s.t \qquad & 2(y_1^+ - y_1^-) + 3(y_2^+ - y_2^-) + z_1 = 3 \leftarrow x_1 \\ &(y_1^+ - y_1^-) - 7(y_2^+ - y_2^-) + z_2 = 2 \leftarrow x_2 \\ &-3(y_1^+ - y_1^-) + 4(y_2^+ - y_2^-) + z_3 = 5 \leftarrow x_3 \\ &5(y_1^+ - y_1^-) + (y_2^+ - y_2^-) + z_4 = 1 \leftarrow x_4 \\ &y_1^+, y_1^-, y_2^+, y_2^-, z_1, \cdots, z_4 \geq 0 \end{aligned}

max3x1+2x2+5x3+x4s.t2x1+x23x3+5x4103x17x2+4x3+x415x1,,x40\begin{aligned} max \qquad & 3x_1 + 2x_2 + 5x_3 + x_4 \\ s.t \qquad & 2x_1 + x_2 - 3x_3 + 5x_4 \leq -10 \\ & 3x_1 - 7x_2 + 4x_3 + x_4 \leq -15 \\ & x_1, \cdots, x_4 \leq 0 \end{aligned}

x1x1x2x2x3x3x4x4\begin{aligned} -x_1 \rightarrow x_1 \\ -x_2 \rightarrow x_2 \\ -x_3 \rightarrow x_3 \\ -x_4 \rightarrow x_4 \end{aligned}

とおいて書き直すと主問題が得られる

  • 対応
    • 双対変数 \leftrightarrow 主制約
    • 双対制約 \leftrightarrow 主変数

弱双対定理

弱双対定理(weak duality theorem):
x^\mathbf{\hat{x}}: 主問題の実行可能解
y^\mathbf{\hat{y}}: 双対問題の実行可能解
cTx^bTy^\Rightarrow \mathbf{c}^T\mathbf{\hat{x}} \geq \mathbf{b}^T \mathbf{\hat{y}}

この定理より,主問題の実行可能解x\mathbf{x}と双対問題の実行可能解(y,z\mathbf{y},\mathbf{z})の目的関数値の差cTxbTy\mathbf{c}^T \mathbf{x} - \mathbf{b}^T \mathbf{y}は,常にゼロ以上である.この差を双対ギャップという.

弱双対定理から次の結果が容易に得られる

(1) x^,y^\mathbf{\hat{x}}, \mathbf{\hat{y}}: 実行可能解がcTx^=bTy^\mathbf{c}^T\mathbf{\hat{x}} = \mathbf{b}^T \mathbf{\hat{y}}を満たす
x^,y^\Rightarrow \mathbf{\hat{x}}, \mathbf{\hat{y}}それぞれ主問題,双対問題の最適解

(2) 主問題が非有界(minfp=\min f_p = -\infty) \Rightarrow双対問題は実行不可能

注意:(2)の逆は成立しない
双対問題が実行不可能 \nRightarrow 主問題が非有界
主問題,双対問題共に実行不可能なこともある

双対定理

(1) 主問題が最適解を持つならば,それに対応する単体乗数が双対問題の最適解になる.さらに,それぞれの最適値は等しい(minfp=maxfd\min f_p = \max f_d)
(2) 主問題及び双対問題が共に実行可能解を持つなら両方共最適解を持ち,それぞれの最適値は一致する.

主問題と双対問題 実行可能 実行可能でない
実行可能 minfp=maxfd\min f_p = \max f_d minfp=\min f_p = -\infty
実行可能でない maxfd=+\max f_d = +\infty -

単体乗数((BT)1cB(B^T)^{-1} \mathbf{c}_B)

mincTxs.tAx=b,x0\begin{aligned} min \qquad & \mathbf{c}^T \mathbf{x} \\ s.t \qquad & A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0 \end{aligned}

B:基底行列
cB\mathbf{c}_B:基底変数に対するc\mathbf{c}の部分ベクトル

例題

主問題

min(5,4,0,0)(x1x2x3x4)s.t(52101201)(x1x2x3x4)=(3014)\begin{aligned} &min \qquad (-5,-4,0,0)\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} \\ &s.t \qquad \begin{pmatrix} 5 & 2 & 1 & 0 \\ 1 & 2 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{pmatrix} = \binom{30}{14} \end{aligned}

その双対問題は

max(30,14)(y1y2)s.t(51221001)(y1y2)(5400)\begin{aligned} &max \qquad (30,14) \binom{y_1}{y_2} \\ &s.t \qquad \begin{pmatrix} 5 & 1 \\ 2 & 2 \\ 1 & 0 \\ 0 & 1 \end{pmatrix} \binom{y_1}{y_2} \leq \begin{pmatrix} -5 \\ -4 \\ 0 \\ 0 \end{pmatrix} \end{aligned}

最後の単体表

x1x_1 x2x_2 x3x_3 x4x_4 定数
x1x_1 1 0 14\frac{1}{4} 14-\frac{1}{4} 4
x2x_2 0 1 18-\frac{1}{8} 58\frac{5}{8} 5
-w 0 0
34\frac{3}{4}
54\frac{5}{4}
40

基底行列は

B=(x1,x2)=(5212)\begin{aligned} B_* = (x_1, x_2) =\begin{pmatrix} 5 & 2 \\ 1 & 2 \end{pmatrix} \end{aligned}

となり,基底変数に対するc\mathbf{c}の部分ベクトルはcB=(54)\mathbf{c}_B = \binom{-5}{-4}である.

従って,yy^*は最適解に対応する単体乗数でy=(BT)1cBy^* = (B_*^T)^{-1} \mathbf{c}_Bを満たす.

y=(BT)1cB=18(2125)(54)=(3454)\begin{aligned} y^* = (B_*^T)^{-1} \mathbf{c}_B = \frac{1}{8}\begin{pmatrix} 2 & -1 \\ -2 & 5 \end{pmatrix} \binom{-5}{-4} = \binom{-\frac{3}{4}}{-\frac{5}{4}} \end{aligned}

y1=34,y2=54,fd=30y1+14y2=40y_1^* = -\frac{3}{4}, y_2^* = -\frac{5}{4}, f_d = 30y_1^* + 14y_2^* = -40

5y1+y2=552y1+2y2=44\begin{aligned} 5y_1^* + y_2^* = -5 \leq -5 \\ 2y_1^* + 2y_2^* = -4 \leq -4 \end{aligned}

が成り立つので,yy^*は双対問題の実行可能解になる.この時,fp=cTx=bTy=fdf_p = \mathbf{c}^T \mathbf{x} = \mathbf{b}^T \mathbf{y} = f_dとなるので,y=(y1y2)y^* = \binom{y_1^*}{y_2^*}は双対問題の最適解になる.

例題

min(5,4,3,0,0,0)(x1x2x3x4x5x6)s.t(231100411010342001)(x1x2x3x4x5x6)=(5118)x1,,x60\begin{aligned} &min \qquad (-5,-4,-3,0,0,0)\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \end{pmatrix} \\ &s.t \qquad \begin{pmatrix} 2 & 3 & 1 & 1 & 0 & 0 \\ 4 & 1 & 1 & 0 & 1 & 0 \\ 3 & 4 & 2 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \end{pmatrix} = \begin{pmatrix} 5 \\ 11 \\ 8 \end{pmatrix} \\ &x_1, \cdots, x_6 \geq 0 \end{aligned}

その双対問題は

max(5,11,8)(y1y2y3)s.t(243314112100010001)(y1y2y3)(543000)\begin{aligned} &max \qquad (5,11,8) \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} \\ &s.t \qquad \begin{pmatrix} 2 & 4 & 3 \\ 3 & 1 & 4 \\ 1 & 1 & 2 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} \leq \begin{pmatrix} -5 \\ -4 \\ -3 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{aligned}

最後の単体表

x1x_1 x2x_2 x3x_3
x4x_4
x5x_5
x6x_6
定数
x1x_1 1 2 0 2 0 -1 2
x5x_5
0 -6 0 -5 1 2 2
x3x_3 0 -1 1 -3 0 2 1
-w 0 3 0
1
0
1
13

基底行列は

B=(x1,x5,x3)=(201411302)\begin{aligned} B_* = (x_1,x_5,x_3) = \begin{pmatrix} 2 & 0 & 1 \\ 4 & 1 & 1 \\ 3 & 0 & 2 \end{pmatrix} \end{aligned}

となり,基底変数に対するc\mathbf{c}の部分ベクトルはcB=(5,0,3)T\mathbf{c}_B = (-5, 0, -3)^Tである.

従って,yy^*は最適解に対応する単体乗数でy=(BT)1cBy^* = (B_*^T)^{-1} \mathbf{c}_Bを満たす.

y=(BT)1cB=(253010122)(503)=(101)\begin{aligned} y^* = (B_*^T)^{-1} \mathbf{c}_B = \begin{pmatrix} 2 & -5 & -3 \\ 0 & 1 & 0 \\ -1 & 2 & 2 \end{pmatrix} \begin{pmatrix} -5 \\ 0 \\ -3 \end{pmatrix} = \begin{pmatrix} -1 \\ 0 \\ -1 \end{pmatrix} \end{aligned}

fd=5y1+11y2+8y3=13f_d = 5y_1^* + 11y_2^* + 8y_3^* = -13

2y1+4y2+3y3=5=5x1>03y1+y2+4y3=74x2=0y1+y2+2y3=3=3x3>0\begin{aligned} 2y_1^* + 4y_2^* + 3y_3^* = -5 = -5 \leftrightarrow x_1^* > 0 \\ 3y_1^* + y_2^* + 4y_3^* = -7 \leq -4 \leftrightarrow x_2^* = 0 \\ y_1^* + y_2^* + 2y_3^* = -3 = -3 \leftrightarrow x_3^* > 0 \end{aligned}

が成り立つので,yy^*は双対問題の実行可能解になる.この時,fp=cTx=bTy=fdf_p = \mathbf{c}^T \mathbf{x} = \mathbf{b}^T \mathbf{y} = f_dとなるので(単体表で目的関数の値共に13で一致する),y=(y1,y2,y3)Ty^* = (y_1^*, y_2^*, y_3^*)^Tは双対問題の最適解になる.

y=(1,0,1)Ty^* = (-1, 0, -1)^Tを注目すると,y1y_1^*は主問題の1番目制約式に対応していて,1番目の制約式はスラック変数x4x_4,2番目はスラック変数x5x_5,3番目はスラック変数x6x_6を対応している.
単体表を見ると,y1,x4;y2,x6y_1^*, x_4; y_2^*, x_6は符号反転して現れている.x5x_5は基底変数なので,下は0である.

また,上の式等号のところを見ると

双対問題1番目の制約式は主変数x1x_1^*,双対問題2番目の制約式は主変数x2x_2^*,双対問題3番目の制約式は主変数x3x_3^*と対応している.
最終的な解を見たら,x1,x3x_1,x_3が正の値を取っている.x2x_2は0である.正の値を取っている主変数に関しては双対問題の制約式が等号で成り立っている.

双対最適解

主問題
mincTx\min \quad \mathbf{c}^T \mathbf{x}
s.tAx=b,x0s.t \quad A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0
にスラック変数を入れたものの時, yiy_i^*:最後の単体表におけるスラック変数xn+ix_{n+i}^*のw係数 ×(1)\times (-1)

相補性定理

x,y\mathbf{x}, \mathbf{y}がそれぞれ主問題と双対問題の最適解になるための必要十分条件は,次の三つの条件が成り立つことである:

(OPT1) Ax=b,x0A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0(主問題の実行可能性)
(OPT2) ATycA^T \mathbf{y} \leq \mathbf{c}(双対問題の実行可能性)
(OPT3) xi(cATy)x_i(\mathbf{c} - A^T \mathbf{y})の第i成分=0 (相補性条件(complementarity condition)または相補スラック条件)

xi>0x_i > 0 \Rightarrow 双対問題の第i式が等号で成立

条件(OPT1),(OPT2),(OPT3)は第5章で述べるKarush-Kuhn-Tucker条件(KKT条件)に相当する.

相補性定理条件を使って解の最適性がチェック可能

x(Ax=b,x0\mathbf{x} (A\mathbf{x} = \mathbf{b}, \mathbf{x} \geq 0を満たす)が主問題の最適解か?

(OPT2),(OPT3)を満たすy\mathbf{y}が作れるか.チェックすれば十分

例題(3.8.1)

次の線形計画問題について考える.

最小値x13x22x3制約条件x1+2x2x34x1+2x2+2x32x1x2+x32x10,x20,x30\begin{aligned} \text{最小値} \qquad &-x_1 - 3x_2 - 2x_3 \\ \text{制約条件} \qquad &-x_1 + 2x_2 - x_3 \leq 4 \\ &-x_1 + 2x_2 + 2x_3 \leq 2 \\ &x_1 - x_2 + x_3 \leq 2 \\ &x_1 \geq 0, x_2 \geq 0, x_3 \geq 0 \end{aligned}

(1) スラック変数を追加して(等式)標準形に書き換えたうえで,双対問題を作れ.
(2) 双対問題の最適解を求めよ.

主問題

min(1,3,2,0,0,0)(x1x2x3x4x5x6)s.t(121100122010111001)(x1x2x3x4x5x6)=(422)x1,,x60\begin{aligned} &min \qquad (-1,-3,-2,0,0,0)\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \end{pmatrix} \\ &s.t \qquad \begin{pmatrix} -1 & 2 & -1 & 1 & 0 & 0 \\ -1 & 2 & 2 & 0 & 1 & 0 \\ 1 & -1 & 1 & 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \end{pmatrix} = \begin{pmatrix} 4 \\ 2 \\ 2 \end{pmatrix} \\ & x_1, \cdots, x_6 \geq 0 \end{aligned}

その双対問題は

max(4,2,2)(y1y2y3)s.t(111221121100010001)(y1y2y3)(132000)\begin{aligned} &max \qquad (4,2,2) \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} \\ &s.t \qquad \begin{pmatrix} -1 & -1 & 1 \\ 2 & 2 & -1 \\ -1 & 2 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \\ y_3 \end{pmatrix} \leq \begin{pmatrix} -1 \\ -3 \\ -2 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{aligned}

最後の単体表は

x1x_1 x2x_2 x3x_3 x4x_4
x5x_5
x6x_6
定数
x4x_4
0 0 -3 1 -1 0 2
x2x_2 0 1 3 0 1 1 4
x1x_1 1 0 4 0 1 2 6
w-w 0 0 11
0
4
5
18

基底行列は

B=(x4,x2,x1)=(121021011)\begin{aligned} B_* = (x_4,x_2,x_1) = \begin{pmatrix} 1 & 2 & -1 \\ 0 & 2 & -1 \\ 0 & -1 & 1 \end{pmatrix} \end{aligned}

となり,基底変数に対するc\mathbf{c}の部分ベクトルはcB=(0,3,1)T\mathbf{c}_B = (0, -3, -1)^Tである.

従って,yy^*は最適解に対応する単体乗数でy=(BT)1cBy^* = (B_*^T)^{-1} \mathbf{c}_Bを満たす.

y=(BT)1cB=(100111012)(031)=(045)\begin{aligned} y^* = (B_*^T)^{-1} \mathbf{c}_B = \begin{pmatrix} 1 & 0 & 0 \\ -1 & 1 & 1 \\ 0 & 1 & 2 \end{pmatrix} \begin{pmatrix} 0 \\ -3 \\ -1 \end{pmatrix} = \begin{pmatrix} 0 \\ -4 \\ -5 \end{pmatrix} \end{aligned}

fd=4y1+2y2+2y3=18f_d = 4y_1^* + 2y_2^* + 2y_3^* = -18

y1y2+y3=1=1x1>02y1+2y2y3=3=3x2>0y1+2y2+y3=132x3=0\begin{aligned} -y_1^* - y_2^* + y_3^* = -1 = -1 \leftrightarrow x_1^* > 0 \\ 2y_1^* + 2y_2^* - y_3^* = -3 = -3 \leftrightarrow x_2^* > 0 \\ -y_1^* + 2y_2^* + y_3^* = -13 \leq -2 \leftrightarrow x_3^* = 0 \end{aligned}

が成り立つので,yy^*は双対問題の実行可能解になる.この時,fp=cTx=bTy=fdf_p = \mathbf{c}^T \mathbf{x} = \mathbf{b}^T \mathbf{y} = f_dとなるので(単体表で目的関数の値共に-18で一致する),y=(y1,y2,y3)T=(0,4,5)Ty^* = (y_1^*, y_2^*, y_3^*)^T = (0, -4, -5)^Tは双対問題の最適解になる.

例題(3.8.2)

次の線形計画問題について考える

最小化x1x2+2x32x4+3x53x6制約x1+2x2+3x3+x4x5+x6=33x1+4x2+x3+2x42x6=9x1,x2,x3,x4,x5,x60\begin{aligned} \text{最小化} \qquad & x_1 - x_2 + 2x_3 - 2x_4 + 3x_5 - 3x_6 \\ \text{制約} \qquad & x_1 + 2x_2 + 3x_3 + x_4 - x_5 + x_6 = 3 \\ & 3x_1 + 4x_2 + x_3 + 2x_4 - 2x_6 = 9 \\ & x_1,x_2,x_3,x_4,x_5,x_6 \geq 0 \end{aligned}

この問題に対して

x1=0,x2=94,x3=0,x4=0,x5=32,x6=0x_1^* = 0, x_2^* = \frac{9}{4}, x_3^* = 0, x_4^* = 0, x_5^* = \frac{3}{2}, x_6^* = 0

が最適解であるかを判定せよ.(相補性条件を用いる)

主問題

min(1,1,2,2,3,3)(x1x2x3x4x5x6)s.t(123112341202)(x1x2x3x4x5x6)=(39)x1,,x60\begin{aligned} &min \qquad (1,-1,2,-2,3,-3)\begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \end{pmatrix} \\ &s.t \qquad \begin{pmatrix} 1 & 2 & 3 & 1 & -1 & 2 \\ 3 & 4 & 1 & 2 & 0 & -2 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \\ x_6 \end{pmatrix} = \begin{pmatrix} 3 \\ 9 \end{pmatrix} \\ & x_1, \cdots, x_6 \geq 0 \end{aligned}

その双対問題は

max(3,9)(y1y2)s.t(132431121022)(y1y2)+(z1z2z3z4z5z6)=(39000000)z10,z20,z30,z40,z50,z60\begin{aligned} &max \qquad (3,9) \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} \\ &s.t \qquad \begin{pmatrix} 1 & 3 \\ 2 & 4 \\ 3 & 1 \\ 1 & 2 \\ -1 & 0 \\ 2 & -2 \end{pmatrix} \begin{pmatrix} y_1 \\ y_2 \end{pmatrix} + \begin{pmatrix} z_1 \\ z_2 \\ z_3 \\ z_4 \\ z_5 \\ z_6 \end{pmatrix} = \begin{pmatrix} 3 \\ 9 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \\ & z_1 \geq 0, z_2 \geq 0, z_3 \geq 0, z_4 \geq 0, z_5 \geq 0, z_6 \geq 0 \end{aligned}

となる.従って,(x1,x2,x3,x4,x5,x6)(x_1,x_2,x_3,x_4,x_5,x_6)が主問題の最適解であり,(y1,y2,z1,z2,z3,z4,z5,z6)(y_1,y_2,z_1,z_2,z_3,z_4,z_5,z_6)が双対問題の最適解である必要十分条件は

{x1+2x2+3x3+x4x5+x6=33x1+4x2+x3+2x42x6=9y1+3y2+z1=32y1+4y2+z2=93y1+y2+z3=0y1+2y2+z4=0y1+z5=02y12y2+z6=0x1z1+x2z2++x6z6=0x1,,x60,z1,,z60\begin{aligned} \begin{cases} & x_1 + 2x_2 + 3x_3 + x_4 - x_5 + x_6 = 3 \\ & 3x_1 + 4x_2 + x_3 + 2x_4 - 2x_6 = 9 \\ & y_1 + 3y_2 + z_1 = 3 \\ & 2y_1 + 4y_2 + z_2 = 9 \\ & 3y_1 + y_2 + z_3 = 0 \\ & y_1 + 2y_2 + z_4 = 0 \\ & -y_1 + z_5 = 0 \\ & -2y_1 - 2y_2 + z_6 = 0 \\ & x_1z_1 + x_2z_2 + \cdots + x_6z_6 = 0 \\ & x_1, \cdots, x_6 \geq 0, z_1, \cdots, z_6 \geq 0 \end{cases} \end{aligned}

条件x1z1+x2z2++x6z6=0x_1z_1 + x_2z_2 + \cdots + x_6z_6 = 0は相補性条件

x1z1=0,x2z2=0,x3z3=0,x4z4=0,x5z5=0,x6z6=0x_1z_1 = 0, x_2z_2 = 0, x_3z_3 = 0, x_4z_4 = 0, x_5z_5 = 0, x_6z_6 = 0

と同値である.

x1=0,x2=94,x3=0,x4=0,x5=32,x6=0x_1^* = 0, x_2^* = \frac{9}{4}, x_3^* = 0, x_4^* = 0, x_5^* = \frac{3}{2}, x_6^* = 0が与えられた時,相補性条件より,z2=0,z5=0z_2 = 0, z_5 = 0,上の必要十分条件に代入すると,
順にy1=0,y2=49,z1=415,z2=0,z3=49,z4=29,z5=0,z6=29y_1 = 0, y_2 = \frac{4}{9}, z_1 = -\frac{4}{15}, z_2 = 0, z_3 = -\frac{4}{9}, z_4 = -\frac{2}{9}, z_5 = 0, z_6 = \frac{2}{9}と計算できる.

この時,条件z1,z3,z40z_1,z_3,z_4 \geq 0を満たさないので,上の必要十分条件を全て満たす解は存在しない.
従って,与えられた解が最適解ではない.

第4章 非線形計画法I(無制約最小化問題)

最適性条件

最小解

f:RnRf:\mathbb{R}^n \rightarrow \mathbb{R}
x:\mathbf{x}^*:大域的最小解: f(x)f(x),xRnf(\mathbf{x})^* \leq f(\mathbf{x}),^\forall x \in \mathbb{R}^n
x:\mathbf{x}^*:居所的最小解: ε>0,f(x)f(x),x,xx<ε^\exists \varepsilon > 0, f(\mathbf{x})^* \leq f(\mathbf{x}) ,^\forall \mathbf{x},||\mathbf{x}^* - \mathbf{x}|| < \varepsilon

  • 一般に局所的最小が見つかれば十分

最適性条件の定理

(1)x\mathbf{x}^*が無制約最小化問題の局所的最小解で,f:RnRf:\mathbb{R}^n \rightarrow \mathbb{R}x\mathbf{x}^*の近傍で連続的微分可能であるならば,

f(x)=0\begin{aligned} \nabla f(\mathbf{x}^*) = \mathbf{0} \end{aligned}

が成り立つ(1次の必要条件).
さらに,ffx\mathbf{x}^*の近傍で2回連続微分可能ならば,

2f(x)は半正定値行列\begin{aligned} \nabla^2 f(\mathbf{x}^*)\text{は半正定値行列} \end{aligned}

になる(2次必要条件).

(2)f:RnRf:\mathbb{R}^n \rightarrow \mathbb{R}x\mathbf{x}^*の近傍で2回連続的微分可能である時,x\mathbf{x}^*がs

f(x)=0かつ2f(x)正定値行列\begin{aligned} \nabla f(\mathbf{x}^*) = \mathbf{0} \text{かつ} \nabla^2 f(\mathbf{x}^*) \text{正定値行列} \end{aligned}

ならば,x\mathbf{x}^*局所的最小解になる(2次の十分条件).

x:f\mathbf{x}^*:f停留点(stationary point).f(x)=0\nabla f(\mathbf{x}^*) = \mathbf{0}

  • 極小点 2f(x)\rightarrow \nabla^2 f(\mathbf{x})半正定値
  • 極大点 2f(x):\rightarrow - \nabla^2 f(\mathbf{x}):半正定値
  • 鞍点(saddle point) \rightarrowどちらでもない

まとめ:【極大値,極小値,鞍点の判定】

  • 二変数の場合,ヘッセ行列の行列式(H<0H < 0)が負なら,この点で極値を取らない(鞍点),行列式が正(H>0H > 0)且つffxx(またはyy)の二階微分(fxxf_{xx} or fyyf_{yy})が正なら極小値,負なら極大値.
  • ヘッセ行列の行列式が0のときは,極大値なのか極小値なのか鞍点なのか全く違うものか一切の判断がつかない.
  • 多変数で一般化した場合,ヘッセ行列が正定値行列なら極小値,負定値行列なら極大値,固有値に正も負も(0ではない)含まれるとき鞍点,それ以外は何もでもない.


2次函数最小化問題を考える,ただし,Qは対称行列である.

最小化f(x)=12xTQx+cTx\begin{aligned} \text{最小化} f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^TQ\mathbf{x} + \mathbf{c}^T\mathbf{x} \end{aligned}

f(x)=Qx+c\nabla f(\mathbf{x}) = Q\mathbf{x} + \mathbf{c}なので1次の必要条件は

Qx+c=0\begin{aligned} Q\mathbf{x} + \mathbf{c} = \mathbf{0} \end{aligned}

となる.QQは正定値.解はglobal minglobal \ min.

例題(4.1.1)

関数f,g:RnRf,g:\mathbf{R}^n \rightarrow \mathbf{R}を凸関数とする.この時次の関数h:h:

h(x)=max(f(x),g(x))(xRn)\begin{aligned} h(x) = max(f(x),g(x)) \qquad (x \in \mathbb{R}^n) \end{aligned}

も凸関数になることを示せ.
証明: u,vRn,λ(0,1)^\forall \mathbf{u},^\forall \mathbf{v} \in \mathbb{R}^n,\lambda \in (0,1)とする,凸関数の定義により,

f(λu+(1λ)v)λf(u)+(1λ)f(v)g(λu+(1λ)v)λg(u)+(1λ)g(v)max(f(λu+(1λ)v),g(λu+(1λ)v))max(λf(u)+(1λ)f(v),g(λu+(1λ)v),λg(u)+(1λ)g(v))λmax(f(u),g(u))+(1λ)max(f(v),g(v))\begin{aligned} f(\lambda \mathbf{u} + (1 - \lambda)\mathbf{v}) &\leq \lambda f(\mathbf{u}) + (1 - \lambda)f(\mathbf{v}) \\ g(\lambda \mathbf{u} + (1 - \lambda)\mathbf{v}) &\leq \lambda g(\mathbf{u}) + (1 - \lambda)g(\mathbf{v}) \\ max(f(\lambda \mathbf{u} + (1 - \lambda)\mathbf{v}), g(\lambda \mathbf{u} + (1 - \lambda)\mathbf{v})) &\leq max(\lambda f(\mathbf{u}) + (1 - \lambda)f(\mathbf{v}), g(\lambda \mathbf{u} + (1 - \lambda)\mathbf{v}), \lambda g(\mathbf{u}) + (1 - \lambda)g(\mathbf{v})) \\ &\leq \lambda max(f(\mathbf{u}), g(\mathbf{u})) + (1 - \lambda)max(f(\mathbf{v}), g(\mathbf{v})) \end{aligned}

従って,h(x)=max(f(x),g(x))h(x) = max(f(x), g(x))も凸関数である.

例題(4.1.2)

以下の2次関数f(x)f(x)それぞれについて,2次の係数行列の固有値を求め,さらに等高線の概形を示せ.

(1)

f(x1,x2)=12(x1,x2)(2223)(x1x2)+(22,1)(x1x2)\begin{aligned} f(x_1,x_2) = \frac{1}{2}(x_1,x_2) \begin{pmatrix} 2 & \sqrt{2} \\ \sqrt{2} & 3 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}+ (2\sqrt{2},-1) \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \end{aligned}

固有値はλ\lambdaとして,det(λIQ)=0det(\lambda I - Q) = 0より,λ=1,λ=4\lambda = 1, \lambda = 4.2つの固有値が同じ符号を持つ場合は,

(2)

f(x1,x2)=12(x1,x2)(122223)(x1x2)+(5,0)(x1x2)\begin{aligned} f(x_1,x_2) = \frac{1}{2}(x_1,x_2) \begin{pmatrix} 1 & -2\sqrt{2} \\ -2\sqrt{2} & 3 \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}+ (5,0) \begin{pmatrix} x_1 \\ x_2 \end{pmatrix} \end{aligned}

固有値はλ\lambdaとして,det(λIQ)=0det(\lambda I - Q) = 0より,λ=1,λ=5\lambda = -1, \lambda = 5.2つの固有値が異なる符号を持つ場合は,

例題(4.1.3)

次の関数f(x):f(x):

f(x1,x2)=x122x1x2+14x2413x23\begin{aligned} f(x_1,x_2) = x_1^2 -2x_1x_2 + \frac{1}{4}x_2^4 - \frac{1}{3}x_2^3 \end{aligned}

の停留点をすべて求め, それぞれの停留点が局所的最小(極小点),極大点,鞍点のいずれであるか判定せよ.

f(x)=0{fx1(x1,x2)=2x12x2=0fx2(x1,x2)=2x1+x23x22=0\begin{aligned} &\nabla f(\mathbf{x}) = \mathbf{0} \\ \Leftrightarrow &\begin{cases} f_{x_1}(x_1,x_2) = 2x_1 - 2x_2 = 0 \\ f_{x_2}(x_1,x_2) = -2x_1 + x_2^3 - x_2^2 = 0 \end{cases} \end{aligned}

よって,停留点は

(x1x2)=(11),(00),(22)\begin{aligned} \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}= \begin{pmatrix} -1 \\ -1 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 2 \\ 2 \end{pmatrix} \end{aligned}

(x1x2)=(11)\binom{x_1}{x_2} = \binom{-1}{-1}の時:

2f(x)=2f(1,1))=(2225)\begin{aligned} \nabla^2 f(\mathbf{x}) = \nabla^2 f(-1,-1)) = \begin{pmatrix} 2 & -2 \\ -2 & 5 \end{pmatrix} \end{aligned}

この時,2f(1,1)\nabla^2 f(-1,-1)の固有値をλ\lambdaとすると,

det(λI2f(1,1))=0λ27λ+6=0\begin{aligned} det(\lambda I - \nabla^2 f(-1,-1)) = 0 \\ \rightarrow \lambda^2 - 7\lambda + 6 = 0 \end{aligned}

λ=7±252>0\lambda = \frac{7 \pm \sqrt{25}}{2} > 0よって,固有値が全て正だから,2f(1,1)\nabla^2 f(-1,-1)は正定値で,(11)\binom{-1}{-1}は極小点.

(x1x2)=(00)\binom{x_1}{x_2} = \binom{0}{0}の時:

2f(x)=2f(0,0))=(2220)\begin{aligned} \nabla^2 f(\mathbf{x}) = \nabla^2 f(0,0)) = \begin{pmatrix} 2 & -2 \\ -2 & 0 \end{pmatrix} \end{aligned}

固有値λ\lambdaとして,det(λI2f(0,0))=0det(\lambda I - \nabla^2 f(0,0)) = 0とすると,λ22λ4=0\lambda^2 -2\lambda -4 = 0より,λ=2±202\lambda = \frac{2 \pm \sqrt{20}}{2},2202<0<2+202\frac{2 - \sqrt{20}}{2} < 0 < \frac{2 + \sqrt{20}}{2}より,2f(0,0)\nabla^2 f(0,0)は不定で,(00)\binom{0}{0}は鞍点.

(x1x2)=(22)\binom{x_1}{x_2} = \binom{2}{2}の時:

2f(x)=2f(1,1))=(2228)\begin{aligned} \nabla^2 f(\mathbf{x}) = \nabla^2 f(-1,-1)) = \begin{pmatrix} 2 & -2 \\ -2 & 8 \end{pmatrix} \end{aligned}

同様に固有値λ\lambdaとして,det(λI2f(2,2))=0det(\lambda I - \nabla^2 f(2,2)) = 0とすると,λ210λ+12=0\lambda^2 -10\lambda + 12 = 0より,λ=10±522>0\lambda = \frac{10 \pm \sqrt{52}}{2} > 0,固有値が全て正のため,2f(2,2)\nabla^2 f(2,2)は正定値で,(22)\binom{2}{2}は極小点.

従って,(11),(22)\binom{-1}{-1}, \binom{2}{2}は極小点,(00)\binom{0}{0}は鞍点.

最小2乗問題

ARm×n,bRm(mn)A \in \mathbb{R}^{m \times n}, \mathbf{b} \in \mathbb{R}^m (m \geq n)

f(x)=12Axb2minf(x)=12(Axb)T(Axb)=12(xTATbT)(Axb)=12{x(ATA)xxTATbbTAx+bTb}=12xT(ATA)x(ATb)Tx+12bTb\begin{aligned} f(\mathbf{x}) &= \frac{1}{2} \parallel A\mathbf{x} - \mathbf{b} \parallel^2 \rightarrow min \\ f(\mathbf{x}) &= \frac{1}{2}(A\mathbf{x} - \mathbf{b})^T(A\mathbf{x} - \mathbf{b}) \\ &= \frac{1}{2}(\mathbf{x}^TA^T - \mathbf{b}^T)(A\mathbf{x} - \mathbf{b}) \\ &= \frac{1}{2} \{\mathbf{x} (A^TA)\mathbf{x} - \mathbf{x}^T A^T \mathbf{b} - \mathbf{b}^T A\mathbf{x} + \mathbf{b}^T\mathbf{b}\} \\ &= \frac{1}{2}\mathbf{x}^T (A^TA) \mathbf{x} - (A^T \mathbf{b})^T \mathbf{x} + \frac{1}{2} \mathbf{b}^T \mathbf{b} \end{aligned}

最小化問題において,Q=ATA,c=ATbQ = A^TA, \mathbf{c} = -A^T\mathbf{b}となる(定数項12bTb\frac{1}{2}\mathbf{b}^T\mathbf{b}を無視しても最小化問題には影響ない).もしrankA=nrank A = nならば行列ATAA^TAは正定値になるので,この最小二乗問題を解くことと連立一次方程式

ATAx=ATb\begin{aligned} A^TA\mathbf{x} = A^T\mathbf{b} \end{aligned}

を解くことは同値になる.これを正規方程式(normal equation)と呼ぶ.

反復法

数値解法は直接法(direct method)と反復法(iterative method)とに大別される.直接法は有限回の手順で真の解を得るような数値解法の総称であり,線形計画問題に対する単体法や連立一次方程式を解くためのガウスの消去法などは直接法に分類される.

反復法は,適切な初期点x0\mathbf{x}_0から出発して反復式xk+1=xk+dk\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{d}_kによって点列{xk}\lbrace \mathbf{x}_k \rbraceを生成し最終的に最適解(もしくは最適性条件を満足する点)x\mathbf{x}^*に収束させようというものである.ここで, xk\mathbf{x}_kkk回目の反復における解x\mathbf{x}^*の近似解である.

探索方向(search direction)dk\mathbf{d}_k:xk\mathbf{x}_kからf(x)f(\mathbf{x})が減少する方向が望ましい.すなわち,点xk\mathbf{x}_kにおける関数f(x)f(\mathbf{x})dk\mathbf{d}_k方向での方向微係数が負になることが望ましい.f(x)f(\mathbf{x})が微分可能の場合には,このことは

limt+0f(xk+tdk)f(xk)t=f(xk)Tdk<0\begin{aligned} \lim_{t \rightarrow +0} \frac{f(\mathbf{x}_k + t\mathbf{d}_k) - f(\mathbf{x}_k)}{t} = \nabla f(\mathbf{x}_k)^T\mathbf{d}_k < 0 \end{aligned}

と書ける.探索方向dk\mathbf{d}_kf(x)f(\mathbf{x})の降下方向(descent direction)と呼ぶ.この時,その方向で適当なステップ幅αk>0\alpha_k > 0を選んで次の近似解を

xk+1=xk+αkdk\begin{aligned} \mathbf{x}_{k+1} = \mathbf{x}_{k} + \alpha_{k}\mathbf{d}_{k} \end{aligned}

として生成していく.こうしたステップ幅の調整を直線探索(line search)という,

  • f(x):x\nabla f(\mathbf{x}): \mathbf{x}においてf(x)f(\mathbf{x})が最も急激に増える方向
  • 方向微分係数の意味:x\mathbf{x}からv\mathbf{v}の向きに少しだけ進んだ時,f(x)f(\mathbf{x})はどのように変化するのか?この変化率を表すのが方向微分である.

アルゴリズム4.1(直線探索を用いた反復法)

  • step0 初期設定をする(初期点x0\mathbf{x_0}などを与える.k=0k = 0とおく).
  • step1 停止条件が満たされていれば,xk\mathbf{x_k}を解として停止する.さもなければ,step2へいく.
  • step2 探索方向dk\mathbf{d}_kを決定する.
  • step3 dk\mathbf{d}_k方向でのステップ幅αk\alpha_kを求める(直線探索).
  • step4 xk+1=xk+αkdk\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_kとおく.
  • step5 k:=k+1k := k + 1とおいてstep1へいく.

step1においてよく用いられる停止条件は,勾配ベクトルの大きさf(xk)\parallel \nabla f(\mathbf{x}_k) \parallelや点列{xk}\lbrace \mathbf{x}_k \rbraceの変動xkxk1\parallel \mathbf{x}_k - \mathbf{x}_{k-1} \parallelがある程度小さくなったら解に収束したと見なすことである.

収束性定義

反復法は点列{x}\lbrace \mathbf{x} \rbraceを生成する.

  • {x}\lbrace \mathbf{x} \rbraceは収束するか
  • 収束するなら,どのぐらいのスピードか

アルゴリズムの収束性は大域的収束性と局所的収束性の2つに分けられる.

大域的収束性(global convergence)とは,任意の初期点から出発した時,有限の反復回数でx\mathbf{x}^*が得られるか,もしくは生成される点列がx\mathbf{x}^*に収束する(言い換えれば,解からかなり離れた初期点から出発してもx\mathbf{x}^*に収束する)ことをいう.ただし,点列{xk}\lbrace \mathbf{x}_k \rbracex\mathbf{x}^*に収束することが言えなくてもf(xk)0\parallel \nabla f(\mathbf{x}_k) \parallel \rightarrow 0が成り立つ場合にも大域的収束するという.

局所的収束性(local convergence)とは初期点をx\mathbf{x}^*の十分近くに選べばx\mathbf{x}^*に収束する性質のことである.

この場合には収束率(rate of convergence)が重要になる.x\mathbf{x}を最小点,{xk}\lbrace \mathbf{x}_k \rbraceを反復法で得られた点列とする.この時,ある正整数k0k_0がとれて,任意のk>k0k > k_0に対して,rk(0,1)r_k \in (0, 1)として

xk+1x<rkxk+1xp\begin{aligned} \parallel \mathbf{x_{k+1}} - \mathbf{x} \parallel < r_k \parallel \mathbf{x_{k+1}} - \mathbf{x} \parallel^p \end{aligned}

が成り立つ時,ppをそのアルゴリズムの収束次数という. また, {rk}kN\lbrace r_k \rbrace_{k \in \mathbb{N}}00に収束する時, 超p次収束という.

直線探索法(line search method)

直線探索法(line search method)は解法の大域的収束性を実現するための手段の1つである.

dk\mathbf{d}_k方向で目的関数値を最小にするステップ幅を選ぶこと,すなわち,

f(xk+αkdk)=mina{f(xk+αdk)  α>0}\begin{aligned} f(\mathbf{x}_k + \alpha_k\mathbf{d}_k) = \min_a \lbrace f(\mathbf{x}_k + \alpha \mathbf{d}_k)\ |\ \alpha > 0 \rbrace \end{aligned}

となるαk\alpha_kを選ぶ直線探索を正確な直線探索(exact line search)という. または, 最小値であるための必要条件を満たすαk\alpha_k, すなわち

αk=min{α  f(xk+αdk)Tdk=0,α>0}\begin{aligned} \alpha_k = \min \lbrace \alpha \ |\ \nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k = 0, \alpha > 0 \rbrace \end{aligned}

となるαk\alpha_kを選ぶ探索も正確な直線探索ということにする.

f(x)=12xTAx+bTx\begin{aligned} f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A\mathbf{x} + \mathbf{b}^T \mathbf{x} \end{aligned}

を考える.近似解xk\mathbf{x}_kと降下方向dk\mathbf{d}_kが与えられた時,正確な直線探索によってステップ幅αk\alpha_kを求める.

αk=dkTf(xk)dkTAdk\alpha_k = -\frac{\mathbf{d}_k^T \nabla f(\mathbf{x}_k)}{\mathbf{d}_k^T A\mathbf{d}_k}

(1)Armijo(アルミホ)条件

  • f(x)f(x)が減少

0<ξ<10 < \xi < 1であるような定数ξ\xiに対して,

f(xk+αdk)f(xk)+ξαf(xk)Tdk\begin{aligned} f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + \xi \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k \end{aligned}

を満たすα>0\alpha > 0を選ぶ.

(2)Wolfe(ウルフ)条件

  • dkd_kが小さくなりすぎない

0<ξ1<ξ2<10 < \xi_1 < \xi_2 < 1であるような定数ξ1,ξ2\xi_1, \xi_2に対して.

f(xk+αdk)f(xk)+ξ1αf(xk)Tdkξ2f(xk)Tdkf(xk+αdk)Tdk\begin{aligned} f(\mathbf{x}_k + \alpha \mathbf{d}_k) \leq f(\mathbf{x}_k) + \xi_1 \alpha \nabla f(\mathbf{x}_k)^T \mathbf{d}_k \\ \xi_2 \nabla f(\mathbf{x}_k)^T \mathbf{d}_k \leq \nabla f(\mathbf{x}_k + \alpha \mathbf{d}_k)^T \mathbf{d}_k \end{aligned}

を満たすα>0\alpha > 0を選ぶ.

アルゴリズム4.2(Armijo条件に対する直線探索法)

  • step0 現在の近似解xk\mathbf{x}_k,パラメータ0<ξ<1,0<τ<10 < \xi < 1, 0 < \tau < 1を与える.
  • step1 探索方向dk\mathbf{d}_kで,Armijo条件を満たすステップ幅αk\alpha_kを求める.(以下はその手順))
  • step1.0 βk,0=1,i=0\beta_{k,0} = 1, i = 0とおく.
  • step1.1 Armijo条件f(xk+βk,idk)f(xk)+ξβk,if(xk)Tdkf(\mathbf{x}_k + \beta_{k,i} \mathbf{d}_k) \leq f(\mathbf{x}_k) + \xi \beta_{k,i} \nabla f(\mathbf{x}_k)^T \mathbf{d}_kを満たすならばstep2へいく.さもなければstep1.2へいく.
  • step1.2 βk,i+1=τβk,i,i:=i+1\beta_{k,i+1} = \tau \beta_{k,i}, i := i+1とおいてstep1.1へいく.
  • step2 αk=βk,i\alpha_k = \beta_{k,i}とおく.

例題(4.4.1)

函数f:RnRf:\mathbb{R}^n \rightarrow \mathbb{R}を凸関数とする.この時

xRnが局所最小解xが大域的最小解\begin{aligned} \mathbf{x}^* \in \mathbb{R}^n \text{が局所最小解} \Rightarrow \mathbf{x}^*\text{が大域的最小解} \end{aligned}

であることを示せ.なお,函数ffは微分可能とは限らない.

[証明の方法1]
xS\mathbf{x}^* \in Sを凸計画問題{minf(x)  xS}\lbrace \min f(\mathbf{x}) \ |\ \mathbf{x} \in S \rbraceの解とする.この問題に, x\mathbf{x}^*とは異なり,

f(x)>f(y)\begin{aligned} f(\mathbf{x}^*) > f(\mathbf{y}^*) \end{aligned}

を満たす大域的最適解yS\mathbf{y}^* \in Sがあると仮定する.この時,f(x)f(\mathbf{x})は凸関数で,0α10 \leq \alpha \leq 1を満たすα^\forall \alphaに対して

x(α)=αx+(1α)y\begin{aligned} \mathbf{x}(\alpha) = \alpha \mathbf{x}^* + (1 - \alpha) \mathbf{y}^* \end{aligned}

とおくと

f(x(α)αf(x)+(1α)f(y)<f(x)\begin{aligned} f(\mathbf{x}(\alpha) \leq \alpha f(\mathbf{x}^*) + (1 - \alpha)f(\mathbf{y}^*) < f(\mathbf{x}^*) \end{aligned}

仮説と矛盾になり,従って,局所的最適解は大域的最適解であること証明された.

[証明の方法2]
f(x)=0\nabla f(\mathbf{x}^*) = 0は一次微分を用いた必要条件であるため,局所的最適解f(x)=0\Rightarrow \nabla f(\mathbf{x}^*) = 0となる.

ffは凸関数は次の性質が成り立つ.

x,yに対してf(x)f(y)f(y)T(xy)\begin{aligned} ^\forall \mathbf{x}, \mathbf{y}\text{に対して}f(\mathbf{x}) - f(\mathbf{y}) \geq \nabla f(\mathbf{y})^T (\mathbf{x} - \mathbf{y}) \end{aligned}

y=x\mathbf{y} = \mathbf{x}^*を代入すると,

f(x)f(x)0\begin{aligned} f(\mathbf{x}) - f(\mathbf{x}^*) \geq 0 \end{aligned}

従って,x\mathbf{x}^*は大域的最適解である.

例題(4.4.2)

以下の点列{xk}\lbrace \mathbf{x}_k \rbraceにおいて,xkx<108\parallel \mathbf{x}_k - \mathbf{x}^* \parallel < 10^{-8}およびxkx<1015\parallel \mathbf{x}_k - \mathbf{x}^* \parallel < 10^{-15}を満たす最小のkkをそれぞれ求めよ.

(1)点列{xk}\lbrace \mathbf{x}_k \rbraceは以下の条件を満たす.

x1x=0.01,xk+1x=0.99xkx(k=1,2,)\begin{aligned} \parallel \mathbf{x}_1 - \mathbf{x}^* \parallel = 0.01, \parallel \mathbf{x}_{k + 1} - \mathbf{x}^* \parallel = 0.99 \parallel \mathbf{x}_k - \mathbf{x}^* \parallel (k = 1,2,\cdots) \end{aligned}

rk=xkxr_k = \parallel x_k - x^* \parallelとする,

r1=x1xr2=0.99r1r3=0.99r2=0.992r1rk=0.99k1r1=0.99k1×0.01\begin{aligned} r_1 &= \parallel x_1 - x^* \parallel \\ r_2 &= 0.99r_1 \\ r_3 &= 0.99r_2 = 0.99^2r_1 \\ &\vdots \\ r_k &= 0.99^{k-1} r_1 = 0.99^{k-1} \times 0.01 \end{aligned}

0.99k1<1060.99k1<1013\begin{aligned} 0.99^{k-1} < 10^{-6} \quad 0.99^{k-1} < 10^{-13} \end{aligned}

をそれぞれ解くと,

1
2
3
4
5
6
>>> import math
>>> math.log(10**-6, 0.99)
1374.6317296601653
>>>
>>> math.log(10**-13, 0.99)
2978.368747597025

よって,条件を満たす最小のkkはそれぞれk=1375,k=2979k = 1375, k = 2979

(2)点列{xk}\lbrace \mathbf{x}_k \rbraceは以下の条件を満たす.

x1x=0.25,xk+1x=2.0xkx2(k=1,2,)\begin{aligned} \parallel \mathbf{x}_1 - \mathbf{x}^* \parallel = 0.25, \parallel \mathbf{x}_{k + 1} - \mathbf{x}^* \parallel = 2.0 \parallel \mathbf{x}_k - \mathbf{x}^* \parallel^2 (k = 1,2,\cdots) \end{aligned}

rk=xkxr_k = \parallel x_k - x^* \parallelとする,

r1=x1xr2=2r12r3=2r22=23r14r4=2r32=27r18rk=22k11r12k1\begin{aligned} r_1 &= \parallel x_1 - x^* \parallel \\ r_2 &= 2r_1^2 \\ r_3 &= 2r_2^2 = 2^3r_1^4 \\ r_4 &= 2r_3^2 = 2^7r_1^8 \\ &\vdots \\ r_k &= 2^{2^{k-1}-1}r_1^{2^{k-1}} \end{aligned}

rk<108r_k < 10^{-8}を解くと

22k11r12k1<108122k1<2×108\begin{aligned} 2^{2^{k-1}-1}r_1^{2^{k-1}} &< 10^{-8} \\ \frac{1}{2}^{2^{k-1}} &< 2 \times 10^{-8} \end{aligned}

これと2回log\logを取ると,

1
2
3
4
>>> math.log(2*10**-8, 0.5)
25.5754247590989
>>> math.log(25.5754247590989, 2)
4.676686295474069

k1<4.676686295474069k-1 < 4.676686295474069となるから,条件を満たす最小のkkk=5k = 5である.

同様に,rk<1015r_k < 10^{-15}を解くと

22k11r12k1<1015122k1<2×1015\begin{aligned} 2^{2^{k-1}-1}r_1^{2^{k-1}} &< 10^{-15} \\ \frac{1}{2}^{2^{k-1}} &< 2 \times 10^{-15} \end{aligned}

2回log\logを取ると,

1
2
3
4
>>> math.log(2*10**-15, 0.5)
48.82892142331043
>>> math.log(48.82892142331043, 2)
5.609664005682176

k1<5.609664005682176k-1 < 5.609664005682176となるから,条件を満たす最小のkkk=6k = 6である.

例題(4.4.3)

次の函数

f(x1,x2)=10(x1x22)2+(x21)2\begin{aligned} f(x_1,x_2) = 10(x_1 - x_2^2)^2 + (x_2 - 1)^2 \end{aligned}

(x1,x2)=(1,1)(x_1^*, x_2^*) = (1,1)で最小値をとる.点(x1,x2)=(1,1)(x_1^*, x_2^*) = (1,1)におけるf(x1,x2)f(x_1,x_2)のヘッセ行列2f(1,1)\nabla^2 f(1,1)の固有値を求め,さらに2次近似

q(x1,x2)=12(x1,x2)2f(1,1)(x1x2)+f(1,1)T(x1x2)\begin{aligned} q(x_1,x_2) = \frac{1}{2}(x_1,x_2) \nabla^2 f(1,1) \binom{x_1}{x_2} + \nabla f(1,1)^T \binom{x_1}{x_2} \end{aligned}

の等高線の概形を示せ.

f(x1,x2)=10x1220x1x22+10x24+x222x2+1\begin{aligned} f(x_1,x_2) = 10x_1^2 - 20x_1x_2^2 + 10x_2^4 + x_2^2 - 2x_2 + 1 \end{aligned}

偏微分をすると,

fx1x1(x1,x2)=20fx2x2(x1,x2)=40x1+120x22+2fx1x2(x1,x2)=fx2x1(x1,x2)=40x2\begin{aligned} f_{x_1x_1}(x_1,x_2) &= 20 \\ f_{x_2x_2}(x_1,x_2) &= -40x_1 + 120x_2^2 + 2 \\ f_{x_1x_2}(x_1,x_2) &= f_{x_2x_1}(x_1,x_2) = -40x_2 \end{aligned}

となる.よって,点(x1,x2)=(1,1)(x_1^*, x_2^*) = (1, 1)におけるf(x1,x2)f(x_1, x_2)のHesse行列は

2f(1,1)=[20404082]\begin{aligned} \nabla^2 f(1, 1) =\begin{bmatrix} 20 & -40 \\ -40 & 82 \end{bmatrix} \end{aligned}

det(λI2f(1,1))=0λ2102λ+40=0\begin{aligned} det(\lambda I - \nabla^2 f(1,1)) = 0 \\ \rightarrow \lambda^2 - 102\lambda + 40 = 0 \end{aligned}

よって,固有値は

λ=51±2561\begin{aligned} \lambda = 51 \pm \sqrt{2561} \end{aligned}

従って,2次近似は

q(x1,x2)=12(x1,x2)2[20404082](x1x2)+f(1,1)T(x1x2)\begin{aligned} q(x_1,x_2) = \frac{1}{2}(x_1,x_2) \nabla^2 \begin{bmatrix} 20 & -40 \\ -40 & 82 \end{bmatrix} \binom{x_1}{x_2} + \nabla f(1,1)^T \binom{x_1}{x_2} \end{aligned}

となる.Pythonで等高線のグラフを作ると,

降下法の大域的収束性

本節では, 降下方向と直線探索を組合わせた反復法の大域的収束性に関する定理を証明する.

Zoutendijk条件

探査方向dk\mathbf{d}_kが降下方向であり(f(xk)Tdk<0\nabla f(\mathbf{x}_k)^T \mathbf{d}_k < 0),ステップ幅αk\alpha_kがWolfe条件を満たすことを仮定する.目的関数f(x)f(x)が下に有界で(minf(x)>\min f(x) > -\infty),かつ,初期点x0\mathbf{x}_0における準位集合{xRn  f(x)f(x0)}\lbrace \mathbf{x} \in \mathbb{R}^n \ |\ f(\mathbf{x}) \leq f(\mathbf{x}_0) \rbraceを含む開集合N\mathbb{N}において連続微分可能であることを仮定する.さらに,f(x)\nabla f(\mathbf{x})N\mathbb{N}上でリプシッツ連続(Lipschitz continuous)であること,つまり

f(x)f(y)Lxy\begin{aligned} \parallel \nabla f(\mathbf{x}) - \nabla f(\mathbf{y}) \parallel \leq L \parallel \mathbf{x} - \mathbf{y} \parallel \end{aligned}

を満たす定数L>0L > 0が存在することを仮定する.この時,反復式xk+1=xk+αkdk\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_kで生成される点列{xk}\lbrace \mathbf{x}_k \rbraceに対して

k=0(f(xk)Tdkdk)2<\begin{aligned} \sum_{k=0}^\infty (\frac{\nabla f(\mathbf{x}_k)^T \mathbf{d}_k}{\parallel \mathbf{d}_k \parallel})^2 < \infty \end{aligned}

が成り立つ.あるいは同値な式として

k=0(f(xk)cosθk)2<\begin{aligned} \sum_{k=0}^\infty (\parallel \nabla f(\mathbf{x}_k)\parallel \cos\theta_k)^2 < \infty \end{aligned}

が成り立つ.ただし,θk\theta_kf(xk)-\nabla f(\mathbf{x}_k)と探索方向dk\mathbf{d}_kとなす角で

cosθk=(f(xk))Tdkf(xk)dk\begin{aligned} \cos\theta_k = \frac{(-\nabla f(\mathbf{x}_k))^T \mathbf{d}_k}{\parallel \nabla f(\mathbf{x}_k) \parallel \parallel \mathbf{d}_k \parallel} \end{aligned}

と定義される.

上の2つの式をZoutendijk(ズーテンダイク)条件という.また,無限級数が収束するための必要条件より

limkf(xk)Tdkdk=0\begin{aligned} \lim_{k \rightarrow \infty} \frac{\nabla f(\mathbf{x}_k)^T \mathbf{d}_k}{\parallel \mathbf{d}_k \parallel} = 0 \end{aligned}

あるいは

limkf(xk)cosθk=0\lim_{k \rightarrow \infty} \parallel \nabla f(\mathbf{x}_k) \parallel \cos\theta_k = 0

が成り立つ.最急降下法を用いることを考え,θk\theta_kが90°から十分に遠いことを仮定するとcosθkδ>0(k)\cos\theta_k \geq \delta > 0(\forall k)を満たす定数δ>0\delta > 0が存在する.従って,

limkf(xk)=0\begin{aligned} \lim_{k \rightarrow \infty} \parallel \nabla f(\mathbf{x}_k) \parallel = 0 \end{aligned}

これは,直線探索付き最急降下法の大域的収束性を表している.

補充: 特にdk=f(xk)\mathbf{d}_k = -\nabla f(\mathbf{x}_k)をとる.このdk\mathbf{d}_kf(xk)dk=f(xk)2<0\nabla f(\mathbf{x}_k) \cdot \mathbf{d}_k = -\parallel f(\mathbf{x}_k) \parallel^2 < 0を満たすので,降下方向である.

Cauchy-Schwarzの不等式における等号成立条件から,dk\parallel \mathbf{d}_k \parallelを固定して考えた時,このdk\mathbf{d}_kf(xk)dk\nabla f(\mathbf{x}_k) \cdot \mathbf{d}_kを最小にするものである.つまり最も急に減少させるものである.そのためdk=f(xk)\mathbf{d}_k = -\nabla f(\mathbf{x}_k)とする方法を最急降下法と呼ぶ.

考えるべきこと:dk\mathbf{d}_kの決め方
一次モデルに基づく方法: 最急降下法

  • 勾配ベクトルのみ使う

f(xk+d)l(d)=f(xk)+f(xk)Td\begin{aligned} f(\mathbf{x}_k + \mathbf{d}) \simeq l(\mathbf{d}) = f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T \mathbf{d} \end{aligned}

二次モデルに基づく方法: 共役勾配法,ニュートン法,準ニュートン法

  • ヘッセ行列も使う

f(xk+d)q(d)=f(xk)+f(xk)Td+12dT2f(xk)d\begin{aligned} f(\mathbf{x}_k + \mathbf{d}) \simeq q(\mathbf{d}) = f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T \mathbf{d} + \frac{1}{2}\mathbf{d}^T \nabla^2 f(\mathbf{x}_k) \mathbf{d} \end{aligned}

最急降下法

最急降下法(steepest descent method)では,kk回目の反復における探査方向として,1次モデルを局所的に最小にする方向,すなわち,方向微係数f(xk)Td\nabla f(\mathbf{x}_k)^T \mathbf{d}が最も小さくなる方向を選ばれる.

dk=f(xk)\begin{aligned} \mathbf{d}_k = -\nabla f(\mathbf{x}_k) \end{aligned}

これを最急降下方向という.

最急降下法の性質

  • 最急降下法は,必ず停留点(f(x)=0\nabla f(\mathbf{x}) = 0となる点)に収束(大域的収束性)

    • 出発点の選ぶ方次第では,局所的最適解に収束
    • 凸関数の場合,必ず大域的最適解に収束
  • ある種の凸関数(狭義凸2次関数)に対しては,一次収束をする

    • 一次収束:毎回の反復で,現在の点と極限との距離が,一定の割合で減少すること.ある定数0<β<10 < \beta < 1である整数k0k_0に対して,k>k0k > k_0ならば,xk+1xβxkx\parallel x^{k+1} - x^* \parallel \leq \beta \parallel x^k - x^* \parallelが成立(xx^*は極限の点,収束先)
    • 一次収束する場合でも,収束スピードは遅いこともある

アルゴリズム4.3(最急降下法(直線探索付き))

step0 初期点x0\mathbf{x}_0を与える.k=0k = 0とおく.
step1 停止条件が満たされていれば,xk\mathbf{x}_kを解くとみなして停止する.さもなければ, step2へいく.
step2 dk=f(xk)\mathbf{d}_k = - \nabla f(\mathbf{x}_k)として探索方向を求める.
step3 Armijo(またはWolfe)条件を用いた直線探索によって, fk\mathbf{f}_k方向のステップ幅αk\alpha_kを求める.
step4 xk+1=xk+αkdk\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_kとおく.
step5 k:=k+1k := k+1とおいてstep1へいく.

最急降下法の大域的収束性

探査方向dk\mathbf{d}_kが降下方向であり(f(xk)Tdk<0\nabla f(\mathbf{x}_k)^T \mathbf{d}_k < 0),ステップ幅αk\alpha_kがWolfe条件を満たすことを仮定する.目的関数f(x)f(x)が下に有界で(minf(x)>\min f(x) > -\infty),かつ,初期点x0\mathbf{x}_0における準位集合{xRn  f(x)f(x0)}\lbrace \mathbf{x} \in \mathbb{R}^n \ |\ f(\mathbf{x}) \leq f(\mathbf{x}_0) \rbraceを含む開集合N\mathbb{N}において連続微分可能であることを仮定する.さらに,f(x)\nabla f(\mathbf{x})N\mathbb{N}上でリプシッツ連続(Lipschitz continuous)である.この時,直線探索を用いた最急降下法で生成される点列{xk}\lbrace \mathbf{x}_k \rbraceは次式を満足する.

limkf(xk)=0\begin{aligned} \lim_{k \rightarrow \infty} \parallel \nabla f(\mathbf{x}_k) \parallel = 0 \end{aligned}

この定理は,解から離れた初期点を選んでも勾配ベクトルの点列{f(xk)}\lbrace \nabla f(\mathbf{x}_k) \rbraceが零に収束することを保証している.最急降下法は大域的収束するという利点を持つ反面,収束の歩みがかなり遅いことが知られており,1次収束する程度にすぎない.

最急降下法の収束率

行列ARn×nA \in \mathbb{R}^{n \times n}が正定値対称でbRn\mathbf{b} \in \mathbb{R}^nが定数ベクトルである時,2次関数最小化問題

f(x)=12xTAx+bTx\begin{aligned} f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A\mathbf{x} + \mathbf{b}^T \mathbf{x} \end{aligned}

を考える.この時,正確な直線探索を用いた最急降下法で生成された点列{xk}\lbrace \mathbf{x}_k \rbrace

xk+1xλ1λnλ1+λnxkxA\begin{aligned} \parallel \mathbf{x}_{k+1} - \mathbf{x}^* \parallel \leq \left\lvert \frac{\lambda_1 - \lambda_n}{\lambda_1 + \lambda_n} \right\rvert \parallel \mathbf{x}_k - \mathbf{x}^* \parallel_A \end{aligned}

を満たす.ただし,0<λ1λn0 < \lambda_1 \leq \lambda_nはそれぞれ行列AAの最小固有値と最大固有値であり,x\mathbf{x}^*は最小解である.また,ノルムはvA=vTAv\parallel \mathbf{v} \parallel_A = \sqrt{\mathbf{v}^T A\mathbf{v}}で定義される.

この定理により,最小固有値に比べて最大固有値が非常に大きい場合(すなわち行列Aの条件数が非常に大きい場合)には係数が1に近い値になるので,収束が遅いことがわかる.

共役勾配法

勾配ベクトルのみを用いる方法である.

ニュートン法

What’s Newton’s method is trying to do is It’s trying to find x-intercepts of functions.Suppose I take some random point and I plug that in and well it’s not the x-intercept, but what you do is you find an equation of a tangent line and then you use the equation of the tangent line to find a new point we’ll call that x2x_2. Then we repeat this process we find the point on the graph we find a new tangent line and notice by finding the new tangent line. This new point that I get x3x_3 that’s even closer to the actual x-intercept. So this process these iterations is what they’re called hopefully by repeating this process over and over again. You’re going to closer and closer to the true x-intercept.

ニュートン法は2次モデルの最小化に基づいた解法である.q(d)q(\mathbf{d})を最小化するためにはq(d)=0\nabla q(\mathbf{d}) = \mathbf{0}を満たすベクトルd\mathbf{d}を求める.従って,関数q(d)q(\mathbf{d})をベクトルd\mathbf{d}で微分すれば,

q(d)=f(xk)+2f(xk)d\begin{aligned} \nabla q(\mathbf{d}) = \nabla f(\mathbf{x}_k) + \nabla^2 f(\mathbf{x}_k)\mathbf{d} \end{aligned}

となるので,探索方向を求めるためには連立1次方程式

2f(xk)d=f(xk)\begin{aligned} \nabla^2 f(\mathbf{x}_k) \mathbf{d} = -\nabla f(\mathbf{x}_k) \end{aligned}

を解けば良い.この方程式をニュートン方程式(Newton equation),その解dk\mathbf{d}_kをニュートン方向(Newton direction)という.

もし2f(xk)\nabla^2 f(\mathbf{x}_k)が正定値ならば,方向微係数は

f(xk)Tdk=f(xk)T2f(xk)1f(xk)<0\begin{aligned} \nabla f(\mathbf{x}_k)^T \mathbf{d}_k = -\nabla f(\mathbf{x}_k)^T \nabla^2 f(\mathbf{x}_k)^{-1} \nabla f(\mathbf{x}_k) < 0 \end{aligned}

となるので,ニュートン方向は目的関数の降下方向になる.幾何学的に解釈すれば,点xk\mathbf{x}_kにおいて目的関数の等高線の接線と曲率を共有するような楕円(体)を描いて,xk\mathbf{x}_kから楕円の中心へ向かうベクトルdk\mathbf{d}_kを求めれば,それがニュートン方向になる.

アルゴリズム4.6(ニュートン法)

  • step0 初期点x0\mathbf{x}_0を与える. k=0k = 0とおく
  • step1 停止条件が満たされていれば,xk\mathbf{x}_kを解とみなして停止する.さもなければ,step2へいく
  • step2 ニュートン方程式を解いて,探索方向dk\mathbf{d}_kを求める
  • step3 xk+1=xk+dk\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{d}_kとおく
  • step4 k:=k+1k := k + 1とおいてstep1へいく

ステップ幅αk=1\alpha_k = 1に取る.xk+1=xk+dk\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{d}_k(dk\mathbf{d}_k:ニュートン方向)

ニュートン法の局所的2次収束性

目的関数f(x)f(\mathbf{x})は最小解x\mathbf{x}^*の開凸近傍DDで2回連続的微分可能とし,2f(x)\nabla^2 f(\mathbf{x}^*)は正定値であるとする.また,ヘッセ行列2f(x)\nabla^2 f(\mathbf{x})DDにおいてリプシッツ連続であるとする.すなわち,任意のベクトルx,yD\mathbf{x}, \mathbf{y} \in Dに対して2f(x)2f(y)γxy\parallel \nabla^2 f(\mathbf{x}) - \nabla^2 f(\mathbf{y}) \parallel \leq \gamma \parallel \mathbf{x} - \mathbf{y} \parallelが成り立つとする.(γ\gammaは正の定数)この時,初期点x0\mathbf{x}_0x\mathbf{x}^*の十分近くに選べば,アルゴリズム4.6で生成される点列{xk}\lbrace \mathbf{x}_k \rbraceは解x\mathbf{x}^*に収束し,かつ

xk+1xνxkx2\begin{aligned} \parallel \mathbf{x}_{k+1} - \mathbf{x}^* \parallel \leq \nu \parallel \mathbf{x}_k - \mathbf{x}^* \parallel^2 \end{aligned}

が成り立つ.ただし,ν\nuは非負定数である.

x0\mathbf{x}_0の選び方が悪い時{xk}\lbrace \mathbf{x}_k \rbraceが収束する保証なし,収束しても極大の場合もある.

例題(4.7.1)

関数f:RnRmf:\mathbb{R}^n \rightarrow \mathbb{R}^mがリプシッツ連続であるならば,ffは連続関数であることを示せ.

証明:
ffがリプシッツ連続の時,任意のϵ>0\epsilon > 0に対してδ=ϵL\delta = \frac{\epsilon}{L}とおくと,

x1x2<δf(x1)f(x2)Lx1x2<Lδ=LϵL=ϵ\begin{aligned} \lvert \mathbf{x_1} - \mathbf{x_2} \rvert < \delta \Rightarrow \lvert f(\mathbf{x}_1) - f(\mathbf{x}_2) \rvert \leq L \lvert \mathbf{x_1} - \mathbf{x_2} \rvert < L \cdot \delta = L \cdot \frac{\epsilon}{L} = \epsilon \end{aligned}

となる.従って,ffは連続関数である.

例題(4.7.2)

行列A=(3111)A = \begin{pmatrix} 3 & -1 \\\\ -1 & 1 \end{pmatrix}とベクトルb=(42)\mathbf{b} = \binom{-4}{2}によって定義される2次関数f(x)f(\mathbf{x})を考える:

f(x)=12xTAx+bTx\begin{aligned} f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A\mathbf{x} + \mathbf{b}^T \mathbf{x} \end{aligned}

(1)行列AAの固有値を求め,正定値であることを確認せよ.

det(λIA)=0λ24λ+2=0\begin{aligned} det(\lambda I - A) &= 0 \\ \rightarrow \lambda^2 - 4\lambda + 2 &= 0 \end{aligned}

λ=4±222>0\lambda = \frac{4 \pm 2\sqrt{2}}{2} > 0よって,固有値が全て正だから,Aの固有値は2±22 \pm \sqrt{2}であり,正定値である.

(2)関数f(x)f(\mathbf{x})に対して正確な直線探索を用いた最急降下法を適用する.初期点x0=(23)\mathbf{x}_0 = \binom{2}{3}の時,x1x_1を求めよ.

f(x,y)=32x2+12y2xy4x+2yf(x,y) = \frac{3}{2} x^2 + \frac{1}{2} y^2 - xy - 4x + 2y
それぞれx,yx,yで偏微分すると

fx(x,y)=3xy4fy(x,y)=x+y+2\begin{aligned} f_x(x,y) &= 3x - y - 4 \\ f_y(x,y) &= -x + y + 2 \end{aligned}

よって,((x0y0)\binom{x_0}{y_0}) = (23)\binom{2}{3}における最急降下方向は,(13)\binom{-1}{3}の反対の向き,つまり,dk=(13)\mathbf{d}_k = \binom{1}{-3}である.

ステップ幅をαk\alpha_kとおくと,

x1=x0+αk(13)\begin{aligned} \mathbf{x}_1 = \mathbf{x}_0 + \alpha_k \binom{1}{-3} \end{aligned}

f(x1)=9α210α2\begin{aligned} f(\mathbf{x_1}) = 9\alpha^2 - 10\alpha - 2 \end{aligned}

f(x1)f(\mathbf{x}_1)を最小にするようなα\alphaを計算すると,α=59\alpha = \frac{5}{9}となる.

よって, x1=(23943)\mathbf{x}_1 = \binom{\frac{23}{9}}{\frac{4}{3}}である.

例題(4.7.3)

正定値対称行列ARn×nA \in \mathbb{R}^{n \times n}とベクトルbRn\mathbf{b} \in \mathbb{R}^nによって定義される凸2次関数f(x)f(\mathbf{x}):

f(x)=12xTAx+bTx\begin{aligned} f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A\mathbf{x} + \mathbf{b}^T \mathbf{x} \end{aligned}

に対して,正確な直線探索を用いた最急降下法を適用した時,点xk+1\mathbf{x}_{k+1}A,bA,bおよびxk\mathbf{x}_kで表現せよ.

最適解x\mathbf{x}^*ffx\mathbf{x}に関する停留条件

Axb=0\begin{aligned} A\mathbf{x}^* - \mathbf{b} = 0 \end{aligned}

より,x=A1b\mathbf{x}^* = A^{-1} \mathbf{b}である.
最急降下法に基づき,解を

xk+1=xαkf(xk)\begin{aligned} \mathbf{x}_{k+1} = \mathbf{x} - \alpha_k \nabla f(\mathbf{x}_k) \end{aligned}

に従って更新する.f(xk)=Axkb\nabla f(\mathbf{x}_k) = A\mathbf{x}_k - \mathbf{b}である.また,ステップ幅αk\alpha_kは正確な直線探索に従って求める場合は

f(xkαf(xk))12(xkαf(xk))TA(xkαf(xk))bT(xkαf(xk))\begin{aligned} f(\mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)) - \frac{1}{2} (\mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k))^T A (\mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)) - \mathbf{b}^T (\mathbf{x}_k - \alpha \nabla f(\mathbf{x}_k)) \end{aligned}

の最小解をαk\alpha_kとおく.停留条件より

αk=f(xk)Tf(xk)f(xk)TAf(xk)\begin{aligned} \alpha_k = \frac{\nabla f(\mathbf{x}_k)^T \nabla f(\mathbf{x}_k)}{\nabla f(\mathbf{x}_k)^T A \nabla f(\mathbf{x}_k)} \end{aligned}

が得られる.従って,最急降下法を適用した場合,xk+1\mathbf{x}_{k+1}は以下の式で表せる.

xk+1=xk(Axkb)T(Axkb)(Axkb)TA(Axkb)(Axkb)\begin{aligned} \mathbf{x}_{k+1} = \mathbf{x}_k - \frac{(A\mathbf{x}_k - \mathbf{b})^T (A\mathbf{x}_k - \mathbf{b})}{(A\mathbf{x}_k - \mathbf{b})^T A (A\mathbf{x}_k - \mathbf{b})} (A\mathbf{x}_k - \mathbf{b}) \end{aligned}

準ニュートン法(quasi-Newton method)

ヘッセ行列を近似する準ニュートン法

ニュートン方程式

2f(xk)d=f(xk)\begin{aligned} \nabla^2 f(\mathbf{x}_k) \mathbf{d} = -\nabla f(\mathbf{x}_k) \end{aligned}

いつもヘッセ行列2f(xk)\nabla^2 f(\mathbf{x}_k)は正定値である保証できないので,ニュートン方向がf(xk)f(\mathbf{x}_k)の降下方向になるとは限らない.

そこで,ヘッセ行列を適当な正定値対称行列BkB_kで近似した新しい2次モデル

Q(d)=f(xk)+f(xk)Td+12dTBkd\begin{aligned} Q(\mathbf{d}) = f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T \mathbf{d} + \frac{1}{2} \mathbf{d}^T B_k \mathbf{d} \end{aligned}

を考えて,連立1次方程式Bkd=f(xk)B_k \mathbf{d} = -\nabla f(\mathbf{x}_k)の解として探索方向dk\mathbf{d}_kを求めるのが準ニュートン法である.

Bk:正定値dkは降下方向Bk:正定値Bk1が正定値\begin{aligned} &B_k: \text{正定値} \Rightarrow \mathbf{d}_k\text{は降下方向} \\ &B_k: \text{正定値} \Leftrightarrow B_k^{-1}\text{が正定値} \end{aligned}

dk=Bk1f(xk)\mathbf{d}_k = -B_k^{-1} \nabla f(\mathbf{x}_k)より

f(xk)Tdk=f(xk)TBk1f(xk)<0\begin{aligned} \nabla f(\mathbf{x}_k)^T \mathbf{d}_k = -\nabla f(\mathbf{x}_k)^T B_k^{-1} \nabla f(\mathbf{x}_k) < 0 \end{aligned}

となるので,探索方向dk\mathbf{d}_kは目的関数の降下方向になる.

この方向はBkB_k2f(xk)\nabla^2 f(\mathbf{x}_k)に近似できていたら,ニュートン方向とほとんど同じになるため,高速な収束が期待できる.今,f(x)\nabla f(\mathbf{x})のテイラー展開を考えると,

f(xk)f(xk+1)2f(xk)(xkxk+1)\begin{aligned} \nabla f(\mathbf{x}_k) - \nabla f(\mathbf{x}_{k+1}) \simeq \nabla^2 f(\mathbf{x}_k)(\mathbf{x}_k - \mathbf{x}_{k+1}) \end{aligned}

となるので,BkB_kもこの条件を満たすようにすることを考える.つまり

sk=xk+1xyk=f(xk+1)f(x)\begin{aligned} \mathbf{s}_k &= \mathbf{x}_{k+1} - \mathbf{x} \\ \mathbf{y}_k &= \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}) \end{aligned}

とした時,

yk=Bk+1sk\begin{aligned} \mathbf{y}_k = B_{k+1} \mathbf{s}_k \end{aligned}

となるようにする.この条件をセカント条件と呼ぶ.セカント条件を満足するようにBkB_kを更新してBk+1B_{k+1}が作られる.

アルゴリズム4.7(準ニュートン法)

  • step0 初期設定をする(初期点x0\mathbf{x}_0や正定値対称な初期行列B0B_0を与える.k=0k = 0とおく).
  • step1 停止条件が満たされていれば,xk\mathbf{x}_kを解とみなして停止する.さもなければ,step2へいく.
  • step2 連立1次方程式Bkd=f(xk)B_k \mathbf{d} = -\nabla f(\mathbf{x}_k)を解いて探索方向dk\mathbf{d}_kを求める.
  • step3 dk\mathbf{d}_k方向でのステップ幅αk\alpha_kを求める.
  • step4 xk+1=xk+αkdk\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_kとおく.
  • step5 BkB_kを更新してBk+1B_{k+1}を生成する.k:=k+1k := k + 1とおいてstep1へいく.

セカント条件を満足するBk+1B_{k+1}は無数に存在するので,いろいろな種類の更新公式が考えられる.

DFP(DavidonFletcherPowell)DFP(Davidon-Fletcher-Powell)公式

y=yk,s=sk,B=Bk\mathbf{y} = \mathbf{y}_k, \mathbf{s} = \mathbf{s}_k, B = B_kとする.

Bk+1=BBsyT+yT(Bs)TsTy+(1+sTBssTy)yyTsTy\begin{aligned} \color{red}{B_{k+1} = B - \frac{B\mathbf{s}\mathbf{y}^T + \mathbf{y}^T (B\mathbf{s})^T}{\mathbf{s}^T \mathbf{y}} + (1 + \frac{\mathbf{s}^T B\mathbf{s}}{\mathbf{s}^T \mathbf{y}}) \frac{\mathbf{y}\mathbf{y}^T}{\mathbf{s}^T \mathbf{y}}} \end{aligned}

BFGS(BroydenFletcherGoldfarbShanno)BFGS(Broyden-Fletcher-Goldfarb-Shanno)公式

Bk+1=B(Bs)(Bs)TsTBs+yyTsTy\begin{aligned} \color{red}{B_{k+1} = B - \frac{(B\mathbf{s})(B\mathbf{s})^T}{\mathbf{s}^T B\mathbf{s}} + \frac{\mathbf{y}\mathbf{y}^T}{\mathbf{s}^T \mathbf{y}}} \end{aligned}

アルゴリズム4.8(準ニュートン法(BFGSBFGS公式))

  • step0 初期点x0\mathbf{x}_0, 初期行列B0B_0(通常は単位行列が選ばれる)を与える.k=0k = 0とおく
  • step1 連立1次方程式Bkd=f(xk)B_k \mathbf{d} = -\nabla f(\mathbf{x}_k)を解いて,探査方向dk\mathbf{d}_kを求める
  • step2 Armijo(またはWolfe)条件を用いた直線探索によって,dk\mathbf{d}_k方向のステップ幅αk\alpha_kを求める
  • step3 xk+1=xk+αkdk\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_kとおく
  • step4 停止条件が満たされていれば,xk+1\mathbf{x}_{k+1}を解とみなして停止する.さもなければstep5へいく
  • step5 sk\mathbf{s}_kyk\mathbf{y}_ksk=xk+1xk,y=f(xk+1)f(xk)\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k, \mathbf{y} = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)で計算する.
  • step6 BFGSBFGS公式を用いて行列を更新する.
  • step7 k:=k+1k := k + 1とおいてstep1へいく.

BFGSBFGS公式を用いた準ニュートン法の性質

BFGSBFGS公式を用いた準ニュートン法で生成した点列{xk}\lbrace \mathbf{x}_k \rbraceと行列の列{Bk}\lbrace B_k \rbraceについて次の性質が成り立つ.ここでx\mathbf{x}^*f(x)=0\nabla f(\mathbf{x}^*) = \mathbf{0}を満たす点とする.

  • 行列{Bk}\lbrace B_k \rbraceはセカント条件を満足する
  • BkB_kが対称ならば,Bk+1B_{k+1}も対称になる
  • BkB_kが正定値対称で,かつsk\mathbf{s}_kyk\mathbf{y}_kskTyk>0\mathbf{s}_k^T \mathbf{y}_k > 0を満たす時,Bk+1B_{k+1}は正定値対称になる
  • DDx\mathbf{x}^*を含む開集合とし,点x\mathbf{x}^*におけるヘッセ行列2f(x)\nabla^2 f(\mathbf{x}^*)が正定値で,かつ,2f(x)\nabla^2 f(\mathbf{x})DDでリプシッツ連続であるとする.この時,xk+1=xkBk1f(xk)\mathbf{x}_{k+1} = \mathbf{x}_k - B_k^{-1} \nabla f(\mathbf{x}_k)で生成される点列{xk}\lbrace \mathbf{x}_k \rbracex\mathbf{x}^*に局所的に超1次収束する(B0B_02f(x)\nabla^2 f(\mathbf{x}^*)に十分近く,2f(x)\nabla^2 f(\mathbf{x}^*)が正則である時に超1次収束する)
  • f(x)f(\mathbf{x})に関する弱い,B0B_0正定値対称で,dkd_kWolfe条件による直線探索とする.この時,lim infkf(xk)=0\liminf_{k \rightarrow \infty} \parallel \nabla f(\mathbf{x}_k) \parallel = 0が成り立つ.さらに,ある集合上で2f(x)\nabla^2 f(\mathbf{x})の固有値の取る範囲が有界.limkxk=x\lim_{k \rightarrow \infty} \mathbf{x}_k = \mathbf{x}^*が成り立つ.
  • 狭義凸2次関数f(x)=12xTAxbTx(x,bRn,ARn×n)は正定値対称f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A\mathbf{x} - \mathbf{b}^T \mathbf{x} \quad (\mathbf{x}, \mathbf{b} \in \mathbb{R}^n, A \in \mathbb{R}^{n \times n})\text{は正定値対称}の最小化問題においてB0=IB_0 = Iと選び正確な直線探索を行えば,生成される探索方向は行列AAに関してお互いに共役になる.そして,高々nn回の反復で最適解x=A1b\mathbf{x}^* = A^{-1}\mathbf{b}が得られ,Bn=AB_{n} = Aとなる(共役勾配法と同じ点列を生成する).

ヘッセ行列の逆行列を近似する準ニュートン法

ヘッセ行列2f(xk)1\nabla^2 f(\mathbf{x}_k)^{-1}を行列HkH_kで近似すると考える.この時Hk=Bk1H_k = B_k^{-1}の関係があるので,探索方向は

dk=Hkf(xk)\begin{aligned} \mathbf{d}_k = -H_k \nabla f(\mathbf{x}_k) \end{aligned}

として求まる.セカント条件はsk=Hk+1yk\mathbf{s}_k = H_{k+1}\mathbf{y}_kである.

HH公式のBFGSBFGS公式

Hk+1=HkHkykskT+sk(Hkyk)TskTyk+(1+ykTHkykskTyk)skskTskTyk\begin{aligned} H_{k+1} = H_k - \frac{H_k \mathbf{y}_k \mathbf{s}_k^T + \mathbf{s}_k (H_k \mathbf{y}_k)^T}{\mathbf{s}_k^T \mathbf{y}_k} + (1 + \frac{\mathbf{y}_k^T H_k \mathbf{y}_k}{\mathbf{s}_k^T \mathbf{y}_k}) \frac{\mathbf{s}_k \mathbf{s}_k^T}{\mathbf{s}_k^T \mathbf{y}_k} \end{aligned}

アルゴリズム4.9(準ニュートン法(HH公式のBFGSBFGS公式))

  • step0 初期点x0\mathbf{x}_0, 初期行列H0H_0(通常は単位行列が選ばれる)を与える.k=0k = 0とおく
  • step1 探査方向dk=Hkf(xk)\mathbf{d}_k = -H_k \nabla f(\mathbf{x}_k)を求める
  • step2 Armijo(またはWolfe)条件を用いた直線探索によって,dk\mathbf{d}_k方向のステップ幅αk\alpha_kを求める
  • step3 xk+1=xk+αkdk\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_kとおく
  • step4 停止条件が満たされていれば,xk+1\mathbf{x}_{k+1}を解とみなして停止する.さもなければstep5へいく
  • step5 sk\mathbf{s}_kyk\mathbf{y}_ksk=xk+1xk,y=f(xk+1)f(xk)\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k, \mathbf{y} = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)で計算する.
  • step6 HH公式のBFGSBFGS公式を用いて行列を更新する.
  • step7 k:=k+1k := k + 1とおいてstep1へいく.

BB公式のDFPDFP公式で,Bk,sk,ykB_k,\mathbf{s}_k,\mathbf{y}_kHk,yk,skH_k,\mathbf{y}_k,\mathbf{s}_kで置き換えばHH公式のBFGSBFGS公式が得られ,また,BB公式のBFGSBFGS公式で同じ置き換えばをすればHH公式のDFPDFP公式が得られる(Bk+1Hk+1=IB_{k+1}H_{k+1} = I)

対称ランクワン公式

Hk+1:=Hk+(skHkyk)(skHkyk)TykT(skHkyk)\begin{aligned} \color{red}{H_{k+1} := H_k + \frac{(\mathbf{s}_k - H_k \mathbf{y}_k)(\mathbf{s}_k - H_k \mathbf{y}_k)^T}{\mathbf{y}_k^T (\mathbf{s}_k - H_k \mathbf{y}_k)}} \end{aligned}

例題(4.8.1)

行列A=(3111)A = \begin{pmatrix} 3 & 1 \\\\ 1 & 1 \end{pmatrix}とベクトルb=(31)\mathbf{b} = \binom{-3}{1}によって定義される2次関数f(x)f(\mathbf{x})を考える:

f(x)=12xTAx+bTx\begin{aligned} f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T A \mathbf{x} + \mathbf{b}^T \mathbf{x} \end{aligned}

この問題に対して,以下のような準ニュートン法を実行して得られる点列を求めよ(2回の反復で終了する).x0=(12)\mathbf{x}_0 = \binom{1}{-2}とする,B0=IB_0 = Iとし,行列BkB_kの更新はBFGSBFGS公式を用いる

f(x)=32x12+x1x2+12x223x1+x2\begin{aligned} f(x) &= \frac{3}{2} x_1^2 + x_1x_2 + \frac{1}{2} x_2^2 - 3x_1 + x_2 \end{aligned}

f(x)=(3x1+x23x1+x2+1)\begin{aligned} \nabla f(\mathbf{x}) &= \binom{3x_1 + x_2 - 3}{x_1 + x_2 + 1} \end{aligned}

(1) k=0k = 0の時

ここで,x0\mathbf{x}_0を代入すると

f(x0)=(20)\nabla f(\mathbf{x}_0) = \binom{-2}{0}

となる.

d0=B01f(x0)=(20)\mathbf{d}_0 = -B_0^{-1} \nabla f(\mathbf{x}_0) = \binom{2}{0},各反復においてステップ幅αk\alpha_kを正確な直線探索で選ぶから,ステップ幅αk\alpha_k

αk=dkTf(xk)dkTAdk\begin{aligned} \alpha_k = -\frac{d_k^T \nabla f(\mathbf{x}_k)}{\mathbf{d}_k^T A \mathbf{d}_k} \end{aligned}

であるから,α0=13\alpha_0 = \frac{1}{3}となる.

x1=x0+α0d0=(532)\mathbf{x}_1 = \mathbf{x}_0 + \alpha_0 \mathbf{d}_0 = \binom{\frac{5}{3}}{-2}, f(x1)=(023)\nabla f(\mathbf{x}_1) = \binom{0}{\frac{2}{3}}となる.

s0=x1x0=(230)y0=f(x1)f(x)=(223)\begin{aligned} \mathbf{s}_0 &= \mathbf{x}_1 - \mathbf{x}_0 = \binom{\frac{2}{3}}{0} \\ \mathbf{y}_0 &= \nabla f(\mathbf{x}_1) - \nabla f(\mathbf{x}) = \binom{2}{\frac{2}{3}} \end{aligned}

B0s0=(230),s0Ty0=43,s0TB0s0=49B_0 \mathbf{s}_0 = \binom{\frac{2}{3}}{0}, \quad \mathbf{s}_0^T \mathbf{y}_0 = \frac{4}{3}, \quad \mathbf{s}_0^T B_0 \mathbf{s}_0 = \frac{4}{9}

BFGSBFGS公式により,

B1=(31143)\begin{aligned} B_1 = \begin{pmatrix} 3 & 1 \\ 1 & \frac{4}{3} \end{pmatrix} \end{aligned}

となる.

(2) k=1k = 1の時

f(x1)=(023),d1=(2932),α=(32)\nabla f(\mathbf{x}_1) = \binom{0}{\frac{2}{3}}, \quad \mathbf{d}_1 = \binom{\frac{2}{9}}{\frac{3}{2}}, \alpha = \binom{3}{2}となるので,次の点を得る

x2=x1+α1d1=(23)\mathbf{x}_2 = \mathbf{x}_1 + \alpha_1 \mathbf{d}_1 = \binom{2}{-3}

この時,f(x2)=(00)\nabla f(\mathbf{x}_2) = \binom{0}{0}となるので,2回の反復で最適解に到達したことになる.

例題(4.8.2)

例題(4.8.1)において,HH公式のBFGSBFGS公式を用いる準ニュートン法を適用した時,行列H1H_1を求め,さらに探索方向d1=H1f(x1)\mathbf{d}_1 = -H_1 \nabla f(\mathbf{x}_1)を求めよ.(5.1と同様にx0=(12),H0=I\mathbf{x}_0 = \binom{1}{-2}, H_0 = Iとする)

(1) k=0k = 0の時

f(x0)=(20)\nabla f(\mathbf{x}_0) = \binom{-2}{0}なので,d0=H0f(x0)=(20)\mathbf{d}_0 = -H_0 \nabla f(\mathbf{x}_0) = \binom{2}{0}となる.

ここで,d0Tf(x0)=4,d0TAd0=12\mathbf{d}_0^T \nabla f(\mathbf{x}_0) = -4, \quad \mathbf{d}_0^T A \mathbf{d}_0 = 12なので,ステップ幅はα0=13\alpha_0 = \frac{1}{3}となり,次の点を得る.

x1=x0+α0d0=(532)\mathbf{x}_1 = \mathbf{x}_0 + \alpha_0 \mathbf{d}_0 = \binom{\frac{5}{3}}{-2}

この時,f(x1)=(023)\nabla f(\mathbf{x}_1) = \binom{0}{\frac{2}{3}}である.

次にベクトル

s0=x1x0=(230),y0=f(x1)f(x0)=(223)\mathbf{s}_0 = \mathbf{x}_1 - \mathbf{x}_0 = \binom{\frac{2}{3}}{0}, \quad \mathbf{y}_0 = \nabla f(\mathbf{x}_1) - \nabla f(\mathbf{x}_0) = \binom{2}{\frac{2}{3}}

を計算すれば,s0y0=43,y0TH0y0=409\mathbf{s}_0 \mathbf{y}_0 = \frac{4}{3}, \quad \mathbf{y}_0^T H_0 \mathbf{y}_0 = \frac{40}{9}となる.よって,

H0y0s0T+s0y0TH0s0Ty0=(213130)\begin{aligned} \frac{H_0 \mathbf{y}_0 \mathbf{s}_0^T + \mathbf{s}_0 \mathbf{y}_0^T H_0}{\mathbf{s}_0^T \mathbf{y}_0} = \begin{pmatrix} 2 & \frac{1}{3} \\ \frac{1}{3} & 0 \end{pmatrix} \end{aligned}

(1+y0H0y0s0y0)s0s0Ts0Ty0=(139000)\begin{aligned} (1 + \frac{\mathbf{y}_0 H_0 \mathbf{y}_0}{\mathbf{s}_0 \mathbf{y}_0}) \frac{\mathbf{s}_0 \mathbf{s}_0^T}{\mathbf{s}_0^T \mathbf{y}_0} = \begin{pmatrix} \frac{13}{9} & 0 \\ 0 & 0 \end{pmatrix} \end{aligned}

なので,BFGSBFGS公式を用いて近似行列を更新すれば,

H1=(4913131)\begin{aligned} H_1 = \begin{pmatrix} \frac{4}{9} & -\frac{1}{3} \\ -\frac{1}{3} & 1 \end{pmatrix} \end{aligned}

(2) k=1k = 1の時

d1=H1f(x1)=(2923)\begin{aligned} \mathbf{d}_1 = -H_1 \nabla f(\mathbf{x}_1) = \binom{\frac{2}{9}}{-\frac{2}{3}} \end{aligned}

例題(4.8.3)

正規行列MRn×nM \in \mathbb{R}^{n \times n}uTv1,vTM1u1\mathbf{u}^T\mathbf{v} \neq -1, \mathbf{v}^T M^{-1} \mathbf{u} \neq -1を満たすベクトルu,vRn\mathbf{u}, \mathbf{v} \in \mathbb{R}^nに関するSherman-Morrisonの公式:

(M+uvT)1=M1M1uvTM11+vTM1u\begin{aligned} (M + \mathbf{u} \mathbf{v}^T)^{-1} = M^{-1} - \frac{M^{-1} \mathbf{u}\mathbf{v}^T M^{-1}}{1 + \mathbf{v}^T M^{-1} \mathbf{u}} \end{aligned}

が成り立つことを,M=(2123)M = \begin{pmatrix} 2 & 1 \\\\ 2 & 3 \end{pmatrix},u=(10)\mathbf{u} = \binom{1}{0},v=(21)\mathbf{v} = \binom{2}{1}に対して確認せよ.

数値を代入すると,左辺は

(M+uvT)1=((2123)+(10)(21))1=18(3224)\begin{aligned} (M + \mathbf{u} \mathbf{v}^T)^{-1} = (\begin{pmatrix} 2 & 1 \\ 2 & 3 \end{pmatrix} + \binom{1}{0}(2\quad1))^{-1} = \frac{1}{8} \begin{pmatrix} 3 & -2 \\ -2 & 4 \end{pmatrix} \end{aligned}

となる.右辺は

M1M1uvTM11+vTM1u=18(3224)\begin{aligned} M^{-1} - \frac{M^{-1} \mathbf{u}\mathbf{v}^T M^{-1}}{1 + \mathbf{v}^T M^{-1} \mathbf{u}} = \frac{1}{8} \begin{pmatrix} 3 & -2 \\ -2 & 4 \end{pmatrix} \end{aligned}

となるから,Sherman-Morrisonの公式が確認された.

まとめ

手法 収束性 メモリ
ニュートン法 ×\times
準ニュートン法 \triangle
共役勾配法 \triangle
最急降下法 ×\times

第5章 非線形計画法II(制約付き最小化問題)

本章では等式制約あるいは不等式制約のついた最小化問題を考える.

  • まずはじめに,最適解であるための条件として,Fritz-Johnの定理とKuhn-Tuckerの定理を紹介する
  • 続いて,非線形計画法の双対定理について学習する
  • さらに,線形計画問題の拡張として,2次計画問題,線形相補性問題,2次錐計画問題,半正定値計画問題についても触れる
  • 最後に,非線形計画問題の代表的な数値解法としてペナルティ関数法,乗数法,逐次2次計画法,主双対内点法を紹介する

最適性条件

本章では,制約付きのついた非線形最小化問題を扱う.

f:RnR,gi:RnR(i=1,,m(m<n)),hj:RnR(j=1,,l)f:\mathbb{R}^n \rightarrow \mathbb{R}, g_i:\mathbb{R}^n \rightarrow \mathbb{R}(i = 1,\cdots,m(m < n)), h_j:\mathbb{R}^n \rightarrow \mathbb{R}(j = 1,\cdots,l)に対して,次の最小化問題を解け

{最小化f(x)制約条件gi(x)=0(i=1,,m):等式制約hj(x)0(j=1,,l):不等式制約\begin{aligned} \begin{cases} \text{最小化} \qquad &f(\mathbf{x}) \\ \text{制約条件} \qquad &g_i(\mathbf{x}) = 0 (i = 1,\cdots,m):\text{等式制約} \\ &h_j(\mathbf{x}) \leq 0 (j = 1,\cdots,l):\text{不等式制約} \end{cases} \end{aligned}

定義5.1(実行可能解と最小解)

  • 制約付き問題において,制約条件を満たす点を実行可能解(feasible solution)または許容解といい,そうした点の集合

F={xRn  gi(x)=0(i=1,,m),hj(x)0(j=1,,l)}\mathcal{F} = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ g_i(\mathbf{x}) = 0 (i = 1,\cdots,m), h_j(\mathbf{x}) \leq 0 (j = 1,\cdots,l) \rbrace

を実行可能領域(feasible region)または許容領域という.

  • 実行可能解xFx^* \in \mathcal{F}が大域的最小解(global minimizer)であるとは,任意の点xF\mathbf{x} \in \mathcal{F}に対して,f(x)f(x)f(\mathbf{x}^*) \leq f(\mathbf{x})が成り立つことである.
  • 実行可能解xFx^* \in \mathcal{F}が局所的最小解(local minimizer)であるとは,xx^*の近傍N(x,ϵ)={xRn  xx<ϵ}\mathcal{N}(\mathbf{x},\epsilon) = \lbrace \mathbf{x} \in \mathbb{R}^n \ |\ \parallel \mathbf{x} - \mathbf{x}^* \parallel < \epsilon \rbraceが存在して,任意の点xFN(x,ϵ)\mathbf{x} \in \mathcal{F} \cap \mathcal{N}(\mathbf{x}^*,\epsilon)に対して,f(x)f(x)f(\mathbf{x}^*) \leq f(\mathbf{x})が成り立つことである.

以下では,

g(x)=[g1(x),,gm(x)]TRmh(x)=[h1(x),,hl(x)]TRlg(x)=[g1(x),,gm(x)]TRn×mh(x)=[h1(x),,hl(x)]TRn×l\begin{aligned} \mathbf{g}(\mathbf{x}) &= [g_1(\mathbf{x}), \cdots, g_m(\mathbf{x})]^T \in \mathbb{R}^m \\ \mathbf{h}(\mathbf{x}) &= [h_1(\mathbf{x}), \cdots, h_l(\mathbf{x})]^T \in \mathbb{R}^l \\ \nabla \mathbf{g}(\mathbf{x}) &= [\nabla g_1(\mathbf{x}), \cdots, \nabla g_m(\mathbf{x})]^T \in \mathbb{R}^{n \times m} \\ \nabla \mathbf{h}(\mathbf{x}) &= [\nabla h_1(\mathbf{x}), \cdots, \nabla h_l(\mathbf{x})]^T \in \mathbb{R}^{n \times l} \end{aligned}

と定義する.

等式制約付き最小化問題の最適性条件

まず等式制約がついた問題を考える

最小化f(x)制約条件gi(x)=0(i=1,,m)\begin{aligned} \text{最小化} \qquad & f(\mathbf{x}) \\ \text{制約条件} \qquad & g_i(\mathbf{x}) = 0 (i = 1, \cdots, m) \end{aligned}

この問題について,次の関数を定義する

L(x,y)=f(x)+yTg(x)(=f(x)+i=1myigi(x))L(\mathbf{x, y}) = f(\mathbf{x}) + \mathbf{y}^T \mathbf{g}(\mathbf{x}) (= f(\mathbf{x}) + \sum_{i=1}^m y_ig_i(\mathbf{x}))

これをラグランジュ関数(Lagrangian function)と呼ぶ.ただし,

y=(y1,,ym)T\mathbf{y} = (y_1,\cdots,y_m)^T

とし,y1y_1を等式制約gi(x)=0g_i(\mathbf{x}) = 0に対するラグランジュ乗数(Lagrangian multiplier),y\mathbf{y}をラグランジュ乗数ベクトルと呼ぶ.

ラグランジュ関数の停留点,すなわち,ラグランジュ関数の勾配ベクトルを零にする点は等式制約付き問題の最適解と密接な関係がある.

定理5.1(等式制約付き問題の最適性条件:1次の必要条件)

f,gi(i=1,,m)f,g_i(i = 1,\cdots,m)が微分可能で,かつ,xx^*が等式制約付き問題の局所的最小解とする.

この時,g1(x),,gm(x)\nabla g_1(x^*), \cdots, \nabla g_m(x^*)が線形独立ならば,m次元ベクトルy=[y1,,ym]T\mathbf{y}^* = [y_1^*, \cdots, y_m^*]^Tが存在して,

xL(x,y)=f(x)+i=1myigi(x)=0yL(x,y)=g(x)=0\begin{aligned} \nabla_\mathbf{x} L(\mathbf{x}^*,\mathbf{y}^*) &= \nabla f(\mathbf{x}^*) + \sum_{i=1}^m y_i^* \nabla g_i(\mathbf{x}^*) = \mathbf{0} \\ \nabla_\mathbf{y} L(\mathbf{x}^*,\mathbf{y}^*) &= \mathbf{g}(\mathbf{x}^*) = \mathbf{0} \end{aligned}

が成り立つ.ただし,xL,yL\nabla_\mathbf{x} L, \nabla_\mathbf{y} Lはそれぞれx,y\mathbf{x,y}に関するLの勾配ベルトルを表す.

簡単な問題なら定理から局所的最適解が計算できる\Rightarrowラグランジュ未定乗数法

例題1

min2x12+3x22s.tx1+x21=0\begin{aligned} min \quad &2x_1^2 + 3x_2^2 \\ s.t \quad &x_1 + x_2 - 1 = 0 \end{aligned}

ラグランジュ関数は

L(x1,x2,y)=2x12+3x22+y(x1+x21)L(x_1,x_2,y) = 2x_1^2 + 3x_2^2 + y(x_1 + x_2 - 1)

となるので

xL(x,y)=(4x1+y6x2+y)=(00)yL(x,y)=x1+x21=0(x1,x2,y)=(35,25,125)\begin{aligned} &\nabla_\mathbf{x} L(\mathbf{x}, \mathbf{y}) = \begin{pmatrix} 4x_1 + y \\ 6x_2 + y \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix} \\ &\nabla_\mathbf{y} L(\mathbf{x},\mathbf{y}) = x_1 + x_2 - 1 = 0 \\ &\Rightarrow (x_1, x_2, y) = (\frac{3}{5}, \frac{2}{5}, -\frac{12}{5}) \end{aligned}

不等式制約付き最小化問題の最適性条件

ここでは次のような不等式制約付き最小化問題を考える

最小化f(x)制約条件hi(x)0(i=1,,l)\begin{aligned} \text{最小化} \qquad & f(\mathbf{x}) \\ \text{制約条件} \qquad & h_i(\mathbf{x}) \leq 0 (i = 1, \cdots, l) \end{aligned}

有効制約式

実行可能解x0\mathbf{x}^0に対して,hi(x0)=0h_i(\mathbf{x}^0) = 0が成り立つ時,この制約式は点x0\mathbf{x}^0で効いている(active)といい,この制約式をx0\mathbf{x}^0での有効制約式(active constraint)という.また,hi(x0)<0h_i(\mathbf{x}^0) < 0の時,この制約式は点x0\mathbf{x}^0で効いていない(inactive)という.

x\mathbf{x}^*に対して有効な不等式制約の添字集合をI(x)={i  hi(x)=0,i=1,,l}I(\mathbf{x}^*) = \lbrace i \ |\ h_i(\mathbf{x}^*) = 0, i = 1,\cdots,l \rbrace

Fritz-Johnの定理

定理5.2: Fritz-Johnの定理

不等式制約付き問題の局所的最小解xx^*においてf,hi(i=1,,l)f, h_i(i = 1, \cdots, l)が微分可能ならば,(z0,z)(0,0)(z_0^*, \mathbf{z}^*) \neq (0, \mathbf{0})となる実数z0z_0^*とl次元ベクトルz=[z1,,zl]T\mathbf{z}^* = [z_1^*, \cdots, z_l^*]^Tが存在して,次式が成り立つ.

z0f(x)+i=1lzihi(x)=0h(x)0,zi0(i=0,1,,l),zihi(x)=0(i=1,,l)\begin{aligned} & z_0^* \nabla f(\mathbf{x}^*) + \sum_{i=1}^l z_i^* \nabla h_i(\mathbf{x}^*) = \mathbf{0} \\ & \mathbf{h}(\mathbf{x}^*) \leq \mathbf{0}, z_i^* \geq 0 (i = 0,1,\cdots,l),\quad z_i^* h_i(\mathbf{x}^*) = 0 (i = 1, \cdots, l) \end{aligned}

  • ラグランジュ乗数:zi(i=0,,l)z_i^*(i=0,\cdots,l)
  • 相補性条件:zihi(x)=0(i=1,,l)z_i^* h_i(\mathbf{x}^*) = 0 (i = 1, \cdots, l)
  • 狭義相補性条件:hi(x)=0,zi=0h_i(\mathbf{x}^*) = 0, z_i^* = 0が両立しない場合

Fritz-Johnの定理において, z0=0z_0^* = 0の場合には目的関数の勾配に関する情報が含まれないことになる.そこでz0>0z_0^* > 0が成り立つような条件を付加したのが,次のKuhn-Tuckerの定理である.Kuhn-Tuckerの定理を述べるために,不等式制約付き最小化問題に対するラグランジュ関数と乗数ベクトルをそれぞれ

L(x,z)=f(x)+zTh(x)(=f(x)+i=1lzihi(x))z=(z1,,zl)T\begin{aligned} L(\mathbf{x},\mathbf{z}) &= f(\mathbf{x}) + \mathbf{z}^T \mathbf{h}(\mathbf{x}) \quad (= f(\mathbf{x}) + \sum_{i=1}^l z_i h_i(\mathbf{x})) \\ \mathbf{z} &= (z_1,\cdots,z_l)^T \end{aligned}

と定義する.

Kuhn-Tuckerの定理

定理5.3: Kuhn-Tuckerの定理:最適性の1次の必要条件

不等式制約付き問題の局所的最小解x\mathbf{x}^*においてf,hi(i=1,,l)f,h_i(i = 1,\cdots,l)が微分可能で,かつ,iI(x)i \in I(\mathbf{x}^*)を満たす全てのiに対してhi(x)\nabla h_i(\mathbf{x}^*)が線形独立ならば(線形独立制約想定),適当なl次元ベクトルz=(z1,,zl)T\mathbf{z}^* = (z_1^*, \cdots, z_l^*)^Tが存在して,(x,z)(\mathbf{x}^*,\mathbf{z}^*)が次の条件を満足する.

xL(x,z)=f(x)+i=1lzihi(x)=0zL(x,z)=h(x)0zi0(i=1,,l)zihi(x)=0(i=1,,l)(相補性)\begin{aligned} \nabla_\mathbf{x} L(\mathbf{x}^*, \mathbf{z}^*) &= \nabla f(\mathbf{x}^*) + \sum_{i=1}^l z_i^* \nabla h_i(\mathbf{x}^*) = \mathbf{0} \\ \nabla_\mathbf{z} L(\mathbf{x}^*, \mathbf{z}^*) &= \mathbf{h}(\mathbf{x}^*) \leq \mathbf{0} \\ z_i^* &\geq 0 \quad (i = 1,\cdots,l) \\ z_i^* h_i(\mathbf{x}^*) &= 0 \quad (i = 1,\cdots,l) (\text{相補性}) \end{aligned}

以上の四つ条件合わせて,Karush-Kuhn-Tucker条件といい,略してKKT条件という.

例題:次の2次計画問題を考える

min12{(x18)2+(x26)2}s.t3x1+x215x1+2x210x1+x23x10,x20\begin{aligned} min \qquad & \frac{1}{2} \lbrace (x_1 - 8)^2 + (x_2 - 6)^2 \rbrace \\ s.t \qquad & 3x_1 + x_2 \leq 15 \\ & x_1 + 2x_2 \leq 10 \\ & x_1 + x_2 \geq 3 \\ & x_1 \geq 0, x_2 \geq 0 \end{aligned}

この問題のラグランジュ関数は

L(x1,x2,z1,z2,z3,z4,z5)=12(x18)2+(x26)2+z1(3x1+x215)+z2(x1+2x210)+z3(3x1x2)z4x1z5x2\begin{aligned} L(x_1,x_2,z_1,z_2,z_3,z_4,z_5) = &\frac{1}{2}{(x_1 - 8)^2 + (x_2 - 6)^2} \\ & + z_1(3x_1 + x_2 -15) + z_2(x_1 + 2x_2 - 10) \\ & + z_3(3 - x_1 - x_2) - z_4x_1 - z_5x_2 \end{aligned}

となるので,KKT条件は次式で表される.

xL(x,z)=(x18x26)+z1(31)+z2(12)+z3(11)+z4(10)+z5(01)=(00)zL(x,z)=(3x1+x215x1+x210x1x2+3x1x2)(00000)z1,,z50,z1(3x1+x215)=0,z2(x1+x210)=0,z3(x1x2+3)=0,z4x1=0,z5x2=0\begin{aligned} &\begin{aligned} \nabla_\mathbf{x} L(\mathbf{x,z}) = &\binom{x_1 - 8}{x_2 - 6} + z_1\binom{3}{1} + z_2\binom{1}{2} \\ & + z_3\binom{-1}{-1} + z_4\binom{-1}{0} + z_5\binom{0}{-1} = \binom{0}{0} \end{aligned} \\ &\begin{aligned} \nabla_\mathbf{z} L(\mathbf{x,z}) &= \begin{pmatrix} 3x_1 + x_2 - 15 \\ x_1 + x_2 - 10 \\ -x_1 - x_2 + 3 \\ -x_1 \\ -x_2 \end{pmatrix} \leq \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{aligned} \\ &\begin{aligned} &z_1,\cdots,z_5 \geq 0, \\ &z_1(3x_1 + x_2 - 15) = 0, z_2(x_1 + x_2 - 10) = 0,z_3(-x_1 - x_2 + 3) = 0, z_4x_1 = 0, z_5x_2 = 0 \end{aligned} \end{aligned}

図により明らかに点(4,3)が最適解になる.

2つの実行可能解(4,3),(5,0)においてKKT条件が成り立つかどうかを吟味する

(1) 最適解(4,3)において:相補性条件より

0z1=0,0z2=0,4z3=0,4z4=0,3z5=0,0 \cdot z_1 = 0, 0 \cdot z_2 = 0, -4z_3 = 0, 4z_4 = 0, 3z_5 = 0,

なので,z3=z4=z5=0z_3 = z_4 = z_5 = 0となる.(これらに対応する制約式は効いていない)よって,KKT条件のxL(x,z)=0\nabla_\mathbf{x} L(\mathbf{x},\mathbf{z}) = \mathbf{0}より,

z1(31)+z2(12)=f(4,3)=(43)z_1\binom{3}{1} + z_2\binom{1}{2} = -\nabla f(4,3) = \binom{4}{3}

なので,z1=1>0,z2=1>0z_1 = 1 > 0, z_2 = 1 > 0を得る(線形独立制約想定が成り立っていることに注意).従って,最適解(4,3)においてKKT条件が成り立つ.

(2) 点(5,0)において:相補性条件より

z2=z3=z4=0z_2 = z_3 = z_4 = 0

なので,KKT条件のxL(x,z)=0\nabla_\mathbf{x} L(\mathbf{x},\mathbf{z}) = \mathbf{0}より,

z1(31)+z5(01)=f(5,0)=(36)z_1\binom{3}{1} + z_5\binom{0}{-1} = -\nabla f(5,0) = \binom{3}{6}

となる(線形独立制約想定は成り立っている).これにより,z1=1>0,z5=5<0z_1 = 1 > 0, z_5 = -5 < 0を得るので,点(5,0)ではKKT条件が成り立たない.

f(x)0f(x)\nabla f(\mathbf{x}^*) \neq \mathbf{0} \Rightarrow -\nabla f(\mathbf{x}^*)方向に進むとfは減る
しかし,zihi(x)=f(x)\sum z_i^* \nabla h_i(\mathbf{x}^*) = -\nabla f(\mathbf{x}^*)
その方向に進むと満たされなくなる制約がある

KKT条件は制約想定を仮定しなければ,そのままでは最適解であるための必要条件になるとは限らないことを注意すること.次の例題を見てみよう.

例題:次の最小化問題を考える

minx1s.tx2(1x1)3x20\begin{aligned} \min \quad &-x_1 \\ s.t \quad &x_2 \leq (1 - x_1)^3 \\ &x_2 \geq 0 \end{aligned}

f(x1,x2)=x1,h1(x1,x2)=x2(1x1)3,h2(x1,x2)=x2f(x_1,x_2) = -x_1, h_1(x_1,x_2) = x_2 - (1 - x_1)^3, h_2(x_1,x_2) = -x_2とおくと

f(x1,x2)=(10),h1(x1,x2)=(3(1x1)21),h2(x1,x2)=(01)\begin{aligned} \nabla f(x_1,x_2) = \begin{pmatrix} -1 \\ 0 \end{pmatrix}, \nabla h_1(x_1,x_2) = \begin{pmatrix} 3(1 - x_1)^2 \\ 1 \end{pmatrix}, \nabla h_2(x_1,x_2) = \begin{pmatrix} 0 \\ -1 \end{pmatrix} \end{aligned}

となる.しかしながら,解(x1,x2)(x_1^*,x_2^*)において

f(x1,x2)+z1h1(x1,x2)+z2h2(x1,x2)=0\nabla f(x_1^*,x_2^*) + z_1 \nabla h_1(x_1^*,x_2^*) + z_2 \nabla h_2(x_1^*,x_2^*) = \mathbf{0}

すなわち

(10)+z1(01)+z2(01)=(00)\binom{-1}{0} + z_1\binom{0}{1} + z_2\binom{0}{-1} = \binom{0}{0}

を満たす非負の数z1,z2z_1,z_2は存在しない.従って,KKT条件は満たされない.この時,制約条件の勾配ベクトルh1(x1,x2)=(0,1)T,h2(x1,x2)=(0,1)T\nabla h_1(x_1^*,x_2^*) = (0,1)^T, \nabla h_2(x_1^*,x_2^*) = (0,-1)^Tが線形独立でない(すなわち線形独立制約条件想定が成り立たない)ことが最適解においてKKT条件が成り立たない原因になっている.他方,Fritz-John条件

z0(10)+z1(01)+z2(01)=(00)z_0\binom{-1}{0} + z_1\binom{0}{1} + z_2\binom{0}{-1} = \binom{0}{0}

z0=0,z1=z2=1z_0 = 0, z_1 = z_2 = 1として成り立っている.

定理5.4: 不等式制約付き問題の最適性条件:2次の必要条件

不等式制約付き問題の局所的最小解x\mathbf{x}^*においてf,hi(i=1,,l)f,h_i(i = 1,\cdots,l)が2回微分可能で上四つのKKT条件を満足するz\mathbf{z}^*が存在するとする.さらに,全てのiI(x)i \in I(\mathbf{x}^*)に対してhi(x)Tv=0\nabla h_i(\mathbf{x}^*)^T \mathbf{v} = 0となる零でない任意のvRn\mathbf{v} \in \mathbb{R}^nに対して,適当な正の数cと連続なベクトル値関数ϕ:[0,c)Rnが存在して,ϕ(0)=x,hi(ϕ(τ))=0(iI(x),τ(0,c)),limτϕ(τ)ϕ(0)τ=βv\phi : [0,c) \rightarrow \mathbb{R}^n\text{が存在して},\phi (0) = \mathbf{x}^*, h_i(\phi(\tau)) = 0(\forall i \in I(\mathbf{x}^*), \forall \tau \in (0,c)),\lim_{\tau \rightarrow \infty} \frac{\phi(\tau) - \phi(0)}{\tau} = \beta \mathbf{v}が成り立つとする(2次の制約想定).ただし,β\betaは正の数である.この時,hi(x)Tv=0(iI(x))\nabla h_i(\mathbf{x}^*)^T \mathbf{v} = 0(\forall i \in I(\mathbf{x}^*))を満たす任意のvRn\mathbf{v} \in \mathbb{R}^nに対して,

vTx2L(x,z)v0\mathbf{v}^T \nabla^2_\mathbf{x} L(\mathbf{x},\mathbf{z})\mathbf{v} \geq 0

となる.ただし,x2L(x,z)\nabla_\mathbf{x}^2 L(\mathbf{x},\mathbf{z})はラグランジュ関数のx\mathbf{x}についての2階偏導関数行列であり,

x2L(x,z)=2f(x)+i=1lzi2hi(x)\nabla_\mathbf{x}^2 L(\mathbf{x},\mathbf{z}) = \nabla^2 f(\mathbf{x}) + \sum_{i=1}^l z_i \nabla^2 h_i(\mathbf{x})

で表される.

最小解であるための2次の十分条件を述べるにあたって,次の集合を定義しておく.

I+(x)={i  zi>0}V(x)={vRn  hi(x)Tv=0,iI+(x),hi(x)Tv0,iI(x)I+(x)}\begin{aligned} I_+(\mathbf{x}^*) &= \lbrace i \ |\ z_i^* > 0 \rbrace \\ V(\mathbf{x}^*) &= \lbrace \mathbf{v} \in \mathbb{R}^n \ |\ \nabla h_i(\mathbf{x}^*)^T \mathbf{v} = 0, i \in I_+(\mathbf{x}^*),\nabla h_i(\mathbf{x}^*)^T \mathbf{v} \leq 0, i \in \frac{I(\mathbf{x}^*)}{I_+(\mathbf{x}^*)} \rbrace \end{aligned}

定理5.5: 不等式制約付き問題の最適性条件:2次の十分条件

x\mathbf{x}^*においてf,hi(i=1,,l)f,h_i(i = 1,\cdots,l)が2回微分可能で,かつ,KKT条件を満足するz\mathbf{z}^*が存在すると仮定し,零でない任意のvV(x)\mathbf{v} \in V(\mathbf{x}^*)に対して,

vTx2L(x,z)v>0\mathbf{v}^T \nabla_\mathbf{x}^2 L(\mathbf{x},\mathbf{z}^*) \mathbf{v} > 0

が成り立つとする.この時,x\mathbf{x}^*は不等式制約付き問題の局所的最小解になり,しかもx\mathbf{x}^*の近傍ではx\mathbf{x}^*が唯一の局所的最小解になる.

例題(5.1.1)

次の非線形最小化問題それぞれに対して,ラグランジュ関数を作り,最適解を求めよ.

(1)

minx12+x22+x32s.tx1+3x2+4x3=61\begin{aligned} \min \quad &x_1^2 + x_2^2 + x_3^2 \\ s.t \quad &x_1 + 3x_2 + 4x_3 = 61 \end{aligned}

ラグランジュ関数は

L(x1,x2,x3,y)=x12+x22+x32+y(x1+3x2+4x361)L(x_1,x_2,x_3,y) = x_1^2 + x_2^2 + x_3^2 + y(x_1 + 3x_2 + 4x_3 - 61)

となる.等式制約付き問題の最適性条件:一次の必要条件より

Lx1=2x1+y=0,Lx2=2x2+3y=0,Lx3=2x3+4y=0Ly=x1+3x2+4x361=0\begin{aligned} &\frac{\partial L}{\partial x_1} = 2x_1 + y = 0, \frac{\partial L}{\partial x_2} = 2x_2 + 3y = 0, \frac{\partial L}{\partial x_3} = 2x_3 + 4y = 0 \\ &\frac{\partial L}{\partial y} = x_1 + 3x_2 + 4x_3 - 61 = 0 \end{aligned}

で表される.ただし,

f(x)=(2x12x22x3),g(x1,x2,x3)=(134)\begin{aligned} \nabla f(\mathbf{x}) = \begin{pmatrix} 2x_1 \\ 2x_2 \\ 2x_3 \end{pmatrix}, \nabla g(x_1,x_2,x_3) = \begin{pmatrix} 1 \\ 3 \\ 4 \end{pmatrix} \end{aligned}

である.これを解くと,y=6113y = -\frac{61}{13}となり,最適解は

(x1,x2,x3)=(6126,18326,12213)(x_1,x_2,x_3) = (\frac{61}{26}, \frac{183}{26}, \frac{122}{13})

となる.

(2)

minx12x22s.tx12+4x22=1\begin{aligned} \min \quad &x_1^2 - x_2^2 \\ s.t \quad &x_1^2 + 4x_2^2 = 1 \end{aligned}

ラグランジュ関数は

L(x1,x2,y)=x12+x22+y(x12+4x221)L(x_1,x_2,y) = x_1^2 + x_2^2 + y(x_1^2 + 4x_2^2 - 1)

となる.等式制約付き問題の最適性条件:一次の必要条件より

Lx1=2x1+2yx1=0,Lx2=2x2+8yx2=0Ly=x12+4x221=0\begin{aligned} &\frac{\partial L}{\partial x_1} = 2x_1 + 2yx_1 = 0, \frac{\partial L}{\partial x_2} = -2x_2 + 8yx_2 = 0 \\ &\frac{\partial L}{\partial y} = x_1^2 + 4x_2^2 - 1 = 0 \end{aligned}

で表される.ただし,

f(x)=(2x12x2),g(x1,x2)=(2x18x2)\begin{aligned} \nabla f(\mathbf{x}) = \begin{pmatrix} 2x_1 \\ -2x_2 \end{pmatrix}, \nabla g(x_1,x_2) = \begin{pmatrix} 2x_1 \\ 8x_2 \end{pmatrix} \end{aligned}

である.これを解くと,y=1,14y = -1, \frac{1}{4}だが,y=1y = -1の時,最大値が求められる.y=14y = \frac{1}{4}の時,最小値が求められる.従って,最適解は

(x1,x2)=(0,12)(x_1,x_2) = (0, \frac{1}{2})

となる.

(3)

minx1+x2++xns.tx12+x22++xn2=1\begin{aligned} \min \quad &x_1 + x_2 + \cdots + x_n \\ s.t \quad &x_1^2 + x_2^2 + \cdots + x_n^2 = 1 \end{aligned}

ラグランジュ関数は

L(x1,,xn,y)=x1+x2++xn+y(x12+x22++xn21)L(x_1,\cdots, x_n, y) = x_1 + x_2 + \cdots + x_n + y(x_1^2 + x_2^2 + \cdots + x_n^2 - 1)

となる.ただし,

f(x)=(11),g(x)=(2x12xn)\begin{aligned} \nabla f(\mathbf{x}) = \begin{pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix}, \nabla g(\mathbf{x}) = \begin{pmatrix} 2x_1 \\ \vdots \\ 2x_n \end{pmatrix} \end{aligned}

である.等式制約付き問題の最適性条件:一次の必要条件より方程式を解くと,

xi=±nn(i=1,,n),y=n2x_i = \pm \frac{\sqrt{n}}{n} (i = 1, \cdots, n), y = -\frac{\sqrt{n}}{2}

となる.最適解は

(x1,,xn)=(nn,,nn)(x_1,\cdots,x_n) = (-\frac{\sqrt{n}}{n}, \cdots, -\frac{\sqrt{n}}{n})

である.

例題(5.1.2)

次の非線形最小化問題のKKT条件を書き,さらにKKT条件を満たす(x,z)(\mathbf{x}^*,\mathbf{z}^*)を求めよ.

min12((x12)2+(x24)2)s.tx1+3x26x1+4x24x10,x20\begin{aligned} \min \quad &\frac{1}{2}((x_1 - 2)^2 + (x_2 - 4)^2) \\ s.t \quad &x_1 + 3x_2 \leq 6 \\ &x_1 + 4x_2 \leq 4 \\ &x_1 \geq 0,x_2 \geq 0 \end{aligned}

ラグランジュ関数は

L(x1,x2,z1,z2,z3,z4)=12((x12)2+(x24)2)+z1(x1+3x26)+z2(x1+4x24)z3x1z4x2\begin{aligned} L(x_1,x_2,z_1,z_2,z_3,z_4) = &\frac{1}{2}((x_1 - 2)^2 + (x_2 - 4)^2) \\ &+ z_1(x_1 + 3x_2 - 6) + z_2(x_1 + 4x_2 - 4) - z_3x_1 - z_4x_2 \end{aligned}

となるので,KKT条件は次式で表される.

xL(x,z)=(x12x24)+z1(13)+z2(14)+z3(10)+z4(01)=(00)zL(x,z)=(x1+3x26x1+4x24x1x2)(0000)z1,,z40,z1(x1+3x26)=0,z2(x1+4x24)=0,z3x1=0,z4x2=0\begin{aligned} &\begin{aligned} \nabla_\mathbf{x} L(\mathbf{x,z}) = &\binom{x_1 - 2}{x_2 - 4} + z_1\binom{1}{3} + z_2\binom{1}{4} \\ & + z_3\binom{-1}{0} + z_4\binom{0}{-1} = \binom{0}{0} \end{aligned} \\ &\begin{aligned} \nabla_\mathbf{z} L(\mathbf{x,z}) &= \begin{pmatrix} x_1 + 3x_2 - 6 \\ x_1 + 4x_2 - 4 \\ -x_1 \\ -x_2 \end{pmatrix} \leq \begin{pmatrix} 0 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{aligned} \\ &\begin{aligned} &z_1,\cdots,z_4 \geq 0, \\ &z_1(x_1 + 3x_2 - 6) = 0, z_2(x_1 + 4x_2 - 4) = 0, z_3x_1 = 0, z_4x_2 = 0 \end{aligned} \end{aligned}

最適解(2017,1217\frac{20}{17}, \frac{12}{17})において,相補性条件より

4617z1=0,0z2=0,2017z3=0,1217z4=0-\frac{46}{17}z_1 = 0, 0 \cdot z_2 = 0, \frac{20}{17}z_3 = 0, \frac{12}{17}z_4 = 0

なので,z1=z3=z4=0z_1 = z_3 = z_4 = 0となる.KKT条件のxL(x,z)=0\nabla_\mathbf{x} L(\mathbf{x},\mathbf{z}) = \mathbf{0}より,

z2(14)=f(2017,1217)=(14175617)z_2 \binom{1}{4} = -\nabla f(\frac{20}{17}, \frac{12}{17}) = \binom{\frac{14}{17}}{\frac{56}{17}}

なので,z2=1417>0z_2 = \frac{14}{17} > 0を得る.他方,Fritz-John条件

z0(14175617)+z2(14)=(00)z_0\binom{-\frac{14}{17}}{-\frac{56}{17}} + z_2\binom{1}{4} = \binom{0}{0}

z0=0,z2=1417z_0 = 0, z_2 = \frac{14}{17}として成り立っている.

最適解(x1,x2)=(2017,1217)(x_1,x_2) = (\frac{20}{17}, \frac{12}{17})である.

一般の制約付き問題に対する最適性条件

等式制約付き問題と不等式制約付き問題のそれぞれの最適性条件をまとめると,一般の制約付き問題に対する最適性条件が得られる.すなわち,ラグランジュ関数を

L(x,y,z)=f(x)+yTg(x)+zTh(x)=f(x)+i=1nyigi(x)+j=1lzjhj(x)\begin{aligned} L(\mathbf{x}, \mathbf{y}, \mathbf{z}) &= f(\mathbf{x}) + \mathbf{y}^T \mathbf{g}(\mathbf{x}) + \mathbf{z}^T \mathbf{h}(\mathbf{x}) \\ &= f(\mathbf{x}) + \sum_{i = 1}^n y_i g_i(\mathbf{x}) + \sum_{j=1}^l z_j h_j(\mathbf{x}) \end{aligned}

と定義した時,制約付き問題を解くことは次の5つの条件を満足する点(x,y,z)(\mathbf{x}^*,\mathbf{y}^*,\mathbf{z}^*)を見つけることに帰着される.

xL(x,y,z)=f(x)+i=1myigi(x)+j=1lzjhj(x)=0yL(x,y,z)=g(x)=0zL(x,y,z)=h(x)0zi0(i=1,,l)zihi(x)=0(i=1,,l)\begin{aligned} &\nabla_\mathbf{x} L(\mathbf{x},\mathbf{y},\mathbf{z}) = \nabla f(\mathbf{x}) + \sum_{i=1}^m y_i \nabla g_i(\mathbf{x}) + \sum_{j=1}^l z_j \nabla h_j(\mathbf{x}) = \mathbf{0} \\ &\nabla_\mathbf{y} L(\mathbf{x},\mathbf{y},\mathbf{z}) = \mathbf{g}(\mathbf{x}) = \mathbf{0} \\ &\nabla_\mathbf{z} L(\mathbf{x},\mathbf{y},\mathbf{z}) = \mathbf{h}(\mathbf{x}) \leq \mathbf{0} \\ &z_i \geq 0 \quad (i = 1,\cdots,l) \\ &z_i h_i(\mathbf{x}) = 0 \quad (i = 1,\cdots,l) \end{aligned}

以上の5つの条件を改めてKarush-Kuhn-Tucker条件(KKT条件)と呼び,KKT条件を満足する点(x,y,z\mathbf{x}^*,\mathbf{y}^*,\mathbf{z}^*)をKKT点と呼ぶ.

定理:凸計画問題のKKT条件:Karush-Kuhn-Tuckerの最適性十分条件

点(x,y,z\mathbf{x}^*,\mathbf{y}^*,\mathbf{z}^*)を制約付き問題のKKT点とする.f(x),hi(x)(i=1,,l)xf(\mathbf{x}),h_i(\mathbf{x})(i = 1,\cdots,l) \text{が}\mathbf{x}^*で微分可能な凸関数でgi(x)(i=1,,m)g_i(\mathbf{x})(i = 1,\cdots,m)が全て1次式ならば,点x\mathbf{x}^*は制約付き問題の最適解になる.

この定理の仮定を満足するような制約付き問題を,特に凸計画問題(convex programming problem)と呼ぶ.
代表的な凸計画問題として線形計画問題と2次計画問題があげられる.

例題:線形計画問題のKKT条件

ARm×n,bRm,cRnA \in \mathbb{R}^{m \times n},\mathbf{b} \in \mathbb{R}^m,\mathbf{c} \in \mathbb{R}^nが与られた時,xRn\mathbf{x} \in \mathbb{R}^nに関する線形計画問題

mincTxs.tAx=b(x0)\begin{aligned} \min \quad &\mathbf{c}^T\mathbf{x} \\ s.t \quad &A\mathbf{x} = \mathbf{b} \quad (\mathbf{x} \geq \mathbf{0}) \end{aligned}

を考える.g(x)=bAx,h(x)=x\mathbf{g}(\mathbf{x}) = \mathbf{b} - A\mathbf{x},\mathbf{h}(\mathbf{x}) = -\mathbf{x}とおくと,ラグランジュ関数は

L(x,y,z)=cTx+yT(bAx)zTxL(\mathbf{x},\mathbf{y},\mathbf{z}) = \mathbf{c}^T\mathbf{x} + \mathbf{y}^T(\mathbf{b} - A\mathbf{x}) - \mathbf{z}^T\mathbf{x}

で定義される.また,KKT条件は次式で与られる.

cATyz=0,Ax=bx0,z0,zixi=0(i=1,,n)\begin{aligned} &\mathbf{c}- A^T\mathbf{y} - \mathbf{z} = \mathbf{0}, \quad A\mathbf{x} = \mathbf{b} \\ &\mathbf{x} \geq \mathbf{0},\quad \mathbf{z} \geq \mathbf{0}, \quad z_ix_i = 0(i = 1,\cdots,n) \end{aligned}

これらの条件式は3.8節の相補性定理で述べた最適性条件にほかならない

例題:凸2次計画問題のKKT条件

QRn×n,ARm×n,bRm,cRnQ \in \mathbb{R}^{n \times n}, A \in \mathbb{R}^{m \times n},\mathbf{b} \in \mathbb{R}^m, \mathbf{c} \in \mathbb{R}^nが与られた時,xRn\mathbf{x} \in \mathbb{R}^nに関する2次計画問題

min12xTQx+cTxs.tAx=b(x0)\begin{aligned} \min \quad &\frac{1}{2}\mathbf{x}^TQ\mathbf{x} + \mathbf{c}^T\mathbf{x} \\ s.t \quad &A\mathbf{x} = \mathbf{b} \quad (\mathbf{x} \geq \mathbf{0}) \end{aligned}

を考える.ただし,Qは半正定値対称行列である.線形計画問題の場合と同様に,ラグランジュ関数は

L(x,y,z)=12xTQx+cTx+yT(bAx)zTxL(\mathbf{x},\mathbf{y},\mathbf{z}) = \frac{1}{2}\mathbf{x}^TQ\mathbf{x} + \mathbf{c}^T\mathbf{x} + \mathbf{y}^T(\mathbf{b} - A\mathbf{x}) - \mathbf{z}^T\mathbf{x}

で定義され,KKT条件は次式で与られる.

Qx+cATyz=0,Ax=bx0,z0,zixi=0(i=1,,n)\begin{aligned} &Q\mathbf{x} + \mathbf{c} - A^T\mathbf{y} - \mathbf{z} = \mathbf{0}, \quad A\mathbf{x} = \mathbf{b} \\ &\mathbf{x} \geq \mathbf{0}, \mathbf{z} \geq \mathbf{0}, z_ix_i = 0(i = 1,\cdots,n) \end{aligned}

凸QPのKKT点は(比較的)簡単に求められる(数値解法あり,5.4節参照)

例題(5.1.3)

次の非線形最小化問題のKKT条件を記述し,さらに最適解を求めよ.

minx1logx1+x2logx2++xnlogxns.tx1+x2++xn=1x1,,xn0\begin{aligned} \min \quad &x_1\log x_1 + x_2\log x_2 + \cdots + x_n\log x_n \\ s.t \quad &x_1 + x_2 + \cdots + x_n = 1 \\ &x_1,\cdots,x_n \geq 0 \end{aligned}

なお,log0=,0log0=0\log 0 = -\infty, 0\log 0 = 0とする.

ラグランジュ関数は

L(x,y,z)=x1logx1++xnlogxn+y(x1++xn1)z1x1znxn\begin{aligned} L(\mathbf{x}, \mathbf{y}, \mathbf{z}) = x_1\log{x_1} + \cdots + x_n\log{x_n} + y(x_1 + \cdots + x_n - 1) - z_1x_1 - \cdots - z_nx_n \end{aligned}

KKT条件より

xL(x,y,z)=0yL(x,y,z)=x1+x2++xn1=0zL(x,y,z)=x0zi0(i=1,,n)zixi(x)=0(i=1,,n)\begin{aligned} &\nabla_x L(\mathbf{x}, \mathbf{y}, \mathbf{z}) = \mathbf{0} \\ &\nabla_\mathbf{y} L(\mathbf{x},\mathbf{y},\mathbf{z}) = x_1 + x_2 + \cdots + x_n - 1 = \mathbf{0} \\ &\nabla_\mathbf{z} L(\mathbf{x},\mathbf{y},\mathbf{z}) = -\mathbf{x} \leq \mathbf{0} \\ &z_i \geq 0 \quad (i = 1,\cdots,n) \\ &z_i x_i(\mathbf{x}) = 0 \quad (i = 1,\cdots,n) \end{aligned}

これを解くと,最適解は

(x1,,xn)=(1n,,1n)(x_1,\cdots,x_n) = (\frac{1}{n}, \cdots, \frac{1}{n})

となり, 最小値はlogn-\log{n}である.

非線形計画法の双対定理

線形計画問題の拡張:2次錐計画問題と半正定値計画問題

制約付き最小解問題の数値解法

ペナルティー関数法

乗数法

逐次2次計画法

主双対内点法

参考文献

  • 工学基礎 最適化とその応用 (矢部 博)