Основы теории оптимизации (стр. 69 )

В этом случае fr > fh, поэтому ясно, что мы переместились слишком далеко от точки xh к точке x0. Попытаемся исправить это, найдя точку xc (а затем fc) с помощью шага сжатия, показанного на рис. 5.

Рис. 5.

3. Если fr > fh, то сразу переходим к шагу сжатия и находим точку xc из соотношения

где - коэффициент сжатия. Тогда

(6)

Если fr < fh, то сначала заменим точку xh на точку xr, а затем произведем сжатие. Тогда точку xc найдем из соотношения

т. е.

(7)

(рис. 6).

Рис. 6.

Ж. Сравним значения функций fc и fh.

1. Если fc < fh, то заменяем точку xh на точку xc и если сходимость не достигнута, то возвращаемся на шаг Б.

2. Если fc > fh, то очевидно, что все наши попытки найти значение меньшее fh закончились неудачей, поэтому мы переходим на шаг 3.

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

Таким образом, точка xj заменяется на точку

,

т. е. заменяем точку xi точкой

(8)

Затем вычисляем fi для i = 1, 2, ...,(n+1), проверяем сходимость и, если она не достигнута, возвращаемся на шаг В.

И. Проверка сходимости основана на том, чтобы стандартное отклонение (n + 1)-го значения функции было меньше некоторого заданного малого значения е. В этом случае вычисляется

(9)

где

.

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

Шаги этой процедуры представлены в виде блок-схемы на рис. 7.

Рис. 7.

Коэффициенты α, β, γ в вышеприведенной процедуре являются соответственно коэффициентами отражения, сжатия и растяжения. Нелдер и Мид рекомендуют брать α=1, β=0,5, γ=2. Рекомендация основана на результатах экспериментов с различными комбинациями значений. Эти значения параметров позволяют методу быть эффективным, но работать в различных сложных ситуациях.

Начальный симплекс выбирается на наше усмотрение. В данном случае точка x1 является начальной точкой, затем формируются точки

(10)

где k - произвольная длина шага, a ej - единичный вектор.

6.7.3. Метод полного перебора (метод сеток)

Многомерные задачи, естественно, являются более сложными и трудоемкими, чем одномерные, причем обычно трудности при их решении возрастают при увеличении размерности. Для того чтобы лучше почувствовать это, возьмем самый простой по своей идее приближенный метод поиска наименьшего значения функции. Покроем рассматриваемую область сеткой G с шагом h (рис. 8) и определим значения функции в ее узлах. Сравнивая полученные числа между собой, найдем среди них наименьшее и примем его приближенно за наименьшее значение функции для всей области.

Рис. 8.

Как мы уже говорили выше, данный метод используется для решения одномерных задач. Иногда он применяется также для решения двумерных, реже трехмерных задач. Однако для задач большей размерности он практически непригоден из-за слишком большого времени, необходимого для проведения расчетов. Действительно, предположим, что целевая функция зависит от пяти переменных, а область определения G является пятимерным кубом, каждую сторону которого при построении сетки мы делим на 40 частей. Тогда общее число узлов сетки будет равно . Пусть вычисление значения функции в одной точке требует 1000 арифметических операций (это немного для функции пяти переменных). В таком случае общее число операций составит 1011. Если в нашем распоряжении имеется ЭВМ с быстродействием 1 млн. операций в секунду, то для решения задачи с помощью данного метода потребуется 105 секунд, что превышает сутки непрерывной работы. Добавление еще одной независимой переменной увеличит это время в 40 раз. Проведенная оценка показывает, что для больших задач оптимизации метод сплошного перебора непригоден. Иногда сплошной перебор заменяют случайным поиском. В этом случае точки сетки просматриваются не подряд, а в случайном порядке. В результате поиск наименьшего значения целевой функции существенно ускоряется, но теряет свою надежность.

6.7.4. Метод покоординатного спуска

Рассмотрим функцию двух переменных. Ее линии постоянного уровня представлены на рис. 9, а минимум лежит в точке . (Напомним, что линией постоянного уровня называется кривая в двумерном сечении пространства параметров (в данном случае в плоскости (х1, х2), значение функции на которой - константа). Простейшим методом поиска является метод покоординатного спуска. Из точки А мы производим поиск минимума вдоль направления оси х1 и, таким образом, находим точку B, в которой касательная к линии постоянного уровня параллельна оси x1. Затем, производя поиск из точки B в направлении оси x2, получаем точку C, производя поиск параллельно оси x1, получаем точку D, и т. д. Таким образом, мы приходим к оптимальной точке. Любой из одномерных методов, описанных ранее, может быть использован здесь для поиска вдоль оси. Очевидным образом эту идею можно применить для функций n переменных.

Рис. 9.

Рассмотрим данный метод более детально на примере некоторой целевой функции.

Пусть нужно найти наименьшее значение целевой функции u=f(M)=f(x1,x2,...,xn). Здесь через M обозначена точка n-мерного пространства с координатами x1,x2,...,xn:M=(x1,x2,...,xn). Выберем какую-нибудь начальную точку и рассмотрим функцию f при фиксированных значениях всех переменных, кроме первой: . Тогда она превратится в функцию одной переменной x1. Изменяя эту переменную, будем двигаться от начальной точки в сторону убывания функции, пока не дойдем до ее минимума при , после которого она начинает возрастать. Точку с координатами обозначим через M1, при этом .

Фиксируем теперь переменные:

и рассмотрим функцию f как функцию одной переменной . Изменяя x2, будем опять двигаться от начального значения в сторону убывания функции, пока не дойдем до минимума при . Точку с координатами обозначим через M2, при этом . Проведем такую же минимизацию целевой функции по переменным x3,x4,...,xn. Дойдя до переменной xn, снова вернемся к x1 и продолжим процесс.