МНОГОМЕРНЫЕ ЗАДАЧИ ОПТИМИЗАЦИИ

2.1. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ: МЕТОД ПОКООРДИНАТНОГО СПУСКА.

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

а) формулу целевой функции f(х₁,х₂,..., х_n),

б) Е - точность нахождения значений независимых переменных, при которых функция достигает минимума,

в) начальные приближения х₁₀,х₂₀..., х_n0.

Зафиксируем все значения х-ов в виде начальных приближений, кроме первого. Тогда f(х₁, х₂₀..., х_n0) - функция одной переменной х₁. Решая задачу одномерной оптимизации, найдем минимум этой функции по координате х₁ при фиксированных остальных координатах – х_i1. В этом состоит первый шаг процесса оптимизации, заключающийся в спуске по координате x₁.

Зафиксируем теперь все координаты, кроме x₂. Снова решая одномерную задачу оптимизации, находим минимум функции по координате x₂. Далее процедура повторяется до x_n. На этом заканчивается первая итерация.

Таким образом, метод покоординатного спуска сводит многомерную задачу оптимизации к многократному решению одномерных задач по каждой независимой переменной.

После каждой итерации вычисляется

D = çx_1i+1 - x_1iç + çx_2i+1 - x_2iç +.... +çx_ni+1 - x_niç

и если D<=E, то вычисления прекращаются и последний набор x-ов считается решением. В противном случае проводится следующая итерация.

Пример 2.1.

Число независимых переменных равняется двум. Ограничения отсутствуют. Требуется найти минимум функции

u = (x₂-x₁²)² + (1-x₁)²

из начальной точки (0,5;0,5) c точностью 0,0001.

Проанализировав функцию, заметим, что она будет иметь минимум, равный нулю. Для чего и первое, и второе слагаемое тоже должны быть равны нулю. Откуда координаты точки минимума (1;1).

Решим эту задачу на EXCEL на новом рабочем листе.

Выделим столбец А под значения х₁, столбец В - под значения х₂, в столбец С будем заносить значения целевой функции и, наконец, в столбец D - значения погрешности D.

Занесем в ячейки А3 и В3 значения начальных приближений, равных 0,5 и в ячейку С3 формулу =(В3-А3^2)^2+(1-A3)^2. Скопируем эту формулу в блок ячеек С4:С17. На этом заканчивается подготовительный этап.

1 итерация.

1 шаг. Скопируем содержимое ячейки В3 в ячейку В4. Сделаем текущей ячейку С4. Процесс одномерной оптимизации для нахождения X₁ выполним с помощью подпрограммы EXCEL Поиск решения.

В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С4, а в поле Изменяя ячейки - адрес А4. Щелкнем по кнопке Выполнить и по кнопке ОК. В результате в ячейке А4 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С4 по координате х₁.

2 шаг. Скопируем содержимое ячейки А4 в ячейку А5.

Текущая ячейка С5, меню Сервис- Поиск решения. В открывшемся диалоге в поле Установить целевую ячейку занесем адрес С5, а в поле Изменяя ячейки - адрес В5, Выполнить.

В результате в ячейке В5 получим числовое значение, при котором целевая функция достигает минимального значения в ячейке С5 по координате х₂.

3 шаг. Занесем в ячейку D5 формулу =ABS(A3-A5)+ABS(B3-B5) для вычисления погрешности решения на первом шаге. На этом заканчивается первая итерация.

Вторая и все последующие итерации проводятся аналогично, но с учетом соответствующих адресов ячеек. Например, во второй итерации будут участвовать адреса ячеек в 6 и 7 строках. Результаты проведения первых семи итераций представлены в таблице. Как видно, значения целевой функции уменьшаются от шага к шагу, но метод сходится чрезвычайно медленно.

Можно построить диаграмму изменения на каждой итерации, выделив блок А2:В17 с помощью Мастера Диаграмм, выбрав тип диаграммы XY-точечная и формат 2. На диаграмме хорошо видны перпендикулярные ломаные линии движения от точки к точке параллельно одной из осей координат.

3.

4.

2.2. БЕЗУСЛОВНАЯ ОПТИМИЗАЦИЯ: МЕТОД НАИСКОРЕЙШЕГО СПУСКА.

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

Даны: а) формулу целевой функции f(x₁,x₂,..., x_n),

б) Е - точность нахождения значений независимых переменных, при которых функция достигает минимума,

в) начальные приближения x₁₀,x₂₀..., x_n0,

г) формулы первых частных производных целевой функции по каждой независимой переменной.

С помощью рассмотренного ранее метода покоординатного спуска осуществляется поиск в направлении, параллельном одной из осей координат, до точки минимума в этом направлении.

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

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

Идея метода наискорейшего спуска:

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

Например, для функции двух переменных формулы первой итерации будут иметь вид

u = f(х_1нов,х_2нов) Þ min,

где х_1нов = х₁₀- h(du/dх₁)_X10 и х_2нов = х₂₀ -h(du/dх₂) _X20, а h - длина отрезка от точки нулевого приближения до точки минимума по выбранному направлению. Эта длина определяется методом одномерной оптимизации.

В найденной точке (х_1нов,х_2нов) снова вычисляем градиент, снова определяем направление поиска, снова методом одномерной оптимизации ищем точку минимума. Эти итерации продолжаются до тех пор, пока не выполнится условие прекращения вычислений, а именно: квадратный корень из суммы квадратов частных производных целевой функции должен быть меньше заданной точности Е.

Пример 2.2.

Решим задачу примера 2.1 методом наискорейшего спуска. Для этого прежде всего найдем частные производные целевой функции

u = (х₂-х₁²)² + (1-х₁)²,

du/dх₁ = - 4(х₂-х₁²) х₁-2(1-х₁),

du/dх₂ = 2(х₂-х₁²).

Составляющие антиградиента должны быть взяты с обратным знаком

antigrad u = {- du/dх₁, -du/d х₂ }.

Выделим столбец А под переменную h, столбцы В и С - под х₁,х₂, столбцы D и Е - под составляющие антиградиента, столбцы F и G - под х_1нов,х_2нов, столбец Н - под целевую функцию u, столбец I - под переменную D.

Приведем таблицу формул в соответствующих ячейках для первых двух итераций в строках 21 и 22.

Числовые значения в столбце А появляются в результате выполнения подпрограммы EXCEL Поиск решения для решения задачи одномерной оптимизации. Формулы блока В23:I28 получаются путем копирования в них формул блока В22:I22.

Для этого сделаем текущей ячейку Н21. Дадим команду меню Сервис- Поиск решения. В появившемся диалоге занесем в поле Установить целевую ячейку адрес Н21, а в поле Изменяя ячейки - адрес А21. Щелкнув по кнопке Выполнить, получим новый диалог, в котором щелкнем по кнопке ОК. В результате в ячейке А21 получим значение h, а ячейках F21 и В22 - новое значение Х1, в ячейках G21 и С22 - новое значение Х2.

5.

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

На диаграмме изображены перпендикулярные ломаные линии, причем в отличие от примера 2.1 их направление не совпадает с направлениями координатных осей.

6.

Поиск по сайту: