Геометрическое программирование

Геометрическая программа ( GP ) является оптимизация задача вида

${\displaystyle {\begin{array}{ll}{\mbox{minimize}}&f_{0}(x)\\{\mbox{subject to}}&f_{i}(x)\leq 1,\quad i=1,\ldots ,m\\&g_{i}(x)=1,\quad i=1,\ldots ,p,\end{array}}}$

где - многочлены и - одночлены. В контексте геометрического программирования (в отличие от стандартной математики) моном - это функция от до, определяемая как${\displaystyle f_{0},\dots ,f_{m}}$${\displaystyle g_{1},\dots ,g_{p}}$${\displaystyle \mathbb {R} _{++}^{n}}$${\displaystyle \mathbb {R} }$

${\displaystyle x\mapsto cx_{1}^{a_{1}}x_{2}^{a_{2}}\cdots x_{n}^{a_{n}}}$

где и . Посином - это любая сумма одночленов. ^{[1] [2]}${\displaystyle c>0\ }$${\displaystyle a_{i}\in \mathbb {R} }$

Геометрическое программирование тесно связано с выпуклой оптимизацией : любой ГП можно сделать выпуклым с помощью замены переменных. ^[2] GP имеют множество приложений, включая определение размеров компонентов при проектировании IC , ^{[3] [4]} проектирование самолетов, ^[5] оценку максимального правдоподобия для логистической регрессии в статистике и настройку параметров положительных линейных систем в теории управления . ^[6]

Выпуклая форма [ править ]

Геометрические программы, как правило, не являются задачами выпуклой оптимизации, но они могут быть преобразованы в выпуклые задачи заменой переменных и преобразованием целевой функции и функций ограничений. В частности, после выполнения замены переменных и записи в журнал целевых функций и ограничений, функции , т. Е. Полиномы, преобразуются в функции log-sum-exp , которые являются выпуклыми, а функции , т. Е. Одночлены , становятся аффинными . Следовательно, это преобразование превращает каждый GP в эквивалентную выпуклую программу. ^[2] Фактически, это преобразование журнала в журнал можно использовать для преобразования более широкого класса задач, известного как выпуклое программирование журнала в журнал.${\displaystyle y_{i}=\log(x_{i})}$${\displaystyle f_{i}}$${\displaystyle g_{i}}$(LLCP) в эквивалентную выпуклую форму. ^[7]

Программное обеспечение [ править ]

Существует несколько программных пакетов, помогающих формулировать и решать геометрические программы.

• MOSEK - это коммерческий решатель, способный решать геометрические программы, а также другие задачи нелинейной оптимизации.
• CVXOPT - это решатель с открытым исходным кодом для задач выпуклой оптимизации.
• GPkit - это пакет Python для точного определения моделей геометрического программирования и управления ими. Есть целый ряд примеров моделей GP , написанных с этим пакетом здесь .
• GGPLAB - это набор инструментов MATLAB для определения и решения геометрических программ (GP) и обобщенных геометрических программ (GGP).
• CVXPY - это встроенный в Python язык моделирования для определения и решения задач выпуклой оптимизации, включая GP, GGP и LLCP. ^[7]

См. Также [ править ]

• Сигномиальный
• Кларенс Зенер

Ссылки [ править ]