二段階最適化

二段階最適化は、ある問題が別の問題に埋め込まれている（入れ子になっている）特殊な最適化の一種です。外側の最適化タスクは一般に上位レベル最適化タスクと呼ばれ、内側の最適化タスクは一般に下位レベル最適化タスクと呼ばれます。これらの問題には、上位レベル変数と下位レベル変数と呼ばれる 2 種類の変数が関係します。^{[1] [2] [3]}

二段階最適化問題の一般的な定式化は次のように記述できます。

${\displaystyle \min \limits _{x\in X,y\in Y}\;\;F(x,y)}$

以下を条件とする:

${\displaystyle G_{i}(x,y)\leq 0}$、 のために${\displaystyle i\in \{1,2,\ldots ,I\}}$

${\displaystyle y\in \arg \min \limits _{z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}}$

どこ

${\displaystyle F,f:R^{n_{x}}\times R^{n_{y}}\to R}$

${\displaystyle G_{i},g_{j}:R^{n_{x}}\times R^{n_{y}}\to R}$

${\displaystyle X\subseteq R^{n_{x}}}$

${\displaystyle Y\subseteq R^{n_{y}}.}$

上記の定式化では、 は上位レベルの目的関数を表し、は下位レベルの目的関数を表します。同様に、は上位レベルの決定ベクトルを表し、 は下位レベルの決定ベクトルを表します。および は、それぞれ上位レベルと下位レベルの不等式制約関数を表します。ある目的関数を最大化する場合、その負の値を最小化することと同義です。 上記の定式化は、不等式制約で簡単に書き直すことができるため、等式制約を表すこともできます。たとえば、は と翻訳できます。ただし、通常は等式制約を別々に扱い、専用の方法でより効率的に処理する価値があります。上記の表現では、簡潔にするために等式制約は省略されています。 ${\displaystyle F}$${\displaystyle f}$${\displaystyle x}$${\displaystyle y}$${\displaystyle G_{i}}$${\displaystyle g_{j}}$${\displaystyle h(x)=0}$${\displaystyle \{h(x)\leq 0,\ -h(x)\leq 0\}}$

二段階最適化は、1934 年にこの階層的問題を説明した「市場の構造と均衡 (Marktform und Gleichgewicht)」を出版したドイツの経済学者ハインリッヒ・フォン・シュタッケルベルクによって、ゲーム理論の分野で初めて実現されました。彼の著書で説明されている戦略ゲームは、リーダーとフォロワーで構成されるシュタッケルベルク ゲームとして知られるようになりました。リーダーは一般にシュタッケルベルク リーダーと呼ばれ、フォロワーは一般にシュタッケルベルク フォロワーと呼ばれます。シュタッケルベルク ゲームでは、ゲームのプレイヤーは互いに競争し、リーダーが最初の動きを行い、フォロワーはリーダーの行動に最適に反応します。この種類の階層的ゲームは非対称な性質を持ち、リーダーとフォロワーを交換することはできません。リーダーは、フォロワーが最適な方法で反応する前にリーダーの行動を観察していることを事前に知っています。したがって、リーダーが目的を最適化したい場合は、フォロワーの最適な反応を予測する必要があります。この設定では、リーダーの最適化問題には、フォロワーの最適化問題に対応するネストされた最適化タスクが含まれます。 スタックベルグ ゲームでは、上位レベルの最適化問題は一般にリーダーの問題と呼ばれ、下位レベルの最適化問題は一般にフォロワーの問題と呼ばれます。

リーダーの特定の選択に対してフォロワーが複数の最適な応答を持つ場合、2 つのオプションが考えられます。リーダーの目的関数に関してフォロワーの最良または最悪のソリューションが想定されます。つまり、フォロワーは協力的または積極的に行動すると想定されます。結果として生じる 2 レベル問題は、それぞれ楽観的 2 レベル計画問題 または悲観的 2 レベル計画問題と呼ばれます。

二階層最適化問題は、多くの現実世界の問題でよく見られます。これには、交通、経済、意思決定科学、ビジネス、工学、環境経済学などの分野における問題が含まれます。文献で研究されている実用的な二階層問題のいくつかについて簡単に説明します。^[4]

交通の分野では、2 レベル最適化は料金設定の問題でよく使用されます。政府が運営する高速道路ネットワークを考えてみましょう。政府は高速道路の最適な料金設定を選択して収入を最大化したいと考えています。しかし、政府は高速道路利用者の問題を考慮に入れることによってのみ収入を最大化できます。任意の税制について、高速道路利用者は独自の最適化問題を解決します。つまり、高速道路を利用するか別のルートを利用するかを決定することで移動コストを最小化します。このような状況では、政府の問題は 2 レベル最適化問題として定式化する必要があります。上位レベルは政府の目的と制約で構成され、下位レベルは特定の税制に対する高速道路利用者の目的と制約で構成されます。高速道路がどの程度使用されるかを決定する下位レベルの問題を解決することによってのみ、政府は特定の税制によって生み出される収入を特定できることは注目に値します。

構造最適化問題は、2 つのレベルの最適化タスクで構成され、一般に平衡制約付き数理計画問題 ( MPEC ) と呼ばれます。このような問題の上位レベルの目的には、変位、応力、接触力の制限を条件としたコスト最小化または重量最小化が含まれます。上位レベルの決定変数は通常、構造の形状、材料の選択、材料の量などです。ただし、任意の上位レベル変数セットについて、状態変数 (変位、応力、接触力) は、平衡満足制約として現れるポテンシャル エネルギー最小化問題、または上位レベル問題に対する下位レベルの最小化タスクを解くことによってのみ算出できます。

