3. 非線形問題の高速化チューニング #

3.1. 説明 #

計算時間の短縮改善策で言及した改善策は広く共通する基本的な戦略である．また数理最適化モデルとして現実的な計算資源で求解可能な問題範囲は，多くの場合で線形問題に限定される．それら問題は変数の数が数千数万という規模が普通であり，問題が有している複雑さを定式化で工夫して簡約させることが基本である．

例えば仮に非線形な定式化が要求されるように見えても，線形な定式化に等価変形できないか，またはそのようなことを意図して，要件自体を近似的に扱えないか，といったことを思案する．

しかし本質的に二次や凸最適化問題やより一般の非線形問題の記述が必須となる場合には，求解アルゴリズムを意識した定式化を思案することも一手段となりえる．

ここで対象とする問題とは，真に非線形問題として扱い甲斐がある問題のことで，次の特徴を持った問題のことである．

変数の数が高々数十である．
変数は連続変数に限る．
非線形性を有する制約条件があまりに多様ではない．

このような問題については以下のような観点でチューニングを行うことで，求解時間の高速化が期待できる傾向にある．

探索領域の明示的な削減
スケール調整
変数の有界性の明示
非線形関数の次数削減

注釈

数式を計算機側が解釈して，より負担の少ない数式に変形することを，モデリング言語のユーザは期待するところがある．そして以下に述べる項目はとりわけそのような期待を抱かせるかもしれない．

しかしこの期待はモデリング言語に求められる機能として不自然ではないにしろ，万能とは言えない．ユーザはそのような計算機側の式変形を過信せずに，自らが計算機にとって解釈が容易にできるよう整える必要がある．

3.1.1. 探索領域の明示的な削減 #

変数 \(x\) として次式のように単に非負条件だけが要求されるような問題だったとしよう．

(3.29)#\[x \geq 0\]

このような場合には文字通り，非負実数全体が探索領域となる．しかしながら現実に遭遇する問題では，そのような探索領域がすべて真に必要だとはそうそう考えられない．要件を洗い出せば，実のところはもっとずっと小さかったということも珍しいことではない．

今もしそのようなことを考えて問題に表れる変数の実行可能領域を縮小できたならば，それだけ計算機側にとっては求解動作に伴う探索領域 (解空間) が削減されることになるので，無駄な探索の機会が減少することに繋がって好ましい定式化だといえる．

3.1.2. スケール調整 #

非線形性が強くなると，そのまま定式を図った場合には，数値の起伏が激しいものになりがちである．求解で得られる変数の値に有意なバラツキが認められる場合には，それら変数が関わる制約条件のスケールを吟味して，式の上で調整を図るとよい．

スケールの確認方法としては求解結果で得られる変数と制約式の絶対値を参照することになる．すると (真に \(0\) の場合を除くうちで) これらが \([10^a,10^b]\) という範囲にあると判明するが，可能な限りこの \(a\) と \(b\) の値を近付けることがスケールの大小を削減することに対応する．

スケールの修正方法としては以下のようなものである．次の制約条件があったとしよう．

(3.30)#\[x_{i,j} \geq A_{i,j}\]

もしこの制約式が特に \(100\) 倍ほどスケール不足だったならば，次のように書き換える．

(3.31)#\[100 \cdot x_{i,j} \geq 100 \cdot A_{i,j}\]

抽象的な数式という観点では自明に等価な変形に過ぎないが，計算機の数式処理という観点ではこれは非自明な前処理となる．

3.1.3. 変数の有界性の明示 #

ある変数 \(x\) とある定数 \(A\) があったとして，式を整理する中で \(x+A\) という形が頻出するために，これを \(y\) と置くことで，上下限制約が次のように単純に書けて都合が良いとする．

(3.32)#\[L \leq y \leq U\]

これは大元の変数 \(x\) の有界性を暗に意味するものである．定式化の式構造をユーザが要点を押さえて把握するという観点では，この記述はどちらかと言えば望ましいといえるだろう．しかし計算機の立場で考えると，変数の有界性は陽に直接記述されている方が解釈が優しい．

今の例ならば次の記述が，陽に変数 \(x\) の有界性を記述している．

(3.33)#\[L - A \leq x \leq U - A\]

上記はモデリング言語で変数クラス Variable と式クラス Expression の違いに換言される．以下の C++SIMPLE の記述で case 1 が変数の有界性が明示的ではない場合であり，case 2 が明示的な場合である．式オブジェクトはモデル記述の可読性を上げるために有効な記述手段であるが，より一層の高速化チューニングが必要な場合は，上記のように可読性を犠牲にする可能性がある．

3.1.3.1. C++SIMPLE #

// case 1
Parameter A, L, U;
Variable x;
Expression y;
y = x + A;
L <= y <= U;

// case 2
Parameter A, L, U;
Variable x;
L - A <= x <= U - A;

3.1.3.2. PySIMPLE #

PySIMPLE の場合は変数宣言時に境界条件を設定するため，可読性の低下は C++SIMPLE ほどではない．

from pysimple import Problem, Parameter, Variable

p = Problem()
A = Parameter()
L = Parameter()
U = Parameter()
x = Variable(lb=L-A, ub=U-A)
y = x + A
p += L <= y
p += y <= U

3.1.4. 非線形関数の次数削減 #

非線形関数は次数が \(2\) に近いほどよく，場合によっては線形関数に帰着できる場合がある．このような具体例を以下に挙げる．

3.1.4.1. 例 1 #

