Задача нелинейного программирования при ограничениях – неравенствах. Седловая точка и задача нелинейного программирования. Применение теоремы Куна – Таккера для задачи выпуклого программирования

Теорема Куна-Таккера. Выше найдены условия оптимальности (1.9), (1.10) для задачи НП с линейными ограничениями. Обобщим эти условия на случай задачи (1.1), (1.2), когда все ограничения нелинейны.

Условия оптимальности решения задачи НП формулируются в следующей теореме, имеющей исключительно важное значение в теории нелинейного программирования.

Теорема 1.1. (Куна-Таккера). Пусть функции $$g_i(x), \; i=\overline{1,m}$$, имеют непрерывные частные производные на некотором открытом множестве Rn, содержащем точку x+. Если x+ является точкой минимума функции f(x) при ограничениях $$g_i(x) \le 0 , \; i=\overline{1,m}$$, удовлетворяющих условию регулярности в виде линейной независимости векторов $$\nabla g_i(x^*)$$, то существуют такие неотрицательные множители Лагранжа $$\lambda_1, \lambda_2, \ldots, \lambda_m$$, что$$\nabla f(x^*) + \sum_{i=1}^m \lambda_i \nabla g_i(x^*) = 0,$$ $$\sum_{i=1}^m \lambda_i g_i(x^*) = 0, \; \lambda \ge 0, \; i=\overline{1,m}$$

Определим функцию Лагранжа следующим образом:$$L(x, \Lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i (x).$$

Тогда теорему Куна-Таккера можно записать в виде$$\nabla_x L(x, \Lambda) = 0,$$ $$\nabla_i L(x, \Lambda) = g(x) \le 0 ,$$ $$\Lambda^T \nabla_{\lambda} L(x, \Lambda) = \sum_{i=1}^m \lambda_i g_i (x) =0.$$

Заметим, что множители Лагранжа $$\lambda_i$$ в задаче НП с ограничениями-равенствами являются знаконеопределенными, тогда как в теореме Куна-Таккера они должны быть положительными.

Доказательство. При достаточно малых t > 0, разлагая f(x++tz) в ряд Тейлора, получим$$g_i(x^* + tz) = g_i(x^*) + t \nabla g_i^T (x^*) z + o(t^2) = t \nabla g_i^T (x^*) z + o(t^2),$$ где o(t2) - остаточный член второго порядка малости (t2). Пусть I - множество активных ограничений. Тогда$$g_i(x^* + tz) = g_i(x^*) + t \nabla g_i^T (x^*) z + o(t^2) = t \nabla g_i^T (x^*) z + o(t^2),$$ так как gi(x+) при $$i \in I$$. Заметим, что система неравенств$$\left. \begin{aligned} \nabla f^T (x^*) z < 0, \\ \nabla g_i^T (x^*) z \le 0. \end{aligned} \right\}$$ несовместна, так как в противном случае при достаточно малом t > 0 для некоторого z получили бы:$$\begin{align*} f (x^* + tz) < f(x^*) \\ g_i(x^* + tz) \le 0, \; i \in J. \end{align*}$$ что противоречит предположению об оптимальности точки x+. Для дальнейшего доказательства воспользуемся леммой, являющейся следствием леммы Фаркаша.

Лемма. При произвольной матрице A выполняется одно из двух условий:

либо выполняется следующая система неравенств:$$Ax < 0,$$ либо выполняется следующая система равенств (уравнений):$$\left\{ \begin{aligned} \Lambda^T A =0 \\ \Lambda \ge 0, \quad \Lambda \neq 0 \end{aligned} \right.$$ Одновременно условия (2.3.22), (2.3.23) выполняться не могут.

Применим эту лемму к (1.20), (1.21), приняв за матрицу A$$\left[ \begin{aligned} \nabla f (x^*) \\ \nabla g_i (x^*) \end{aligned} \right] , \quad i \in I$$

Поскольку система (1.20), (1.21) не имеет решений, то существуют такие $$\lambda_0 \ge 0, \lambda_1 \ge 0, \ldots, \lambda_m \ge 0$$, что$$\lambda_0 \nabla f(x^*) + \sum_{i \in I} \lambda_i \nabla g_i (x^*) = 0,$$ где$$\left[ \begin{aligned} \lambda_0 \\ \lambda_1 \end{aligned} \right] \neq 0.$$

Если присвоим $$\lambda_i$$ значение 0 для $$i \in I$$, то получим $$\sum_{i = I}^m \lambda_i g_i (x^*) = 0$$. Условие $$\sum_{i = I}^m \lambda_i g_i (x^*) = 0$$ называют условием дополняющей нежесткости.

Покажем, что $$\lambda_0$$ в (1.24) не может равняться 0. В самом деле, если допустить, что $$\lambda_0 = 0$$, то получим$$\sum_{i \in I} \lambda_i \nabla g_i (x^*) = 0$$

Однако (1.25) противоречит условию теоремы о линейной независимости векторов $$\nabla g_i (x^*)$$. Остается принять $$\lambda_0 \neq 0$$.. Тогда, разделив обе части (1.24) на $$\lambda_0$$, получим$$\nabla f(x^*) + \sum_{i=I}^m \lambda_i \nabla g_i(x^*) = 0$$ Следовательно, теорема доказана.

Понятие регулярности было впервые введено Г.Куном и А.Таккером и имеет различные формы. В частном случае, когда все $$g_i()x, \; i = \overline{1,m}$$ являются выпуклыми функциями, условие регулярности записывается в виде: существует такой вектор x, что gi(x)<0 для всех $$i = \overline{1,m}$$. Это означает, что может существовать хотя бы одна внутренняя точка допустимого множества решений. Это условие называют условием регулярности Слейтера.

2. Седловая точка и задача нелинейного программирования

Рассмотрим функцию Лагранжа $$L(x, \Lambda)=f(x)+\sum_{i=1}^m \lambda_i g_i (x)$$

Определение 2.1. Пара векторов $$x^*, \Lambda^*$$ называется седловой точкой функции Лагранжа $$L(x, \Lambda)$$, если при всех $$\Lambda \ge 0, \; x \in R^n$$ выполняется условие$$L(x^*, \Lambda) \le L(x^*, \Lambda^*) \le L(x, \Lambda^*)$$

Неравенство (2.1) называют неравенством для седловой точки. Очевидно, что в седловой точке выполняется условие$$L(x^*, \Lambda^*) = \max_{A \ge 0} \min_{x \in R^n} L(x, \Lambda) = \min_{x \in R^n} \max_{A \ge 0} L(x, \Lambda)$$

Между понятием седловой точки функции Лагранжа $$L(x, \Lambda) = f(x) + \sum_{i=1}^m \lambda_i g_i (x)$$ и решением задачи НП существует взаимосвязь, которая устанавливается в следующей теореме.

Теорема 2.1. Пусть f(x) и все gi(x) выпуклы и функции gi(x) удовлетворяют условию регулярности Слейтера. Вектор x+ является решением задачи НП (1.1), (1.2) тогда и только тогда, когда существует такой вектор $$\Lambda^* \ge 0$$, что$$L(x^*, \Lambda) \le L(x^*, \Lambda^*) \le L(x, \Lambda^*)$$ и$$\Lambda^{+T} g(x^*) = \sum_{i=1}^m \lambda_i^* g_i (x^*) = 0.$$

Доказательство. Сначала докажем достаточность условий теоремы. Пусть $$(x^*, \Lambda^*)$$ - седловая точка функции $$L(x, \Lambda)$$. Тогда из правого неравенства (1.24) получим$$L(x^*, \Lambda^*) = f(x^*) + \sum_{i=1}^m \lambda_i^* g_i (x^*) \le L(x, \Lambda^*) = f(x) + \sum_{i=1}^m \lambda_i^* g_i (x)$$

Поскольку $$\lambda_i^* \ge 0$$, а $$g_i(x) \le 0$$, то $$\sum_{i=1}^m \lambda_i^* g_i (x) \le 0$$. Вместе с тем $$\sum_{i=1}^m \lambda_i^* g_i (x^*) = 0$$ согласно с (2.4). Поэтому из (2.3) следует неравенство$$f(x^*) \le (x) + \sum_i \lambda_i^* g_i (x) \le f(x)$$ для всех x, удовлетворяющих ограничениям задачи НП. Таким образом, x* - оптимальное решение задачи НП.

Перейдем к доказательству необходимости. Допустим, что x* - оптимальное решение задачи НП. Заметим, что система$$\left. \begin{aligned} f(x) - f(x^*) < 0, \\ g(x) \le 0 \end{aligned} \right\}$$ не имеет решения, так как x* - точка минимума задачи НП. Отсюда следует также, что не имеет решений и следующая система:$$\left. \begin{aligned} f(x) - f(x^*) < 0, \\ g(x) < 0 \end{aligned} \right\}$$

Тогда согласно теореме Фана существуют такие $$\lambda_0^*, \lambda_1^*, \ldots, \lambda_m^* \ge 0$$, что$$\lambda_0^* \left[ f(x) - f(x^*) \right] + \sum_{i=1}^m \lambda_i^* g_i (x) \ge 0.$$

