Дробное программирование - Fractional programming - Wikipedia

В математическая оптимизация, дробное программирование является обобщением дробно-линейное программирование. В целевая функция в дробной программе - это соотношение двух функций, которые, в общем, являются нелинейными. Оптимизируемый коэффициент часто описывает некоторую эффективность системы.

Определение

Позволять ${\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} }$, называется дробной программой.

Вогнутые дробные программы

Дробная программа, в которой ж неотрицательный и вогнутый, грамм положительный и выпуклый, а S это выпуклый набор называется вогнутая дробная программа. Если грамм аффинно, ж не должно быть ограничено знаком. Дробно-линейная программа - это частный случай дробно-вогнутой программы, в которой все функции ${\displaystyle f,g,h_{j},j=1,\ldots ,m}$ аффинны.

Характеристики

Функция ${\displaystyle q({\boldsymbol {x}})=f({\boldsymbol {x}})/g({\boldsymbol {x}})}$ полустрого квазивогнутый на S. Если ж и грамм дифференцируемы, то q является псевдовогнутая. В дробно-линейной программе целевая функция псевдолинейный.

Преобразование в вогнутую программу

Преобразованием ${\displaystyle {\boldsymbol {y}}={\frac {\boldsymbol {x}}{g({\boldsymbol {x}})}};t={\frac {1}{g({\boldsymbol {x}})}}}$, любая вогнутая дробная программа может быть преобразована в эквивалентную безпараметрическую вогнутая программа ^[1]

${\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}}}$

Если грамм аффинно, первое ограничение заменяется на ${\displaystyle tg({\frac {\boldsymbol {y}}{t}})=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). "Выпуклые эквивалентные и двойные программы без параметров". Zeitschrift für Operations Research. 18 (5): 187–196. Дои:10.1007 / BF02026600. МИСТЕР  0351464.

Рекомендации

• Авриэль, Мардохей; Diewert, Walter E .; Шейбл, Зигфрид; Занг, Израиль (1988). Обобщенная вогнутость. Пленум Пресс.
• Шейбл, Зигфрид (1983). «Дробное программирование». Zeitschrift für Operations Research. 27: 39–54. Дои:10.1007 / bf01916898.