非負実数変数 \(x\) に対して次の制約条件があったとしよう．

(3.34)#\[L \leq \sqrt{x} \leq U\]

この制約条件式には非線形関数として \(\sqrt{x}\) が左辺にある．平方根関数は原点で傾きが無限大のため，数値計算をする上では非常に厄介な関数の代表格である．

何かしらの理論的な要件でこのように制約条件式を整理することが美しいもしくは自然な場合があり，それをそのまま記述した場合をここでは想定したとしよう．

この制約条件式は数理最適化の文脈では必ずしも，この形を使う必要があるとはいえず，次の線形式の記述が望ましいと期待される．

(3.35)#\[L^2 \leq x \leq U^2\]

3.1.4.2. 例 2 #

次の実数値を与える非線形関数 \(G_1,G_2\) の積で定義される非負の目的関数 \(f_G\) があったとしよう．

(3.36)#\[\mathrm{Minimize:}~ f_G := G_1 \cdot G_2 \geq 0\]

\(G_1,G_2\) の引数には様々な変数 \(x,y,z,\ldots\) に依存しているが，ここでは詳細を問わない．今こうして定義された目的関数に対して，次の非負な中間変数 \(g_1,g_2\) を追加した次の定式化を考えたとする．

(3.37)#\[\begin{split}& \mathrm{Minimize:}~ f_g := g_1\cdot g_2 \\ & \mathrm{subject~to:}~ \\ & -g_1 \leq G_1 \leq g_1, \\ & -g_2 \leq G_2 \leq g_2\end{split}\]

但し \(G_1\) と \(G_2\) のそれぞれに表れる変数の集合は互いに素だとする．

これら \(2\) つの定式化は等価な定式化になっている．それは次のとおり．

非線形関数 \(G\) があったとして，これは実行可能領域で (正負の無限大まで含めて) 上下界が何かしら定まっており，どんなに複雑な非線形関数であっても \(G\) はある実数値をとる．その範囲を \(-g\leq G\leq g\) として，複雑さを一つの連続変数に押し付ける．各 \(g\) はそれぞれ独立に動き得るが，それは元々の \(G\) で変数が分離できているため問題ない．

以上のようにして次数を下げることができるが，動きうる変数が分離できている場合には，上記のように一度に解くのではなく，それぞれ各 \(G\) について順に求解すれば良いともいえる．

3.1.4.3. 例 3 #

先ほどの例の特殊な場合として次を挙げる．

(3.38)#\[G_1 = G_2 = G := \sum_{i} x_i^2 = \langle x,x\rangle\]

ちょうど内積 \(\langle\cdot,\cdot\rangle\) の形の構造をもった目的関数を設定する場合である．この場合には目的関数は \(4\) 次の高次関数だが，次のようにして \(2\) 次関数に次数を削減できる．

(3.39)#\[\begin{split}& \mathrm{Minimize:}~ f_g := g^2 \\ & \mathrm{subject~to:}~ \\ & -g \leq \langle x,x\rangle \leq g\end{split}\]

もしくは次のように \(G\) に添字が残っている場合を考える．

(3.40)#\[G_{j,k} = \sum_{i} x_{i;j,k}^2 = \langle x_{j,k},x_{j,k}\rangle\]

目的関数は次のより複雑な非負の \(4\) 次関数である．

(3.41)#\[\mathrm{Minimize:}~ f_G := G\cdot G = \sum_{j,k} G_{j,k}^2\]

これは次のように \(2\) 次へと次数削減される．

(3.42)#\[\begin{split}& \mathrm{Minimize:}~ f_g := g\cdot g = \sum_{j,k} g_{j,k}^2 \\ & \mathrm{subject~to:}~ \\ & -g_{j,k} \leq \langle x_{j,k},x_{j,k}\rangle \leq g_{j,k}\end{split}\]

3.1.4.4. 例 4 #

(3.43)#\[\begin{split}& f(x_1,x_2) := G1\cdot G2, \\ & G_1 := 1 + (x_1 + x_2 + 1)^2 (19 - 14 x_1 + 3 x_1^2 - 14 x_2 + 6 x_1 x_2 + 3 x_2^2), \\ & G_2 := 30 + (2 x_1 - 3 x_2)^2 (18 - 32 x_1 + 12 x_1^2 + 48 x_2 - 36 x_1 x_2 + 27 x_2^2)\end{split}\]

\(f\) は Goldstein Price 関数とよばれ，\(-2\leq x_{i=1,2}\leq 2\) の範囲で，その最小化の大域的最適解は \((x_1,x_2)=(0,-1)\) で最適値は \(3\) である．

Variable x1, x2;
-2 <= x1;
x2 <= 2;

Expression G1, G2;
G1 = 1 + pow(x1 + x2 + 1, 2) * (19 - 14 * x1 + 3 * x1 * x1 - 14 * x2 + 6 * x1 * x2 + 3 * x2 * x2);
G2 = 30 + pow(2 * x1 - 3 * x2, 2) * (18 - 32 * x1 + 12 * x1 * x1 + 48 * x2 - 36 * x1 * x2 + 27 * x2 * x2);

// case 1
// Minimize f = G1 * G2;

// case 2
Variable g1; g1 >= 0;
Variable g2; g2 >= 0;
- g1 <= G1 <= g1;
- g2 <= G2 <= g2;
Minimize f = g1 * g2;

solve();
x1.val.print(); // x1 = 3.37271e-11
x2.val.print(); // x2 = -1
f.val.print();  // f = 3

非線形問題の高速化チューニング

目次