Алгоритм метода сопряженных направлений Пауэлла

Шаг 1. Задать начальную точку x^o и систему N линейно независимых направлений sⁱ; целесообразно принять sⁱ = eⁱ, i=1,2,...,N.

Шаг 2. Минимизировать W(x) при последовательном движении по N+1 направлениям; при этом полученная ранее точка минимума берется в качестве исходной, а направление s^N используется как при первом, так и при последнем поиске.

Шаг 3. Определить новое сопряженное направление с помощью обобщенного свойства параллельного подпространства.

Шаг 4. Заменить s¹ на s² и так далее. Заменить s^N сопряженным направлением. Перейти к шагу 2.

Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Если целевая функция квадратична и обладает минимумом, то точка минимума находится в результате реализации N циклов, включающих шаги 2-4. Здесь N - число переменных. Если же функция W(x) не является квадратичной, то требуется более чем N циклов.

13.3.3.Градиентныеметоды

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

Все методы основаны на итерационной процедуре, реализуемой в соответствии с формулой

x^k+1 = x^k + a^k s(x^k), (13.9)

где

x^k - текущее приближение к решению x^*;

a^k - параметр, характеризующий длину шага,

s(x^k) - направление поиска в N - мерном пространстве управляемых переменных x_i, i = 1, 2,..., N.

Способ определения a^k и s(x^k) на каждой итерации связан с особенностями применяемого метода. Обычно выбор a^k осуществляется путем решения задачи минимизации W(x) в направлении s(x^k). Поэтому при реализации градиентных необходимо использовать эффективные алгоритмы одномерной минимизации.

Простейший градиентный метод

В основе метода лежит следующая итерационная модификация формулы (13.9):

x^k+1 = x^k - a DW(x^k), (13.10)

где

a - заданный положительный коэффициент;

DW(x^k) - градиент целевой функции первого порядка.

Недостатки:

· необходимость выбора подходящего значения a;

· медленная сходимость к точке минимума ввиду малости DW(x^k) в окрестности этой точки.

Метод наискорейшего спуска

Свободен от первого недостатка простейшего градиентного метода, т.к. a^k вычисляется путем решения задачи минимизации DW(x^k) вдоль направления DW(x^k) с помощью одного из методов одномерной оптимизации

x^k+1 = x^k - a^k DW(x^k). (13.11)

Данный метод иногда называют методом Коши.

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

Метод Ньютона

Последовательное применение схемы квадратичной аппроксимации приводит к реализации оптимизационного метода Ньютона по формуле

x^k+1 = x^k - D²W(x^k)^-1 DW(x^k). (13.12)

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

x^k+1 = x^k - a^k D²W(x^k)^-1 DW(x^k), (13.13)

где

a^k - параметр, выбираемый таким образом, чтобы W(x^k+1)®min.