辞書式最大最小最適化

辞書式最大最小最適化( lexmaxmin、leximin、leximax、または辞書式最大順序最適化とも呼ばれる) は、多目的最適化の一種です。一般に、多目的最適化は、2 つ以上の目的関数を同時に最適化する最適化問題を扱います。lexmaxmin 最適化では、意思決定者が最小の目的値をできるだけ高くしたいと考えていることを前提としています。この条件に従って、2 番目に小さい目的値をできるだけ高くする、などとなります。言い換えると、意思決定者は、目的関数値のleximin 順序に従って、可能なソリューションをランク付けします。

例として、平等主義の社会計画者を考えてみましょう。彼らは、最も貧しい人の効用が可能な限り高くなるような政策を決定したいと考えています。このことを前提として、彼らは 2 番目に貧しい人の効用を最大化したいと考えています。この計画者は、目的関数番号iがエージェント番号iの効用であるlexmaxmin 問題を解決します。

lexmaxmin最適化アルゴリズム（この名前は使用されていない）は、協力ゲームの核小体を計算するために開発されました。 ^{[1] [2]} lexmaxminの初期の応用は、Melvin Dresher ^[3]がゲーム理論の本の中で、ゼロサムゲームで相手のミスを最大限に活用するという文脈で発表しました。Behringer ^[4]は、ゲーム理論だけでなく意思決定理論でも多くの例を挙げています。