Поскольку$$\lambda_i^* \ge 0, \quad g_i(x^*) \le 0, \forall i,$$ то$$\sum_{i=1}^m \lambda_i^* g_i (x) \le 0, \text{для всех} \; x .$$

Если же в (2.8) положить x=x*, то получим$$\sum_{i=1}^m \lambda_i^* g_i (x) \ge 0.$$

Сравнив (2.9) с (2.10), получим$$\sum_{i=1}^m \lambda_i^* g_i (x) = 0.$$

Тогда из уравнений (2.8) и (2.11) получим$$\lambda_0^* f(x^*) + \sum_{i=1}^m \lambda_i^* g_i (x^*) \le \lambda_0^* f(x) + \sum_{i=1}^m \lambda_i^* g_i (x).$$

Таким образом доказано правое неравенство для седловой точки. Поскольку $$g(x^*) \le 0$$, то $$\lambda^T g(x) \le 0$$ при любом $$\lambda \ge 0$$. Следовательно,$$\lambda_0^* f(x^*) + \Lambda^T g(x^*) \le \lambda_0^* f(x^*) + \Lambda^{*T} g(x^*).$$

Разделив обе части (2.13) на $$\lambda_0^* > 0$$, получим левое неравенство для седловой точки:$$f(x^*) + \frac{\Lambda^T}{\lambda_0^*} \, g(x^*) = L(x^*, \Lambda) \le f(x^*) + \frac{\Lambda^{*T}}{\lambda_0^*} \, g(x^*) = L(x^*, \Lambda^*)$$

Таким образом, теорема доказана.

Чтобы обеспечить условие $$\lambda_0^* > 0$$, необходимо предположить существования условия регулярности Слейтера. В самом деле, пусть $$\lambda_0^* = 0$$. Тогда выражение (2.12) примет вид$$\sum_{i=1}^m \lambda_i^* g_i (x^*) = 0 \le \sum_{i=1}^m \lambda_i^* g_i (x)$$

Вместе с тем условие регулярности Слейтера утверждает, что существует такой вектор x, что g(x)<0, и, следовательно, $$\sum_{i=1}^m \lambda_i^* g_i (x) < 0$$. Так как это противоречит уравнению (2.14), то предположения теоремы вместе с условием регулярности Слейтера обеспечивает ее справедливость.

Таким образом, при выполнении условий теоремы 2.1 задача НП становится эквивалентной задаче отыскания седловой точки функции Лагранжа.

3. Применение теоремы Куна – Таккера для задачи выпуклого программирования

Выше была рассмотрена задача НП в виде (1.1), (1.2), когда на переменные xj не накладывались условия неотрицательности. Тем не менее часто в задачах исследования операций приходится решать задачи, в которых переменные xj по физическим условиям должны удовлетворять условию $$x_j \ge 0$$ для всех $$j=\overline{1,n}$$.

Покажем, как основные положения изложенной теории можно распространить и на этот случай. Действительно, пусть задача НП имеет вид:$$\text{минимизировать} \; f(x)$$ при ограничениях$$g_i(x) \le 0, \quad i=\overline{1,m} ;$$ $$x_j \ge 0, \quad j=\overline{1,n}$$

Введем обозначения $$x_j = -h_j(x)$$. Тогда ограничения (3.3) можно записать в общем виде:$$h_j(x) \le 0, \quad j=\overline{1,n}$$

Теперь задача задана в каноническом виде (1.1), (1.2). Применим к ней теорему Куна-Таккера, для чего составим функцию Лагранжа:$$L(x, \Lambda, u) = f(x) + \sum_{i=1}^m \lambda_i g_i(x) + \sum_{j=1}^n u_j h_j (x),$$ где $$u_j \ge 0$$ - множители, связанные с ограничениями $$h_j(x) \le 0$$. Условия теоремы Куна-Таккера для (3.5) выглядят так:$$\nabla L(x, \Lambda, u)= \nabla j(x) + \sum_{i=1}^m \lambda_i \nabla g_i(x) + \sum_{j=1}^n u_j \nabla h_j(x) = 0 ,$$ или$$\frac{\partial L(x, \Lambda, u)}{\partial x_j} = \frac{\partial f(x)}{\partial x_j} + \sum_{i=1}^m \lambda_i \frac{\partial g_i(x)}{\partial x_j} -u_j = 0; \quad j=\overline{1,n}$$ $$u_j x_j = 0, \; u_j \ge 0 ,$$ $$\lambda_i g_i(x)=0, \; \lambda_i \ge 0.$$

