Метод покоординатного спуска пример

Метод покоординатного спуска пример

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

Поиск экстремума ведется в направлении осей координат, т.е. в процессе поиска изменяется только одна координата. Таким образом, многомерная задача сводится к одномерной.

Алгоритм

  • , , , . .
  • Ищем экстремум функции . Положим, экстремум функции в точке .
  • , , , . . Экстремум функции равен
  • .
  • , , , . .
    В результате выполнения n шагов найдена новая точка приближения к экстремуму . Далее проверяем критерий окончания счета: если он выполнен – решение найдено, в противном случае выполняем еще один цикл.

Подготовка

Сверим версии пакетов:

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

В качестве модельной функции выберем эллиптический параболоид

Покоординатный спуск

Метод реализуем в функции принимающей название метода одномерной оптимизации, размерность задачи, желаемую погрешность, начальное приближение, и ограничения для отрисовки линий уровня. Всем параметрам зададим значения по-умолчанию.

Далее опробуем различные методы одномерной оптимизации

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

Идея метода проста как и реализация

Ньютон довольно требователен к начальному приближению, а без ограничения по шагам вполне может ускакать в неведанные дали. Расчет производной желателен, но можно обойтись и малым варьированием. Модифицируем нашу функцию:

Обратная параболическая интерполяция

Метод не требующий знания производной и имеющий неплохую сходимость

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

Последовательная параболическая интерполяция

Тоже требует три начальных точки, но на многих тестовых функциях показывает более удовлетворительные результаты

Выйдя из весьма дрянной стартовой точки дошло за три шага! Хорош… Но у всех методов есть недостаток — они сходятся к локальному минимуму. Возьмём теперь для исследований функцию Экли


Метод золотого сечения

Теория. Хоть реализация сложна, метод порой показывает себя хорошо перепрыгивая локальные минимумы

На этом с покоординатным спуском всё. Алгоритмы представленных методов довольно просты, так что имплементировать их на предпочитаемом языке не составит труда. В дальнейшем можно рассмотреть встроенные средства языка Julia, но пока хочется всё, так сказать, пощупать руками, рассмотреть методы посложней и поэффективней, затем можно перейти к глобальной оптимизации, попутно сравнивая с реализацией на другом языке.

Читайте также:  Как пользоваться электронной почтой видеоурок бесплатно

Методы безусловной оптимизации

Отчет по лабораторной работе №2

«Оптимизация инженерных вычислений»

Студенты: Кучеренко Г. А.

Преподаватель: Селиванова И.А.

Метод наискорейшего спуска

В данном методе на каждой итерации величина шага выбирается из условия минимума функции в направлении движения, т.е.:

(47)

Таким образом, в данном варианте градиентного спуска на каждой итерации необходимо решить задачу одномерной минимизации (47). Алгоритм метода наискорейшего спуска состоит в следующем:

1. В точке вычисляется значение градиента функции и шага путем решения задачи одномерной минимизации (47).

2. Осуществляется спуск в направлении антиградиента с выбранным шагом до тех пор, пока значение функции убывает, т.е. выполняется условие (46).

3. Если на i-ом шаге , то в точке вычисляются новые значения градиента и шага и выполняется переход к п.2

4. Критериями останова итерационного процесса служат следующие условия: если минимум вдоль данного направления спуска не может быть определен на последней итерации с помощью формулы (47); при превышении заданного числа итерации; при полученных значениях компонент градиента, меньших по абсолютной величине заданных минимально допустимых значений первой производной минимизируемой функции.

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

1. Задаются: xº — начальное приближение, ε1 > 0, ε2> 0, M – предельное число итераций;

2. Количество итераций n = 0 ;

3. Вычисляется: gradf(xⁿ);

4. Вычисляется || gradf(xⁿ) || ;

4.1) если || gradf(xⁿ) || ε1 , то к 5);

Зафиксируем теперь все координаты, кроме x2, и рассмотрим функцию этой переменной . Снова решая одномерную задачу оптимизации, находим ее наименьшее значение при , т.е. в точке . Аналогично проводится спуск по координатам x3,x4,…,xn, а затем процедура снова повторяется от x1 до xn и т.д. В результате этого процесса получается последовательность точек M0,M1,…, в которых значения целевой функции составляют монотонно убывающую последовательность f . На любомk-м шаге этот процесс можно прервать, и значение f(Mk) принимается в качестве наименьшего значения целевой функции в рассматриваемой области.

Таким образом, метод покоординатного спуска сводит задачу о нахождении наименьшего значения функции многих переменных к многократному решению одномерных задач оптимизации по каждому проектному параметру.

Данный метод легко проиллюстрировать геометрически для случая функции двух переменных z=f(x,y), описывающей некоторую поверхность в трехмерном пространстве. На рис. 1 нанесены линии уровня этой поверхности. Процесс оптимизации в этом случае проходит следующим образом. Точка M0(x0,y0) описывает начальное приближение. Проводя спуск по координате х, попадем в точку M1(x1,y0). Далее, двигаясь параллельно оси ординат, придем в точку M2(x1,y1)и т.д.

Читайте также:  Как прибавить яркость в фотошопе

Важным здесь является вопрос о сходимости рассматриваемого процесса оптимизации. Другими словами, будет ли последовательность значений целевой функции f(M0), f(M1),… сходиться к наименьшему ее значению в данной области? Это зависит от вида самой функции и выбора начального приближения.

