Оптимизация при наличии ограничений. Ограничения в виде равенств. Ограничения в виде неравенств. Выпуклость и вогнутость. Комплексный метод

2. Ограничения в виде неравенств

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

Рассмотрим общую задачу математического программирования: минимизировать функцию f(х) при наличии m ограничений $$g_i(х) \le b_i (i = 1, 2,..., m)$$, Причем такие ограничения не ограничивают общности. (Ограничение $$\varphi(x) \ge c$$ можно записать в виде $$-\varphi(x) \le -c$$.

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

Ограничения в виде неравенств могут быть преобразованы в ограничения в виде равенств добавления к каждому из них неотрицательной ослабляющей переменной $$u_i^2$$ (отметим, что переменная $$u_i^2$$ всегда положительна):$$g_i(x)+u_i^2=b_i$$ или$$g_i(x)+u_i^2-b_i=0.$$

Таким образом, задача сводится к минимизации функции f(х) при наличии m ограничений в виде равенства $$g_i(x) + u_i^2 - b_i$$. Следуя изложенному в предыдущем разделе методу, сформируем функцию Лагранжа$$F(x,\lambda,u)=f(x)+\sum_{i=1}^m \lambda_i[g_i(x)+u_i^2-b_i].$$

Необходимыми условиями, которые должны выполняться в стационарной точке, являются следующие:$$\frac{\partial F}{\partial x_j} = 0 = \frac{\partial f}{\partial x_j} + \sum_{i=1}^m \lambda_i \frac{\partial g_i}{\partial x_j} \quad \text{при} \quad j=1,2,\ldots,n,$$ $$\frac{\partial F}{\partial \lambda_i} = 0 = g_i(x) + u_i^2 - b_i \quad \text{при} \quad j=1,2,\ldots,m,$$ $$\frac{\partial F}{\partial u_i} = 0 = 2 \lambda_i u_i \quad \text{при} \quad j=1,2,\ldots,m,$$

Умножив последнее уравнение на ui/2, получим$$\lambda_i u_i^2 = 0,$$ т.е.$$\lambda_i [b_i - g_i(x)]=0 \quad \text{при} \quad j=1,2,\ldots,m.$$

Уравнения (2.3), (2.4) и (2.6) являются необходимыми условиями минимума в точке х* при наличии ограничений. Уравнения (2.4) являются повторной записью ограничений $$g_i(x) \le 0$$. Уравнение (2.6) означает, что либо $$\lambda_i = 0$$, либо bi–gi(x*)=0. Если $$\lambda_i \neq 0$$, то gi(x*)=bi и ограничение является активным и представляет собой ограничение в виде равенства. С другой стороны, если ограничение является ограничением в виде строгого неравенства gi(х*) < bi, то соответствующий множитель Лагранжа $$\lambda_i = 0$$. В самом деле, если gi(x*) < bi, то рассматривается минимум, удовлетворяющий ограничению, которое является неактивным, и которым можно пренебречь, а соответствующие множители $$\lambda_i = 0$$. Конечно, предварительно не известно, какими ограничениями можно пренебречь.

Есть также дополнительное условие, которое должно быть выполнено в точке минимума при наличии ограничений, а именно $$\lambda_i > 0$$.

Предположим, что уравнения (2.3), (2.4) и (2.6) справедливы в точке $$(х^*; \lambda^*; u^*)$$. Если фактический минимум функции при наличии ограничений z = f(х*), то можно рассматривать z как функцию от bi и изменения bi будут изменять ограничения и, таким образом, изменять саму функцию z. Покажем, что$$\begin{gathered} \frac{\partial z}{\partial b_i} = -\lambda_i^*, \\ \frac{\partial z}{\partial b_i} = \sum_{j=1}^n \frac{\partial f}{\partial x_j} \, \frac{\partial x_j}{\partial b_i} \end{gathered}$$ где частные производные вычисляются в точке х*.

Поскольку $$g_k(x) + u_k2^ = b_k$$, то$$\frac{\partial g_k}{\partial b_i} = \sum_{j=1}^n \frac{\partial g_k}{\partial x_j} \, \frac{\partial x_j}{\partial b_i} = \left\{ \begin{aligned} 0,\quad \text{если} \quad i \neq k, \\ 1,\quad \text{если} \quad i = k. \end{aligned} \right.$$

Тогда$$\frac{\partial z}{\partial b_i} + \sum_{k=1}^m \lambda_k \frac{\partial g_k}{\partial b_i} = \frac{\partial z}{\partial b_i} + \lambda_i^* = \sum_{j=1}^n \left( \frac{\partial f}{\partial x_j} + \sum_{k=1}^m \lambda_k^* \frac{\partial g_k}{\partial x_j} \right) \frac{\partial x_j}{\partial b_i}.$$

Но это выражение равно нулю в соответствии с уравнением (2.3). Таким образом,$$\frac{\partial z}{\partial b_i} = -\lambda_i^*.$$

С возрастанием bi область ограничений расширяется, что не может привести к увеличению значения z - минимума функции f(х), находящегося внутри области ограничений, а может лишь уменьшить его. Таким образом,$$\frac{\partial z}{\partial b_i} \leqslant 0,$$ т.е.$$\lambda_i^* \geqslant 0.$$

Необходимые условия минимума функции f(х) при наличии ограничений gi(х) < bi (i=1,2,...,m) имеют такой вид, что можно найти x и $$\lambda$$, для которых$$\left. \begin{aligned} \frac{\partial f}{\partial x_j} + \sum_{i=1}^m \lambda_i \frac{\partial g_i}{\partial x_j} = 0 \quad \text{при} \quad j=1,\ldots,n , \\ g_i(x) \leqslant b_i \quad \text{при} \quad i=1,2,\ldots,m; \\ \lambda_i [g_i(x)-b_i]=0 \quad \text{при} \quad i=1,2,\ldots,m, \\ \lambda_i \geqslant 0 \quad \text{при} \quad i=1,\ldots,m. \end{aligned} \right\}$$ (Знак $$\lambda_i$$ меняется на противоположный, если рассматривается максимум.)

Эти условия известны как условия Куна - Таккера.

3. Выпуклость и вогнутость

Общая задача математического программирования является очень сложной и до cих пор не имеет полного решения. Некоторые трудности встречаются в задачах, графически проиллюстрированных (рис. 12.1). На рисунке изображены линии постоянного уровня функции. По мере перемещения от точки х* - точки минимума функции при отсутствии ограничений - значения функции будут расти. На рис. 12.1 показаны также границы области ограничений gi(x) = bi, а сама область заштрихована.

На рис. 12.1,a минимум функции при наличии ограничений совпадает с минимумом функции без ограничений. Все ограничения имеют вид строгих неравенств, и, зная это, можно было бы пренебречь ограничениями и решить зaдачу методами, изложенными в изложенными ранее. На рис. 12.1,б точка минимума при наличии ограничений лежит на кривой g2(x) = b2, а два других ограничения неактивны. Зная это, можно было бы пренебречь ограничениями g1 и g3 и решить эту задачу как задачу с ограничениями в виде равенств, учитывая только ограничение g2(х) = b2. Из этого следует, что в точке минимума x при наличии ограничений справедливо соотношение $$\Lambda f(x) = \lambda \Lambda g_2(x)$$, поскольку направление $$\Lambda f(x)$$ перпендикулярно линии постоянного уровня и границе области ограничений в данной точке. (Сравните с уравнением (2.3).)

Возможно, что наличие ограничений будет приводить к появлению локального минимума. Это может произойти даже в том случае, когда функция имеет только одну точку минимума при отсутствии ограничений. Такая ситуация иллюстрируется рис. 12.2

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

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

Определим эти термины. Область является выпуклой, если отрезок прямой, соединяющей любые две точки области, принадлежит этой области. Следовательно, если x1 и x2 находятся в этой области, то любая точка вида $$\theta x_2 + (1-\theta)x_1$$, где $$0 < \Theta < 1$$, находится в этой же области. На рис. 12.3,а изображена выпуклая область, а на рис. 12.3,б - невыпуклая.

Функция f(х) является выпуклой на выпуклой области X, если для любых двух точек $$x_1, х_2 \in X$$ выполняется соотношение$$f[\theta x_2 + (1-\theta)x_1] \leqslant \theta f(x_2)+(1-\theta)f(x_1) \quad \text{при} \quad 0 < \theta < 1.$$

Для функции одной переменной это означает, что она лежит ниже хорды, соединяющей любые две точки ее графика (рис. 12.4).

Для вогнутой функции, определенной на выпуклом множестве, следует изменить знак неравенства, в результате чего получим соотношение$$f[\theta x_2 + (1-\theta)x_1] \geqslant \theta f(x_2)+(1-\theta)f(x_1).$$

Такая функция лежит выше хорды, соединяющей любые две точки ее графика.

Если в соотношениях (3.1) и (3.2) неравенства заменить на строгие неравенства, то функция f(х) будет строго выпуклой или строго вогнутой.

Есть еще два важных свойства выпуклых (вогнутых) функций, которые можно вывести из соотношений (3.1) и (3.2). Если функция f(х) выпукла на выпуклой области X и $$х_1, x_2 \in X$$ то$$f(x_2) \geqslant f(x_1) + (x_2 - x_1)^T \nabla f(x_1).$$

Для вогнутых функций знак неравенства меняется на противоположный, что устанавливается следующим образом. Поскольку f(х) выпукла, то для $$0 < \theta < 1$$ справедливо соотношение$$f[\theta x_2 + (1-\theta)x_1] \leqslant \thetaf(x_2) + (1-\theta)f(x_1)$$ следовательно,$$f[x_1 + \theta(x_2 - x_1)] - f(x_1) \leqslant \theta [f(x_2) - f(x_1)]$$ и$$f(x_2) \geqslant f(x_1) + \frac{f[x_1 + \theta(x_2 - x_1)]- f(x_1)}{\theta}.$$

Но по теореме о среднем$$f[x_1 + \theta(x_2 - x_1)] = f(x_1) + \theta(x_2 - x_1)^T \nabla f[x_1 + \lambda \theta (x_2 - x_1)],$$ где $$0 < \lambda < 1$$, т. е. производная вычисляется в некоторой точке, лежащей между точками x1 и $$х_1 + \theta (х_2 - х_1)$$.

Следовательно,$$f(x_2) \geqslant f(x_1) + (x_2 - x_1)^T \nabla f[x_1 \theta \lambda (x_2 - x_1)]$$ и при $$\theta > 0$$ получаем соотношение (3.3).

Из соотношения (3.3) следует, что выпуклые функции одной переменной (двух переменных) лежат выше любой касательной (плоскости) к данной функции (см. рис. 12.4).

Функция выпукла, если гессиан$$\mathbf{H} = \left( \frac{\partial^2 f}{\partial x_i \partial x_j} \right)$$ положительно определен. По теореме Тейлора можно записать$$\begin{aligned} f(x)=f(x_1)+(x-x_1)^T \nabla f(x_1) + \frac12 (x-x_1)^T \mathbf{H}(x-x_1) , \\ \text{где} \; \mathbf{H} \; \text{вычисляется в точке} \; x_1 + \lambda(x-x_1) \; \text{и} \; 0 < \lambda < 1. \end{aligned}$$

Таким образом, достаточно показать, что положительно определенная квадратичная функция $$^1 \! /_2 \, x^T \mathbf{H} x$$ является выпуклой. Это сделать несложно.

Пусть x1 и x2 - произвольные значения x и пусть $$X = \theta х_2 + (1 - \theta)х_1$$, где $$0 < \theta < 1$$.

Тогда$$\begin{aligned} \bar{x}^T \mathbf{H}\bar{x} - \theta x_2^T \mathbf{H} x_2 - (1-\theta) x_1^T \mathbf{H} x_1 = \\ = \theta^2 x_2^T \mathbf{H} x_2 + 2\theta (1-\theta) x_2^T \mathbf{H} x_1 + (1 - \theta)^2 x_1^T \mathbf{H} x_1 - \theta x_2^T \mathbf{H} x_2 - (1 - \theta) x_1^T \mathbf{H} x_1 = \\ = - \theta (1- \theta)(x_2 - x_1)^T \mathbf{H} (x_2 - x_1). \end{aligned}$$

Так как $$0 < \theta < 1$$, то $$(1 - \theta) > 0$$, и если матрица Н положительно определена, то $$-\theta (1 - \theta) < 0$$. Следовательно,$$[\theta x_2 + (1-\theta)x_1]^T \mathbf{H} [\theta x_2 + (1-\theta)x_1] \leqslant \theta x_2^T \mathbf{H} x_2 + (1-\theta)x_1^T \mathbf{H} x_1 .$$

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

4. Комплексный метод

Трудности, встречающиеся при попытке использовать существовавшие ранее методы поиска, подтолкнули Бокса в 1964 году к созданию своего метода. По существу, он является модификацией симплексного метода Нелдера - Мида, однако позволяет учитывать ограничения. Бокс назвал его комплексным методом. Решаемая задача состоит в минимизации функции f(х) = f(x1, х2, ..., хn), где $$x$$ определяется явными ограничениями $$l_j \leqslant x_j \leqslant u_j \quad \text{при } j=1,2,\ldots,n,$$ а также неявными ограничениями$$g_i(x) \leqslant b_i \quad \text{при } i=1,2,\ldots,m.$$

Если целевая функция f(х) выпукла и функции gi(x) тоже выпуклы, то задача будет иметь единственное решение. Значения lj и uj являются нижней и верхней границами переменных. Если в конкретной задаче заданные переменные теоретически не имеют ограничений, то предположение о наличии у них "безопасных" границ, т.е. границ, включающих оптимум, позволит применить комплексный метод.

Данный метод является итерационным. В нем предполагается, что известны значения n и m, lj и uj и начальная точка x1, удовлетворяющая всем ограничениям (см. неравенства (4.1) и (4.2)). В первую очередь необходимо выбрать к точек, которые удовлетворяют ограничениям, а также вычислить целевую функцию во всех k точках. Множество этих точек называется комплексом. Бокс обнаружил, что k должно быть больше (n + 1) - числа точек, используемых в симплексном методе Нелдера-Мида и положил k = 2n.

Как упоминалось выше, предполагается, что точка k1, удовлетворяющая всем ограничениям, задана. Остальные точки, удовлетворяющие неравенству (4.1), могут быть выбраны следующим образом:$$x_{ij} = l_j + r (u_j - l_j)$$

для j = 1,2,...,n и i = 2,3,...,k, где r - псевдослучайная равномерно распределенная переменная в интервале (0;1).

Точки, выбираемые в соответствии с уравнением (4.3) для данного j будут автоматически удовлетворять неравенству (4.1). Если эти точки удовлетворяют также неравенству (4.2), то они принимаются в качестве начальных точек комплекса. Если точка, выбранная в соответствии с уравнением (4.3), не удовлетворяет неравенству (4.2), то она смещается на половину расстояния до центра тяжести множества уже принятых точек, т.е. формируется точка$$x'_i = \frac{(x_i + x_c)}{2} ,$$ где$$x_c = \frac{1}{i-1} \sum_{e=1}^{i-1} x_e$$

Если точка в соотношении (4.4) все еще не является допустимой, то описанная соотношением (4.3) процедура повторяется вновь до тех пор, пока точка не станет допустимой. Если функция gi(x) выпукла, то в конце концов ограничения будут выполняться. Конечно, поскольку точка x1 находится внутри области ограничений, то комплекс будет состоять из допустимых точек.

Удобно упорядочить точки комплекса в соответствии со значениями функции. Процедуру инициализации комплекса можно описать с помощью блок-схемы (рис. 12.5).

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

1. Найти точку с наибольшим значением функции xh и найти центр x0 остальных (k - 1) точек.

2. Попытаемся сместиться от точки xh и получить при этом точку xr, отражением точки xh относительно точки x0, используя коэффициент отражения $$\alpha > 1$$, что можно записать как$$x_r = (1 + \alpha)x_0 - \alpha x_h .$$

3. Проверить, является ли точка xr допустимой.

а). Если точка xr не является допустимой и не выполняется ограничение для lj, то полагаем xrj = lj + 10-6 ; если не выполняется ограничение для uj то полагаем xrj = uj - 10-6

