変数の分割

応用数学とコンピュータサイエンスにおいて、変数分割は一連の制約を緩和する分解方法である。^[1]

詳細

変数が2組の制約に現れる場合、最初の制約と2番目の制約に新しい変数を代入し、2つの変数を新しい「リンク」制約^[2]で結合することが可能であり、 $x$ $x_{1}$ $x_{2}$

x_{1}=x_{2}

この新しいリンク制約は、ラグランジュ乗数を使用して緩和できます。多くのアプリケーションでは、ラグランジュ乗数は、新しい制約におけるとの等価性の価格として解釈できます。 $x_{1}$ $x_{2}$

多くの問題では、分割変数の等式を緩和することでシステムを細分化し、各サブシステムを個別に解くことができます。これにより、計算時間とメモリ使用量が大幅に削減されます。変数分割を緩和した問題を解くと、初期問題のおおよその解が得られます。おおよその解を「ウォームスタート」として使用すると、変数のみを使用して元の問題を反復的に解くことが容易になります。 $x$

これは1985年にJörnsten、Näsberg、Smedsによって初めて導入されました。^[3]同時に、M. GuignardとS. Kimは「ラグランジュ分解」という名前で同じアイデアを導入しました（彼らの論文は1987年に発表されました）。^[4]

参考文献

^ Pipatsrisawat, Knot; Palyan, Akop; Chavira, Mark; Choi, Arthur; Darwiche, Adnan (2008). 「縮小された検索空間での重み付きMax-SAT問題の解決：パフォーマンス分析」。Journal on Satisfiability Boolean Modeling and Computation (JSAT)。4(2008). UCLA: 4 。 2022年4月18日閲覧。
^ ヴァンダーベイ（1991）
^ Kurt O. Jörnsten、Mikael Näsberg、A. Smeds による。 (1985) 「変数分割: いくつかの数学的プログラミングモデルへの新しいラグランジュ緩和アプローチ」LiTH MAT R の第 84 ～ 85 巻: Matematiska Institutionen 出版社 - リンシェーピング大学数学学部、
^ Monique Guignard と Siwhan Kim (1987)「ラグランジュ分解: より強い境界を生み出すモデル」、Authors Mathematical Programming、39(2)、pp. 215-228。

文献

Adlers, Mikael; Björck, Åke (2000). 「スパース最小二乗問題のための行列ストレッチ」.数値線形代数の応用. 7 (2): 51–65. doi :10.1002/(sici)1099-1506(200003)7:2<51::aid-nla187>3.0.co;2-o. ISSN 1099-1506.
Alvarado, Fernando (1997). 「行列拡大法とその応用」BIT Numerical Mathematics . 37 (3): 473–505. CiteSeerX 10.1.1.24.5976 . doi :10.1007/BF02510237. S2CID 120358431.
Grcar, Joseph (1990).線形方程式の行列ストレッチング(技術レポート). Sandia National Laboratories. arXiv : 1203.2377 . Bibcode :2012arXiv1203.2377G. SAND90-8723.
Vanderbei, Robert J. (1991 年 7 月)。「疎な線形システムにおける密な列の分割」。線形代数とその応用。152 : 107–117。doi : 10.1016 /0024-3795(91)90269-3。ISSN 0024-3795。

Jörnsten, Kurt O.; Näsberg, Mikael; Smeds, Per A. (1985). 「変数分割: いくつかの数理計画モデルに対する新しいラグランジュ緩和アプローチ」LiTH MAT R . 84–85. リンショーピング大学、数学部: 1–52.

Guignard, Monique; Kim, Siwhan (1987). 「ラグランジュ分解: より強い境界を生み出すモデル」.数学プログラミング. 39 (2): 215–228. doi :10.1007/BF02592948.

[jsat-1] Pipatsrisawat, Knot; Palyan, Akop; Chavira, Mark; Choi, Arthur; Darwiche, Adnan (2008). 「縮小された検索空間での重み付きMax-SAT問題の解決：パフォーマンス分析」。Journal on Satisfiability Boolean Modeling and Computation (JSAT)。4(2008). UCLA: 4 。 2022年4月18日閲覧。

[Vanderbei-2] ヴァンダーベイ（1991）

[Jornsten-3] Kurt O. Jörnsten、Mikael Näsberg、A. Smeds による。 (1985) 「変数分割: いくつかの数学的プログラミングモデルへの新しいラグランジュ緩和アプローチ」LiTH MAT R の第 84 ～ 85 巻: Matematiska Institutionen 出版社 - リンシェーピング大学数学学部、

[Guignard-4] Monique Guignard と Siwhan Kim (1987)「ラグランジュ分解: より強い境界を生み出すモデル」、Authors Mathematical Programming、39(2)、pp. 215-228。