Задача ГП с ограничениями

Постановка задачи

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

$$\mbox{Задача GP:}\qquad g_{0}(x)\rightarrow \min\qquad\$$

при ограничениях

$$g_{k}(x)\leq 1,\quad k = \overline{1,p},$$ $$x_{j}> 0 ,\quad j= \overline{1,m}.$$

где

$$g_{k}(x)=\sum\limits_{i\in [k]}c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}},\quad k= \overline{0,p},\quad c_{i}>0,\ a_{ij}\in \mathbb{R}.$$

Поясним, что означает обозначение $$[k]$$ в приведенной выше постановке задачи, на которую далее мы будем ссылаться как на задачу GP. Обозначим через $$n$$ общее число мономов, входящих в $$(p+1)$$ позином. Индексное множество $$I=[1,\ldots,n ]$$ нумерует их последовательно так, что первый моном позинома $$g_0$$ имеет номер $$1$$, а последний моном позинома $$g_p$$ - номер $$n$$.

Будем обозначать через $$[k]$$ индексное подмножество, соответствующее позиному $$g_k$$:

$$I = [0]\cup[1]\cup\ldots\cup[p],\quad [k]\cap[l]=\emptyset, \ k\neq l.$$

Обозначим через $$A=||a_{ij}||$$ матрицу экспонент, состоящую из матриц экспонент всех позиномов, входящих в задачу. Количество строк в матрице $$A$$ равно $$n$$ (числу мономов, входящих в $$p+1$$ позином), число столбцов равно $$m$$ (числу переменных задачи). Матрицу экспонент позинома $$g_k$$ будем обозначать через $$A_{[k]},\ k=\overline{0,p}$$.

Обозначим через $$c$$ вектор коэффициентов задачи, состоящий из последовательно записанных векторов коэффициентов всех позиномов. Вектор коэффициентов позинома $$g_k$$ будем обозначать через $$c_{[k]},\ k=\overline{0,p}$$.

Рассмотрим пример.

Пример 31 Запишем индексное множество, вектор коэффициентов и матрицу экспонент следующей задачи ГП:

$$g_{0}(x) = 40 {x}_{1}^{-1}x_{2}^{-0.5} x_{3}^{-1} + 20 {x}_{1}{x}_{3} + 20 x_{1}x_{2}x_{3}\rightarrow\min$$

при ограничениях

$$g_{1}(x) = \frac{1}{3} x_{1}^{-2}x_{2}^{-2} + \frac{4}{3} x_{2}^{0.5}x_{3}^{-1}\leq 1.$$ $$x_j>0,\ j=\overline{1,3}.$$

Запишем индексное множество задачи ГП. Индексное множество, соответствующее целевой функции $$g_{0}$$, состоящей из трех мономов, $$[0] = \{1, 2, 3\}$$. Индексное множество, соответствующее позиному $$g_{1}$$, состоящему из двух мономов, $$[1] = \{4, 5\}$$. Индексное множество задачи (60)-(62)

$$I=[0]\cup[1] = \{1, 2, 3, 4, 5\}.$$

Запишем теперь вектор коэффициентов задачи ГП. Вектор коэффициентов целевой функции $$g_0$$

$$c_{[0]} = (40, 20, 20),$$

вектор коэффициентов ограничения $$g_1$$

$$c_{[1]} = (1/3, 4/3),$$

следовательно, вектор коэффициентов задачи (60)-(62)

$$c = (c_{[0]}, %\cup%\bigcup c_{[1]}) = (40, 20, 20, 1/3, 4/3).$$

Запишем матрицу экспонент задачи ГП. Матрица экспонент позинома $$g_{0}$$

$$A_{[0]}=\left\| \begin{array}{rlr} -1 -0.5 -1 \\ 1 \phantom{-}0 1 \\ 1 \phantom{-}1 1 \end{array} \right\|,$$

матрица экспонент позинома $$g_{1}$$

$$A_{[1]}=\left\| \begin{array}{rlr} -2 -2 0 \\ 0 \phantom{-}0.5 -1 \end{array} \right\|,$$

следовательно, матрица экспонент задачи (60)-(62)

$$A =\left|\left| \begin{array}{c} A_{[0]} \\ A_{[1]} \end{array} \right|\right| = \left\| \begin{array}{rlr} -1 -0.5 -1 \\ 1 \phantom{-}0 1 \\ 1 \phantom{-}1 1 \\ -2 -2 0 \\ 0 \phantom{-}0.5 -1 \end{array} \right\|.$$

Формула для вычисления степени трудности задачи ГП с ограничениями такая же, как для задачи ГП без ограничений:

$$DOD = n -(m_{ind} + 1),$$

где $$n$$ - общее число мономов во всех позиномах, $$m_{ind}$$ - число независимых переменных (определяемое рангом матрицы экспонент задачи $$A$$ ).

Пример 32 Вычислим степень трудности для задачи ГП из примера 31.

Общее число мономов в задаче $$n = 5$$, можно показать, что число независимых переменных $$m = 3$$, следовательно, по формуле (63) $$DOD = 5 - (3+1) = 1$$.

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

Пример 33 Оценим минимальное значение целевой функции $$g_0$$ из примера 31.

Рассмотрим соответствующую задачу ГП без ограничений:

$$g_{0}(x) = 40 {x}_{1}^{-1}x_{2}^{-0.5} x_{3}^{-1} + 20 {x}_{1}{x}_{3} + 20 x_{1}x_{2}x_{3}\rightarrow\min,$$ $$x_{1}>0,\ x_{2}>0,\ x_{3}>0.$$

Легко заметить, что произведение переменных $$x_{1}x_{3}$$ входит во все мономы функции $$g_{0}(x)$$. Следовательно, мы можем понизить размерность задачи на единицу, выполнив замену $$x_{1}x_{3}=t$$. Функцию, которая получится после выполнения замены, обозначим через $$f(t, x_{2})$$:

$$f(t, x_{2}) = g_{0}(x | x_{1}x_{3}=t) =40 {t}^{-1}x_{2}^{-0.5} + 20 t + 20 t x_{2}.$$

Функция $$f(t, x_{2})$$ является регулярным позиномом (см. лекцию 3), так как выполнены следующие равенства:

$$\sum\limits_{i=1}^{3}c_{i}a_{i1} = 40\times (-1) + 20\times 1 + 20\times 1 = 0,$$ $$\sum\limits_{i=1}^{3}c_{i}a_{i2} = 40\times (-0.5) + 0 + 20\times 1 = 0.$$

Из регулярности позинома $$f(t, x_{2})$$ следует (см. теорему 5), что его наименьшее значение, которое мы обозначим через $$f^{*}$$, вычисляется по формуле:

$$f^{*} = \sum\limits_{i=1}^{3}c_{i} = 40+20+20=80,$$

и достигается при $$t=x_2=1$$.

Выполнив обратную подстановку, получим, что точкой глобального минимума функции $$g_{0}(x)$$ является любая точка вида

$$x =\big( x_1, 1, \frac{1}{x_1}\big),\ x_1>0.$$

Вернемся к задаче (60)-(62). Для этой задачи величина $$f^{*} = 80$$ является нижней оценкой для оптимального значения функции $$g_{0}(x)$$, так как при добавлении ограничения значение минимума может только возрасти.

Проверим, существуют ли среди точек вида (64) такие, которые удовлетворяют ограничению (61):

$$g_{1}(x) = \frac{1}{3} x_{1}^{-2}x_{2}^{-2} + \frac{4}{3} x_{2}^{0.5}x_{3}^{-1}\leq 1.$$

То есть необходимо проверить выполнение неравенства

$$\frac{1}{3} x_{1}^{-2}+ \frac{4}{3} x_{1}\leq 1.$$

Данное неравенство не выполняется ни в одной точке, следовательно, среди точек вида (64) нет таких, которые удовлетворяют ограничению (61), и минимальное значение целевой функции $$g_{0}(x)$$ в задаче (60)-(62) больше, чем 80.

Замечание. В предложенном методе оценивания решения задачи (60)-(62) существенным является шаг понижения размерности задачи.

Двойственная задача

Как и в случае задачи ГП без ограничений, задаче ГП с ограничениями можно сопоставить двойственную задачу. При некоторых предположениях о свойствах прямой и двойственных задач оптимальные значения их целевых функций равны. Это дает возможность получить решение прямой задачи, решив двойственную задачу.

Двойственная задача к задаче GP (задача DGP ) имеет вид:

$$\mbox{ Задача DGP:} \qquad v(l,w)=\Bigl(\prod\limits_{i=1}^{n}(c_{i}/w_{i}) ^{w_{i}}\Bigl)\Bigl(\prod\limits_{k=1}^{p}{l_{k}(w)}^{l_{k}(w)}\Bigl)\rightarrow\max$$

при ограничениях:

$$l_{k}(w) = \sum\limits_{i\in [k]}w_{i},\quad k=\overline{0,p},$$ $$l_{0}(w) =1,$$ $$\sum\limits_{i=1}^{n}w_{i}a_{ij}=0, \quad j=\overline{1, m},$$ $$w_{i},\ l_{k} \geq 0,\ k=\overline{0,p},\ i=\overline{1,n}.$$

Ограничение (67) называется условием нормальности, ограничения (68) - условиями ортогональности. Для функции $$v(l,w)$$ полагаем, что $$y^y = y^{-y} = 1$$ для $$y = 0$$.

Пример 34 Запишем двойственную задачу для задачи ГП из примера 31.

Определим двойственную функцию (65) для задачи ГП. Поскольку в задаче пять мономов, следовательно, двойственная функция имеет пять переменных. Вектор коэффициентов задачи $$c = (40, 20, 20, 1/3, 4/3)$$, $$l_{1}(w) = w_4 + w_5$$. Следовательно, двойственная функция для задачи ГП имеет вид:

$$v(w) = \left(\frac{40}{w_1}\right)^{w_1}\left(\frac{20}{w_2}\right)^{w_2} \left(\frac{20}{w_3}\right)^{w_3}\left(\frac{1/3}{w_4}\right)^{w_4}\left(\frac{4/3}{w_5}\right)^{w_5} (w_4 + w_5)^{(w_4 + w_5)}.$$

Запишем теперь условия ортогональности (68). Поскольку в прямую задачу входят три переменные $$x_1,\ x_2,\ x_3$$, то условия ортогональности состоят из трех равенств. В каждом равенстве пять слагаемых, поскольку в задаче пять мономов. Матрица экспонент задчи

$$A=\left\| \begin{array}{rlr} -1 -0.5 -1 \\ 1 \phantom{-}0 1 \\ 1 \phantom{-}1 1 \\ -2 -2 0 \\ 0 \phantom{-}0.5 -1 \end{array} \right\|,$$

где $$j$$ -й столбец образован показателями степеней при $$j$$ -й переменной $$(j=1, 2, 3)$$. По формуле (68) условия ортогональности для задачи ГП имеют вид:

$$\begin{array}{rcrcrcrcrcr} -w_1+w_2+w_3-2 w_4=0, \\ -0.5 w_1+w_3-2 w_4+0.5 w_5=0, \\ -w_1+w_2+w_3-w_5=0. \end{array}$$

Запишем условие нормальности. Поскольку позином $$g_{0}(x)$$ состоит из трех мономов, то в условие нормальности входят три слагаемых. Согласно формуле (67) условие нормальности имеет вид:

$$w_1 + w_2 + w_3 = 1.$$

Таким образом, двойственная задача имеет вид:

$$v(w) = \left(\frac{40}{w_1}\right)^{w_1}\left(\frac{20}{w_2}\right)^{w_2} \left(\frac{20}{w_3}\right)^{w_3}\left(\frac{1/3}{w_4}\right)^{w_4}\left(\frac{4/3}{w_5}\right)^{w_5} (w_4 + w_5)^{(w_4 + w_5)}\rightarrow\max,$$

при ограничениях

$$\begin{array}{rcrcrcrcrcr} -w_1+w_2+w_3-2 w_4=0, \\ -0.5 w_1+w_3-2 w_4+0.5 w_5=0, \\ -w_1+w_2+w_3-w_5=0, \\ w_1+w_2+w_3=1, \end{array}$$ $$w_{i}\geq 0,\ i=\overline{1,5}.$$

