Методы спуска
Методы спуска
По аналогии с методами спуска для системы линейных уравнений заменим задачу решения системы (7) задачей минимизации функции .
Идея методов спуска:
1) Выбирается начальное приближение ;
2) Выбирается направление, в котором убывает;
3) В этом направлении от выбирается следующее приближение ;
4) По рекуррентной формуле последовательно находят приближения ,…,;
5) Последнее приближение .
1 способ) Покоординатный спуск
Рекомендуемые материалы
Пусть .
Подставим в значения всех координат , кроме первой переменной.
Получим функцию от одной переменной. Найдем ее точку минимума. Это будет x1(1).
Затем подставим в x1(1) и значения всех остальных координат , кроме второй переменной.
Получим функцию от одной переменной. Найдем ее точку минимума. Это будет x1(2). Продолжая таким образом, получим . И т.д.
Проиллюстрируем поведение алгоритма для m = 2.
Модификации алгоритма:
1) Случайный покоординатный спуск — порядок переменных выбирается случайным образом.
2) "Метод муравьиной кучи" — покоординатный спуск выполняется для нескольких разных нулевых приближений.
Недостатки алгоритма:
1) Не гарантирует сходимости.
2) Не гарантирует приближение к глобальному экстремуму.
2 способ) Метод наискорейшего спуска.
Использует рекуррентную формулу , где – некоторый параметр, определяемый из условия:
Бесплатная лекция: "35 Провозглашение независимости Республики Беларусь" также доступна.
.
3 способ) Условная минимизация
Задача: Найти точку , в которой достигается минимум , при условиях в виде неравенств или равенств:
Методы решения таких задач получили название математическое программирование.
Если все функции F, j, y являются линейными — линейное программирование. Если есть нелинейные функции — нелинейное программирование. Если искомое решение должно состоять из целых чисел — целочисленное программирование.