Многометрическая (многомерная) оптимизация. Методы многомерной оптимизации: метод Хука – Дживса, метод Нелдера – Мида, метод полного перебора, метод покоординатного спуска, метод градиентного спуска

2. Метод Нелдера – Мида.

Метод Нелдера — Мида (называется также поиском по деформируемому многограннику) является развитием симплексного метода Спендли, Хекста и Химсворта. Множество (n + 1) -й равноудаленной точки в n -мерном пространстве называется регулярным симплексом. Эта конфигурация рассматривается в методе Спендли, Хекста и Химсворта. Следовательно, в двумерном пространстве симплексом является равносторонний треугольник, а в трехмерном пространстве — правильный тетраэдр. Идея метода состоит в сравнении значений функции в (n + 1) вершинах симплекса и перемещении симплекса в направлении оптимальной точки с помощью итерационной процедуры. В симплексном методе, предложенном первоначально, регулярный симплекс использовался на каждом этапе. Нелдер и Мид предложили несколько модификаций этого метода, допускающих, чтобы симплексы были неправильными. В результате получился очень надежный метод прямого поиска, являющийся одним из самых эффективных, если $$n \le 6$$.

В методе Спендли, Хекста и Химсворта симплекс перемещается с помощью трех основных операций: отражения, растяжения и сжатия. Смысл этих операций станет понятным при рассмотрении шагов процедуры.

A. Найдем значения функции f1=f(x1),f2=f(x2) ... fn+1=f(хn+1) в вершинах симплекса.

Б. Найдем наибольшее значение функции fh, следующее за наибольшим значением функции fg наименьшее значение функции fl и соответствующие им точки xh, xg, xl.

B. Найдем центр тяжести всех точек, за исключением точки хh. Пусть центром тяжести будет$$x_0 = \frac{1}{n} \sum_{i \neq h} x_i$$ и вычислим f(x0)=f0.

Г. Удобнее всего начать перемещение от точки xh. Отразив точку xh относительно точки х0, получим точку хr и найдем f(xr) = fr. Операция отражения иллюстрируется рис.10.3. Если а > 0 - коэффициент отражения, то положение точки хr определяется следующим образом:$$x_r - x_0 = a (x_0 - x_h)$$ т.е.$$x_r = (1+a) x_0 - ax_h$$

Замечание: $$a = | x_r – x_0 | / | x_0 - x_h |$$

Д. Сравним значения функций fr и fl.

1. Если fr < fl, то мы получили наименьшее значение функции. Направление из точки x0 в точку xr наиболее удобно для перемещения. Таким образом, мы производим растяжение в этом направлении и находим точку xe и значение функции fe = f(xe). Рисунок 10.4 иллюстрирует операцию растяжения симплекса.

Коэффициент растяжения $$\gamma > 1$$ можно найти из следующих соотношений:$$x_e - x_0 = \gamma (x_r - x_0)$$ т.е.$$x_e = \gamma x_r + (1 - \gamma) x_0$$

Замечание: $$\gamma = | x_e – x_0 | / | x_r – x_0 |$$

а) Если fe < fl, то заменяем точку xh на точку xe и проверяем (n + 1) -ую точку симплекса на сходимость к минимуму (см. шаг И). Если сходимость достигнута, то процесс останавливается; в противном случае возвращаемся на шаг Б.

б) Если fe > fl, то отбрасываем точку xe. Очевидно, мы переместились слишком далеко от точки x0 к точке xr. Поэтому следует заменить точку xh на точку xr, в которой было получено улучшение (шаг Д, 1), проверить сходимость и, если она не достигнута, вернуться на шаг Б.

2. Если fr > fl, но fr < fg, то xr является лучшей точкой по сравнению с другими двумя точками симплекса и мы заменяем точку xh на точку xr и, если сходимость не достигнута, возвращаемся на шаг Б, т.е. выполняем пункт 1,6, описанный выше.

