Методы нахождения условного и безусловного экстремума

Продифференцировав полученное выражение по λ, получим:

df/dλ = 135.375·λ-45.125. Приравняв его к нулю, находим λ* = 1/3.

Получили  х(4) = [8/3 ; 8/3]T.

f(x(4) ) = 32/3.

Таким образом, получили точку = [8/3 ; 8/3]T, значение функции в которой f() = 32/3, что точно совпадает со стационарной точкой, так как округления отсутствовали.

Рис 4.  Графическое пояснение метода сопряженных направлений Пауэлла

4.5 Метод Коши

Описание алгоритма

В методе Коши или методе наискорейшего спуска в качестве направления поиска выбирается направление антиградиента.

,

Ñf = - градиент функции f(x)

Алгоритм метода выглядит следующим образом:

x(k + 1) = x(k) - a(k)×Ñf(x(k)),  где Ñf (x) – градиент.

Значение a(k) на каждой итерации вычисляется путем решения задачи одномерного поиска экстремума f(x) вдоль направления градиента Ñf(x(k)). Если в качестве a(k) взять некоторое положительное число, то получится простейший градиентный алгоритм:

       f(k + 1) = x(k) - a×Ñf(x(k))

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

        f(x(k + 1))  £ f(x(k))

Однако вблизи экстремума скорость сходимости алгоритма становится недопустимо низкой, так как вблизи экстремума значение градиента стремится к нулю.

Нахождение минимума целевой функции методом Коши.

Исходные данные:

f(х1,х2)=(х1–4)2+(х2–4)2 +х1·х2.

Вычислим компоненты градиента:

,

.

Зададим начальное приближение х(0) = [-10;-10]Т;

Новое приближение определим по формуле:

х(1) = х(0) – α (0)·Ñf (x(0) ).

Ñf (x(0) ) = [-38;-38]T.

1.   Выбираем α (0) такое, чтобы минимизировать функцию f (x(1) ).

x(1) = [-10;-10]T- α (0) [-38;-38]T = [-10+α (0)·38;-10+α (0) ·38]T.

f(x(1))=4332·(α (0))2-2888·α (0)+492, f’(α (0))=8664·α (0)-2888=0, α (0)=0.3333.

x(1) = [2.654 ; 2.654]T.

2.  Далее найдём точку x(2) = х(1) - α (1)·Ñf (x(1) ).

Ñf (x(1) ) = [-0.038 ; -0.038]T

x(2) = [2.654 ; 2.654]T - α (1)·[-0.038 ; -0.038]T.

f(x(2))=0.004332·(α(1))2-0.002888·α(1)+10.667148, f’(α(1))=0.008664·α(1)-0.002888=0,

α(1)=0.3333.

x(2) = [2.666654 ; 2.666654]T;

Уже после двух итераций найдено достаточно точное значение точки минимума =[2.666654;2.666654]T, при котором значение целевой функции
f() =10.666666667. Поэтому продолжать поиск нет смысла. Это объясняется симметричностью функции относительно параметров a и b. Если бы округления отсутствовали, то уже на первой итерации было бы найдено точное решение при α (0)=1/3.

Рис 5.  Графическое пояснение метода Коши

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

Описание алгоритма

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

x(k+1) = x(k) – α(k) V2f(x(k))-1 Vf(x(k)), где

- гессиан (матрица Гессе)

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

Нахождение минимума целевой функции методом Ньютона.

Исходные данные:

f(х1,х2)=(х1–4)2+(х2–4)2 +х1·х2.

x(0) = [-10,-10]T – начальная точка.

Вычислим компоненты градиента:

,

.

Ñf(x) = [; ]T.

Найдем гессиан функции:

;        ; 

;         ;

, = 3.

x(1) = x(0) – [Ñ2f(x(0))]-1·Ñf (x(0) );

Ñf (x(0) ) = [ -38; -38]T;

x(1) = [-10;-10]Т-=[-10;-10]Т-=[8/3;8/3]Т.

f(x(1)) = 32/3;

