Метод Циклического покоординатного спуска

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

Начальный этап

Выбрать x1, e, k=1, l=1.

Основной этап

Шаг 1

(1) В качестве направления p выбрать Метод Циклического покоординатного спуска - student2.ru , где ненулевая позиция имеет индекс l.

(2) Найти L как результат минимизации функции по направлению p.

(3) Метод Циклического покоординатного спуска - student2.ru

(4) Если l<n то Шаг 2, иначе повторить Шаг 1 с l = l+1.

Шаг 2

(1) Вычислить Метод Циклического покоординатного спуска - student2.ru

(2) Проверить КОП: если Метод Циклического покоординатного спуска - student2.ru , то Метод Циклического покоординатного спуска - student2.ru , иначе Метод Циклического покоординатного спуска - student2.ru , l=1 и на Шаг 1.

Метод параллельных касательных

Начальный этап:

Выбрать х1, ε = 10-4 – 10-8 установить k = 1;

Основной этап:

Шаг 1.

Из точки x1 выполнить антиградиентный в точку x2= x11р1, где p1=-Ñу1.

Шаг 2.

Последовательно выполнить две операции:

1. Антиградиентный спуск в точку x3.

2. Вычислить ускоряющее направление d=x3-x1 и, не останавливаясь совершить ускоряющий шаг в точку x4=x33d.

Шаг 3.

Проверить КОП: Метод Циклического покоординатного спуска - student2.ru - остановиться x*=x4.

Иначе:

1. Обозначить x2 как новую начальную x1=x2, а точку x4 как новую точку ускорения x2=x4.

Перейти к шагу 2.

Метод Гаусса-Зейделя

Начальный этап

Выбрать х1, ε = 10-4 – 10-8 установить k = 1;

Основной этап:

Шаг 1.

Выполнить серию одномерных поисков вдоль координатных орт

Метод Циклического покоординатного спуска - student2.ru

Шаг 2.

Вычислить ускоряющее направление и проверить КОП: Метод Циклического покоординатного спуска - student2.ru , если выполняется, минимум найден: x*=xn+1.

Иначе:

1. Выполнить ускоряющий шаг в новую точку хn+2

2. Обозначить последнюю точку как начальную и вернуться на шаг 1.

Метод комплексов Бокса

Комплекс-метод предназначен для отыскания условного экстремума непрерывной целевой функции (1) в выпуклой допустимой области.

При использовании метода принимаются следующие предпо­ложения:

1. Задача поиска экстремума функционала (1) решается при наличии ограничений 1-го и 2-го рода.

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

3. Допустимая область выпукла.

4. Значения целевой функции и функций ограничений вычисляются без ошибок.

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

В отличие от симплексного метода, в комплексе-методе используется случайный набор N точек – Комплекс, а число точек Комплекса определяется по правилу:

(5)
Метод Циклического покоординатного спуска - student2.ru Метод Циклического покоординатного спуска - student2.ru Метод Циклического покоординатного спуска - student2.ru

где n – число независимых переменных.

Вычислительная последовательность (алгоритм) комплекс-метода включает в себя следующие этапы.

1) Формируется исходный комплекс. Координаты вершин исходного Комплекса хij вычисляются последовательно с помощью равномерно распределенных на интервале (0;1) псевдослучайных чисел rij:

(6)
xij=gi+rij(hi - gi), i=1, 2,…,n, j=1, 2, ,N.

В каждой вершине с номером j проверяется выполнение ограничений 2-го рода (ограничения 1-го рода выполняются автоматически).

Точка фиксируется как вершина Комплекса, если в ней удовлетворяются все ограничения. Если же ни в одной из точек ограничения не выполнены, то формуле (6) вычисляются координаты новых точек, в которых вновь проверяется ограничения.

Пусть число точек, удовлетворяющих ограничениям 2-го рода Р (Р≥1), тогда (N–P) – число точек, в которых ограничения нарушены.

Далее для каждой из еще незафиксированных вершин выполняется операция по ее смещению к центру Р вершин Комплекса, при этом новые координаты точки х*ij вычисляются по формуле

(7)
Метод Циклического покоординатного спуска - student2.ru , i=1, 2,…, n, j=P+1, P+2,…,N.

Процесс смещения j-й точки продолжается до тех пор, пока для нее не будут выполнены все ограничения. Такой момент обязательно наступит, поскольку допустимая область выпукла. Точка фиксируется как новая вершина Комплекса (Р увеличивается на единицу), после чего операция смещения повторяется для очередной вершины.