3. Если fr > fl и fr > fg, перейдем на шаг Е.

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

1. Если fr > fh, то переходим непосредственно к шагу сжатия Е,2.

Если fr < fh, то заменяем точку xh на точку xr и значение функции fh на значение функции fr. Запоминаем значение fr > fg из шага Д,2, приведенного выше. Затем переходим на шаг Е,2.

2. В этом случае fr > fh, поэтому ясно, что мы переместились слишком далеко от точки xh к точке x0. Попытаемся исправить это, найдя точку xc (а затем fc ) с помощью шага сжатия, показанного на рис. 10.5. Если fr > fh, то сразу переходим к шагу сжатия и находим точку xc из соотношения$$x_c - x_0 = \beta (x_h - x_0)$$ где $$\beta (0 < \beta < 1)$$ - коэффициент сжатия. Тогда$$x_c = \beta x_h + (1 - \beta) x_0$$ Если fr < fh, то сначала заменим точку xh на точку xr, а затем произведем сжатие. Тогда точку xc найдем из соотношения$$x_c - x_0 = \beta(x_r - x_0)$$ т.е.$$x_c = \beta x_r + (1-\beta) x_0$$ (рис. 10.6).

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

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

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

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

Таким образом, точка xj заменяется на точку xl = (xl + xi)/2, т.е. заменяем точку xi точкой (xi - xl)/2 (2.6). Затем вычисляем fi для i = 1, 2, ...,(n+1), проверяем сходимость и, если она не достигнута, возвращаемся на шаг В.

И. Проверка сходимости основана на том, чтобы стандартное отклонение (n + 1) -го значения функции было меньше некоторого заданного малого значения е. В этом случае вычисляется$$\sigma^2 = \sum_{i=I}^{n+1} (f_i - \overline{f})^2 / (n+1)$$ где $$\overline{f} = \sum f_i / n+1$$.

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

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

Коэффициенты $$\alpha, \beta, \gamma$$ в вышеприведенной процедуре являются соответственно коэффициентами отражения, сжатия и растяжения. Нелдер и Мид рекомендуют брать $$\alpha = 1, \beta = 0,5 \; \text{и} \; \gamma = 2$$. Рекомендация основана на результатах экспериментов с различными комбинациями значений. Эти значения параметров позволяют методу быть эффективным, но работать в различных сложных ситуациях.

Начальный симплекс выбирается на наше усмотрение. В данном случае точка x1 является начальной точкой, затем формируются точки$$\begin{gathered} x_2 = x_1 + ke_1 \\ x_3 = x_1 + ke_2 \\ x_{n+1} = x_1 + ke_n \end{gathered}$$

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

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

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

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

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

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

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

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

Фиксируем теперь переменные: $$x_1=x_1^1, x_3=x_3^0,...,x_n=x_n^0$$ и рассмотрим функцию f как функцию одной переменной $$x_2:f(x_1^1, x_2, x_3^0,\ldots,x_n^0)$$. Изменяя x2, будем опять двигаться от начального значения $$x_2=x_2^0$$ в сторону убывания функции, пока не дойдем до минимума при $$x_2=x_2^1$$. Точку с координатами $$(x_1^1, x_2, x_3^0,\ldots,x_n^0)$$ обозначим через M2, при этом $$f(M^1) \ge f(M^2)$$. Проведем такую же минимизацию целевой функции по переменным x3,x4,...,xn. Дойдя до переменной 1 и продолжим процесс.

Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек M0,M1,M2,... которой соответствует монотонная последовательность значений функции $$f(M^0) \ge f(M^1) \ge f(M^2) \ldots$$ Обрывая ее на некотором шаге k, можно приближенно принять значение функции f(Mk) за ее наименьшее значение в рассматриваемой области (рис. 10.10).

