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

редактировать

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

минимизировать f 0 (x) при условии, что fi (x) ≤ 1, i = 1,…, mgi (x) = 1, i = 1,…, p, {\ displaystyle {\ begin {array} {ll} {\ t_dv {minim}} f_ {0} (x) \\ {\ t_dv {при условии}} f_ {i} (x) \ leq 1, \ quad i = 1, \ ldots, m \\ g_ {i} (x) = 1, \ quad i = 1, \ ldots, p, \ end {array}}

{\ displaystyle {\ begin {array} {ll} {\ t_dv {minim}} f_ {0} (x) \\ {\ t_dv {при условии}} f_ {i} (x) \ leq 1, \ quad i = 1, \ ldots, m \\ g_ {i} (x) = 1, \ quad i = 1, \ ldots, p, \ end {array}}}

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

x ↦ cx 1 a 1 x 2 a 2 ⋯ xnan {\ displaystyle x \ mapsto cx_ {1} ^ {a_ { 1}} x_ {2} ^ {a_ {2}} \ cdots x_ {n} ^ {a_ {n}}}

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

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

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

Содержание

1 Выпуклая форма
2 Программное обеспечение
3 См. также
4 Ссылки

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

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

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

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

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

См. Также

Ссылки