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

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

${\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},\точки ,f_{м}}$${\displaystyle g_{1},\точки ,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] ГП имеют многочисленные приложения, включая определение размеров компонентов при проектировании ИС , ^{[3] [4]} проектирование самолетов, ^[5] оценку максимального правдоподобия для логистической регрессии в статистике и настройку параметров положительных линейных систем в теории управления . ^[6]

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

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

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

• Знаменитый
• Кларенс Зенер