Преобразование некоторых задач оптимизации в задачи ГП

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

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

Напомним постановку канонической задачи ГП из предыдущей лекции

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

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

$$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}.$$

Рассмотрим сначала наиболее простые случаи преобразования задач оптимизации в задачи ГП.

Простейшие случаи преобразования

Положительная константа в правой части ограничения.

Если имеется ограничение вида

$$g(x)\leq q,\ q\in \mathbb{R},\ q > 0,$$

то эквивалентное ограничение имеет вид:

$$\frac{1}{q} g(x) \leq 1.$$

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

Пример 37 Преобразуем ограничение

$$8 x_{1}^{-3}x_{2}+12 x_{1}^{0.5}x_{2}^{-0.5}\leq 4$$

в ограничение вида (70).

Используя преобразование (71), получим ограничение

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

Моном в правой части ограничения.

Если имеется ограничение вида

$$g(x)\leq u(x),$$

где $$u(x)$$ - моном, то эквивалентное ограничение имеет вид:

$$g(x)/u(x) \leq 1.$$

Заметим, что $$g(x)/u(x)$$ - позином, если $$g(x)$$ является позиномом, и $$g(x)/u(x)$$ - моном, если $$g(x)$$ является мономом. Рассмотрим пример.

Пример 38 Преобразуем ограничение

$$8 x_{1}^{-3}x_{2}+12 x_{1}^{0.5}x_{2}^{-0.5}\leq 4 x_{1}x_{2}^{-2}$$

в ограничение вида (70).

Используя преобразование (72), получим ограничение

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

Максимизация монома.

Нахождение максимума (условного или безусловного) монома $$g_{0}(x)$$ эквивалентно нахождению минимума монома $$\overline{g}_{0}(x)$$:

$$\overline{g}_{0}(x) = \frac{1}{g_{0}(x)} =\frac{1}{c_{1}}\prod\limits_{j=1}^{m}{x_{j}}^{-a_{ij}},\quad c_{1}>0,\ a_{ij}\in \mathbb{R}.$$

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

Пример 39 Преобразуем задачу с целевой функцией

$$2 x_{1}^{2}x_{2}^{-1}\rightarrow\max$$

в задачу с целевой функцией вида (69).

Используя преобразование (73), получим эквивалентную задачу:

$$0.5 x_{1}^{-2}x_{2}\rightarrow\min.$$

Обратное ограничение на моном.

Если имеется ограничение вида

$$u(x)\geq q, \ q\in \mathbb{R},\ q > 0,$$

где $$u(x)$$ - моном, то эквивалентное ограничение имеет вид:

$$q u(x)^{-1} \leq 1.$$

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

Пример 40 Преобразуем ограничение

$$8 x_{1}^{-3}x_{2}\geq 4,$$

в ограничение вида (70).

Используя преобразование (74), получим ограничение

$$0. 5 x_{1}^{3}x_{2}^{-1}\leq 1.$$

Преобразования, использующие дополнительные переменные.

В этом пункте мы рассмотрим только частный случай преобразования, использующего дополнительные переменные. Однако сама схема преобразования носит весьма общий характер. Пусть имеется задача:

$$g_{0}(x)={\frac{[h_{1}(x)]^{\alpha}}{[h_{2}(x)-h_{3}(x)]^{\beta}}}\rightarrow\min,$$

где $$h_{1}(x)$$, $$h_{3}(x)$$ - позиномы, $$h_{2}(x)$$ - моном, $$\alpha \in \mathbb{R},\ \alpha>0$$, $$\beta\in \mathbb{R},\ \beta >0$$. Предполагается, что функция $$[h_{2}(x)-h_{3}(x)]> 0$$, $$x>0$$.

Введем вектор дополнительных переменныx $$t=(t_{1},\ t_{2})>0$$, такой что выполняются неравенства

$$h_{1}(x)\leq t_{1},$$ $$h_{2}(x)-h_{3}(x)\geq t_{2}.$$

Тогда выполняется неравенство

