biceps-spb.ru

Инновационный проект biceps-spb.ru

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

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

Содержание

Основные понятия

Определим терминологию:

Пусть .

Введём на целевую функцию .

Вектора называются сопряжёнными, если:


где — матрица Гессе .

Теорема (о существовании).
Существует хотя бы одна система сопряжённых направлений для матрицы , т.к. сама матрица (её собственные вектора) представляет собой такую систему.

Обоснование метода

Нулевая итерация

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

Пусть

Тогда .

Определим направление

так, чтобы оно было сопряжено с :

Разложим в окрестности и подставим :

Транспонируем полученное выражение и домножаем на справа:

В силу непрерывности вторых частных производных . Тогда:

Подставим полученное выражение в (3):

Тогда, воспользовавшись (1) и (2):

Если , то градиент в точке перпендикулярен градиенту в точке , тогда по правилам скалярного произведения векторов:

Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления :

К-я итерация

На k-й итерации имеем набор .

Тогда следующее направление вычисляется по формуле:

Это выражение может быть переписано в более удобном итеративном виде:

где непосредственно рассчитывается на k-й итерации.

Алгоритм

  • Пусть — начальная точка, — направление антиградиента и мы пытаемся найти минимум функции . Положим и найдем минимум вдоль направления . Обозначим точку минимума .
  • Пусть на некотором шаге мы находимся в точке , и — направление антиградиента. Положим , где выбирают либо (стандартный алгоритм — Флетчера-Ривса, для квадратичных функций с ), либо (алгоритм Полака–Райбера). После чего найдем минимум в направлении и обозначим точку минимума . Если в вычисленном направлении функция не уменьшается, то нужно забыть предыдущее направление, положив и повторив шаг.

Формализация

  1. Задаются начальным приближением и погрешностью:
  2. Рассчитывают начальное направление:
    • Если или , то и останов.
    • Иначе
      • если , то и переход к 3;
      • иначе и переход к 2.

Случай квадратичной функции

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

Литература

  1. Акулич И.Л. Математическое программирование в примерах и задачах: Учеб. пособие для студентов эконом. спец. вузов. — М.: Высш. шк., 1986.
  2. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. Пер. с англ. — М.: Мир, 1985.
  3. Коршунов Ю.М., Коршунов Ю.М. Математические основы кибернетики. — М.: Энергоатомиздат, 1972.
  4. Максимов Ю.А.,Филлиповская Е.А. Алгоритмы решения задач нелинейного программирования. — М.: МИФИ, 1982.
  5. Максимов Ю.А. Алгоритмы линейного и дискретного программирования. — М.: МИФИ, 1980.
  6. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. — М.: Наука, 1970. — С. 575-576.

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