Сравнительный анализ методов оптимизации
Сравнение методов исключения отрезков. При сравнении прямых методов минимизации обычно учитывают количество N значений f (x), гарантирующее заданную точность определения точки х* тем или иным методом. Чем меньше N, тем эффективнее считается метод. При этом вспомогательные операции такие, как выбор пробных точек, сравнение значений f (x) и т.п., не учитываются. Во многих практических случаях определение значений целевой функции требует больших затрат (например, времени ЭВМ или средств для проведения экспериментов) и вспомогательными вычислениями можно пренебречь. А эффективность метода минимизации особенно важна именно в таких случаях, поскольку позволяет сократить указанные затраты.
Эффективность методов минимизации можно также сравнивать, на основании гарантированной точности e (N) нахождения точки х*, которую они обеспечивают в результате определения N значений f (x). Метод золотого сечения считают более точным, чем метод дихотомии, однако разница в точности в данном случае незначительна.
2.1.3 Практическое применение прямых методов одномерной безусловной оптимизации
Пусть заданы следующие параметры:

Примем
и
.
Тогда
(рисунок 7).

Рисунок 7 - Поведение исходной функции на заданном отрезке
Проведем несколько итерации методом дихотомии:

Поскольку f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда для следующей итерации:

Так как f (x1) > f (x2), то a: =x1, b оставляем прежним. Тогда на третьем шаге:

Результаты полного решения данной задачи представлены на рисунке 8. Листинг программы представлен в приложении А.

Рисунок 8 - Получение решения методом дихотомии
Для метода золотого сечения:

Так как f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда для следующей итерации:

Поскольку f (x1) < f (x2), то b: =x2, a оставляем прежним. Тогда на третьем шаге:

И так далее до тех пор, пока не достигнем указанной точности. Полный расчет представлен на рисунке 9. Листинг программы представлен в приложении А.

Рисунок 9 - Получение решения методом золотого сечения
2.2 Методы безусловной минимизации функций многих переменных
Теперь рассмотрим задачи оптимизации, сводящиеся к поиску точек минимума функции многих переменных на всем пространстве. В большинстве случаев такая задача бывает сложнее задачи минимизации функции одной переменной, так как с ростом размерности пространства переменных, как правило, возрастают объем вычислений и сложность алгоритмов, а также затрудняется анализ поведения целевой функции.
2.2.1 Метод циклического покоординатного спуска
Этот метод заключается в последовательной минимизации целевой функции f (x) по направлениям x1 и x2.

Рисунок 10 - Циклический покоординатный спуск.
Опишем этот алгоритм.
Шаг
0. Выбрать х О
En,
критерий достижения
точности e
и шаг
.
Найти f (x1
(0),x2 (0)).
Шаг
1. Принять
x1 (1) = x1 (0) +
.
Определить
f (x1 (1),x2
(0)). Сравнить
полученное
значение с
значением
начальной
функции. Если
f (x1 (1),x2
(0)) < f (x1 (0),x2
(0)), то перейти
к шагу 5, если
же f (x1 (1),x2
(0)) > f (x1 (0),x2
(0)), то перейти
к шагу 2.
Шаг
2. Принять
x1 (1) = x1 (0) -
.
Определить
f (x1 (1),x2
(0)). Сравнить
полученное
значение с
значением
начальной
функции. Если
f (x1 (1),x2
(0)) < f (x1 (0),x2
(0)), то перейти
к шагу 5, если
же f (x1 (1),x2
(0)) > f (x1 (0),x2
(0)), то перейти
к шагу 3.
Шаг
3. Принять
x2 (1) = x2 (0) +
.
Определить
f (x1 (0),x2
(1)). Сравнить
полученное
значение с
значением
начальной
функции. Если
f (x1 (0),x2
(1)) < f (x1 (0),x2
(0)), то перейти
к шагу 5, если
же f (x1 (0),x2
(1)) > f (x1 (0),x2
(0)), то перейти
к шагу 4.
Шаг
4. Принять
x2 (1) = x2 (0) -
.
Определить
f (x1 (0),x2
(1)). Сравнить
полученное
значение с
значением
начальной
функции. Если
f (x1 (0),x2
(1)) < f (x1 (0),x2
(0)), то перейти
к шагу 4, если
же f (x1 (0),x2
(1)) > f (x1 (0),x2
(0)), то принять
исходную точку
за минимум.
Шаг
5. Проверить
условие достижения
точности
.
Если
в процессе
решения с шагом
не получено
решения, то
принять
![]()
2.2.2 Алгоритм Хука-Дживса
Этот алгоритм содержит две основные процедуры:
а) исследующий покоординатный поиск в окрестности данной точки, предназначенный для определения направления убывания f (х);
б) перемещение в направлении убывания.