б). Если не выполняются ограничения, то точку xr, перемещают на половину расстояния между xr и центром x0, т.е.$$x_r \; \text{(новое)} \; = (x_r + x_0)/2.$$

Затем производится повторная проверка на допустимость и шаг 3 повторяется до тех пор, пока не будет получена допустимая точка.

4. Если точка xr является допустимой, то вычисляется значение функции f(xr) и сравнивается с f(xk) - наибольшим значением функции.

Если f(хr) > f(xk), т.е. "хуже", чем наибольшее значение, полученное ранее, то точка xr смещается к центру x0 на половину расстояния между ними, т.е.$$x_r \; \text{(новое)} \; = (x_r + x_0)/2.$$ и процесс возвращается на шаг 3.

5. Если f(xr) < f(хk), то точка x заменяется на точку xr, затем точки и значения функции комплекса снова упорядочиваются.

6. Вычисляются две величины, использующиеся при проверке сходимости метода: среднее квадратическое отклонение $$\sigma$$ для k значений функции и максимальное расстояние dm между двумя точками комплекса. Первая величина вычисляется как$$\sigma = \left\{ \sum_{e=1}^k [f(x_e) - \bar{f}]^2 / k \right\}^{1/2} ,$$ где$$\bar{f} = \frac{1}{k} \sum_{e=1}^k f(x_e) ,$$ но для вычисления $$\sigma^2$$ лучше использовать формулу$$\sigma^2 = \left. \left\{ \sum_{e=1}^k f(x_e)^2 - \frac{[\sum f(x)]^2}{k} \right\} \right/ k.$$

7. Величины $$\sigma^2$$ и dm проверяются на сходимость. Если обе эти величины достаточно малы, то процедура поиска минимума заканчивается. В противном случае необходимо вернуться на шаг 1 и повторить процедуру.

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

Bы6op k = 2n и $$\alpha = 1,3$$ является эмпирическим правилом, предложенным Боксом. Первое значение частично предотвращает преждевременное сжатие комплекса. Коэффициент отражения $$\alpha > 1$$ позволяет комплексу расширяться и перемещаться в нужном направлении. Перемещения на половину расстояния от начальной точки к центру сжимают комплекс. Поэтому комплекс может перемещаться внутри допустимой области вдоль границ и огибать углы в местах пересечения ограничений.

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