指数関数が含まれる場合の大域的最適化

Aug 19 2020

関係する非線形関数が次の形式のみである場合、MINLP問題のグローバル最適値を決定する方法があるのだろうか。 $Z = Y e^{- \alpha X}$、 どこ $Y \ge 0$ そして $X \ge 0$

そのようなアプローチを説明している論文はありますか?これらの機能には、悪用される可能性のある特性がありますか?

対数を使用して、関数を次のように書き直すことができます。 $\log(Z) = \log(Y) - \alpha X$、しかし私は何も勝っていないと思います。

回答

4 NikosKazazakis Aug 20 2020 at 19:43

これは非凸の大域的最適化問題です。これを解決するための最先端の方法は、因数分解可能な緩和を使用することです。

ここでの重要な洞察は $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を無料で使用することもできます。

4 ErlingMOSEK Aug 20 2020 at 12:28

連続緩和が凸であると仮定すると、指数円錐で円錐最適化を使用できる可能性があります。Mosekモデリング料理は、詳細があります。

当然のことながら、Mosekはそのような問題の混合整数バージョンを解決できます。

2 ClaudioContardo Aug 21 2020 at 03:32

JPVielmaとJHuchetteによる次の記事(ORで発表予定)で、質問に対する部分的な回答を見つけることができます。 https://arxiv.org/abs/1708.00050

その論文では、著者は、複数の超平面の論理和を介して、目的の1つまたは2つの変数の非線形関数を近似する問題を検討しています。次に、結果のMIPを汎用の混合整数ソルバーに渡すことができます。

その記事には、他の情報源への引用も含まれています。