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

А геометрическая программа (GP) является оптимизация проблема формы

${displaystyle {egin {array} {ll} {mbox {minim}} & 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_ {m}}$ находятся многочлены и ${displaystyle g_ {1}, точки, g_ {p}}$ являются одночленами. В контексте геометрического программирования (в отличие от стандартной математики) моном - это функция от ${displaystyle mathbb {R} _ {++} ^ {n}}$ к ${displaystyle mathbb {R}}$ определяется как

${displaystyle xmapsto cx_ {1} ^ {a_ {1}} x_ {2} ^ {a_ {2}} cdots x_ {n} ^ {a_ {n}}}$

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

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

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

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

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

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

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

Смотрите также

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

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