Model Building in Mathematical Programming: Chapter 7

Optimization Night で H. Paul Williams, Model Building in Mathematical Programming, 5th Edition, Wiley, 2013. の輪読会をしているので、そのメモです。

Chapter 7 Non-linear models

ここでは、非線形問題をどうやって線形な問題に変形するか、関数の凸性等について学んだ

7.1 Typical applications

目的関数が線形の場合、スケールによるメリットやデメリットを表現できない。例えば、目的関数が利益だった場合、

目的関数が線形である == 生産量が少なくても多くても、1単位あたりの利益は同じ

という意味だ。現実的には、生産量が多くなるほど1単位あたりのコストが下がったり、逆にリソースの取り合いが発生してコストが上がったりする。

価格弾力性 $E _ {x}$ は以下の式で定義される

$E _ {x} = \frac{\rm 需要の変化量}{\rm 価格の変化量}$

これがある範囲で一定だと思うと、適正な価格は $p(x) = kx^{-1/E_x}$ という形となるので、目的関数には、 $p(x)x = kx^{1-1/E_x}$ のような項が入ってくることになる。

他の例だと、2つ以上の原料を混ぜ合わせて新しいものをつくる混合問題で、硬さなどの指標が必ずしも各原料の割合に比例するわけではない場合や、地理情報を入れる場合に、多項式の項が出てきたりする。

7.2 Local and global optima

ここでは、凸性の定義などを確認した。凸であることがとても大事だというお話だ。

7.3 Separable programming

ここは短いけれども結構面白かった。まず、 separable (分離可能）とは、1変数の関数の和の形であらわせる関数のこと。例えば $x ^ 2 _ 1 + 2 x _ 2$ は separable だが、 $x_1 x_2 + x_2 / (1 + x _ 1)$ は separable ではない。