指数関数が含まれる場合の大域的最適化
関係する非線形関数が次の形式のみである場合、MINLP問題のグローバル最適値を決定する方法があるのだろうか。 $Z = Y e^{- \alpha X}$、 どこ $Y \ge 0$ そして $X \ge 0$。
そのようなアプローチを説明している論文はありますか?これらの機能には、悪用される可能性のある特性がありますか?
対数を使用して、関数を次のように書き直すことができます。 $\log(Z) = \log(Y) - \alpha X$、しかし私は何も勝っていないと思います。
回答
これは非凸の大域的最適化問題です。これを解決するための最先端の方法は、因数分解可能な緩和を使用することです。
ここでの重要な洞察は $e^{-\alpha X}$ 凸面です( $\alpha$ は正です)。
方法論は次のようになります。
- 新しい補助変数を導入する $w=e^{-\alpha X}$
- あなたは今持っています $Z=Yw$、および $w=e^{-\alpha X}$
- 両方の制約が非凸であるため、それぞれを2つの不等式に分割します。
$Z\leq Yw, -Z\leq -Yw$
$ w\leq e^{-\alpha X}, -w\leq -e^{-\alpha X}$
不等式の最初のセットは、マコーミック緩和を使用して凸状にすることができます。
不等式の2番目のセットは、それぞれ凸面と凹面です。凸不等式は外部近似を使用して緩和でき、凹不等式は割線を使用して緩和できます。
次に、緩和された問題を分枝限定アルゴリズムにプラグインすると、二次収束します。
この方法論は、の兆候とは無関係であることに注意してください $Z,Y,X$。
または、これをグローバルソルバーにプラグインして、これらすべてを自動的に実行することもできます。Couenneはオープンソースの選択肢であり、学者/学生の場合は、SCIPまたは独自のOcteractEngineを無料で使用することもできます。
連続緩和が凸であると仮定すると、指数円錐で円錐最適化を使用できる可能性があります。Mosekモデリング料理は、詳細があります。
当然のことながら、Mosekはそのような問題の混合整数バージョンを解決できます。
JPVielmaとJHuchetteによる次の記事(ORで発表予定)で、質問に対する部分的な回答を見つけることができます。 https://arxiv.org/abs/1708.00050
その論文では、著者は、複数の超平面の論理和を介して、目的の1つまたは2つの変数の非線形関数を近似する問題を検討しています。次に、結果のMIPを汎用の混合整数ソルバーに渡すことができます。
その記事には、他の情報源への引用も含まれています。