逆凸2次計画問題に対するFJ点列挙法を用いた大域的最適化手法

摘要

目的関数が線形関数で与えられ，複数の凸2次制約と一つの逆凸2次制約をもつ数理計画問題は逆凸2次計画問題と呼ばれ，配置禁止領域をもつ配置問題などがこのような問題で近似できることが知られている。しかしならが，制約集合が連結であるとは限らないため，従来の非線形計画法ではこの問題に対して，大域的最適値に近い目的関数値をもつ近似解が求まることを保証できない。本研究では，FJ点列挙法を導入し，ラグランジュ乗数に対する分枝限定法を提案する。FJ点を列挙することで，提案手法によって生成される暫定解列の任意の集積点は対象問題の大域的最適解であることが証明される。