分数計画法

数理最適化において、分数計画法は線形分数計画法の一般化です。分数計画法における目的関数は、一般に非線形である2つの関数の比です。最適化対象となる比は、多くの場合、システムの何らかの効率性を表します。

意味

集合 上で定義された実数値関数とする。とする。非線形計画法${\displaystyle f,g,h_{j},j=1,\ldots ,m}$ ${\displaystyle \mathbf {S} _{0}\subset \mathbb {R} ^{n}}$ ${\displaystyle \mathbf {S} =\{{\boldsymbol {x}}\in \mathbf {S} _{0}:h_{j}({\boldsymbol {x}})\leq 0,j=1,\ldots ,m\}}$

${\displaystyle {\underset {{\boldsymbol {x}}\in \mathbf {S} }{\text{maximize}}}\quad {\frac {f({\boldsymbol {x}})}{g({\boldsymbol {x}})}},}$

ここで、 は分数計画法と呼ばれます。 ${\displaystyle g({\boldsymbol {x}})>0}$ ${\displaystyle \mathbf {S} }$

凹分数プログラム

fが非負かつ凹、gが正かつ凸、Sが凸集合であるような分数計画は、凹分数計画と呼ばれる。g がアフィン関数である場合、 fは符号に制限される必要はない。線型分数計画は、すべての関数がアフィン関数となる凹分数計画の特殊なケースである。 ${\displaystyle f,g,h_{j},j=1,\ldots ,m}$

プロパティ

関数はS上で半厳密準凹関数である。fとg が微分可能ならば、qは擬凹関数である。線形分数計画問題において、目的関数は擬線形関数である。 ${\displaystyle q({\boldsymbol {x}})=f({\boldsymbol {x}})/g({\boldsymbol {x}})}$

凹型プログラムへの変換

変換により、任意の凹分数計画は、等価なパラメータフリー凹計画に変換できる^[1]${\displaystyle {\boldsymbol {y}}={\frac {\boldsymbol {x}}{g({\boldsymbol {x}})}};t={\frac {1}{g({\boldsymbol {x}})}}}$

${\displaystyle {\begin{aligned}{\underset {{\frac {\boldsymbol {y}}{t}}\in \mathbf {S} _{0}}{\text{maximize}}}\quad &tf\left({\frac {\boldsymbol {y}}{t}}\right)\\{\text{subject to}}\quad &tg\left({\frac {\boldsymbol {y}}{t}}\right)\leq 1,\\&t\geq 0.\end{aligned}}}$

gがアフィンの場合、最初の制約は に変更され、 gが正であるという仮定は削除できます。また、これは に簡約されます。 ${\displaystyle tg({\frac {\boldsymbol {y}}{t}})=1}$ ${\displaystyle g({\boldsymbol {y}})=1}$

二重性

等価な凹プログラムのラグランジアン双対は

${\displaystyle {\begin{aligned}{\underset {\boldsymbol {u}}{\text{minimize}}}\quad &{\underset {{\boldsymbol {x}}\in \mathbf {S} _{0}}{\operatorname {sup} }}{\frac {f({\boldsymbol {x}})-{\boldsymbol {u}}^{T}{\boldsymbol {h}}({\boldsymbol {x}})}{g({\boldsymbol {x}})}}\\{\text{subject to}}\quad &u_{i}\geq 0,\quad i=1,\dots ,m.\end{aligned}}}$

注記

1. シャイブレ、ジークフリート (1974)。 「パラメータフリーの凸型等価およびデュアルプログラム」。オペレーションズリサーチの時代。18 (5): 187–196。土井:10.1007/BF02026600。MR  0351464。S2CID 28885670  。

参考文献

• アヴリエル、モルデカイ、ディワート、ウォルター・E、シャイブル、ジークフリート、ザング、イスラエル (1988).一般化凹面. プレナム・プレス.
• シャイブレ、ジークフリート (1983)。 「分数プログラミング」。オペレーションズリサーチの時代。27 : 39–54 .土井:10.1007/bf01916898。S2CID  28766871。