トップ > 数理計画用語集 > スケーリング

数理計画用語集

スケーリング

読み:すけーりんぐ

数理計画問題を記述する係数データの大きさを1程度に均一化し,数値的振る舞いを安定化させる操作のこと.例えば

equation

のような線形制約群を考えてみる.equationと置きなおせば

equation

さらに最初の式の両辺をequation倍すれば

equation (A)

と変形できる.すなわち変数,制約式を定数倍するのみで意味を変えずに制約式を記述する係数データの大きさをそろえることができる.数値計算アルゴリズムの適用前にこのような操作を行っておくことにより,オーダー(大きさ)が異なる数同士の計算が行われてしまう可能性を減らして計算を安定化することができる.また,数値計算プログラムにおける「十分小さい」という判定をできるだけ有効なものにするためには,扱うデータのオーダーを1程度としておくのが無難であると言える.

現在,多くのソルバー(特に線形・二次計画法ソルバー)は前処理の一部として「変数のスケーリング」「制約式のスケーリング」を自動的に行い,計算の安定化を図っている.具体的には,線形制約を記述する係数を列方向,行方向にみて,そのばらつきを最小化するような変数のスケーリング(列スケーリング),制約式のスケーリング(行スケーリング)を施す.ただし,係数データの値のみを見て行うスケーリングには限界があり,問題の意味を考えないスケーリングが状況を悪化させることはあり得る.例えば上記の例で,equationequationとして二番目の式をequationすれば

equation (B)

という,係数値は同一だが,全く違ったスケーリング結果(B)が得られる.最初に述べたスケーリング結果(A)における変形での解におけるequationのオーダーが1程度だとすると,この変形で得られるequationのオーダーはequationになってしまい,値のオーダーは揃うが変数値は1から遠く離れてしまう.スケーリング結果(B)の右辺値に非常に小さな数が現れていることから(A)に比べてスケーリングが適切でないことを判断することができる.また,線形制約の係数のみならず右辺値も考えたスケーリングが有効と思われる.しかしながら右辺値が 0 である場合には,どのスケーリングが適当なのかを係数値のみを見て確定的に判断するのは一般に難しい,また「上限が存在しない」ことを示すため,制約の上限値として無意味に大きな数を入れるといった慣習もあるので常に有効とは言えない.この慣習は単体法が主要なソルバーのアルゴリズムとして用いられている場合には入力を簡便にするために有効で,原理的に数値的悪化を招かないが,内点法がアルゴリズムとして主流なものになってきた現在は,往々にしてスケーリングプログラムを惑わす結果となる.

スケールのばらついた問題が現れるそもそもの原因としては,たとえば物理系を記述する単位が不適切だったり揃っていない場合,また,精度の異なる量を同一のモデルに組み込んだ場合などがある.多くはモデル作成側で注意を払えば解消できるケースであり,上述したように自動化には限界があるため,モデル作成時に十分な注意を払うことが推奨される.

非線形計画問題の場合には,一般に計算オーダーを大幅に狂わせることになる高次のべきや指数関数や分数などが定式中に現れ得るために,線形計画問題のように簡明な方法は存在しない.少なくとも変数同士のオーダーのばらつきは少ないことを「期待」して,制約式,あるいは変数,あるいは目的関数全体を定数倍する,といった手法にとどまっている.