(8)
2) Для всех N вершин Комплекса вычисляются значения целевой функции Fi:

Fj=F(xj), Метод Циклического покоординатного спуска - student2.ru , j=1, 2,…,N.

(9)
3) Выбираются наилучшее R и наихудшее S (с точки зрения экстремума) значения из массива Fi:

R=FG; S=FD.

где G – номер самой «хорошей»; а D – самой «плохой» вершины.

4) Определяются координаты Ci центра Комплекса с отброшенной «наихудшей» вершиной:

(10)
Метод Циклического покоординатного спуска - student2.ru , i=1, 2,…,n.

5) Проверяется условие окончания поиска. Для этого вычисляется величина В:

(11)
Метод Циклического покоординатного спуска - student2.ru .

Если В<ε (ε – заданная точность вычисления), т.е. среднее расстояние от центра Комплекса до худшей (D) и лучшей (G) вершин меньше ε, то поиск заканчивают, считая экстремум найденным.

В противном случае вычисления продолжаются:

(12)
6) взамен наихудшей вычисляются координаты новой точки Комплекса:

xi0=2,3Ci – 1,3xiD, i=1, 2,…,n.

В этой новой точке проверяется выполнение ограничений 1-го рода. В случае, если ограничения нарушаются, xi0 принимает значения gi+ε или hi–ε в зависимости от того, в какую сторону i-е ограничение нарушено;

(13)
7) для новой точки проверяется выполнение ограничение 2-го рода. Если хотя бы одно из ограничений нарушено, то новую точку смещают к центру Комплекса на половину расстояния:

Метод Циклического покоординатного спуска - student2.ru .

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

8) В новой точке вычисляют значения целевой функции F0:

(14)
Метод Циклического покоординатного спуска - student2.ru Метод Циклического покоординатного спуска - student2.ru .

(15)
9) Если F0 оказывается хуже S (значение целевой функции в наихудшей точке D предыдущего комплекса), т.е. новая точка находится дальше от экстремума, чем вершина с номером D, то новая вершина находится смещением xi0 на половину расстояния к лучшей из вершин комплекса G:

Метод Циклического покоординатного спуска - student2.ru .

Затем вновь вычисляют значение целевой функции F0 и сравнивают его с S. Смещением к лучшей вершине по формуле (15) продолжают до тех пор, пока F0 не станет лучше S.

За счет этой процедуры происходит последовательное сжатие комплекса к лучшей вершине.

10) Если вычисленное в новой точке х0 значение F0 лучше S, то в Комплексе на месте наихудшей точки хD фиксируется точка х0 и значение S заменяется на F0.

Затем вычисления повторяются, начиная с п. 3, и продолжаются до тех пор пока не будет выполнено условие остановки, т.е. не будет найден с заданной точностью экстремум целевой функции.

Метод Хука-Дживса (конфигураций)

Эффективность прямого поиска точки минимума можно повысить, если на ка­ждом k-м шаге поиска соответствующим образом выбирать направление спуска. Для этого на каждом k-м шаге выделяют предварительный этап исследующего поиска. Целью этого этапа является выбор направления спуска путем исследования поведения целевой функции f(x) в окрестности точки xk-1, найденной на предыдущем шаге. В результате выполнения этапа исследующего поиска находится точка xk, для которой f(xk) < f(xk-1). Направление спуска, завершающего k-w. шаг поиска, определяется вектором xk - xk-1. Такая стратегия поиска, получила название метода Хука - Дживса.

Исследующий поиск 1

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

Метод Циклического покоординатного спуска - student2.ru

Ускоряющий поиск

Выполняем единичный шаг вдоль направления Метод Циклического покоординатного спуска - student2.ru , Метод Циклического покоординатного спуска - student2.ru . Затем производим исследующий поиск в окрестности x3, в надежде найти точку лучшую чем x2.

Начальный этап

β = 10, ε = 10-4 – 10-8 , k = 1, х1, h1= … =hn=0.1;

Основной этап

Шаг 1.

Выполнить ИП1 и отыскать т. х2 для которой Метод Циклического покоординатного спуска - student2.ru .

Шаг 2.

Если ИП1 удачен т.е. найдена х2, то перейти на шаг 3, иначе, но в то же время h<ε необходимо уменьшить шаг в β раз и вернуться на шаг 1. При h<ε остановиться х* = х1.