Прежде чем показать, как связаны между собой решения задач GP и DGP, введем следующие определения.

Задача GP называется совместной, если существует по крайней мере один положительный вектор $$x$$, удовлетворяющий ее ограничениям.

Задача DGP называется совместной, если существует по крайней мере один неотрицательный вектор $$w$$, удовлетворяющий ее ограничениям.

Методы решения для задачи ГП с ограничениями базируются на теоремах, отражающих связь между прямой и двойственной задачами. Приведем формулировки двух основных теорем. Их доказательства можно найти, например, в [5].

Теорема 9 Если пара векторов $$(x, w)$$ являются допустимыми решениями задач GP и DGP соответственно, то выполняется неравенство

$$g_{0}(x)\geq v(w).$$

Равенство

$$g_{0}(x)= v(w)$$

достигается тогда и только тогда, когда выполняются следующие условия:

$$g_{0}(x) w_{i}= c_i\prod\limits_{j=1}^{m}{x_j}^{a_{ij}},\ i\in [0],$$ $$w_{i}=l_{k}(w) c_i\prod\limits_{j=1}^{m}{x_j}^{a_{ij}},\ i\in [k],\ k=\overline{1,p}.$$

В следующей теореме сформулированы достаточные условия существования оптимального решения задачи GP.

Теорема 10 Если задача GP совместна и существует допустимое решение $$w$$ двойственной задачи DGP, то существует вектор $$x^*$$, который является оптимальным решением задачи GP.

Связь между ГП и выпуклым программированием

Прежде чем показать, какая связь существует между ГП и выпуклым программированием, напомним определения выпуклого множества, выпуклой функции и задачи выпуклого программирования.

Множество точек $$S\subset E_N$$ называется выпуклым, если для любых двух точек $$x$$ и $$y$$ из $$S$$ соединяющий их отрезок $$xy$$ содержится в $$S$$.

Функция $$f$$, определенная на выпуклом множестве $$S\subset E_N$$, называется выпуклой, если для любых двух точек $$x$$ и $$y$$ из $$S$$ выполняется неравенство

$$f(\alpha_{1}x + \alpha_{2}y)\leq \alpha_{1}f(x) + \alpha_{2}f(y),$$

где $$\alpha_{1},\ \alpha_2 \geq 0$$, $$\alpha_{1}+\alpha_{2}=1$$.

Задача выпуклого программирования заключается в минимизации выпуклой функции $$f$$ на выпуклом множестве $$S$$, которое содержится в области определения функции $$f$$: $$\min\limits_{S}f$$.

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

Покажем теперь, что при помощи монотонной замены переменных задачу ГП можно заменить эквивалентной задачей выпуклого программирования.

Выполним следующую замену переменных:

$$x_{j} = e^{z_j},\ j=\overline{1,m}.$$

Для записи результатов подстановки мы будем использовать другое обозначение: $$x_{j} = \exp(z_j)$$, более удобное, когда степень экспоненты является сложным выражением. Выполнив замену, получим положительные показательные функции вида

$$f_k(z)=g_{k}(e^{z_1}, \dots, e^{z_m}) = \sum\limits_{i\in [k]}c_{i}\exp\left(\sum\limits_{j=1}^{m}a_{ij}z_{j}\right),\ k=\overline{0,p}.$$

Заметим, что переменные $$z_j \in \mathbb{R}$$, тогда как переменные $$x_j>0$$.

Таким образом, получим следующую задачу, которую мы будем называть преобразованная задача $$GP_z$$ :

$$f_{0}(z)\rightarrow\min$$

при ограничениях

$$f_k(z)\leq 1,\ k=\overline{1,p},$$

где

$$f_k(z) = \sum\limits_{i\in[k]}c_{i}\exp\left(\sum\limits_{j=1}^{m}a_{ij}z_{j}\right), \ k=\overline{0,p},\ c_i>0,\ a_{ij}\in \mathbb{R},\ z_j\in\mathbb{R}.$$

Пример 35 Запишем ГП из примера 31 в виде преобразованной задачи ГП.

