Методом квадратичной аппроксимации

В основе метода лежит аппроксимация функции Ф(a) квадратичным полиномом. Для ускорения поиска на этапе выделения интервала неопределенности необходимо ввести, как и ранее, переменный шаг a_i в (4):

; (10)

a₀ = 1, если при этом происходит убывание функции, a_-1 = 0, t - коэффициент, численное значение которого в начале одномерного поиска равно нулю, а затем возрастает на 1 через каждые R шагов. Пусть произведены измерения функции в точках a₀, a₁, a₂ согласно алгоритму. Интервал неопределенности лежит между точками a₀ и a₂ (рис. 1). Для сокращения интервала заменяем реальную функцию Ф(a) аппроксимирующей функцией Ф_апр(a), которая проходит через те же точки a₀, a₁, a₂, Ф_апр(a)=aa²+ba+c и имеет координату минимума a_опт= – b/(2a). Связывая неизвестные коэффициенты a, b, c со значениями a₀, a₁, a₂ и Ф(a₀), Ф(a₁), Ф(a₂) получаем расчетную формулу:

. (11)

Причем точка a₃=a_опт (рис. 2) попадает внутрь интервала неопределенности a₂ - a₀.

Новый интервал неопределенности уменьшился и стал равным a₂ - a₁. Вычислительный процесс сокращения интервала необходимо продолжить, пока не будет выполнено условие одномерного поиска (9).

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

,

где H – симметричная и положительно определенная матрица вторых частных и смешанных производных (матрица Гессе, или гессиан), с – постоянный вектор, b – константа.

Оптимальное решение приведенной задачи соответствует нулевым значениям первых производных, то есть

, откуда .

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

Среди подобных алгоритмов одним из наиболее популярных и используемых в пакете Optimization Toolbox является так называемый BFGS-алгоритм, получивший свое название по фамилиям предложивших его авторов (Broyden, Fletcher, Goldfarb, Shanoo), в котором аппроксимация Н производится итерационно, по формуле

, где , .

Заметим, что наиболее удобно иметь аппроксимацию не матрицы Н, а обратной к ней матрицы Н^-1, приведенное рекуррентное соотношение подобную замену допускает, при этом сам алгоритм становится практически идентичным хорошо известному отечественным исследователям алгоритму Давидона-Флетчера-Пауэлла, за тем исключением, что в последнем векторы q заменены на векторы s и наоборот.

Именно такие алгоритмы являются основой численных методов, заложенных в распространенные математические пакеты прикладных программ (MS Excel, Mathcad, Mathlab).

Блок-схема алгоритма минимизации функции многих переменных метода Давидона-Флетчера-Пауэлла приведена на рис. 3.

Рис. 3. Блок-схема алгоритма минимизации функции

Поиск по сайту: