データ分析関連のまとめ

データ分析・機械学習周りのもくもく会LTやイベント参加をまとめていきます

数理最適化(線形計画問題)について

技術キャッチアップ

現実の問題を定式化できる線形計画問題をまとめました。
解釈間違い等ある時がありますので、その場合指摘いただけると助かります。

主に以下の内容で構成されています。

  • 線形計画問題および整数計画問題の概要
  • 問題を解くアルゴリズムはどのようなものがあるのか(中身の詳細は触れません)
  • 現実の問題を解く場合に極力線形計画問題として解きたいが、どのような定式化があるのか

背景および概要

  • 実務の中で限られたリソース等の制約の下で目的関数を最大化(or 最小化)をする際に最適化問題を解く事がある。
  • 有名な例
  • 線形計画問題:上記の目的関数が線形で制約条件が線形等式や線形不等式で表される基本的な最適化問題
  • 整数(線形)計画問題:全変数が離散的な整数値のみを取る線形計画問題
  • 組み合わせ最適化問題:制約条件を満たす解の集合が組み合わせ的な構造を持つ(解の記述例:集合、割り当て、グラフ、論理値、整数等)

線形計画問題

一般に以下の形で表される。


 minimize(maximize) \sum_{j=1}^{n} c_j x_j 

 \sum_{j=1}^{n}a_{ij} x_j \geq b_i, i=1,...,m
x_j \geq 0, j=1,...,n

  • 1番目の式:目的関数、2,3番目の式:制約式
    • 実行可能解:制約式を満たす変数の値の組
    • 最適解:実行可能解のうち最も良い目的関数を達成するもの
    • 最適値:最適解の目的関数値

また、下記のように表される事もある。


 min(\textbf{c}^t \textbf{x} | \textbf{A}\textbf{x} \geq \textbf{b} ,\textbf{x} \geq 0 )

整数計画問題

  • 整数計画問題は実行可能解が有限となる場合が多いため、理論上は最適解が求められるが問題が複雑になったり、大規模になる程現実的でなくなる。
  • 整数計画問題の代表的なアルゴリズムは以下となる。
    • 分岐限定法:以下の2つの操作を繰り返す。
      • 分岐操作:直接解くのが難しい問題を小規模な部分問題に分解する。
      • 限定操作:部分問題の中で最適解が得られないと判断されたものを除く。
    • 切除平面法:線形計画緩和問題を解き、切除平面を生成し、線形計画緩和問題に逐次追加することで整数最適解を得る。
      • 線形計画緩和問題:各変数の制約条件を緩和した線形計画問題
      • 切除平面:実行可能な整数解を残しつつ線形計画緩和問題の最適解を除去する制約式

双対問題

元の最適化問題を裏あるいは別の側面から見た問題として双対問題がある。
2つの問題を一緒に考慮することで線形計画問題の様々な性質がわかり、深い理解につながる。


 min(\textbf{c}^T \textbf{x} | \textbf{A}\textbf{x} \geq \textbf{b} ,\textbf{x} \geq 0 )

上記の線形計画問題(主問題)に対応する線形計画問題は下記で表される。


 max(\textbf{y}^T \textbf{}b | \textbf{y}^T\textbf{A} \leq \textbf{c}^T ,\textbf{y} \geq 0 )

双対問題には以下の定理がある。

定理1:反射律

双対問題の双対問題は主問題である。

定理2:弱双対性

xが主問題の実行可能解であり、yが双対問題の実行可能解ならば下記が常に成り立つ。


 \textbf{c}^T \textbf{x} \leq \textbf{y}^T\textbf{b}

定理3:強双対性

主問題と双対問題のどちらにも実行可能解が存在するならば、それぞれ最適解x,yも存在し、下記が成り立つ。


 \textbf{c}^T \textbf{x} = \textbf{y}^T\textbf{b}

線形計画問題の主問題と双対問題には次が成り立つ。

  1. 主問題と双対問題がともに実行可能ならば，主問題の実行可能解での目的関数値 は，双対問題の最適値の上界となる。
  2. 主問題と双対問題がともに実行可能ならば，それぞれ最適解をもつ。
  3. 主問題が実行可能で非有界ならば，双対問題は実行不能である。
  4. 主問題の実行可能解での目的関数値と双対問題の実行可能解での目的関数値が一致すれば、それぞれの関数値は、それぞれの問題の最適解である。

線形計画問題への定式化

実際に最適化を行おうとした場合、線形式のみを用いて目的関数と制約条件を定義する必要がある。

  • 現実の問題を線形計画問題に定式化するには、下記を見極める必要がある。
    • 与えられた現実問題を線形計画問題で正確に記述できるか
    • 許容可能な範囲で近似できるか

連立一次方程式の近似解

  • 目標計画法:全ての制約式を満たせない連立一次方程式に、出来る限り多くの制約式を満たす近似解を求める問題。

 \sum_{j=1}^{n} a_{ij} x_j = b_i 


 i=1,...,m

上記の連立一次方程式に対して、その誤差を小さくするxの近似解を求める。


 z_i = | b_i - \sum_{j=1}^{n} a_{ij} x_j^* |


 i=1,...,m

各々の誤差をm個分足し合わせたものを最小化させるため下式のようになり


 minimize \sum_{i=1}^{m}| b_i - \sum_{j=1}^{n} a_{ij} x_j |

分解すると以下の線形計画問題になる。


 minimize \sum_{i=1}^{m}z_i

 b_i - \sum_{j=1}^{n} a_{ij} x_j \geq -z_i
 b_i - \sum_{j=1}^{n} a_{ij} x_j \leq z_i
 z_i \geq 0

その他の定式化

  • 凸関数最小化問題
  • 比率の最小化(分数計画問題)等

整数計画問題への定式化

線形計画問題の方が整数計画問題より解きやすい事から、整数変数を用いた場合に解くのが困難になる場合がある。
(e.g.自動車等の生産数を決定する際に整数計画問題への定式化を行う)
上記のような場合、以下の方法で解を得られる場合がある。

  1. 各変数の整数条件を取り除いた線形計画問題を解いて実数最適解を得る。
  2. 1の端数を丸めて近い整数解を求める。

定式化例

まとめ&Next Action

  • 線形計画問題において離散的な整数値のみを持つものを整数計画問題という。
  • 整数計画問題で理論上は計算できるが、現実的に解くのが困難な場合連続値の線形計画問題として解いた結果を丸めると解が得られる場合がある。
  • 定式化にはいろいろな例があるので、実際に最適化問題を解く場合は例を参考にしてアレンジや組み合わせを行うと解きやすくなる(無理なこともある)。
  • 今回はあくまで解ける問題を作るヒントを得るために調べたが、次は代表的なアルゴリズムの中身を調べていきたい。

参考文献

1.組み合わせ最適化入門:線形計画から整数計画まで

https://www.jstage.jst.go.jp/article/jnlp/21/5/21_1059/_pdf/-char/ja

2.シンプレックス法

http://www.me.titech.ac.jp/~mizu_lab/text/pdf-file/LP3-simplex.pdf

3.数理最適化入門 (1) ：線形計画

https://www.jstage.jst.go.jp/article/bjsiam/23/1/23_KJ00008611265/_pdf/-char/ja

4.双対問題と双対定理

http://www.me.titech.ac.jp/~mizu_lab/text/pdf-file/LP3-simplex.pdf

5.応答曲面法 による最適設計と適応的累積関数近似法の紹介

https://www.jstage.jst.go.jp/article/qjjws1943/73/3/73_3_147/_pdf