Вектор коэффициентов целевой функции $$g_0$$ равен$$c_{[0]} = (40, 20, 20),$$ матрица экспонент целевой функции $$g_{0}$$ равна

$$A_{[0]}=\left\| \begin{array}{rlr} -1 -0.5 -1 \\ 1 \phantom{-}0 1 \\ 1 \phantom{-}1 1 \end{array} \right\|,$$

следовательно, преобразованная целевая функция имеет вид

$$f_{0}(z) = 40 \exp(-z_1-0.5z_2-z_3) + 20 \exp(z_1+z_3)+20 \exp(z_1 + z_2 + z_3).$$

Вектор коэффициентов ограничения $$g_1$$ равен

$$c_{[1]} = (1/3, 4/3),$$

матрица экспонент ограничения $$g_{1}$$ равна

$$A_{[1]}=\left\| \begin{array}{rlr} -2 -2 0 \\ 0 \phantom{-}0.5 -1 \end{array} \right\|,$$

следовательно, преобразованное ограничение имеет вид

$$f_{1}(z) = 1/3 \exp(-2z_1-2z_2) + 4/3 \exp(0.5z_2 - z_3)\leq 1.$$

Таким образом, преобразованная задача имеет вид:

$$f_{0}(z) = 40 \exp(-z_1-0.5z_2-z_3) + 20 \exp(z_1+z_3)+20 \exp(z_1 + z_2 + z_3)\rightarrow\min$$

при ограничении

$$f_{1}(z) = 1/3 \exp(-2z_1-2z_2) + 4/3 \exp(0.5z_2 - z_3)\leq 1.$$

Сформулируем основное свойство преобразованной задачи $$GP_z$$ в виде теоремы, доказательство которой можно найти, например, в [5].

Теорема 11 Преобразованная задача $$GP_z$$ является выпуклой задачей. Все положительные показательные функции $$f_{k}(z)$$ выпуклы.

Из теоремы следует, что для решения задач ГП можно использовать методы, разработанные специально для решения задач выпуклого программирования, предварительно преобразовав задачу ГП в задачу вида $$GP_z$$.

Связь между ГП и линейным программированием

Напомним постановку задачи линейного программирования.

Задача ЛП - это задача поиска экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений (равенств или неравенств), связывающих эти переменные:

$$\sum\limits_{j=1}^{n}c_{j}x_{j}\rightarrow \min (\max)$$

при ограничениях

$$\sum\limits_{j=1}^{n}a_{ij}x_{j}\geq (\leq,\ =)\ b_i,\ i=\overline{1,m},$$ $$x_{j}\geq 0,\ j=\overline{1,n}.$$

Одним из подходов к решению задач ГП является замена ее задачей линейного программирования, в которой целевая функция и функции ограничений являются линейными аппроксимациями соответствующих позиномов. Желающие могут прочесть об этом в статье [6]. Мы же рассмотрим на примере реализацию этого подхода для частного случая задач ГП, когда все позиномы являются мономами.

Пример 36 Найдем длины сторон параллелепипеда, имеющего наибольший объем, если площадь нижней и верхней стороны не превышает 20 (см $$^2$$ ), площадь фронтальных сторон не превышает 10 (см $$^2$$ ), площадь боковых сторон не превышает 5 (см $$^2$$ ).

Введем обозначения: $$x_1$$ - ширина параллелепипеда, $$x_2$$ - длина, $$x_3$$ - высота параллелепипеда. Тогда математическая модель задачи примет вид:

$$x_{1}x_{2}x_{3}\rightarrow\max$$

при ограничениях:

$$x_1 x_2\leq 20,$$ $$x_2 x_3\leq 10,$$ $$x_1 x_3\leq 5,$$ $$x_1>0,\ x_2>0,\ x_3>0.$$

Эта задача эквивалентна следующей задаче ГП в каноническом виде:

$$g_0(x) =x_{1}^{-1}x_{2}^{-1}x_{3}^{-1}\rightarrow\min$$

при ограничениях:

