Геометричне програмування

Геометричне програмування — розділ математичного програмування, що вивчає підхід до розв'язування нелінійних задач оптимізації спеціальної структури. Термін вперше ввели 1967 року Р. Даффін^[en], Е. Пітерсон і К. Зенер. Назва дисципліни пов'язана з тим, що однією з основних у викладаній теорії є нерівність між середнім геометричним і середнім арифметичним і її узагальнення. Передумовою до розвитку геометричного програмування стали деякі геометричні задачі і методи їх розв'язування. Базовим поняттям геометричного програмування є позіном.

Формулювання задачі геометричного програмування

Знайти найменше значення функції ${\displaystyle g_{0}(t)}$ за обмежень:

${\displaystyle t_{1}>0,t_{2}>0,...,t_{m}>0}$

і

${\displaystyle g_{1}(t)\leqslant 1,g_{2}(t)\leqslant 1,...,g_{p}(t)\leqslant 1,}$.

Тут

${\displaystyle g_{k}(t)=\sum _{i\in J[k]}c_{i}t_{1}^{a_{i1}}t_{2}^{a_{i2}}...t_{m}^{a_{im}},k=0,1,...,p}$,

де

${\displaystyle J[k]=(m_{k},m_{k}+1,m_{k}+2,...,n_{k})k=0,1,...,p}$

і

${\displaystyle m_{0}=1,m_{1}=n_{0}+1,m_{2}=n_{1}+1,...,m_{p}=n_{p-1}+1,n_{p}=p}$.

Функції ${\displaystyle g_{k}(t)}$ — позіноми.

Приклади задач геометричного програмування

Приклад 1

Знайти довжини сторін прямокутника заданого периметра, що має найбільшу площу. Те саме для трикутника.

Приклад 2

${\displaystyle \prod \limits _{i=1}^{n}x_{i}^{\beta _{i}}\rightarrow \max }$

за обмежень

${\displaystyle \sum \limits _{i=1}^{n}\alpha _{i}x_{i}=S,\ x_{i}>0,\ x_{i}\in \mathbb {R} ,}$

де ${\displaystyle \beta _{i}>0,\ \alpha _{i}>0,\beta _{i}\in \mathbb {R} ,\alpha _{i}\in \mathbb {R} ,\ i={\overline {1,n}},}$

Розв'язком задачі є вектор ${\displaystyle x_{}^{*}}$ з компонентами ${\displaystyle x_{i}^{*}={\frac {\beta _{i}S}{\alpha _{i}\beta }},}$ де ${\displaystyle \ \beta =\sum \limits _{i=1}^{n}\beta _{i}.}$

Програмні засоби

Існує декілька пакунків програм, які допомагають формулювати та розв'язувати задачі геометричного програмування.

• MOSEK [Архівовано 28 жовтня 2020 у Wayback Machine.] — це комерційний розв'язувач, здатний розв'язувати задачі геометричного програмування, а також інші задачі нелінійної оптимізації.
• CVXOPT [Архівовано 28 жовтня 2020 у Wayback Machine.] — це розв'язувач із відкритим кодом для опуклих задач оптимізації.
• GPkit [Архівовано 4 жовтня 2020 у Wayback Machine.] — це пакунок Python для чіткого визначення та маніпулювання моделями геометричними програмування. Містить низку прикладів моделей геометричного програмування, написаних разом із цим пакетом.
• GGPLAB [Архівовано 26 вересня 2020 у Wayback Machine.] — це набір інструментів MATLAB для постановки та вирішення задач геометричного програмування (ГП) та узагальнених задач геометричного програмування (УГП).
• CVXPY [Архівовано 28 жовтня 2020 у Wayback Machine.] — це вбудована в Python мова моделювання для визначення та розв'язування опуклих задач оптимізації, включано з ГП, УГП та LLCP[1].

Див. також

• Моном
• Позіном

Примітки

1. A. Agrawal, S. Diamond, and S. Boyd. Disciplined Geometric Programming. [Архівовано 28 жовтня 2020 у Wayback Machine.] Retrieved 8 January 2019.

Література

• Richard J. Duffin, Elmor L. Peterson, Clarence Zener. Geometric Programming. — John Wiley and Sons, 1967. — P. 278. — ISBN 0-471-22370-0.
• Р. Даффин, Э. Питерсон, К. Зенер. Геометрическое программирование. — М. : Мир, 1972. — 311 с.