Virtual Laboratory Wiki
Advertisement

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

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

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

Пусть .

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

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


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

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

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

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

Файл:Conjugate gradient illustration.svg

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

Пусть

Тогда .

Определим направление так, чтобы оно было сопряжено с :

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

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

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

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

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

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

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

К-я итерация

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

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

где непосредственно рассчитывается на k-й итерации, а все остальные уже были рассчитаны на предыдущих.

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

Алгоритм

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

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

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

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

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

Литература

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


См. также

Градиентные методы:

Ссылки

Поиск глобального оптимума для задач оптимального проектирования систем или определения оптимальных законов управления.



Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Метод сопряжённых градиентов. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .


Advertisement