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

Задача многомерной безусловной оптимизации:

Стандартная математическая задача оптимизации формулируется таким образом. Среди элементов x, образующих множества X, найти такой элемент x*, который доставляет минимальное значение f(x*) заданной функции f(x). Для того, чтобы корректно поставить задачу оптимизации необходимо задать:

Допустимое множество ;

Целевую функцию — отображение ;

Критерий поиска (max или min).

Квазиньютоновские методы.

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

Также в отличие от м. Ньютона, где мы вычисляли каждый следующий элемент по формуле:

= — , где – обратная матрица Гессе (обратная матрица вторых производных).

Данный метод обладает следующими недостатками:

1. Нужно вычислять матрицу 2-х производных (Гессе);

2. Находить обратную ей матрицу.

Из-за трудности вычисления алгоритмы часто расходятся.

Поэтому в Квазиньютоновских методах матрицу Гессе, заменили на функцию, аппроксимирующую ее. Т.е. вычисление происходит по формуле:

= — , где –функция, аппроксимирующая матрицу Гессе.

В отличие от метода Ньютона в квазиньютоновских методах нужно вычислять только градиент, что значительно сокращает время расчета.

К Квазиньютоновским методам относят методы: BFGS, Давидона-Флетчера-Пауэлла и др.