辞書最適化

レキシミン最適化問題${\displaystyle n}$目標は、一連の手順を使用して解決できます。${\displaystyle n}$単一目的最適化問題は以下のとおりです。^{[ 1 ] [ 3 ]：アルゴリズム1}

• のために${\displaystyle t=1,\dots ,n}$する
  • 以下の単一目的問題を解いてください。$${\displaystyle {\begin{aligned}\max ~~~f_{t}(x)\\{\text{制約条件}}~~~&x\in X,\\&f_{k}(x)\geq z_{k}{\text{すべての}}k{\text{in}}1,\ldots ,t-1について}}\end{aligned}}}$$
  • 問題が実行不可能または無制限である場合は、そこで作業を中止し、解決策がないことを宣言する。
  • それ以外の場合は、最適解の値を${\displaystyle z_{t}}$そして続ける。
• 終了

したがって、最初の反復では、最も重要な目的関数の最大実行可能値を求めます。${\displaystyle f_{1}(x)}$、そしてこの最大値を$\displaystyle z_{1}}$2回目の反復では、2番目に重要な目的関数の最大実行可能値を求めます。${\displaystyle f_{2}(x)}$さらに、最も重要な目的はその最大値を維持しなければならないという制約がある。$\displaystyle z_{1}}$; 等々。

逐次アルゴリズムは汎用的であり、単一目的関数のソルバーが存在する場合にはいつでも適用できる。

線形辞書式最適化^{[ 2 ]}は、目的関数が線形であり、実行可能集合が線形不等式で記述される辞書式最適化の特殊なケースです。これは次のように記述できます。$${\displaystyle {\begin{aligned}\operatorname {lex} \max &&c_{1}\cdot x,c_{2}\cdot x,\ldots ,c_{n}\cdot x\\{\text{subject to}}&&A\cdot x\leq b,x\geq 0\end{aligned}}}$$どこ${\displaystyle c_{1},\ldots ,c_{n}}$は、最大化すべき線形目的関数を表すベクトルであり、重要度の高いものから低いものへと順に並べられています。${\displaystyle x}$は決定変数のベクトルであり、実行可能集合は行列によって決定される。${\displaystyle A}$そしてベクトル${\displaystyle b}$。

Isermann ^{[ 2 ]}は、線形計画双対性の理論を辞書式線形計画に拡張し、辞書式シンプレックスアルゴリズムを開発した。逐次アルゴリズムとは対照的に、このシンプレックスアルゴリズムはすべての目的関数を同時に考慮する。

SheraliとSoyster ^{[ 1 ]}は、任意の線形辞書式最適化問題に対して、重みの集合が存在することを証明している。${\displaystyle w_{1}>w_{2}>\cdots >w_{n}}$辞書式最適解の集合が、以下の単目的問題の解の集合と同一となるようにする。$${\displaystyle {\begin{aligned}\max &&w_{1}f_{1}(x)+\cdots +w_{n}f_{n}(x)\\{\text{subject to}}&&x\in X\end{aligned}}}$$重みを計算する一つの方法はYagerによって示されている。^{[ 4 ]}彼は、すべての目的値が0から1の間の実数であり、可能な2つの値間の最小差が何らかの定数であると仮定している。${\displaystyle d<1}$（したがって、差が小さい値${\displaystyle d}$（等しいとみなされる）次に、重量${\displaystyle w_{t}}$の${\displaystyle f_{t}(x)}$約${\displaystyle d^{t}}$これは、加重和を最大化することを保証します。${\displaystyle \sum _{t}w_{t}f_{t}(x)}$これは辞書式最大化と同等である。

Cococcioni、Pappalardo、Sergeyev ^{[ 5 ]}は、無限小を用いた数値計算が可能なコンピュータがあれば、無限小の重み（具体的には：${\displaystyle w_{1}=1}$;${\displaystyle w_{2}}$極めて小さい。${\displaystyle w_{3}}$（は無限小の二乗など）を用いて、線形辞書式最適化を無限小を用いた単目的線形計画問題に還元します。彼らは、シンプレックス法を無限小に適用した方法を提示し、いくつかの実行例を示します。