$${\frac{[h_{1}(x)]^{\alpha}}{[h_{2}(x)-h_{3}(x)]^{\beta}}}\leq \frac{t_{1}^{\alpha}}{t_{2}^{\beta}} = t_{1}^{\alpha}t_{2}^{-\beta},$$

и задача (75) эквивалентна задаче

$$t_{1}^{\alpha}t_{2}^{-\beta}\rightarrow\min$$

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

$$h_{1}(x)\leq t_{1},$$ $$h_{2}(x)-h_{3}(x)\geq t_{2}.$$

Теперь, используя описанные в предыдущих пунктах преобразования, приведем задачу (76)--(78) к задаче ГП в канонической форме. Применив преобразование (72) к ограничению (77), получим ограничение

$$t_{1}^{-1}h_{1}(x)\leq 1.$$

Перепишем неравенство (78) в виде

$$t_{2}+h_{3}(x)\leq h_{2}(x)$$

и применим преобразование (72). Получим ограничение

$$t_{2}{h_{2}(x)}^{-1}+h_{3}(x){h_{2}(x)}^{-1}\leq 1.$$

Таким образом получили задачу GP:

$$\overline{g}_{0}(x, t)=t_{1}^{\alpha}t_{1}^{-\beta}\rightarrow\min$$

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

$$\begin{array}{rclcr} \overline{g}_{1}(x, t)=t_{1}^{-1}h_{1}(x)\leq 1, \\ \overline{g}_{2}(x, t)=t_{2}{h_{2}(x)}^{-1}+h_{3}(x){h_{2}(x)}^{-1}\leq 1. \end{array}$$

Отметим, что при использовании преобразований, описанных выше, размерность задачи увеличивается на две переменные, при этом появляются два дополнительных ограничения.

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

Пример 41 Преобразуем задачу

$${\frac{[2 x_{1}^{2}x_{2}^{-1}+x_{1}^{-2}+x_{2}^{3}]^{5}}{[3 x_{1}x_{2}^{3} - (x_{1}^{-2}+x_{2}^{2})]^{4}}}\rightarrow\min,$$

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

$$x_{1}^{-1}\leq 1,$$ $$x_{2}^{-1}\leq 1,$$ $$x_{1}>0,\ x_{2}>0$$

в задачу GP.

Введем следующие обозначения: $$h_{1}(x) = 2 x_{1}^{2}x_{2}^{-1}+x_{1}^{-2}+x_{2}^{3}$$, $$h_{2}(x)=3 x_{1}x_{2}^{3}$$, $$h_{3}(x) = x_{1}^{-2}+x_{2}^{2}$$, $$\alpha = 5$$, $$\beta=4$$. Тогда целевая функция примет вид, задаваемый формулой (75). Выполним преобразования, предложенные для этого случая. Введем вектор дополнительных переменныx $$t=(t_{1},\ t_{2})>0$$, для которого выполняются неравенства:$$2 x_{1}^{2}x_{2}^{-1}+x_{1}^{-2}+x_{2}^{3}\leq t_{1},$$

$$3 x_{1}x_{2}^{3} -(x_{1}^{-2}+x_{2}^{2})\geq t_{2}.$$

Выполнив элементарные преобразования, получим следующую задачу GP:

$$t_{1}^{5}t_{2}^{-4}\rightarrow\min$$

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

$$2 t_{1}^{-1}x_{1}^{2}x_{2}^{-1}+t_{1}^{-1}x_{1}^{-2}+t_{1}^{-1}x_{2}^{3}\leq 1,$$ $$\frac{1}{3} t_{2}x_{1}^{-1}x_{2}^{-3}+ \frac{1}{3} x_{1}^{-3}x_{2}^{-3}+ \frac{1}{3} x_{1}^{-1}x_{2}^{-1}\leq 1,$$ $$x_{1}^{-1}\leq 1,$$ $$x_{2}^{-1}\leq 1,$$ $$x_{1}>0,\ x_{2}>0,\ t_{1}>0,\ t_{2}>0.$$

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

В следующем разделе мы покажем, как преобразовывать задачи с ограничениями более общего вида.

Обратная задача ГП

Обратной задачей геометрического программирования называется следующая задача:

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

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

$$g_{k}(x)\leq 1,\quad k = \overline{1, p_1},$$ $$g_{k}(x)\geq 1,\quad k = \overline{p_1+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}.$$

Обратная задача ГП отличается от задачи GP наличием ограничений вида (80), которые называются обратными ограничениями.

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

Лемма 1 Для положительных чисел $$u_{i},\ (i=\overline{1,n})$$ и положительных чисел $$\alpha_{i},\ (i = \overline{1,n})$$, удовлетворяющих условию

$$\sum\limits_{i=1}^{n}\alpha_{i} = 1,$$

выполняются неравенства

$$\left(\sum\limits_{i=1}^{n}u_{i}\right)^{-1}\leq \prod\limits_{i=1}^{n}\left(\frac{\alpha_i}{u_i}\right)^{\alpha_i}\leq \sum\limits_{i=1}^{n}\left(\frac{\alpha_{i}^{2}}{u_i}\right).$$

Эти неравенства превращаются в равенства тогда и только тогда, когда

$$u_{i} = \alpha_{i}\left(\sum\limits_{j=1}^{n}u_{j}\right),\ i=\overline{1,n}.$$

Введем определения. Геометрическим обратным мономом $$\overline{g}(x, \alpha)$$ для позинома

$$g(x)=\sum\limits_{i=1}^{n}c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}}$$

называется моном вида

$$\overline{g}(x,\alpha)={\prod\limits_{i=1}^{n}}% \left(\frac{\alpha_i}{c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}}}\right)^{\alpha_i},$$

где положительные веса $$\alpha_{i}$$, $$i=\overline{1,n}$$, удовлетворяют условию $$\sum\limits_{i=1}^{n}\alpha_{i} = 1$$.

Гармоническим обратным позиномом $$\widetilde{g}(x, \alpha)$$ для позинома $$g(x)$$ называется позином вида

$$\widetilde{g}(x,\alpha)=\sum\limits_{i=1}^{n}% {\frac{\alpha_{i}^{2}}{c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}}}}.$$

где положительные веса $$\alpha_{i}$$, $$i=\overline{1,n}$$, удовлетворяют условию $$\sum\limits_{i=1}^{n}\alpha_{i} = 1$$.

Из леммы 1 следует, что, если положить $$u_i=c_{i}\prod\limits_{j=1}^{m}{x_{j}}^{a_{ij}}$$, то для любого $$x>0$$ выполняются неравенства:

$$1/g(x)\leq \overline{g}(x,\alpha)\leq \widetilde{g}(x,\alpha).$$

Введем в рассмотрение семейство сжатых задач $$CGP(\alpha)$$ для задачи IGP, в которых обратные ограничения заменены ограничениями вида $$\overline{g}_k(x,\alpha)\leq 1$$:

$$\mbox{Задача CGP}(\alpha):\quad g_{0}(x)\rightarrow \min$$

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

$$g_{k}(x)\leq 1,\quad k = \overline{1, p_1},$$ $$\overline{g}_{k}(x,\alpha)\leq 1,\quad k = \overline{p_1+1, p},$$ $$x_{j}> 0 ,\quad j= \overline{1,m},$$ $$\sum\limits_{i=1}^{n}\alpha_{i} = 1.$$

где $$g_{k}(x)$$ - позиномы вида (81), $$\overline{g}_{k}(x,\alpha)$$ - мономы вида (82). Каждой задаче из семейства соответствует вектор весов $$\alpha$$, который удовлетворяет условиям

$$\sum\limits_{i\in [k]}\alpha_{i} = 1, \quad k = \overline{p_1+1, p}.$$

Задачи из семейства $$CGP(\alpha)$$ являются задачами ГП. Связь между обратной задачей ГП и соответстующим семейством сжатых задач $$CGP(\alpha)$$ сформулируем в виде теоремы.

Теорема 12 Оптимальное решение $$x^*(\alpha)$$ любой сжатой задачи из семейства $$CGP(\alpha)$$ является допустимым решением соответствующей обратной задачи IGP. Если обратная задача IGP имеет оптимальное решение $$x^*$$, то существует вектор весов $$\alpha^*$$, при котором $$x^*$$ является оптимальным решением сжатой задачи, соответсвующей этому вектору весов.

Доказательство. Обозначим через $$x^*(\alpha)$$ оптимальное решение задачи из семейства $$CGP(\alpha)$$ при векторе весов $$\alpha$$. Так как оптимальное решение $$x^*(\alpha)$$ является допустимым решением задачи, то для него выполнены неравенства

$$g_{k}(x^*(\alpha))\leq 1,\quad k = \overline{1, p_1},$$ $$\overline{g_k}(x^*(\alpha),\alpha)\leq 1, \quad k = \overline{p_1+1, p}.$$

Тогда из неравенства (84) следует, что выполнены неравенства

$$g_k(x^*(\alpha))\geq 1, \quad k = \overline{p_1+1, p}.$$

Следовательно, $$x^*(\alpha)$$ является допустимым решением задачи IGP.

Пусть задача IGP имеет оптимальное решение. Обозначим его через $$x^*$$. Покажем, что существует вектор весов $$\alpha^*$$ такой, что для соответствующей ему задачи вектор $$x^*$$ будет допустимым решением. Введем следующие обозначения:

$$\beta_k=g_k(x^*)=\sum\limits_{i\in [k]}u_i^* \leq 1, \quad k = \overline{p_1+1, p}.$$

Тогда вектор

$$\alpha^*_i = \frac{u_i^*}{\beta_k},\ i\in [k], \quad k = \overline{p_1+1, p}$$

является вектором весов, а $$x^*$$ - допустимым (и оптимальным) решением соответствующей ему сжатой задачи:

$$\overline{g_k}(x^*,\alpha^*)=\frac{1}{g_k(x^*)}\leq 1, \quad k = \overline{p_1+1, p}.$$

Приведем пример на построение семейства сжатых задач.

Пример 42 Образуем для обратной задачи ГП

$$g_{0}(x) =4 x_{1}x_{2}^{-1}+5x_{1}^{3}x_{2}^{-4}x_{3}+x_{1}^{-2}\rightarrow\min$$

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

$$g_{1}(x) = 2 x_{1}x_{3}^{2}+3x_{2}^{-1}\leq 1,$$ $$g_{2}(x) = x_{1}^{-1}x_{2}^{2}+4 x_{1}x_{3}^{-1}\geq 1,$$ $$x_1>0,\ x_2>0,\ x_3>0$$

семейство сжатых задач.

Заменим обратное ограничение (85) прямым. Для этого вычислим геометрическое обратное для позинома $$g_{2}(x)$$ по формуле (82):

$$\overline{g}_{2}(x, \alpha) = \left(\frac{\alpha_1}{x_{1}^{-1}x_{2}^{2}}\right)^{\alpha_1}\left(\frac{\alpha_2}{4 x_{1}x_{3}^{-1}}\right)^{\alpha_2}.$$

Упростим последнюю формулу:

$$\overline{g}_{2}(x, \alpha) =4^{-\alpha_2}\alpha_{1}^{\alpha_{1}}\alpha_{2}^{\alpha_{2}}x_{1}^{\alpha_1 - \alpha_2}x_{2}^{-2\alpha_1}x_{3}^{\alpha_2}.$$

Таким образом, семейство сжатых задач для рассматриваемой задачи имеет вид

$$g_{0}(x) =4 x_{1}x_{2}^{-1}+5x_{1}^{3}x_{2}^{-4}x_{3}+x_{1}^{-2}\rightarrow\min$$

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

$$\begin{array}{lclcr} g_{1}(x)=2 x_{1}x_{3}^{2}+3x_{2}^{-1}\leq 1, \\ \overline{g}_{2}(x, \alpha) =4^{-\alpha_2}\alpha_{1}^{\alpha_{1}}\alpha_{2}^{\alpha_{2}}x_{1}^{\alpha_1 - \alpha_2}x_{2}^{-2\alpha_1}x_{3}^{\alpha_2}\leq 1, \\ x_1>0,\ x_2>0,\ x_3>0. \end{array}$$

