Сравнительный анализ методов оптимизации (стр. 3 из 5)
Листинг программы реализующей методы дихотомии и золотого сечения представлен в приложении А
3. Численные методы многомерной безусловной оптимизации
Рассмотрим конкретные вычислительные алгоритмы решения задачи безусловной минимизации f (х) ® min, xÎ En, которые опираются только на вычисление значений функции f (х), т.е. прямые методы минимизации. Важно отметить, что для их применения не требуется дифференцируемость целевой функции и даже ее аналитическое задание. Нужно лишь иметь возможность вычислять или измерять значения f (х) в произвольных точках. Такие ситуации часто встречаются в практически важных задачах оптимизации.
3.1 Поиск точки min методом правильного симплекса
В пространстве E2 правильным симплексом является совокупность вершин равностороннего треугольника, в E3 – правильного тетраэдра.
Если х0 – одна из вершин правильного симплекса в En то координаты остальных n вершин х1 ,..,хn можно найти, например, по формулам:
(3.1)где d1
, d2 
, a– длина ребра. Вершину х0 симплекса, построенного по формулам (3.1), будем называть бaзовой.По известному симплексу можно построить новый симплекс отрaжением какой–либо вершины, например, хk симметрично относительно центра тяжести хc остальных вершин симплекса.
Пусть задана функция f(x,y) ® min и начальный базис (x0,y0).
Новая и старая вершины связаны соотношением:
, где xc 
, где уc 
(3.2)Вычисляем значение функции в точках f(A), f(B), f(D) (пусть f(A)<f(B)<f(D)) и присваиваем им номера в порядке возрастания A-1, B-2, D-3.
Вершину с наибольшим номером отражаем относительно центра тяжести стороны 1-2
Координаты вершины Е:
(3.3)Затем вычисляем f(E) и сравниваем f(E) и f(D). Если в отраженной вершине получается меньшее значение функции, то переходят к новому симплексу. В противном случае выполняют еще одну попытку отражения для вершины со следующим по величине значением f (х). Если и она не приводит к уменьшению функции, то сокращают длину ребра симплекса, например, вдвое и строят новый симплекс с этим ребром. В качестве базовой выбирают ту вершину х0 старого симплекса, в которой функция принимает минимальное значение. Поиск точки минимума f (x) заканчивают, когда либо ребро симплекса, либо разность между значении функции в вершинах симплекса становятся достаточно малыми.
3.2 Поиск точки min методом деформируемого симплекса
Алгоритм, описанный выше, можно модифицировать, добавив к процедуре отражения при построении нового симплекса процедуры сжатия и растяжения. Положение новой вершины находится сравнением и выбором наименьшего среди значений целевой функции в точках;
(3.5)Так как величина aÎ (0; 1), то выбор точек z1 и z2 соответствует сжатию симплекса; b» 1, поэтому выбор точки z3 соответствует отражению, а g > 1 и выбор точки z4 приводит к растяжению симплекса. На практике хорошо зарекомендовал себя следующий набор параметров a, b и g для выбора пробных точек zi: a = 1/2, b = 1 и g =2.
Рис. 3.2. Пробные точки z1,z2,z3,z4 для перехода к новому симплексу
Рис. 3.3. Новые симлексы полученные в результате процедур сжатия (а,б); отражения (в); растяжения(г).
Опишем алгоритм метода поиска точки минимума функции по деформируемому симплексу.
Шаг 0 – Шаг 3Аналогичны методу правильного симплекса.
Шаг 4.Найти
и пробные точки zk , k=1, …, 4 пo формулам (3.5). Найти f(z*)= minf(zk). Если f(z*) < f(zn). то положить xn=z* и перейти к шагу 2. Иначе – перейти к шагу 5.3.3 Поиск точки min методом циклического покоординатного спуска
Этот метод заключается в последовательной минимизации целевой функции f(x) сначала по направлению первого базисного вектора е1, затем второго – е2 и т.д. После окончания минимизации по направлению последнего базисного вектора еn цикл повторяется.
Опишем этот алгоритм.
Шаг 0.Выбрать х ÎEn ,критерий достижения точности, величину e. Найти f(x), положить j= 1.
Шаг 1.Решить задачу одномерной минимизации Ф(a) = f(х + aеj)®min, aÎR, т.е. найти a*. Положить 
= х +a*еj, вычислить f (х).
Шаг 2.Если j < п, то положить х = , j=j+1 и перейти к шагу 1, иначе – перейти к шагу 3.
Шаг 3.Проверить условие достижения точности ||х– || < e
3.4 Поиск точки min методом Хука – Дживса
Этот алгоритм содержит две основные процедуры:
а) исследующий покоординатный поиск в окрестности данной точки, предназначенный для определения направления убывания f(х);
б) перемещение в направлении убывания.
Опишем алгоритм исследующего покоординатного поиска из заданной точки х с приращениями по каждой координате Dj , j= 1, …, n
Шаг 1.Положить
= x , i= 1.Шаг 2. Сделать пробный шаг y=
– Dje j, где e j –j–й базисный вектор. Если f ( ) £f(y), то перейти к шагу 3, иначе – к шагу 4.