Шаг 3.

Выполнить УП в пробную точку Метод Циклического покоординатного спуска - student2.ru

Обозначить Метод Циклического покоординатного спуска - student2.ru

В окрестности х3 попытаться ИП2 найти т. х4 «лучшую» чем х1.

Шаг 4.

Если ИП2 удачен, то положить Метод Циклического покоординатного спуска - student2.ru и вернуться на шаг 1.

Иначе: уменьшить шаг в β раз и вернуться на шаг 1.

Метод Хука-Дживса с одномерной минимизацией

Данный метод является аналогом метода циклического покооординатного спуска (ЦПС) с ускоряющим шагом. Начиная со второй итерации, устанавливается новый способ построения направления ускоряющего поиска. Организацию итерационной процедуры и отличие метода Хука-Дживса с одномерной минимизацией от метода ЦПС раскрывает представленное ниже пошаговое описание алгоритма.

Начальный этап

(1) Исходные данные - базовая точка x, погрешность вычисления минимума e, матрица координатных направлений p = {pi}, i = 1,2,...,n, где pi = ei - i-ый единичный орт в Rn, т.е. ei = 1 и eji = 0 при всех i ¹ j.

(2) Начальную точку x1 принять равной базовой точке: x1 = x.

Основнй этап

Шаг 1.

Выполнить ЦПС из начальной точки x1 в конечную точку xn+1, последовательно решая n-задач одномерной минимизации вдоль координатных направлений p.

Шаг 2.

Проверить критерий окончания поиска:

(1) построить направление ускоряющего поиска d = xn+1 - x;

(2) если ½½d½½ << e, остановиться.

Шаг 3.

Определить начальные условия для очередной итерации:

(1) найти оптимальный шаг an+1 в точку xn+2 = xn+1 + an+1d;

(2) взять точку xn+2 за новую начальную точку x1 = xn+2, а точку xn+1 за новую базовую x = xn+1;

(3) вернуться на шаг 1.

Метод Ньютона

Если f(x) является дважды дифференци­руемой в Rn, то эффективность процесса поиска точки х* ее минимума можно повысить, используя информацию не толь­ко о градиенте этой функции, но и о ее матрице Гecce H(x). Алгоритмы такого поиска обычно относят к ме­тоду Ньютона. В простейшем варианте алгоритма на каждой k-й итерации целевая функция аппроксимируется в окрестно­сти точки xk-1 (на первой итерации в окрестности начальной точки х0) квадратичной функцией Метод Циклического покоординатного спуска - student2.ru и затем определяется точка xk минимума функции Метод Циклического покоординатного спуска - student2.ru . На следующей, (k+1)-й итерации строится новая квадратичная аппроксимация уже в окрестности точки xk.

Начальный этап:

Выбрать x0, e, k=1.

Основной этап

Шаг 1

(1) Строится Ньютоновское направление: Метод Циклического покоординатного спуска - student2.ru - градиент в заданной точке, H – матрица Гессе

(2) Найти Метод Циклического покоординатного спуска - student2.ru как результат решения системы уравнений Метод Циклического покоординатного спуска - student2.ru

(3) Метод Циклического покоординатного спуска - student2.ru

(4) Метод Циклического покоординатного спуска - student2.ru

Шаг 3

Проверить КОП: если Метод Циклического покоординатного спуска - student2.ru , то Метод Циклического покоординатного спуска - student2.ru , иначе на Шаг 1.

Метод Зангвилла

Начальный этап

Выбрать константу остановки e > 0 и начальную точку x1. Положить y1 = x1, k = j =1, Метод Циклического покоординатного спуска - student2.ru и перейти к основному этапу.

Основной этап

Шаг 1. Взять в качестве Метод Циклического покоординатного спуска - student2.ru оптимальное решение задачи минимизации Метод Циклического покоординатного спуска - student2.ru при Метод Циклического покоординатного спуска - student2.ru и положить Метод Циклического покоординатного спуска - student2.ru . Если Метод Циклического покоординатного спуска - student2.ru , то перейти к шагу 4; в противном случае перейти к шагу 2.

Шаг 2. Положить Метод Циклического покоординатного спуска - student2.ru и взять в качестве Метод Циклического покоординатного спуска - student2.ru оптимальное решение задачи минимизации Метод Циклического покоординатного спуска - student2.ru при Метод Циклического покоординатного спуска - student2.ru . Положить Метод Циклического покоординатного спуска - student2.ru , Метод Циклического покоординатного спуска - student2.ru и перейти к шагу 3.