Задачи ГП из этого семейства отличаются только видом второго ограничения (на значения позинома $$\overline{g}_{2}(x, \alpha)$$ ). Например, при $$\alpha_{1}= \alpha_{2}=1/2$$ это ограничение будет иметь вид:

$$\overline{g}_{2}(x) =\frac{1}{4} x_{2}^{-1}x_{3}^{\frac{1}{2}} \leq 1.$$

Из (84) следует, что минимум $$M_{IGP}$$ задачи $$IGP$$ и минимум $$M_{CGP(\alpha)}$$ задачи $$CGP(\alpha)$$ связаны соотношением

$$M_{CGP(\alpha)}\geq M_{IGP}.$$

Таким образом, можно решить задачу $$CGP(\alpha)$$ для некоторых весов $$\alpha_{i},\ i=\overline{1,n}$$ и полученное решение будет оценкой сверху для обратной задачи $$IGP$$.

Введем в рассмотрение семейство гармонических задач $$HGP(\alpha)$$ для задачи IGP, в которых обратные ограничения заменены ограничениями вида $$\widetilde{g}_k(x,\alpha)\leq 1$$:

$$\mbox{Задача HGP(\alpha):} \quad g_{0}(x)\rightarrow \min$$

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

$$g_{k}(x)\leq 1,\quad k = \overline{1, p_1},$$ $$\widetilde{g}_{k}(x,\alpha)\leq 1,\quad k = \overline{p_1+1, p},$$ $$x_{j}> 0 ,\quad j= \overline{1,m},$$

где $$g_{k}(x)$$ - позиномы вида (81), $$\widetilde{g}_{k}(x,\alpha)$$ - позиномы вида (83).

Каждой задаче из семейства соответствует вектор весов $$\alpha$$, который удовлетворяет условиям

$$\sum\limits_{i\in [k]}\alpha_{i} = 1, \quad k = \overline{p_1+1, p}.$$

Задачи из семейства $$HGP(\alpha)$$ являются задачами ГП. Связь между обратной задачей ГП и соответстующим семейством гармонических задач $$HGP(\alpha)$$ сформулируем в виде теоремы.

Теорема 13 Оптимальное решение $$\widetilde{x}(\alpha)$$ любой гармонической задачи из семейства $$HGP(\alpha)$$ является допустимым решением соответствующей обратной задачи IGP. Если обратная задача IGP имеет оптимальное решение $$\widetilde{x}$$, то существует вектор весов $$\widetilde{\alpha}$$, при котором $$\widetilde{x}$$ является оптимальным решением гармонической задачи, соответсвующей этому вектору весов.

Доказательство этой теоремы аналогично доказательству теоремы 12.

Приведем пример на построение семейства гармонических задач.

Пример 43 Образуем для обратной задачи ГП

$$g_{0}(x) =4 x_{1}x_{2}^{-1}+5x_{1}^{3}x_{2}^{-4}x_{3}+x_{1}^{-2}\rightarrow\min$$

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

$$g_{1}(x) = 2 x_{1}x_{3}^{2}+3x_{2}^{-1}\leq 1,$$ $$g_{2}(x) = x_{1}^{-1}x_{2}^{2}+4 x_{1}x_{3}^{-1}\geq 1,$$ $$x_1>0,\ x_2>0,\ x_3>0$$

семейство гармонических задач.

Заменим обратное ограничение (86) прямым. Для этого вычислим гармоническое обратное для позинома $$g_{2}(x)$$ по формуле (83):

$$\widetilde{g}_{2}(x, \alpha) = \frac{\alpha_{1}^{2}}{x_{1}^{-1}x_{2}^{2}}+ \frac{\alpha_{2}^{2}}{4 x_{1}x_{3}^{-1}}.$$

Упростим последнюю формулу:

$$\widetilde{g}_{2}(x, \alpha) =\alpha_{1}^{2}x_{1}x_{2}^{-2}+0.25 \alpha_{2}^{2}x_{1}^{-1}x_{3}.$$

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

$$g_{0}(x) =4 x_{1}x_{2}^{-1}+5x_{1}^{3}x_{2}^{-4}x_{3}+x_{1}^{-2}\rightarrow\min$$

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

$$\begin{array}{lclcr} g_{1}(x)=2 x_{1}x_{3}^{2}+3x_{2}^{-1}\leq 1, \\ \widetilde{g}_{2}(x, \alpha) =\alpha_{1}^{2}x_{1}x_{2}^{-2}+0.25 \alpha_{2}^{2}x_{1}^{-1}x_{3}\leq 1, \\ x_1>0,\ x_2>0,\ x_3>0. \end{array}$$

Задачи ГП из этого семейства отличаются только видом второго ограничения (на значения позинома $$\widetilde{g}_{2}(x, \alpha)$$ ). Например, при $$\alpha_{1}= \alpha_{2}=1/2$$ это ограничение будет иметь вид:

$$\widetilde{g}_{2}(x) =\frac{1}{4}x_{1}x_{2}^{-2}+\frac{1}{16}x_{1}^{-1}x_{3} \leq 1.$$

Из (84) следует, что минимум $$M_{IGP}$$ задачи $$IGP$$ и минимум $$M_{HGP(\alpha)}$$ задачи $$HGP(\alpha)$$ связаны соотношением

$$M_{HGP(\alpha)}\geq M_{CGP(\alpha)}\geq M_{IGP}.$$

Таким образом, можно решить задачу $$HGP(\alpha)$$ для некоторых весов $$\alpha_{i},\ i=\overline{1,n}$$ и полученное решение будет оценкой сверху для обратной задачи $$IGP$$.

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

Оценивание знакопеременных задач с позиномами

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

Введем определение. Знакопеременным полиномом (сигномом) называется (обобщенный) полином

$$f(x) = \sum\limits_{i=1}^{n}c_{i}\prod\limits_{j=1}^{m}{x}_{j}^{a_{ij}},\ x_j>0,\ a_{ij}\in\mathbb{R},\ c_i\in \mathbb{R},$$

который отличается от позинома тем, что коэффициенты $$c_i$$ могут быть отрицательными. Члены знакопеременного полинома удобно располагать так, чтобы первыми в сумме стояли члены с положительными коэффициентами $$c_i$$ (если такие имеются).

Рассмотрим преобразование ограничений на знакопеременные полиномы в ограничения на позиномы, описанное, например, в [5].

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

$$f(x) \leq -1,\quad f(x) \leq 0,\quad f(x)\leq 1.$$

Если целевая функция является сигномом, то сначала ее надо преобразовать путем введения новой положительной дополнительной переменной, появится дополнительное ограничение. Опустим это преобразование, предположив, что рассматривается задача, у которой целевая функция - позином. Итак, пусть требуется минимизировать позином $$g_0(x)$$ при ограничениях на знакопеременные полиномы:

$$f_1(x) \leq -1,\quad f_2(x) \leq 0,\quad f_3(x)\leq 1.$$

Если $$f_1(x)$$ - позином, то ограничение $$f_1(x) \leq -1$$ не может быть удовлетворено, следовательно, задача несовместна (противоречива). Если $$f_1(x)$$ - позином с отрицательным знаком, то это ограничение эквивалентно ограничению $$-f_1(x)\geq 1$$, которое имеет второй из требуемых видов, указанных в (88), следовательно, остается рассмотреть случай, когда $$f_1(x)$$ представляет собой разность двух позиномов.

Если $$f_2(x)$$ - позином, то ограничение $$f_2(x) \leq 0$$ не может быть удовлетворено, следовательно, задача несовместна (противоречива). Если $$f_2(x)$$ - позином с отрицательным знаком, то это ограничение удовлетворяется автоматически и может быть исключено из рассмотрения, следовательно, остается рассмотреть случай, когда $$f_2(x)$$ представляет собой разность двух позиномов.

Если $$f_3(x)$$ - позином, то ограничение $$f_3(x) \leq 1$$ имеет первый из требуемых видов, указанных в (88). Если $$f_2(x)$$ - позином с отрицательным знаком, то это ограничение удовлетворяется автоматически и может быть опущено, следовательно, остается рассмотреть случай, когда $$f_3(x)$$ представляет собой разность двух позиномов.

Таким образом, предположим, что нужно минимизировать позином $$g_0(x)$$ при ограничениях

$$h_1(x) - h_2(x) \leq 1,$$ $$h_3(x) - h_4(x) \leq -1,$$ $$h_5(x) - h_6(x) \leq 0,$$

где $$h_i$$ - позиномы, $$i=\overline{1,6}$$.

Введем дополнительный вектор $$t=(t_1,\ t_2,\ t_3)>0$$. Вектор $$x$$ является допустимым решением этих ограничений тогда и только тогда, когда имеются положительные значения для $$t_1,\ t_2,\ t_3$$ такие, что дополненный вектор $$(x, t_1, t_2, t_3)$$ является допустимым решением, удовлетворяющим ограничениям

$$\begin{array}{lcrcl} h_1(x)\leqt_1\leqh_2(x) + 1, \\ 1 + h_3(x)\leqt_2\leqh_4(x), \\ h_5(x)\leqt_3\leqh_6(x), \end{array}$$

следовательно, получим шесть ограничений:

$$h_1(x) t_{1}^{-1}\leq 1,$$ $$h_2(x) t_{1}^{-1} + t_{1}^{-1}\geq 1,$$ $$t_{2}^{-1}+h_3(x) t_{2}^{-1}\leq 1,$$ $$h_4(x) t_{2}^{-1}\geq 1,$$ $$h_5(x) t_{3}^{-1}\leq 1,$$ $$h_6(x) t_{3}^{-1}\geq 1.$$

Таким образом, получили обратную задачу ГП:

$$g_{0}(x)\rightarrow\min$$

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

$$\begin{array}{lcr} h_1(x) t_{1}^{-1}\leq 1, \\ t_{2}^{-1}+h_3(x) t_{2}^{-1}\leq 1, \\ h_5(x) t_{3}^{-1}\leq 1, \\ h_4(x) t_{2}^{-1}\geq 1, \\ h_2(x) t_{1}^{-1} + t_{1}^{-1}\geq 1, \\ h_6(x) t_{3}^{-1}\geq 1. \end{array}$$

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

Пример 44 Преобразуем задачу с ограничениями на сигномы вида

$$g_{0}(x) = x_{1}^{-2}x_{2}^{-1}x_{3}+0.2 x_{1}^{2}x_{2}+7 x_{2}^{3}x_{3}^{-1}\rightarrow\min$$

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

$$f_{1}(x)= 2 x_{1}^{0.5}x_{2}^{-0.5} + 6 x_{3}^{-4} - 3.5 x_{1}^{-1}x_{3} - 9 x_{2}x_{3}^{-4}\leq \phantom{-}1,\\ f_{2}(x) = 5 x_{1}^{6}+4 x_{2}^{5} - x_{1}x_{3}^{-0.4}-x_{1}^{-3}x_{2}x_{3}^{0.5}-x_{1}^{-1}x_{3}^{-1}\leq -1, \\ f_{3}(x) =x_{1}^{2}x_{2}^{-2}x_{3}^{2} + 3 x_{1}^{-1}x_{2}+x_{3}^{-1} - 4 x_{1}^{3}x_{2}^{3}-2 x_{2}^{-2}x_{3}^{-2}\leq \phantom{-}0$$

в обратную задачу ГП.

Ограничение на сигном $$f_{1}(x)$$ имеет вид (89), здесь $$h_{1}(x) =2 x_{1}^{0.5}x_{2}^{-0.5} + 6 x_{3}^{-4}$$, $$h_{2}(x) = 3.5 x_{1}^{-1}x_{3} + 9 x_{2}x_{3}^{-4}$$. Ограничение на $$f_{1}(x)$$ порождает два ограничения вида (92) и (93):

$$(2 x_{1}^{0.5}x_{2}^{-0.5} + 6 x_{3}^{-4}) t_{1}^{-1}\leq 1,$$ $$(3.5 x_{1}^{-1}x_{3} + 9 x_{2}x_{3}^{-4}) t_{1}^{-1} + t_{1}^{-1}\geq 1.$$

Здесь $$t_1$$ - положительная дополнительная переменная, такая, что выполняются неравенства:

$$h_1(x) \leq t_1 \leq h_2(x) + 1.$$

Ограничение на сигном $$f_{2}(x)$$ имеет вид (90), здесь $$h_{3}(x) = 5 x_{1}^{6}+4 x_{2}^{5}$$, $$h_{4}(x) = x_{1}x_{3}^{-0.4}+x_{1}^{-3}x_{2}x_{3}^{0.5}+x_{1}^{-1}x_{3}^{-1}$$. Ограничение на $$f_{2}(x)$$ порождает два ограничения вида (94) и (95):

$$t_{2}^{-1} +(5 x_{1}^{6}+4 x_{2}^{5}) t_{2}^{-1}\leq 1,$$ $$(x_{1}x_{3}^{-0.4}+x_{1}^{-3}x_{2}x_{3}^{0.5}+x_{1}^{-1}x_{3}^{-1}) t_{2}^{-1}\geq 1.$$

Здесь $$t_2$$ - положительная дополнительная переменная, такая, что выполняются неравенства:$$1 + h_3(x)\leq t_2 \leq h_4(x).$$

Ограничение на сигном $$f_{3}(x)$$ имеет вид (91), здесь $$h_{5}(x) = x_{1}^{2}x_{2}^{-2}x_{3}^{2} + 3 x_{1}^{-1}x_{2}+x_{3}^{-1}$$, $$h_{6}(x)=4 x_{1}^{3}x_{2}^{3}+2 x_{2}^{-2}x_{3}^{-2}$$. Ограничение на $$f_{3}(x)$$ порождает два ограничения вида (96) и (97):

$$(x_{1}^{2}x_{2}^{-2}x_{3}^{2} + 3 x_{1}^{-1}x_{2}+x_{3}^{-1}) t_{3}^{-1}\leq 1,$$ $$(4 x_{1}^{3}x_{2}^{3}+2 x_{2}^{-2}x_{3}^{-2}) t_{3}^{-1}\geq 1.$$

Здесь $$t_3$$ - положительная дополнительная переменная, такая, что выполняются неравенства:

$$h_5(x)\leq t_3 \leq h_6(x).$$

Таким образом, получили обратную задачу ГП:

$$g_{0}(x) = x_{1}^{-2}x_{2}^{-1}x_{3}+0.2 x_{1}^{2}x_{2}+7 x_{2}^{3}x_{3}^{-1}\rightarrow\min$$

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

$$\begin{array}{lcl} 2 x_{1}^{0.5} x_{2}^{-0.5} t_{1}^{-1} + 6 x_{3}^{-4} t_{1}^{-1}\leq 1, \\ t_{2}^{-1} + 5 x_{1}^{6} t_{2}^{-1}+4 x_{2}^{5} t_{2}^{-1}\leq 1, \\ x_{1}^{2} x_{2}^{-2} x_{3}^{2} t_{3}^{-1} + 3 x_{1}^{-1} x_{2} t_{3}^{-1}+x_{3}^{-1} t_{3}^{-1}\leq 1, \\ 3.5 x_{1}^{-1} x_{3} t_{1}^{-1} + 9 x_{2} x_{3}^{-4} t_{1}^{-1} + t_{1}^{-1}\geq 1, \\ x_{1} x_{3}^{-0.4} t_{2}^{-1}+x_{1}^{-3} x_{2} x_{3}^{0.5} t_{2}^{-1}+x_{1}^{-1} x_{3}^{-1} t_{2}^{-1}\geq 1, \\ 4 x_{1}^{3} x_{2}^{3} t_{3}^{-1}+2 x_{2}^{-2} x_{3}^{-2} t_{3}^{-1}\geq 1. \end{array}$$

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

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

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