Таким образом точка минимума = [8/3 ; 8/3]Т, значение функции в которой f() = 32/3, найдена за одну итерацию.

Рис 6.  Графическое пояснение метода Ньютона

4.7 Метод сопряженных градиентов

Описание алгоритма

Данный метод обладает положительными свойствами методов Коши и Ньютона. Кроме того этот метод использует информацию только о первых производных исследуемой функции. Метод сопряженных градиентов позволяет получить решение за N шагов в N-мерном пространстве и обладает квадратичной сходимостью. В основе метода лежит организация поиска вдоль сопряженных направлений, причем для получения сопряженных направлений используется квадратичная аппроксимация целевой функции и значения компонент градиента.

Операции аргумента проводятся по формуле

                        x(k + 1) = x(k) + a(k)×s(x(k))

Направление поиска на каждой итерации определяется с помощью формулы

                        s(k) = -g(k) + ×s(k - 1)

В этом случае направление s(k)  будет C - сопряжено со всеми ранее построенными направлениями поиска.

Если функция f(x1, x2, ... , xN) квадратичная, то для нахождения точки экстремума требуется определить N-1 таких направлений и провести поиски вдоль каждой прямой.  Если f(x) не является квадратичной, то количество поисков возрастет.

Используемые в методе формулы:

Градиент квадратичной функции:

              Vf(x) = Vg(x) = Cx + b = g(x).

Изменение градиента при переходе от точки х(0) к точке х(1):

              Δg(x) = g(x(1)) – g(x(0)) = C(x(1) – x(0))

              Δg(x) = CΔx

Изменения аргумента:

x-(k+1) = x(k) – α(k)s(x(k)).

Направление поиска:

              s(k) = -g(k) + ∑ γ(i) s(i) , s(0) = -g(0), γ(i) =

              s(k) = -g(k) + *s(k+1)           (рекуррентная формула Флетчера-Ривса)

Нахождение минимума целевой функции методом сопряжённых градиентов.

Исходные данные:

f(х1,х2)=(х1–4)2+(х2–4)2 +х1·х2.

x(0) = [-10,-10]T – начальная точка.

Вычислим компоненты градиента:

,

.

Ñf(x) = [; ]T.

ШАГ 1:

k=0.

Ñf(x(0) ) = [-38 ; -38]T;

s(0) = -g(0) = -Ñf(x(0) ) = [38 ; 38]T.

ШАГ 2:

Поиск вдоль прямой:

х(1) = х(0) - α (0)·Ñf(x(0)).

  Выбираем α (0) такое, чтобы минимизировать функцию f (x(1) ).

x(1) = [-10;-10]T- α (0) [-38;-38]T = [-10+α (0)·38;-10+α (0) ·38]T.

f(x(1))=4332·(α (0))2-2888·α (0)+492, f’(α (0))=8664·α (0)-2888=0 Þ α (0)=1/3.

x(1) = [8/3 ; 8/3]T.

Ñf(x(1) ) = [0 ; 0]T.

Так как градиент равен нулю, то можно было бы остановиться в силу симметрии функции, но продолжим.

ШАГ 3:

k=1.

Определим направление s(1):

g(1) =Ñf(x(1) ) = [0 ; 0]Т

s(1) = -g(1) + [ ||g(1)||2 / || g(0)||2]·s(0) ;

s(1) = -[0 ; 0]T + [0/(38·)]·[38;38]T = [0 ; 0]T.

ШАГ 4:

Поиск вдоль прямой:

х(2) = х(1) + α (1) ·s(1)= х(1) = [8/3 ; 8/3]T.

Ñf(x(2) ) = [0 ; 0]T.

Таким образом, =[ 8/3; 8/3 ]T. Решение получено в результате проведения двух одномерных поисков, поскольку целевая функция квадратичная.

Рис 7.  Графическое пояснение метода сопряженных градиентов

4.8 Квазиньютоновский метод

Описание алгоритма

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

                                               x(k+1) = x(k) + a(k)×s(k)

Направление поиска определяется выражением

s(k) = -A(k)×Ѧ(x(k)),  где A(k) - матрица порядка N*N (метрика)

Матрица A – вычисляется по формуле

           A(k+1) = A(k) +Ac(k), где

           Ac(k) = ,      (1)

где Dg(k-1) = g(k) - g(k-1)   изменение градиента на предыдущем шаге.

Данный алгоритм отличается устойчивостью, так как обеспечивает убывание целевой функции от итерации к итерации.

Нахождение минимума целевой функции Квазиньютоновским методом:

Исходные данные:

f(х1,х2)=(х1–4)2+(х2–4)2 +х1·х2.

x(0) = [-10,-10]T – начальная точка.

Вычислим компоненты градиента:

,

.

Ñf(x) = [; ]T.

ШАГ 1:

k=0.

Ñf(x(0) ) = [-38 ; -38]T;

Положим s(0) = -Ñf(x(0) ) = [38 ; 38]T.

ШАГ 2:

Поиск вдоль прямой:

х(1) = х(0) - α (0)·Ñf(x(0) ) Þ α (0) = 0.3355;

  Выбираем α (0) такое, чтобы минимизировать функцию f (x(1) ).

x(1) = [-10;-10]T- α (0) [-38;-38]T = [-10+α (0)·38;-10+α (0) ·38]T.

f(x(1))=4332·(α (0))2-2888·α (0)+492, f’(α (0))=8664·α (0)-2888=0 Þ α (0)=1/3.

x(1) = [8/3 ; 8/3]T.

Ñf(x(1) ) = [0 ; 0]T.

Так как градиент равен нулю, то можно было бы остановиться в силу симметрии функции, но продолжим.

ШАГ 3:

k=1.

А(1) = A(0) + Ac(0);

А(0) = Е = ;

Dх(0) = x(1) – x(0) =[8/3 ; 8/3]T- [-10;-10]T =[38/3 ; 38/3]T;

Dg(0) = g(1) – g(0) = Ñf(x(1) ) -Ñf(x(0) ) =[0 ; 0]T -  [-38;-38]T = [38 ; 38]T;

s(1) = - A(1)·Ñf(x(1) );   s(1) = [0 ; 0]T.

ШАГ 4:

Поиск вдоль прямой:

x(2) = x(1) + ·s(1)= x(1) = [8/3 ; 8/3]T.

Точка минимума  = x(2) =  [8/3 ; 8/3]Т;

f() =32/3.

Рис 8.  Графическое пояснение к квазиньютоновскому методу

5.     Нахождение условного экстремума

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

5.1 Метод штрафных функций (квадратичный штраф)

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

min  f (x),        ХRN

при ограничениях   

                                                              gj (x)  ≥  0, i=1…J

hk(x)  =  0,    k = 1...K,

то преобразованная задача имеет вид:

P(x,R) = f(x) + [R, h(x),g(x)],

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

     Виды штрафов.

   Квадратичный штраф имеет вид  = R{h(x)}2. Этот вид штрафов используется для учёта ограничений-равенств. Функция  непрерывна и имеет непрерывную производную, откуда следует, что если непрерывны и дифференцируемые f(x) и h(x), то стационарную точку можно найти ана-литически.      

  Логарифмический штраф.

      = - Rln(g(x));

Этот штраф положителен для всех х таких, что 0 < g(x) <1, и отрицателен при g (x) > 1. Логарифмический штраф – это барьерная функция, неопределённая в точках, где g (x) < 0. Поэтому на начальном этапе поиска, когда значение шага поиска велико, необходимо обеспечить защиту процедуры от попадания рабочей точки в недопустимую область.

Штраф, заданный обратной функцией.

 = R·1/g(x);

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

Штраф типа квадрата срезки.

 = <g(x)>2,

               α, если α ≤ 0,

< α > =

                  0, если α  >  0.

Этот штраф является внешним, и недопустимые точки не создают проблем по сравнению с допустимыми. Различие заключается в том, что в допустимых точках штраф равен нулю. Этот вид штрафа удобен тем, что P(x,R) непрерывна и определена всюду. Параметр R положителен и увеличивается от итерации к итерации.