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

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

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

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

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

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

Геометрическое программирование – это тесно связано с выпуклой оптимизацией : любую ГП можно сделать выпуклой посредством замены переменных. GP имеют множество применений, включая определение размеров компонентов при ИС , проектировании дизайн самолета, оценка максимального правдоподобия для логистической регрессии в статистике и настройка параметров положительных линейных систем в теории управления .

Выпуклая форма

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

Программное обеспечение

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

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

См. также

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