Для функции двух переменных очевидно, что метод неприменим в случае наличия изломов в линиях уровня. Это соответствует так называемому оврагу на поверхности. Здесь возможен случай, когда спуск по одной координате приводит на “дно” оврага. Тогда любое движение вдоль любой координаты ведет к возрастанию функции, соответствующему подъему на “берег” оврага. Поскольку поверхности типа “оврага” встречаются в инженерной практике, то при использовании метода покоординатного спуска следует убедиться, что решаемая задача не имеет этого недостатка.

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

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

В двумерном пространтсве R2. Решение задачи (2) методом покоординатного спуска, иначе называемого методом Гаусса — Зейделя, производят по следующей общей схеме.
Выбирают произвольно начальную точку х(0) из области определения функции f(х). Приближения х(k) определяются соотношениями (3):
x(k+1)=x(k)+t(k)S(k) (k=0,1,2, . ),
где вектор направления спуска s(k)- это единичный вектор, совпадающий с каким-либо координатным направлением (например, если S(k) параллелен х1, то S(k)= <1,0,0. 0>, если он параллелен x2, то S(k)= <0, 1, 0, . . . ,0>и т.д.) ; величина t(k) является решением задачи одномерной минимизации:
f(x(k)+ts(k)) —> min, t ОR1, (k=0,1,2, . ),
и может определяться, в частности, методом сканирования.
Детальная реализация общей схемы в двумерном случае R2 дает траекторий приближения к точке х* методом покоординатного спуска, состоящую из звеньев ломаной, соединяющих точки х(k), х

(k), x(k+1) (k=0, 1, 2,) (рис.2). При k=0, исходя из начальной точки х(0)=(x1(0),x2(0)), находят точку х

(0),x2(0)), минимума функции одной переменной f(x1,x2(0)); при этом f(x

Поиск экстремума ведется в направлении осей координат, т.е. в процессе поиска изменяется только одна координата. Таким образом, многомерная задача сводится к одномерной (рис. 3.6).

Читайте также:  Как выяснить свой инн

Рис. 3.6. Метод покоординатного спуска

(– новые точки приближения к экстремуму)

Ищем экстремум функции f(х1). Положим, экстремум функции в точке х1 1 .

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

Далее проверяем критерий окончания счета (3.15):

если – решение найдено, в противном случае выполняем еще один цикл.

= (0, 0),  = 0,1.

Любым известным методом находим экстремум: x1 1 = 3,25.

= (3,2; 1,625)

3. Проверка критерия окончания счета:

Как видим, , следовательно, требуется выполнить еще хотя бы один цикл.

= (1, 1),  = 0,01.

Любым известным методом находим экстремум:

= (0,5; 0,3).

3. Проверка критерия окончания счета:

Видим, , следовательно, требуется выполнить еще хотя бы один цикл.

3.4.2.2. Метод наискорейшего спуска

Поиск экстремума ведется шагами в направлении градиента (max) или антиградиента (min). На каждом шаге в направлении градиента (антиградиента) движение осуществляется до тех пор, пока функция возрастает (убывает).

Этот метод имеет лучшую сходимость, чем предыдущий.

Допустим, требуется найти минимум функции.

. (3.16)

тогда

2. Делаем шаг в направлении антиградиента. Выражения для нахождения координат новой точки приближения к экстремуму выглядят следующим образом:

(3.17)

где  1 – величина шага в направлении антиградиента при 1-ой итерации.

3. Нахождение величины шага.

В направлении антиградиента движемся до тех пор, пока функция убывает. Следовательно, шаг выбирается из условия минимума функции f( 1 ).

Для этого в функцию f(х1, х2хn) подставляем выражения для координат новой точки (3.17).

В результате получим функцию одной переменной f( 1 ). Минимум f( 1 ) находим любым известным методом поиска экстремума функции одной переменной.

4. Полученное значение  1 подставляется в формулы (3.17). В результате получаем точку X1 = (x1 1 ,,xn 1 ).

5. Проверка критерия окончания счета.

Если , то решение в точке, иначе – требуется сделать еще шаг.

f(x1, x2) = x1 2 – 7x1 + x2 2 – 4x2x1x2 + 35, = (1, 1), = 0,5.

1. = 2x1 – 7 – x2, a1 = 21 –7 –1 = –6.

= 2x2 – 4 – x1, a2 = 21 –4 –1 = –3.

(6; 3,5)

4. , следовательно, нужен еще шаг.

Найти безусловный экстремум методом наискорейшего спуска

1. = 10x1 – 4x2, – 1, a1 = 101 – 41 – 1= 5,

= –4x1 +10x1 – 1, a2 = –41 + 101 – 1 = 5.

Ссылка на основную публикацию
Мгтс проверить подключение дома
МГТС - главный оператор связи в Москве. За более чем 130 лет существования бренд закрепился в поцизии надежного поставщика телекоммуникационных...
Лучшие игры на windows 10 mobile
Майнкраф это моя жизнь блат Неплохая часть sims,нечем не хуже пк версии! Практически самая лучшая песочница!(после майнкрафта конечно) Хорошая часть...
Лучшие игры для детей на ps3
Здесь представлены лучшие игры для PS3 (PlayStation 3) за последнее время, рейтинг которых составлялся по данным оценок пользователей проголосовавших за...
Мгтс проверить остаток трафика
Для проверки баланса наберите на телефоне команду *100#?. Если баланс лицевого счета отрицательный, но при этом не превышает кредитный лимит...
Adblock detector