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




Что вообще из себя представляет метод покоординатного спуска ?

Это один из способов найти локальный минимум/максимум у некоторой n-мерной функции.

Как оно работает?

На вход этого алгоритма дается Некоторая n-мерная функция F(x1, x2, x3, ... , xn) , некоторая n-мерная точка X0=(x10, x20, x30, ... , xn0).

Рассмотрим эту функцию, "фиксируем" все координаты этой функции кроме первой, то есть заменяем x2 на x20 , x3 на x30 и так далее xn на xn0 и рассматриваем уже вот такую функцию F1(x1, x20, x30, ... , xn0), которая уже является функцией от одной переменной.

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

Допустим мы определили направление убывания/возрастания, теперь двигаясь с некоторым шагом ε(эпсилон) в этом направлении. После некоторого количества шагов МОЖЕТ БЫТЬ найдена точка X1 локального минимума/максимума этой одномерной функции, если F1 не является монотонной. Будет очень хорошо если функция будет унимодальной, то есть ее локальные минимум и максимум будут глобальными.

Теперь у нас есть точка X1=(x11, x20, x30, ... , xn0). Далее "Фиксируем" 2-ую координату, но уже используем не X0, а X1, и рассматриваем функцию F2(x11, x2, x30, ... , xn0). Эта функция также зависит только от одной переменной. Поступаем с ней также, как и с функцией F1, и пробуем найти локальный минимум/максимум.

Получаем следующую точку X2=(x11, x21, x30, ... , xn0). Теперь нужно еще n-2 раза фиксируя все координаты кроме одной пройтись по функции. После выполнения мы получаем точку Xn=(x11, x21, x31, ... , xn1).

Теперь можем повторять все пройденое, пока изменение расстояния от Xk-1 до Xk будет не больше некоторой погрешности σ(сигма), которая устанавливается заранее. В итоге ЕСЛИ МИНИМУМ СУЩЕСТВУЕТ, то мы его получаем. Далее я рассмотрю работу этого алгоритма, на функции F(x,y)=x2+y2.

Пример

Рассмотрим функции F(x,y)=x2+y2 и начальную точку X0=(1,2), искать мы будем минимум функции



Зафиксируем переменную y, и рассмотрим функцию F1(x,2)=x2+22 <=> F1(x)=x2+4.

Если мы рассмотрим производную в точке, то сможем определить возрастание/убывание функции. F1(1+ε)-F1(1), где ε некоторая бесконечно малая положительна величина. Если эта разность положительна, то при положительном движении по оси абцисс(x) функция F1(x) будет возрастать, в обратном случае - убывать.

Найдем же значение производной в точке: F1(1+ε)-F1(1)=(1+ε)2+4-(1+4)-=ε2+2ε+1+4-1-4=ε2+2ε.

Получилось положительное число, а значит функция возрастает при положительном движении по оси абцисс, но мы то ищем минимум, значит идем в противоположную сторону, то есть мы будем уменьшать x.

На рисунке пунктирной стрелкой показано направление изменение координаты х, а красной кривой - изменение значения функции при изменении координаты x.

Уменьшаем x до точки X1, до того момента, пока значение функции F1 не начнет увеличиваться. X1=(0, 2).

Теперь "Фиксируем" функцию уже в точке X1 и заменяем x на x из X1 а именно 0, и рассматриваем функцию F2(0,y)=02+y2 <=>F2(y)=y2.

Снова находим значение производной в точке. F2(2+ε)-F2(2)=4+ε2+2ε-4=ε2+2ε. Опять значение положительное, значит идем в противоположную сторону.

На рисунке второй пунктирной стрелкой показано направление изменение координаты y, а зеленой кривой - изменение значения функции при изменении координаты y.

В данном случае получилось так, что после 1 прохода алгоритма, он нашел минимум, и этот минимум X2=(0, 0), опять же эта функция ИМЕЕТ локальынй минимум, если же начать искать максимум на этой же функции, то программная реализация алгоритма его не найдет и даже зависнет, если не продумать критерий остановки.

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

Инструкция по работе с реализацией:

Вам будет предложенно ввести количество переменных, начальную точку, n-мерную функцию и погрешность(шаг), n-мерную функцию стоит вводить в виде F(x0,x1,x2,..xn), к примеру "sin(x0)*cos(x1)+sin(pow(1,x3))", после всех вычислений, будут выведены промежуточные значения(точка и значение функции в точке), последнее из которых будет финальным.



Программная релизация

Введите количество переменных :



Введите начальную точку:




Введите функцию Выражение:
Шаг/погрешность: