Глава III
Безусловная минимизация функций нескольких переменных без использования производных
Введение. Все рассмотренные нами методы (за исключением метода золотого сечение и метода дихотомии) предполагают дифференцируемость целевой функции. Далеко не каждая прикладная задача этому требованию удовлетворяет, поэтому большое значение имеют такие методы поиска минимизации целевой функции, в которых не используются производные, даже первого порядка. Весь алгоритм должен строиться на вычислении только значений целевой функции.
3.1. Метод жесткого многогранника
Суть метода разберем на частном случае, когда целевая функция зависит только от двух переменных.
Постановка задачи – найти такие значения x1 и x2, при которых целевая функция
(3.1)
достигает минимума.
З
адаем
три точки
,
так, что они образуют равносторонний
треугольник, рис. 3.1.
П
усть
,
,
значения целевой функции в каждой из
вершин треугольника. Среди трех вершин
найдем такую, в которой значение
наибольшее. Допустим, что это точка
.
Тогда на стороне
строится новый равносторонний треугольник
с вершинами
.
Вновь определяется вершина с наибольшим
значением целевой функции и т.д. Рис.
3.2. иллюстрирует процесс поиска точки
минимума
методом жесткого многогранника.
Методу присущи недостатки. Размеры многогранника (в данном случае треугольника) остаются за все время поиска неизменными, а потому при больших размерах многогранника точность решения задачи оказывается не высокой, при малых размерах получаем относительно большое время поиска решения. Очевидно, что необходимо изменять размеры многогранника в процессе поиска.
Метод деформируемого многогранника
Найти такую точку
,
в которой целевая функция
(3.2)
достигает минимума.
Вначале выбирается
базовая точка
,
а затем строится правильный базовый
многогранник, у которого одна из вершин
лежит в точке
.
Правильные многогранники изучались
еще Евклидом. Воспользуемся этими
результатами и координаты остальных n
вершин
многогранника вычислим по формулам
Евклида, т.е.
(3.3)
где i – номер вершины, j – номер координаты,
,
;
; (3.4)
,
причем
– размер ребра многогранника. Так при
,
многогранник имеет ребро единичной
длины. Пусть, например,
,
,
тогда для двух остальных вершин
и
согласно (3.3), (3.4) имеем:
;
,
;
.
Таким образом,
;
.
Расположение точек , , при показано на рис. 3.3.
П
усть
– i-я
вершина многогранника, k
– номер итерации (номер многогранника).
Обозначим через l
и h
номера вершин, в которых целевая функция
достигает соответственно наименьшего
и наибольшего значения, т.е.
(3.5)
Находим центр
тяжести вершин многогранника, исключая
вершину
,
т.е.
(3.6)
В развернутом виде формула (3.6) записывается, как
,
. (3.7)
Рассмотрим операцию
«отражение», т.е. образование на
продолжении прямой
новой точки в
соответствии с равенством, рис. 3.4.
. (3.8)
При
.
Рекомендуется назначать
.
Возможны три случая
a)
; (3.9)
б)
; (3.10)
в)
. (3.11)
В случае а выполняется «растяжение», т.е. вычисляется точка
. (3.12)
Рекомендуется
назначать
.
Точку
заменяют на лучшую из точек
,
,
т.е.
(3.13)
и переходят к k+1-й итерации.
В случае б) выполняется «сжатие», т.е. определяется точка по правилу
. (3.14)
Рекомендуется
.
(3.15)
Из точек и выбирается лучшая и ей присваивается номер h, т.е. полагают, что
(3.16)
и затем осуществляется переход к k+1-й итерации. Операция (3.16) понимается как «некоторое улучшение наихудшей вершины».
В случае b)
выполняется операция под названием
«редукция». При этом все векторы
уменьшаются вдвое, т.е.
,
(3.17)
(многогранник сжимается к вершине с наименьшим значением целевой функции).
Эта операция одновременно является переходом к k+1-й итерации.
Процесс вычислений заканчивается, если
, (3.18)
где
– малое положительное число.
Вместо условия (3.18) можно использовать расстояние наиболее удаленной вершины от многогранника. Оно не должно превышать величины , т.е.
, (3.19)
где
.
Преимущества метода – логика и формулы просты, невысок объем требуемой памяти.
Недостатки – диапазоны изменения компонент вектора x – различные. Они могут отличаться на несколько порядков. Это отрицательно сказывается на процессе вычислений. Лучше вначале провести масштабирование всех переменных, чтобы они изменялись в одинаковых пределах.