緩和（近似）

数学的最適化および関連分野において、緩和はモデリング戦略です。緩和とは、解決が容易な近くの問題で難しい問題を近似することです。緩和された問題の解は、元の問題に関する情報を提供します。

たとえば、整数計画問題に対する線形計画緩和は、整数制約を取り除き、非整数有理数解法を可能にします。組み合わせ最適化における複雑な問題に対するラグランジュ緩和は、いくつかの制約違反にペナルティを課し、より簡単な緩和問題を解けるようにします。緩和技法は、組み合わせ最適化の分岐限定アルゴリズムを補完または補足します。線形計画法とラグランジュ緩和は、整数計画の分岐限定アルゴリズムで境界を取得するために使用されます。^[1]

緩和のモデリング戦略は、逐次過剰緩和（SOR）などの緩和の反復法と混同しないでください。緩和の反復法は、微分方程式、線形最小二乗法、および線形計画法の問題を解くために使用されます。^{[2] [3] [4]}ただし、緩和の反復法はラグランジュ緩和を解くために使用されています。^[a]

最小化問題 の緩和

${\displaystyle z=\min\{c(x):x\in X\subseteq \mathbf {R} ^{n}\}}$

は、次の形式の別の最小化問題である。

${\displaystyle z_{R}=\min\{c_{R}(x):x\in X_{R}\subseteq \mathbf {R} ^{n}\}}$

これら2つの特性により

1. ${\displaystyle X_{R}\supseteq X}$
2. ${\displaystyle c_{R}(x)\leq c(x)}$すべてに対して。${\displaystyle x\in X}$

最初の特性は、元の問題の実行可能領域が緩和された問題の実行可能領域のサブセットであることを示します。2番目の特性は、元の問題の目的関数が緩和された問題の目的関数以上であることを示します。^[1]

が元の問題の最適解である場合、 であり、 です。したがって、は の上限を提供します。 ${\displaystyle x^{*}}$${\displaystyle x^{*}\in X\subseteq X_{R}}$${\displaystyle z=c(x^{*})\geq c_{R}(x^{*})\geq z_{R}}$${\displaystyle x^{*}\in X_{R}}$${\displaystyle z_{R}}$

前述の仮定に加えて、、次のことが成り立ちます。緩和された問題の最適解が元の問題に対して実行可能であれば、その最適解は元の問題に対して最適です。^[1]${\displaystyle c_{R}(x)=c(x)}$${\displaystyle \forall x\in X}$

• 線形計画法の緩和
• ラグランジアン緩和
• 半正定値緩和
• 代理緩和と二重性

• Buttazzo, G. (1989)。変分法における半連続性、緩和および積分表現。Pitman Res. 数学ノート 207。Harlow: Longmann。
• Geoffrion, AM (1971). 「非線形計画法における双対性: 簡略化されたアプリケーション指向の開発」SIAM Review . 13 (1): 1–37. JSTOR  2028848.
• Goffin, J.-L. (1980). 「線形不等式システムを解くための緩和法」.オペレーションズリサーチの数学. 5 (3): 388–414. doi :10.1287/moor.5.3.388. JSTOR  3689446. MR  0594854.
• Minoux, M. (1986).数理計画法: 理論とアルゴリズム. チチェスター: Wiley-Interscience 出版. John Wiley & Sons. ISBN 978-0-471-90170-9. MR  0868279。『Programmation mathématique: Théorie et programminges』から Steven Vajda によって翻訳されました。パリ：デュノー。 1983年。MR  2571910 。
• Murty, Katta G. (1983)。「16 線形不等式と線形計画法の反復法 (特に 16.2 緩和法、および 16.4 線形計画法のスパース性保存反復 SOR アルゴリズム)」。線形計画法。ニューヨーク: John Wiley & Sons。ISBN 978-0-471-09725-9. MR  0720547。
• Nemhauser, GL ; Rinnooy Kan, AHG; Todd, MJ 編 (1989)。最適化。オペレーションズ リサーチとマネジメント サイエンスのハンドブック。第 1 巻。アムステルダム: North-Holland Publishing Co. ISBN 978-0-444-87284-5. MR  1105099。
  • WR Pulleyblank、「多面体組合せ論」（pp. 371–446）
  • George L. Nemhauser と Laurence A. Wolsey、「整数計画法」(pp. 447–527)
  • クロード・ルマレシャル、「微分不可能な最適化」（pp.529–572）
• ラルディン、ロナルド L. (1998)。オペレーションズリサーチにおける最適化。プレンティスホール。ISBN 978-0-02-398415-0。
• Roubíček, T. (1997).最適化理論と変分計算における緩和. ベルリン: Walter de Gruyter. ISBN 978-3-11-014542-7。