階層連立1次方程式

本節では階層連立1次方程式 ( HLS ) の定式化を行う。制約としては1次方程式を 用いるが、ここで述べる定式化と性質は 1 次方程式に限定されたものではなく、 より一般的な制約に対しても応用できる。

■■ 1 (HLS).

HLS とは、n 個の変数 x 1, x 2, ..., x n に関する m 個の 1 次元方程式の順序集合である。 第 i 式を a i 1 x 1 + a i 2 x 2 + … + a i n x n = c i とする。 第 i 式の係数ベクトルとは a 2 = ( a i 1 a i 2 … a i n ) であり、 この HLS の系数行列とは、 A = ( a i j ) であり、 拡大係数行列とは ( A c ) である。 ただし、 とする。

本論文では以下、常に ( A c ) を HLS と見なす。直観的には、 第 1 行すなわち最上位の行が HLS の解を決定する上で最も強い影響力があり、 下の行ほど影響力は弱くなる。この性質のために次のように解を定義する。

■■ 2 (解).

( A c ) の解集合とは、   である。ただし、 とは、 、または である。

直観的には、 は 2 つの誤差を表すベクトルを「階層的」に比較し、 ( A c ) の解集合は、 の意味で最小の誤差を生ずる全てのベ クトルの集合である。

制約階層の全てのレベルを順に連結して得られる HLS は、元の制約階層の locally-error-better 解集合の部分集合を生成する。従って、全ての解を必要としない場合、 制約階層を HLS で代用することが可能である。通常、GUI で制約を利用する場合、 1 つの解で十分であり、この性質は、制約階層解消系のために HLS を用いるとい う本研究の方針を裏付ける本質的な根拠となっている。