二段階最適化は、戦略的な攻撃および防御力構造の設計、戦略的な爆撃機の戦力構造、および戦術航空機の任務への割り当てなど、防衛において多くの用途があります。この場合、攻撃側はリーダーとみなされ、防御側はフォロワーとみなされます。リーダーが敵に与えるダメージを最大化したい場合、リーダーがフォロワーの反応を考慮に入れた場合にのみ、それが達成されます。合理的なフォロワーは、常にリーダーの攻撃に対して最適に反応します。したがって、リーダーの問題は上位レベルの最適化タスクとして現れ、リーダーの行動に対するフォロワーの最適な応答は、下位レベルの最適化タスクを解決することによって決定されます。

二段階最適化は、実際の状況で企業が労働力と人事に関する意思決定を改善するための意思決定支援ツールとして役立ちます。最初のレベルは、収益性を最大化するという企業の目標を反映しています。2 番目のレベルは、希望する給与と望ましい勤務計画のギャップを最小化するという従業員の目標を反映しています。二段階モデル​​は、混合整数定式化に基づく正確なソリューションを提供し、企業の戦略に応じて変化する従業員の行動に基づく計算分析を提示し、問題のパラメータが意思決定ポリシーにどのように影響するかを示します。^[5]

2 レベル最適化問題は解決が困難です。解決方法の 1 つは、2 レベル最適化問題を、堅牢な解決アルゴリズムが利用できる最適化問題に再定式化することです。拡張数理計画法 (EMP)は、2 レベル最適化問題にいくつかのキーワードを提供する数学プログラミング言語の拡張機能です。これらの注釈により、成熟したソルバー テクノロジが存在する均衡制約付き数学プログラム(MPEC)への自動再定式化が容易になります。EMPはGAMS内で利用できます。

特定の二レベル計画、特に凸下位レベルを持ち、正則性条件（例えば、スレーターの条件）を満たすものは、下位レベルの問題をそのカルシュ・キューン・タッカー条件で置き換えることによって、単一レベルに再定式化できます。これにより、相補性制約、つまり MPEC を持つ単一レベルの数学計画が生成されます。下位レベルの問題が凸でない場合、このアプローチでは、二レベル最適化問題の実行可能セットが下位レベルの局所最適解と定常点によって拡大されます。つまり、得られる単一レベルの問題は、元の二レベル問題の緩和です。

で示す

${\displaystyle \phi (x)=\min \limits _{z\in Y}\{f(x,z):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}}$

いわゆる最適値関数では、2レベル問題の可能な単一レベルの再定式化は

${\displaystyle \min \limits _{x\in X,y\in Y}\;\;F(x,y)}$

以下を条件とする:

${\displaystyle G_{i}(x,y)\leq 0}$、 のために${\displaystyle i\in \{1,2,\ldots ,I\}}$

${\displaystyle g_{j}(x,y)\leq 0,j\in \{1,2,\ldots ,J\}}$

${\displaystyle f(x,y)\leq \phi (x).}$

これは、下位レベルの問題におけるすべての制約関数と目的関数が滑らかであっても、最適値関数は一般に微分可能ではないため、非滑らかな最適化問題である。^[6]

複雑な二階層問題の場合、非線形性、離散性、非微分性、非凸性などの問題により、古典的な方法がうまく機能しないことがあります。このような状況では、ヒューリスティックな方法が使用されることがあります。その中でも、進化的方法は、計算量が多くなりますが、正確な方法が遭遇するこれらの問題の一部を相殺する代替ツールとなることがよくあります。ただし、生成されるソリューションの最適性は保証されません。^[7]

2 レベル最適化問題は、1 つまたは両方のレベルで複数の目的を持つ多目的 2 レベル最適化問題に一般化できます。一般的な多目的 2 レベル最適化問題は、次のように定式化できます。

${\displaystyle \min \limits _{x\in X,y\in Y}\;\;F(x,y)=(F_{1}(x,y),F_{2}(x,y),\ldots ,F_{p}(x,y))}$ シュタッケルベルクゲームにおけるリーダー問題

以下を条件とする:

${\displaystyle G_{i}(x,y)\leq 0}$、 のために;${\displaystyle i\in \{1,2,\ldots ,I\}}$

${\displaystyle y\in \arg \min \limits _{z\in Y}\{f(x,z)=(f_{1}(x,z),f_{2}(x,z),\ldots ,f_{q}(x,z)):g_{j}(x,z)\leq 0,j\in \{1,2,\ldots ,J\}\}}$ シュタッケルベルクゲームにおけるフォロワー問題

どこ

${\displaystyle F:R^{n_{x}}\times R^{n_{y}}\to R^{p}}$

${\displaystyle f:R^{n_{x}}\times R^{n_{y}}\to R^{q}}$

${\displaystyle G_{i},g_{j}:R^{n_{x}}\times R^{n_{y}}\to R}$

${\displaystyle X\subseteq R^{n_{x}}}$

${\displaystyle Y\subseteq R^{n_{y}}.}$

上記の定式化では、 は目的を持つ上位レベルの目的ベクトルを表し、は目的を持つ下位レベルの目的ベクトルを表します。同様に、は上位レベルの決定ベクトルを表し、 は下位レベルの決定ベクトルを表します。および はそれぞれ上位レベルと下位レベルの不等式制約関数を表します。 等式制約は 2 レベル プログラムにも存在する可能性がありますが、簡潔にするために省略されています。 ${\displaystyle F}$${\displaystyle p}$${\displaystyle f}$${\displaystyle q}$${\displaystyle x}$${\displaystyle y}$${\displaystyle G_{i}}$${\displaystyle g_{j}}$

• 数理計画用語集