Отметим, что данный метод сводит задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Если целевая функция f(x1,x2,\ldots,xn задана явной формулой и является дифференцируемой, то мы можем вычислить ее частные производные и использовать их для определения направления убывания функции по каждой переменной и поиска соответствующих одномерных минимумов.

На рис. 10.10. изображены линии уровня некоторой функции двух переменных u=f(x,y). Вдоль этих линий функция сохраняет постоянные значения, равные 1, 3, 5, 7, 9. Показана траектория поиска ее наименьшего значения, которое достигается в точке O, с помощью метода покоординатного спуска.

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

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

Функция Розенброка:$$f(x_1, x_2) = 100(x_2 - x_1^2)^2 + (1-x_1)^2; \quad x^* = (1; 1).$$

Функция Пауэлла:$$\begin{aligned} f(x)=(x_1+10x_2)^2+5(x_3-x_4)^2+(x_2-2X_3)^4+10(x_1-x_4)^4; \\ x^*=(0;0;0;0). \end{aligned}$$

Двумерная экспоненциальная функция:$$\begin{aligned} f(x_1,x_2)=\sum_a [(e^{-ax_1}-e^{-ax_2})-(e^{-a}-e^{-10a})]^2, \\ \text{где} \; a=0,1(0,1)1^*; \; x^*=(1;10). \end{aligned}$$

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

Рассмотрим функцию f считая для определенности, что она зависит от трех переменных х, у, z. Вычислим ее частные производные df/dx, df/dy, df/dz и образуем с их помощью вектора, который называют градиентом функции:$$grad \; f(x,y,z)=\frac{df}{dx}(x,y,z)i+\frac{df}{dy}(x,y,z)j+\frac{df}{dz}(x,y,z)k.$$

Здесь i, j, k - единичные векторы, параллельные координатным осям. Частные производные характеризуют изменение функции по каждой независимой переменной в отдельности. Образованный с их помощью вектор градиента дает общее представление о поведении функции в окрестности точки (x, y, z). Направление этого вектора является направлением наиболее быстрого возрастания функции в данной точке. Противоположное ему направление, которое часто называют антиградиентным, представляет собой направление наиболее быстрого убывания функции. Модуль градиента$$|grad \; f(x,y,z)|=\sqrt{ \left(\frac{df}{dx}(x,y,z)i\right)^2+ \left(\frac{df}{dy}(x,y,z)j\right)^2+ \left(\frac{df}{dz}(x,y,z)k\right)^2}$$ определяет скорость возрастания и убывания функции в направлении градиента и антиградиента. Для всех остальных направлений скорость изменения функции в точке (x, y, z) меньше модуля градиента. При переходе от одной точки к другой как направление градиента, так и его модуль, вообще говоря, меняются. Понятие градиента естественным образом переносится на функции любого числа переменных.

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

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

Метод требует вычисления градиента целевой функции на каждом шаге. Если она задана аналитически, то это, как правило, не проблема: для частных производных, определяющих градиент, можно получить явные формулы. В противном случае частные производные в нужных точках приходится вычислять приближенно, заменяя их соответствующими разностными отношениями:$$\frac{df}{dx}\approx \frac{f(x_1,\ldots,x_i+\Delta x_i,\ldots,x_n)- f(x_1,\ldots,x_i,\ldots,x_n)}{\Delta x_i}$$

Отметим, что при таких расчетах $$\Delta x_i$$, нельзя брать слишком малым, а значения функции нужно вычислять с достаточно высокой степенью точности, иначе при вычислении разности$$\Delta f = f(x_1,\ldots,x_i+\Delta x_i,\ldots,x_n)-f(x_1,\ldots,x_i,\ldots,x_n)$$ будет допущена большая ошибка.

На рис.10.12 изображены линии уровня той же функции двух переменных u=f(x,y), что и на рис.10.11, и приведена траектория поиска ее минимума с помощью метода градиентного спуска. Сравнение рис.10.11 и рис.10.12 показывает, насколько более эффективным является метод градиентного спуска.