Условия (3.5), (3.6), (3.7) можно записать в следующей эквивалентной форме:$$\frac{\partial L(x, \Lambda)}{\partial x_j} = \frac{\partial f(x)}{\partial x_j} + \sum_{i=1}^m \lambda_i \frac{\partial g_i(x)}{\partial x_j} = u_j \ge 0,$$ $$\frac{\partial L(x, \Lambda)}{\partial x_j} \cdot x_j =0, \quad j=\overline{1,n}$$

Нетрудно увидеть, что условия (3.10) представляют собой условия дополняющей нежесткости для ограничений неотрицательности.

Таким образом, найдены необходимые условия для оптимального решения задачи НП вида (3.1) - (3.3), которые можно сформулировать в следующей теореме.

Теорема 3.1. Пусть задача НП задана в виде (3.1) - (3.3), а функции f(x) и g1(x), g2(x), ..., gm(x) дифференцируемы и выпуклы (по x ). Вектор $$x^0 \ge 0$$ является оптимальным решением задачи НП тогда и только тогда, когда существует такой вектор $$\Lambda \ge 0$$, что пара $$(x^0 \Lambda_0)$$ является седловой точкой функции Лагранжа, то есть выполняются такие условия:$$\frac{\partial L(x^0, \Lambda^0)}{\partial x_j} \ge 0, \; j=\overline{1,n} ;$$ $$\frac{\partial L(x^0, \Lambda^0)}{\partial x_j} \cdot x_j^0 = 0, \; j=\overline{1,n} ;$$ $$\frac{\partial L(x^0, \Lambda^0)}{\partial \lambda_i} = g_i(x^0) \le 0, \; i=\overline{1,m} ;$$ $$\frac{\partial L(x^0, \Lambda^0)}{\partial \lambda_i} \cdot \lambda_i^0 = g_i(x^0)\lambda_i^0 = 0, \; i=\overline{1,m} .$$

Задача (3.1) - (3.3) при условиях, что все f()x, gi(x) - выпуклые функции, является задачей выпуклого программирования. Ограничения $$g_i(x) \le 0, i=\overline{1,m}$$, определяют выпуклое множество, и требуется найти минимум выпуклой функции f(x) на выпуклом множестве решений $$R(x)= \left\{ x: g_i(x) \le 0, \; i=\overline{1,m} , \; x \ge 0 \right\}$$. Рассмотрим задачу вогнутого программирования.$$\text{максимизировать} f(x)$$ при ограничениях$$\left. \begin{aligned} g_1(x) \ge 0, \\ g_2(x) \ge 0, \\ .\;.\;.\;.\;.\;.\;.\;.\; \\ g_m(x) \ge 0, \end{aligned} \right\}$$ $$x \ge 0.$$ где f(x) и все функции gi(x) вогнуты по x.

Покажем ее эквивалентность задаче выпуклого программирования (3.1) - (3.3). Для этого обозначим $$f'(x) = -f(x), \; g'_i(x) = -g_i(x)$$, и так как $$\max f \sim \min - f(x)$$, то приходим к задаче:$$\text{минимизировать} f(x)$$ при ограничениях$$g'_i(x) \le 0, \; i=\overline{1,m} ;$$ $$x \ge 0 .$$

Легко увидеть, что все функции $$f(x), g'_i(x)$$ будут выпуклы по x, а поэтому задача (3.18) - (3.20) - это задача выпуклого программирования. Итак, эквивалентность задач (3.15) - (3.17) и (3.1) - (3.3) установлена.

Нетрудно получить соответствующие признаки оптимальности для задачи (3.15) - (3.17), аналогичные условиям (3.11) - (3.14).

Теорема 3.2. Пусть задача НП задана в виде (3.15) - (3.17), а функции $$f(x), g_i(x), i=\overline{1,m}$$, - дифференцируемы . Для того чтобы вектор x0 являлся оптимальным решением этой задачи, необходимо, чтобы существовал такой вектор $$\Lambda^0 \ge 0$$, для которого выполнялись бы такие условия:$$\text{а)} \qquad \frac{\partial L (x^0, \Lambda^0)}{\partial x_j} \le 0, \; j=\overline{1,n}$$ $$\text{б)} \qquad \frac{\partial L (x^0, \Lambda^0)}{\partial x_j} \cdot x_j^0 = 0, \; j=\overline{1,n}$$ $$\text{в)} \qquad \frac{\partial L (x^0, \Lambda^0)}{\partial \lambda_i} = g_i(x^0) \ge 0, \; i=\overline{1,m}$$ $$\text{г)} \qquad \frac{\partial L (x^0, \Lambda^0)}{\partial \lambda_i} \cdot \lambda_i^0 = g_i(x^0) \lambda_i^0 = 0, \; i=\overline{1,m}$$

Если функции $$f(x), g_i(x)$$ вогнуты, то условия (3.21) - (3.24) оказываются и достаточными.