lexmaxmin 問題は次のように記述できます。ここで、は最大化する関数、 は決定変数のベクトル、 は実行可能集合、つまり の可能な値の集合です。 $${\displaystyle {\begin{aligned}\operatorname {lex} \max \min &&f_{1}(x),f_{2}(x),\ldots ,f_{n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$${\displaystyle f_{1},\ldots ,f_{n}}$${\displaystyle x}$${\displaystyle X}$${\displaystyle x}$

Lexmaxmin 最適化は、辞書式最適化と密接に関連しています。ただし、辞書式最適化では、関数の順序が固定されており、 が最も重要で、が次に重要、というようになります。対照的に、lexmaxmin では、すべての目的関数が同等に重要です。lexmaxmin を辞書式最適化の特殊なケースとして表すには、x内の最小の目的関数値を で表します。同様に、 x 内の 2 番目に小さい目的関数値を で表す、というようにして、 とします。すると、lexmaxmin 最適化問題は、次の辞書式最大化問題として記述できます。${\displaystyle f_{1}}$${\displaystyle f_{2}}$${\displaystyle f_{[1]}(x):=\min(f_{1}(x),\ldots ,f_{n}(x))=}$${\displaystyle f_{[2]}(x):=}$${\displaystyle f_{[1]}(x)\leq f_{[2]}(x)\leq \cdots \leq f_{[n]}(x)}$$${\displaystyle {\begin{aligned}\operatorname {lex} \max &&f_{[1]}(x),\ldots ,f_{[n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$

一般に、lexmaxmin最適化問題には複数の最適解が存在する可能性があります。と が2つの最適解である場合、それらの順序付けられた値ベクトルは同じである必要があります。つまり、すべての に対して、^{[5] : Thm.2}つまり、最小の値は同じで、2番目に小さい値も同じであり、以下同様に続きます。ただし、並べ替えられていない値ベクトルは異なる場合があります。たとえば、(1,2,3)と(2,1,3)はどちらも同じ問題に対する最適解である可能性があります。 ${\displaystyle x^{1}}$${\displaystyle x^{2}}$${\displaystyle f_{[i]}(x^{1})=f_{[i]}(x^{2})}$${\displaystyle i\in [n]}$

しかし、実行可能領域が凸集合で、目的関数が凹関数である場合、すべての最適解の値ベクトルは同じでなければなりません。なぜなら、2つの異なる最適解がある場合、それらの平均は、目的関数がより高い値を達成する別の実行可能解になり、元の解の最適性と矛盾するからです。^{[5] : Thm.6}

飽和アルゴリズムは、実行可能集合が凸集合で、目的関数が凹関数である場合に機能します。これらのアルゴリズムの変種は多くの論文に登場しています。最も古い登場は、ElkindとPasechnikによるAlexander Kopelowitz ^[1]に帰属します。^[6]他の変種は、次の論文に登場します。^{[7] ：20–27  [8] [9] [5] ：Alg.2  [10] [11] [12] [13] [14] [15]}

アルゴリズムは、飽和していると見なされる (ブロッキングとも呼ばれる)一連の目標を保持します。つまり、それらの値を向上させると、より価値の低い目標に悪影響が出ることになります。その他の目標はフリーと呼ばれます。最初は、すべての目標がフリーです。一般に、アルゴリズムは次のように動作します。

• 一部の目的は無料ですが、
  • (P1) 次の単目的問題を解きます。ここで は目的関数の飽和値です。${\displaystyle z_{k}}$${\displaystyle f_{k}}$$${\displaystyle {\begin{aligned}\max ~~~z\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)=z_{k}{\text{ for all saturated objectives }}k,\\&f_{k}(x)\geq z{\text{ for all free objectives }}k\end{aligned}}}$$
  • 問題が実行不可能または無制限である場合は、停止して解決策がないことを宣言します。
  • それ以外の場合は、最初の問題の最大値とします。${\displaystyle z_{\max}}$
  • 他の目的を 以下に減らさずに以上に値を増やすことができない自由目的を探します。どの lexmaxmin ソリューションでも、そのような目的の値は と正確に一致する必要があります。そのような目的をすべて飽和目的のセットに追加し、それらの飽和値を に設定して、(P1) に戻ります。${\displaystyle z_{\max}}$${\displaystyle z_{\max}}$${\displaystyle z_{\max}}$${\displaystyle z_{\max}}$

各反復で新しい飽和目標をどのように見つけることができるかを説明する必要があります。

方法1：内部最適化装置。^{[1] [6]線形計画法の}内部最適化装置は、制約が可能な限り少なくなる最適解である。言い換えれば、それは最適面の内部における解である。(P1)の内部最適化装置は、楕円体法または内点法を使用して(P1)を解くことによって見つけることができる。

内部最適化装置における厳密な制約のセットは一意です。証明: 矛盾により、異なる厳密な制約のセットを持つ 2 つの内部最適化装置 x1 と x2 があるとします。実行可能セットは凸であるため、平均解 x3 = (x1+x2)/2 も最適化装置です。x1 または x2 のどちらでも厳密でない制約は、x3 でも厳密ではありません。したがって、x3 の厳密な制約の数は x1 および x2 よりも少なく、内部最適化装置の定義と矛盾します。

したがって、内部最適化器の厳しい制約のセットは、飽和する自由目的のセットに対応します。この方法を使用すると、最大n回の反復を使用して、leximin ソリューションを計算できます。

方法2：すべての目的関数を反復する。^[7]次のアルゴリズムを使用すると、少なくとも1つの飽和目的関数を見つけることができます。

• 無料の目標ごとに： ${\displaystyle f_{j}}$
  • (P2) 次の単一目的問題を解いてください。$${\displaystyle {\begin{aligned}\max ~~~f_{j}(x)\\{\text{subject to}}~~~&x\in X,\\&f_{k}(x)\geq z_{k}{\text{ for all saturated objectives }}k,\\&f_{k}(x)\geq z_{\max }{\text{ for all free objectives }}k\end{aligned}}}$$
  • 最適値が に等しい場合、目的関数j は今後飽和状態になります。${\displaystyle z_{\max}}$
  • それ以外の場合、最適値は より大きくなければなりません。目的j は今のところ自由のままです。${\displaystyle z_{\max}}$
• 終了

各ステップで、少なくとも 1 つの自由目的関数が飽和する必要があります。これは、目的関数が飽和しなかった場合、(P2) のすべての最適解の平均は、すべての目的関数の値が- より大きい実行可能な解になるため、(P1) の解の最適性と矛盾するからです。たとえば、値ベクトル (3,1) の解が存在するため目的関数 1 は飽和せず、値ベクトルと (1,3) の解が存在するため目的関数 2 は飽和しないとします。この場合、値ベクトルが少なくとも (2,2) の解が存在しますが、少なくとも 2 である必要があります。 ${\displaystyle z_{\max}}$${\displaystyle z_{\max}=1}$${\displaystyle z_{\max}}$

したがって、最大n回の反復の後、すべての変数が飽和し、レキシミン最適解が見つかります。各反復tで、アルゴリズムは最大n - t +1 個の線形計画を解きます。したがって、アルゴリズムの実行時間は、最大でLP ソルバーの実行時間の数倍になります。 ${\displaystyle (n+2)(n+1)/2\in O(n^{2})}$

場合によっては、飽和アルゴリズムの実行時間を改善できる。飽和した目的関数をすべて見つける代わりに、飽和した目的関数を1つ見つけたら内部ループから抜け出すことができる。アルゴリズムは最大でn回の反復後に停止し、解く必要のある線形計画法(P2)の数を減らすことができる。^{[5] : Alg.3}

さらに、飽和した目的関数を見つけるためにすべての目的関数をループする代わりに、このアルゴリズムは(P1) の双対問題を使用して飽和した目的関数を見つけることができる。場合によっては、双対変数は (P1) を解く副産物として与えられる。たとえば、目的関数と制約が線形で、ソルバーが単体アルゴリズムである場合などである。この場合、(P2) はまったく必要なく、アルゴリズムの実行時間は(P1) のソルバーの実行時間の最大 2 倍である。^{[5] : Alg.4}${\displaystyle n}$

これらのバリエーションはすべて凸問題にのみ機能します。非凸問題の場合、飽和目的関数が存在しない可能性があるため、アルゴリズムは停止しない可能性があります。

Ordered Outcomes アルゴリズムは任意のドメイン (必ずしも凸ではない) で動作します。これは Ogryczak と Śliwiński ^{[16]によって開発され、Ogryczak、Pioro、Tomaszewski [5]}によって通信ネットワークのコンテキストで、またOgryczak ^{[17 ] によって}ロケーション問題のコンテキストで提示されました。このアルゴリズムは、lexmaxmin 最適化をより簡単な問題である辞書式最適化に簡約します。辞書式最適化は、最大でn 個の線形計画を解く単純な順次アルゴリズムで実行できます。簡約は、lexmaxmin の次の表現から始まります。$${\displaystyle {\begin{aligned}(L1)\\\operatorname {lex} \max &&f_{[1]}(x),\ldots ,f_{[n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$

この問題は、 （のt番目に小さい値）がxの単純な関数ではないため、そのままでは解くことができません。問題（L1）は、 のt個の最小値の合計が次の問題と同等です。${\displaystyle f_{[t]}(x)}$${\displaystyle \mathbf {f} (x)}$${\displaystyle f_{[1..t]}(x):=\sum _{i=1}^{t}f_{[i]}(x)=}$${\displaystyle \mathbf {f} (x)}$$${\displaystyle {\begin{aligned}(L2)\\\operatorname {lex} \max &&f_{[1..1]}(x),f_{[1..2]}(x),\ldots ,f_{[1..n]}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$

この問題は辞書式最適化を使用して反復的に解くことができますが、各反復tにおける制約の数はC( n , t )、つまりサイズtのサブセットの数です。これはnとともに指数関数的に増加します。この問題を、制約の数がnの多項式である別の問題に縮小することは可能です。

すべてのtについて、合計は、 n +1 個の補助変数（無制限の変数、および1,..., nのすべてのjに対する非負の変数）とn 個の追加制約を伴う次の問題に対する最適値として計算できます。 ^{[5] ： Thm.8  [18]}証明。最適解における補助変数の値を計算してみましょう。 ${\displaystyle f_{[1..t]}(x)}$${\displaystyle r_{t}}$${\displaystyle d_{t,j}}$$${\displaystyle {\begin{aligned}(L3)\\\max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})\\{\text{subject to}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ for all }}j\in [n],\\&d_{t,j}\geq 0{\text{ for all }}j\in [n].\end{aligned}}}$$

• すべてのjについて、 は 少なくとも 0 と の両方と同じ大きさでなければなりません。また、この条件に従って、 は最小化される必要があります。これは、 が目的関数にマイナス符号付きで現れるためです。したがって、 です。したがって、この目的は次のように記述できます 。${\displaystyle d_{t,j}}$${\displaystyle r_{t}-f_{j}(x)}$${\displaystyle d_{t,j}=\max(0,r_{t}-f_{j}(x))}$${\displaystyle t\cdot r_{t}-\sum _{j=1}^{n}\max(0,r_{t}-f_{j}(x))}$
• 0 から n までの任意のkについて、 が最小のk 個の目的値 (つまり)より大きい場合、右側の和にはちょうどk 個の正の要素が含まれます。その場合、目的関数は と記述できます 。 はk < tのときはとともに増加し、k > tのときはとともに減少することに注意してください。したがって、 k = tのとき、つまり が最小のt 個の目的値より大きいとき、最大値が達成されます。その場合、目的関数は主張どおり と正確に等しくなります。${\displaystyle r_{t}}$${\displaystyle r_{t}\geq f_{[k]}(x)}$${\displaystyle \sum _{j=1}^{k}(r_{t}-f_{[j]}(x))=k\cdot r_{t}-f_{[1..k]}(x)}$${\displaystyle (t-k)\cdot r_{t}+f_{[1..k]}(x)}$${\displaystyle (t-k)\cdot r_{t}}$${\displaystyle r_{t}}$${\displaystyle r_{t}}$${\displaystyle r_{t}}$${\displaystyle f_{[1..t]}(x)}$

したがって、問題(L2)は次の辞書式最大化問題と同等である: ^{[5] : (32)}$${\displaystyle {\begin{aligned}(L4)\\\operatorname {lex} \max(t\cdot r_{t}-\sum _{j=1}^{n}d_{t,j})_{t=1}^{n}\\{\text{subject to}}~~~&x\in X,\\&r_{t}-f_{j}(x)\leq d_{t,j}{\text{ for all }}j\in [n],\\&d_{t,j}\geq 0{\text{ for all }}j\in [n].\end{aligned}}}$$

この問題 (L4) には追加の変数と追加の制約があります。これは、 n線形計画法を使用した順次アルゴリズムや、辞書式単体アルゴリズム (目的と制約が線形の場合) など、 辞書式最大化を解決するためのすべてのアルゴリズムで解決できます。${\displaystyle n^{2}+n}$${\displaystyle n^{2}}$

順序付き結果アルゴリズムの利点の1つは、単一問題ソルバーが不正確で近似解しか返さない場合でも使用できることです。具体的には、単一問題ソルバーが乗法係数α∈(0,1]と加法係数ϵ≥0で最適な単一問題ソリューションを近似する場合、アルゴリズムは乗法係数α2 /(1−α+α2)と加法係数ϵ/(1−α+α2)でレキシミン最適ソリューションを近似するソリューション^を返し^ます。^[ 19 ^]

順序値アルゴリズムは、目的関数の可能な値のセットが有限である任意のドメインで機能します。これは、Ogryczak と Śliwiński によって開発されました。^{[16] が、}となる関数 によって返される可能性のあるすべての値の集合であると します。解xと{1,.., r }内の整数kが与えられた場合、をベクトル 内の 値v _rの出現回数として定義します。すると、lexmaxmin 問題は、次の辞書式最小化問題として記述できます。最小値を達成する関数をできるだけ少なくしたいので、これを条件として、次に小さい値を達成する関数をできるだけ少なくします。などとなります。Ogryczak と Śliwiński ^{[16] は}、この非線形プログラムを補助変数を含む線形プログラムに変換する方法を示しています。計算実験では、順序値アルゴリズムは、飽和アルゴリズムや順序付き結果アルゴリズムよりもはるかに高速に実行されます。 ${\displaystyle V=\{v_{1},\ldots ,v_{r}\}}$${\displaystyle f_{1},\ldots ,f_{n}}$${\displaystyle v_{1}<\cdots <v_{r}}$${\displaystyle h_{k}(x)}$${\displaystyle f_{1}(x),\ldots ,f_{n}(x)}$$${\displaystyle {\begin{aligned}(H1)\\\operatorname {lex} \min &&h_{1}(x),\ldots ,h_{r-1}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$

Behringer ^[4]は、目的関数が準凸関数であり、実行可能集合Xが凸集合である場合のlexmaxmin最適化^{[説明が必要]}のための逐次アルゴリズムを提示した。

Yager ^[20]は、順序付き加重平均集約演算子を使用して、leximinの順序を解析的に表現する方法を提示しました。彼は、すべての目的値が0から1までの実数であり、任意の2つの値の間の最小の差が定数d < 1であると仮定しています（したがって、差がdより小さい値は等しいと見なされます）。の重みは、およそ に設定されます。これにより、加重合計を最大化することがlexmaxminと同等であることが保証されます。 ${\displaystyle w_{t}}$${\displaystyle f_{[t]}(x)}$${\displaystyle d^{t}}$${\displaystyle \sum _{t}w_{t}f_{[t]}(x)}$

ベクトルの集合が離散的であり、領域が十分に小さい場合、制約充足問題用のソルバーを使用して、制約に従ってレキシミン順序を表す関数の 1 つを使用してそれを最大化することが可能になります。

しかし、ドメインが大きい場合、この関数が取り得る値の数が非常に多いため、上記のアプローチは実行不可能になります。ここで、mはドメイン内の異なる値の数、nは変数の数です。^[21]${\displaystyle {m+n-1 \choose n}}$

ブーヴェレとルメートルは、離散制約充足問題に対するレキシミン最適解を見つけるための5つの異なるアルゴリズムを提示している。^[21]

1. LEXIMIN 制約に基づく分岐限定法。LEXIMIN 制約は、 yがxよりも leximin 大きいという2 つのベクトルxとyに対する制約です。
2. 飽和サブセットでの分岐 - 最小値に固定する必要がある変数のサブセットを見つけ、他の変数の最大最小値を見つけます。
3. SORT制約を使用する - 2つのベクトルxとyに対する制約で、 yには昇順でソートされたxと同じ要素が含まれているという制約。この制約はいくつかのアルゴリズムで効率的に計算できます。^{[22] [23]}
4. ATLEAST 制約を使用します。
5. 最大最小変換を使用します。

彼らの実験では、最もパフォーマンスの良かったアプローチは 4 (ATLEAST) で、次いで 3 (SORT)、1 (LEXIMIN) の順でした。

Dall'aglio ^[24]は、レキシミン最適資源配分を計算するアルゴリズムを提示している。