数理計画法

  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