Рисунок 11 - Метод Хука-Дживса
Трактовать данный метод можно по-разному. Рассмотрим один из многочисленных вариантов.
Опишем один из алгоритмов данного метода.
Шаг 1. Выбираем начальную точку и находим в ней значение функции.
Шаг
2. Обозначим
координаты
начального
вектора:
.
Тогда, соответственно, угол направления движения
.
Рассчитываем координаты 4-х точек в окрестности начальной по следующим формулам:
![]()
![]()
![]()
![]()
Находим в указанных точках значения функции. Если какое-нибудь из них оказалось меньше значения функции в точке x0, то принимаем его за исходное.
Шаг 3. Сравниваем полученные значения с f (x1 (0),x2 (0)). Если какое-нибудь из них оказалось меньше значения функции в 0-й точке точке, то принимаем его за исходное и переходим к шагу 5.
Шаг
4. Если же все
полученные
значения функции
оказались
больше исходного,
то уменьшаем
шаг
и переходим
к шагу5.
Шаг 5. Проверить условие достижения точности
.
Если данное условие не выполнено, возвращаемся к шагу 2.
2.2.3 Практическое применение прямых методов безусловной многомерной оптимизации
Пусть заданы следующие условия:

Тогда по методу циклического покоординатного спуска будет выполнен счет следующего вида:


Т. к.
,
будем двигаться
в противоположную
сторону по оси
абсцисс с тем
же шагом:

,
поэтому
продолжаем
двигаться
дальше с тем
же шагом в данном
направлении
до достижения
указанной
точности, в
противном
случае уменьшаем
шаг (
):

Результаты работы данного алгоритма представлены на рисунке 12. Листинг программы приведен в приложении Б.

Рисунок 12 - Решение поставленной задачи методом спуска
Перейдем
к методу Хука-Дживса.
Обозначим
координаты
начального
вектора:
.
Тогда, соответственно, угол направления движения
.
Найдем значения функции 4-х точек в окрестности начальной:
![]()
![]()
![]()
![]()
Минимальное значение функция принимает в точке2, поэтому движемся в заданном направлении 2 пока идет уменьшение функции до достижения указанной точности, в противном случае уменьшаем шаг
(
):
![]()
Конечный результат получен на ЭВМ за 36 итераций. Результат представлен на рисунке 13. Листинг программы приведен в приложении Б.

Рисунок 12 - Решение поставленной задачи методом спуска
2.2.4 Минимизация по правильному симплексу
Правильным симплексом в пространстве En называется множество из n + 1 равноудаленных друг от друга точек (вершин симплекса). Отрезок, соединяющий две вершины, называется ребром симплекса.
В пространстве E2 правильным симплексом является совокупность вершин равностороннего треугольника, в E3 - правильного тетраэдра.
Если х0 - одна из вершин правильного симплекса в En то координаты остальных п вершин х1,. ., хn можно найти, например, по формулам:
(6), где
d1
,
d2
,
a-
длина ребра.
Вершину х0
симплекса,
построенного
по формулам
(6), будем называть
бaзовой.
В алгоритме
симплексного
метода используется
следующее
важное свойство
правильного
симплекса. По
известному
симплексу можно
построить новый
симплекс отрaжением
какой-либо
вершины, например,
хk симметрично
относительно
центра тяжести
хc остальных
вершин симплекса.
Новая и старая
вершины
и
хk связаны
соотношением:
,
где xc
.
В результате
получается
новый правильный
симплекс с тем
же ребром и
вершинами
=2xc
- хk, хi,
i= 0,. ., n, i№
k. Таким
образом, происходит
перемещение
симплекса в
пространстве
Еn. На
рисунке 13 представлена
иллюстрация
этого свойства
симплекса в
пространстве
Е2.

Рисунок
13 - Построение
нового симплексa
в E2 отрaжением
точки х: a
- нaчaльный
симплекс х0,
х1,
;
б - новый симплекс
х0, х1,
;
центр отрaжения
- точкa xc
= (х0+ х1) /2
Поиск точки минимума функции f (x) с помощью правильных симплексов производят следующим образом. На каждой итерации сравниваются значения f (х) в вершинах симплекса. Затем проводят описанную выше процедуру отражения для той вершины, в которой f (х) принимает наибольшее значение. Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f (х). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f (x) заканчивают, когда либо ребро симплекса, либо разность между значении функции в вершинах симплекса становятся достаточно малыми. Опишем один из вариантов алгоритма этого метода.
Шаг
0. Выбрать параметр
точности e,
базовую точку
х0, ребро
и построить
начальный
симплекс по
формулам:

Вычислить f (х1 (0),x2 (0)).
Шаг 1. Вычислить значения f (х) в вершинах симплекса х1,. ., xn.
Шаг 2. Упорядочить вершины симплекса х0,. ., хn так, что бы f (х1 (0),x2
(0)) Ј …Ј Јf (х1) Ј f (хn-1) Ј f (хn).
Шаг 3. Найти среднее значение функции:
.
Проверить
условие
из учета того,
что:
(3.38)
Если оно выполнено, то вычисления прекратить, полагая х* » х0, f * » f (x0). В противном случае перейти к шагу 4.
Шаг 4. Найти
и выполнить отражение вершины хn. К примеру, для отражения вершины А следует найти точку
.
Тогда отраженная вершина будет иметь вид:
.
Если f (Е) <f (xn), то перейти к построению нового симплекса, иначе - перейти к шагу 5.
Шаг 5. Перейти к новому правильному симплексу с вдвое меньшим ребром (редуцирование), считая базовой вершиной х0. Остальные n вершин симплекса найти по формуле хi = (хi + х0) /2, i=1,. ., n. Перейти к шагу 1.
Геометрическая иллюстрация работы алгоритма в пространстве показана на рисунке 14, где точки х0, х1, х2 - вершины начального симплекса, а пунктиром указаны процедуры отражения.

![]()
Рисунок
14 - Поиск точки
минимума функции
с
помощью правильных
симплексов
в пространстве
![]()
Замечания:
1. Следует иметь в виду, что если функция f (х) многомодальна, то описанным методом может быть найдена точка локального, а не глобального минимума f (х).
2. Если ограниченность снизу целевой функции не очевидна, то в алгоритм метода следует включить дополнительную процедуру останова.
2.2.5 Поиск точки минимума по деформируемому симплексу
Алгоритм, описанный в разд.2.2.4, можно модифицировать, добавив к процедуре отражения при построении нового симплекса процедуры сжатия и растяжения. А именно, положение новой вершины вместо вершины хn, соответствующей наибольшему значению функции, находится сравнением и выбором наименьшего среди значений целевой функции в точках;
(7)
Геометрическая иллюстрация этих процедур для пространства E2 приведена на рисунках 15 и 16.

Рисунок 15 - Пробные точки z1,z2,z3,z4 для перехода к новому симплексу

Рисунок 16 - Новые симлексы, полученные в результате процедур сжатия (а, б); отражения (в); растяжения (г).
Так как величина a О (0;
1), то выбор точек z1 и z2 соответствует сжатию симплекса; b » 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит к растяжению симплекса. Численные эксперименты показывают, что этот алгоритм хорошо работает в пространстве En для n Ј 6. Отметим, что при деформациях утрачивается свойство правильности исходного симплекса. Поэтому, не стремясь к правильности начального симплекса, его строят из произвольной базовой точки х0 О En, по формулам
,
(8)
где e i - i-й базисный вектор; a- параметр симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек zi в формулах (9): a = 1/2, b = 1 и g =2.
Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.
Шаг 0. Выбрать параметр точности e, параметры a, b и g, базовую точку х0, параметр a и построить начальный симплекс. Вычислить f (х0).
Шаг 1. Вычислить значения функции в вершинах симплекса х1,..., xn.
Шаг 2. Упорядочить вершины х0,..., xn так, чтобы f (х0) Ј … Ј f (хn).
Шаг 3. Проверить достижение заданной точности. Если оно выполняется, то вычисления завершить, полагая х * » х0, f * » f (х0). Иначе - перейти к шагу 4.
Шаг
4. Найти
и
пробные точки
zk,
k=1, …, 4 пo
формулам (9). Найти
f (z*) = min
f (zk).
Если f (z*)
< f (zn).
то положить
xn=z*
и перейти к
шагу 2. Иначе -
перейти к шагу
5.
Шаг 5. Уменьшить симплекс, полагая хi = (хi + х0) /2, i = 1,. ., n и перейти к шагу 1.
Замечание. Для того чтобы избежать сильной деформации симплекса, алгоритм иногда дополняют процедурой обновления. Например, после N шагов алгоритма из точки х0 снова строят симплекс, полагая а = ||x0-xn||.
С теоретической точки зрения описанные методы минимизации слабо исследованы, однако практика показывает их работоспособность.
2.2.6 Практическая реализация симплексных методов
Пусть заданы следующие условия:

Для первой вершины:

Для второй вершины:

Для третьей вершины:

Наибольшее значение функция принимает в точке2, ее и будем отражать. Для этого найдем точку С, лежащую между 1-й и 3-й точками:

Рассмотрим метод симплекса.
Находим координаты отраженной вершины Е и значение в ней функции:

Т. к.
,
то строим новый
симплекс на
вершинах Е,1 и
3 и повторяем
эту операцию
до тех пор, пока
среднеквадратичное
отклонение
не примет указанной
величины, в
противном
случае приступаем
к редуцированию
- уменьшению
размеров симплекса.
Результат рабочей программы представлен на рисунке 17. Листинг приведен в приложении В.

Рисунок 17 - Практическая реализация симплекс-метода
Перейдем к методу деформируемого симплекса.
Введем коэффициенты
уменьшения
и увеличения:
.
Найдем значения функции 4-х точек в окрестности начальной:
![]()
![]()
![]()