緩和（近似）

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

例えば、整数計画問題における線形計画緩和法は、整数性制約を取り除き、非整数有理数解を許容します。組合せ最適化における複雑な問題におけるラグランジュ緩和法は、いくつかの制約違反にペナルティを課すことで、より容易な緩和問題を解くことを可能にします。緩和法は、組合せ最適化における分岐限定法を補完または補足します。線形計画法とラグランジュ緩和法は、整数計画における分岐限定法において境界値を求めるために使用されます。^{[ 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}$

いくつかの緩和法

• 線形計画法による緩和
• ラグランジュ緩和
• 半正定値緩和
• 代理緩和と双対性

注記

1. 線形不等式系の実行可能解を求める緩和法は、線形計画法とラグランジュ緩和法で用いられる。 ^{[ 2 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ]}

1. ジェオフリオン（1971）
2. ゴフィン（1980） .
3. マーティ（1983）、453-464頁。
4. ミヌー (1986) .
5. ミヌー（1986）、セクション4.3.7、pp.120–123。
6. シュムエル・アグモン（1954）
7. セオドア・モツキンとアイザック・シェーンベルク（1954）
8. LT グビン、ボリス・T・ポリアク、EV・ライク (1969)

参考文献

• Buttazzo, G. (1989).変分法における半連続性、緩和、および積分表現．Pitman Research. Notes in Math. 207. Harlow: Longmann
• ジェフリオン, AM (1971). 「非線形計画法における双対性：簡略化された応用指向開発」. SIAMレビュー. 13 (1): 1– 37. doi : 10.1137/1013001 . JSTOR  2028848 .
• Goffin, J.-L. (1980). 「線形不等式系を解くための緩和法」.オペレーションズ・リサーチ数学. 5 (3): 388– 414. doi : 10.1287/moor.5.3.388 . JSTOR  3689446. MR  0594854 .
• ミヌー, M. (1986).数理計画法：理論とアルゴリズム. チチェスター: ワイリー・インターサイエンス出版. ジョン・ワイリー・アンド・サンズ. ISBN 978-0-471-90170-9 MR  0868279Steven Vajda著『Programmation mathématique: Théorie et algorithmes』パリ：Dunod、1983年、MR 2571910より翻訳 
• Murty, Katta G. (1983). 「16 線形不等式と線形計画法の反復法（特に16.2 緩和法、および16.4 線形計画法のためのスパース性保存反復SORアルゴリズム）」.線形計画法. ニューヨーク: John Wiley & Sons. ISBN 978-0-471-09725-9 MR  0720547
• ネムハウザー、GL、リンヌーイ・カン、AHG、トッド、MJ編 (1989)。最適化。オペレーションズ・リサーチとマネジメント・サイエンスのハンドブック。第1巻。アムステルダム：ノースホランド出版。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。
• ルービチェク、T. (1997).最適化理論と変分計算における緩和. ベルリン: Walter de Gruyter. ISBN 978-3-11-014542-7。