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

Теория

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

а) формулу целевой функции 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-ов считается решением. В противном случае проводится следующая

1.2.Алгоритм метода покоординатного спуска:

Решим эту задачу на 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. На диаграмме хорошо видны перпендикулярные ломаные линии движения от точки к точке параллельно одной из осей координат.

2. Ход решения:

Дана функция =2*х³-0,6*х²+0,06*х-0,002

1) Открываем чистый лист в MS Exel. Для выполнения 1 шага строим таблицу, состоящую из 4 столбцов и 13 строк.

Вносим следующие элементы:

1 ст. – Х1

2 ст. – Х2

3ст. - F

4 ст. – E (const)

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

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

.

3)

4)

Вывод:

При выполнении лабораторной работы №3 мы познакомились с многомерными методами оптимизациями: методом координатного спуска, методом1и1методом1наискорейшего1спуска.
При выполнении практической части лабораторных работ, я применила полученные теоретические знания и научилась использовать метод покоординатного спуска для решения задач с помощью табличного процессора MS Excel.

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