7.3.3 Комплексный метод Бокса

Этот метод представляет модификацию метода деформируемого многогранника и предназначен для решения задачи нелинейного программирования с ограничениями-неравенствами. Для минимизации функции nпеременныхf(x)вn-мерном пространстве строят многогранники, содержащиеq п+1 вершин. Эти многогранники называюткомплексами,что и определило наименование метода.

Введем следующие обозначения:

х[j, k] (х₁[j, k], …,х_i[j, k], …,х_n[j, k])^T, (7.50)

где j 1, ...,q; k 0, 1, 2, ... -j-я вершина комплекса наk-м этапе поиска;

х[h, k] -вершина, в которой значение целевой функции максимально, т. е.f(x[h, k]) max{f(x[l,k]), ..., f(x[q, k])}; x[h,k]- центр тяжести всех вершин, за исключениемх[h, k].Координаты центра тяжести вычисляются по формуле

, i l, ...,n. (7.51)

Алгоритм комплексного поиска состоит в следующем. В качестве первой вершины начального комплекса выбирается некоторая допустимая точка х[1, 0]. Координаты остальныхq-1 вершин комплекса определяются соотношением

х_j[j,0] а_i+ r_i(b_i - a_i),i 1, ...,п;j 2, ...,q. (7.52)

Здесь а_i,b_i- соответственно нижнее и верхнее ограничения на переменнуюх_i', r_i - псевдослучайные числа, равномерно распределенные на интервале [0, 1]. Полученные таким образом точки удовлетворяют ограниченияма х b ,однако ограниченияh_j(x) 0 могут быть нарушены. В этом случае недопустимая точка заменяется новой, лежащей в середине отрезка, соединяющего недопустимую точку с центром тяжести выбранных допустимых вершин. Данная операция повторяется до тех пор, пока не будут выполнены все ограничения задачи. Далее, как и в методе деформируемого многогранника, на каждой итерации заменяется вершинах[h, k],в которой значение целевой функции имеет наибольшую величину. Для этогох[h, k] отражается относительно центра тяжестих[l, k] остальных вершин комплекса. Точках[р, k], заменяющая вершинух[h, k], определяется по формуле

x[p, k] (a+1)х[l, k] + ax[h, k], (7.53)

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

Если f(x[р, k]) f(x[h, k]),то новая вершина оказывается худшей вершиной комплекса, В этом случае коэффициентауменьшается в два раза. Если в результате отражения нарушается какое-либо из ограничений, то соответствующая переменная просто возвращается внутрь нарушенного ограничения. Если при отражении нарушаются ограниченияh_j(x) 0. то коэффициента каждый раз уменьшается вдвое до тех пор, пока точках[р, k] не станет допустимой. Вычисления заканчиваются, если значения целевой функции мало меняются в течение пяти последовательных итераций: |f(х[l, k+1])– f(х [l,k])| ,k 1, ..., 5, где- заданная константа. В этом случае центр тяжести комплекса считают решением задачи нелинейного программирования.

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

Выбор начальной точки допустимой области

Для применения прямых методов решения задач нелинейного программирования требуется знание некоторой допустимой начальной точки области G . Если структура этой области сложная, отыскание такой точки представляет серьезные трудности. Произвольно выбранная начальная точка в общем случае может удовлетворять только части ограничений. Следовательно, необходим алгоритм, приводящий из произвольной точки в допустимую область. На практике для получения начального вектора применяют тот же метод, которым решают исходную задачу нелинейного программирования. Рассмотрим один из способов отыскания такого вектора.

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

J₁ {j|h_j()0,j 1, …,m}; (7.54)

J₂ {j|h_j()0,j 1, …,m}; (7.55)

Введем дополнительную переменную и сформулируем задачу поиска допустимой точки следующим образом: найти минимум функции z при ограничениях:

h_j(х) 0,j J₁;

h_j(х)- 0,j J₂; (7.57)

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

, (7.58)

то точка является допустимым решением сформулированной задачи. Так как областьGисходной задачи не пуста, то существует такая точка ,что

h(x) 0,j 1, …,m. (7.59)

Следовательно, минимальное значение меньше нуля. В силу этого после конечного числа шагов некоторого прямого алгоритма будут полученыx[0],, такие, что 0, и условия задачи удовлетворяются. Точках[0] и принимается в качестве начальной для исходной задачи нелинейного программирования.