Шаг 3. Если Метод Циклического покоординатного спуска - student2.ru , то остановиться; Метод Циклического покоординатного спуска - student2.ru -- оптимальное решение. В противном случае взять в качестве Метод Циклического покоординатного спуска - student2.ru оптимальное решение задачи минимизации Метод Циклического покоординатного спуска - student2.ru при Метод Циклического покоординатного спуска - student2.ru . Положить Метод Циклического покоординатного спуска - student2.ru . Если Метод Циклического покоординатного спуска - student2.ru , то заменить Метод Циклического покоординатного спуска - student2.ru на Метод Циклического покоординатного спуска - student2.ru и повторить шаг 3. В противном случае положить Метод Циклического покоординатного спуска - student2.ru , заменить Метод Циклического покоординатного спуска - student2.ru на Метод Циклического покоординатного спуска - student2.ru и перейти к шагу 1.

Шаг 4. Положить Метод Циклического покоординатного спуска - student2.ru , Метод Циклического покоординатного спуска - student2.ru , заменить Метод Циклического покоординатного спуска - student2.ru на Метод Циклического покоординатного спуска - student2.ru , положить Метод Циклического покоординатного спуска - student2.ru и перейти к шагу 1.

Метод Флетчера-Ривса

Метод сопряжённых направлений основан на свойствах векторов сопряженных относительно некоторой квадратной матрицы. Различие в способах построения системы сопряженных векторов, определяющих сопряжённые направления спуска, порождает несколько алгоритмов этого метода. В качестве матрицы сопряжений берётся матрица Гессе. Особенность алгоритмов метода сопряженных направле­ний состоит в том, что систему сопряженных векторов строят последовательно в процессе выполнения итераций, причем найденный на очередной, k-й итерации вектор pk определяет на этой итерации направление спуска. Для не квадратичных функций получаемые направления, в конце концов, перестают быть взаимносопряженными поэтому, как и в ДФП через n шагов вектор направления делают равным антиградиенту.

Начальный этап

Выбрать x1, e, k=1.

Основной этап

Шаг 1.

Построить вектор pk:

Метод Циклического покоординатного спуска - student2.ru

Шаг 2.

Найти новую точку Метод Циклического покоординатного спуска - student2.ru как результат одномерного поиска полученного направления Метод Циклического покоординатного спуска - student2.ru .

Шаг 3.

Проверить КОП: Метод Циклического покоординатного спуска - student2.ru .

Расчетное соотношение Флетчера-Ривса

Метод Циклического покоординатного спуска - student2.ru

Метод Пауэлла

Метод достаточно прост в реализации и обладает квадратичной сходимостью вблизи минимума. Стратегия метода базируется на свойстве квадратичных функций параллельного подпространства: если x1 минимум квадратичной функции по вектору p, а x2 минимум этой же функции по вектору параллельному предыдущему, то Метод Циклического покоординатного спуска - student2.ru .

Первый варианталгоритма метода Пауэлла

Начальный этап

(1) Выбрать x1, e, k=1.

(2) Положить Метод Циклического покоординатного спуска - student2.ru

Основной этап:

Шаг 1.

(1) Выполнить n переходов по векторам базиса Метод Циклического покоординатного спуска - student2.ru : Метод Циклического покоординатного спуска - student2.ru

(2) Определить новое направление и спуститься вдоль него: Метод Циклического покоординатного спуска - student2.ru

Метод Циклического покоординатного спуска - student2.ru

Шаг 2.

Проверить КОП: если Метод Циклического покоординатного спуска - student2.ru ,или k = n (для квадратичных функций) то прекратить поиск, иначе Шаг 3

Шаг 3.

Построить новую поисковую систему: из предыдущей системы удаляется первый вектор, а в конец добавляется вектор d.

Таким образом изменение системы поиска выглядит так:

Метод Циклического покоординатного спуска - student2.ru

Второй вариант алгоритма метода Пауэлла

Отличается от первого варианта тем, что изначально строится поисковая система где первый и последний вектор параллельны:

Метод Циклического покоординатного спуска - student2.ru

Изменение поисковой системы выглядит так:

Метод Циклического покоординатного спуска - student2.ru

Наши рекомендации