$$g_1(x)=\frac 1{20} x_1 x_2\leq 1$$ $$g_2(x)=\frac 1{10} x_2 x_3\leq 1,$$ $$g_3(x)=\frac 1{5} x_1 x_3\leq 1,$$ $$x_1>0,\ x_2>0,\ x_3>0.$$

Все позиномы в задаче являются мономами. Сведем эту задачу ГП к задаче ЛП. Выполним следующую замену переменных: $$\ln(x_j) =t_j,\ j=1, 2, 3$$. Получим эквивалентную задачу линейного программирования, в которой переменные могут иметь любой знак:

$$\ln(g_0)=-t_1-t_2-t_3 \rightarrow\min$$

при ограничениях

$$t_1+t_2\leq \ln 20,$$ $$t_2+t_3\leq\ln 10,$$ $$t_1+t_3\leq\ln 5,$$ $$t_j \gtrless 0,\ j=\overline{1,3}.$$

Сведем эту задачу к задаче ЛП в стандартном виде, выполнив замену:

$$t_j=v_j-d_j,\ v_j \ge 0, \ d_j\ge 0,\ j=\overline{1,3}.$$

В результате получим следующую задачу ЛП:

$$-v_1-v_2-v_3+d_1+d_2+d_3 \rightarrow\min$$

при ограничениях

$$v_1+v_2-d_1-d_2\leq \ln 20,$$ $$v_2+v_3-d_2-d_3\leq\ln 10,$$ $$v_1+v_3-d_1-d_3\leq \ln 5,$$ $$v_j \ge 0,\ d_j\ge 0,\ j=\overline{1,3}.$$

Для решения задач ЛП в этом курсе мы будем использовать пакет FinPlus, в котором реализован двухфазный модифицированный симплекс-метод. Версия пакета FinPlus для свободного копирования и руководство пользователя размещены на сайте exponenta.ru:

(рис 5.2) FinPlus: ввод данных задачи (рис 5.1) FinPlus: лист с отчетом о решении задачи

Решим задачу в пакете FinPlus. На рис. 5.1 показано диалоговое окно для ввода размерности задачи, типа целевой функции и имени задачи. На рис. 5.2 приведен фрагмент рабочего листа с данными задачи и ее решением:

$$\min\ln(g_0) = -3.45,\ v_{1} = 1.15,\ v_{2} = 1.84,\ v_{3}=0.46,\ d_{1} = d_{2} = d_{3} = 0.$$

Выполнив обратную замену $$x_j = \exp(t_j)\ (\ j=1, 2, 3)$$, получим:

$$\min g_0 =0.0317,\ x_1 = 3.16,\ x_2 = 6.33,\ x_3 = 1.58.$$

Таким образом, максимальный объем параллелепипеда, равный $$\frac1{0.0317}= 31.55$$ (см $$^3$$ ), достигается при следующих размерах: ширина $$x_1 = 3.16$$ (см), длина $$x_2=6.33$$ (см), высота $$x_3 = 1.58$$ (см).

Замечание. При такой постановке задачи ГП (когда все позиномы являются мономами) не обязательно приводить задачу ГП к каноническому виду.

О методах решения задач ГП с ограничениями

Методы решения задач ГП можно разделить на прямые, решающие прямую задачу ГП, и двойственные, решающие соответствующую двойственную задачу. Ряд авторов считают двойственные методы наиболее эффективными. Мы не будем излагать общие методы решения задач ГП в этом вводном курсе, так как они довольно сложны. Сообщим только, что на практике чаще всего используют метод внутренней точки ([7]) и метод Ражгопала-Бриккера ([9]). Последний метод основан на обобщенном линейном программировании и идее метода генерации столбцов.

Краткие итоги

Приведены постановки прямой задачи ГП с ограничениями в канонической форме и двойственной к ней задачи. Введено определение совместной задачи ГП. Сформулированы теоремы двойственности для задачи ГП с ограничениями. Описана связь между теорией выпуклого программирования и геометрическим программированием, а также связь между линейным и геометрическим программированием. Описано преобразование задачи ГП в выпуклую задачу. Описано преобразование мономиальной задачи ГП в задачу ЛП. Рассказано об основных методах решения задач ГП с ограничениями. Все понятия объяснены на примерах.