Особенности методов второго порядка

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

Необходимым условием экстремума функции многих переменных f(x) в точке х* является равенство нулю ее градиента в этой точке:

f’(х^*) 0.

Разложение f’(х) в окрестности точки х[k] в ряд Тейлора с точностью до членов первого порядка позволяет переписать предыдущее уравнение в виде

f'(x) f’(x[k]) + f"(x[k]) (х - х[k]) 0.

Здесь f"(x[k]) Н(х[k]) ‑ матрица вторых производных (матрица Гессе) минимизируемой функции. Следовательно, итерационный процесс для построения последовательных приближений к решению задачи минимизации функции f(x) описывается выражением

x[k+l] x[k] - H^-1(x[k]) f’(x[k]) ,

где H^-1(x[k]) - обратная матрица для матрицы Гессе, а H^-1(x[k])f’(x[k]) р[k] - направление спуска.

Полученный метод минимизации называют методом Ньютона. Очевидно, что в данном методе величина шага вдоль направления р[k] полагается равной единице. Последовательность точек {х[k]}, получаемая в результате применения итерационного процесса, при определенных предположениях сходится к некоторой стационарной точке х* функции f(x). Если матрица Гессе Н(х*) положительно определена, точка х* будет точкой строгого локального минимума функции f(x). Последовательность x[k] сходится к точке х* только в том случае, когда матрица Гессе целевой функции положительно определена на каждой итерации.

Если функция f(x) является квадратичной, то, независимо от начального приближения х[0] и степени овражности, с помощью метода Ньютона ее минимум находится за один шаг. Это объясняется тем, что направление спуска р[k] H^-1(x[k])f’(x[k]) в любых точках х[0] всегда совпадает с направлением в точку минимума х*. Если же функция f(x) не квадратичная, но выпуклая, метод Ньютона гарантирует ее монотонное убывание от итерации к итерации. При минимизации овражных функций скорость сходимости метода Ньютона более высока по сравнению с градиентными методами. В таком случае вектор р[k] не указывает направление в точку минимума функции f(x), однако имеет большую составляющую вдоль оси оврага и значительно ближе к направлению на минимум, чем антиградиент.

Существенным недостатком метода Ньютона является зависимость сходимости для невыпуклых функций от начального приближения х[0]. Если х[0] находится достаточно далеко от точки минимума, то метод может расходиться, т. е. при проведении итерации каждая следующая точка будет более удаленной от точки минимума, чем предыдущая. Сходимость метода, независимо от начального приближения, обеспечивается выбором не только направления спуска р[k] H^-1(x[k])f’(x[k]), но и величины шага а вдоль этого направления. Соответствующий алгоритм называют методом Ньютона с регулировкой шага. Итерационный процесс в таком случае определяется выражением

x[k+l] x[k] - a_kH^-1(x[k])f’(x[k]).

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

f(x[k] – a_k H^-1(x[k])f’(x[k]) (f(x[k] - aH^-1(x[k])f’(x[k])).

Вследствие накопления ошибок в процессе счета матрица Гессе на некоторой итерации может оказаться отрицательно определенной или ее нельзя будет обратить. В таких случаях в подпрограммах оптимизации полагается H^-1(x[k]) Е , где Е — единичная матрица. Очевидно, что итерация при этом осуществляется по методу наискорейшего спуска.

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

Алгоритм метода Ньютона состоит в следующем.

1. В начальной точке х [0] вычисляется вектор

p[0]- H^-1(x[0])f’([0]).

2. На k-й итерации определяются шаг а_k и точка х[k+1].

3. Вычисляется величина f(х[k+1]).

4. Проверяются условия выхода из подпрограммы, реализующей данный алгоритм. Эти условия аналогичны условиям выхода из подпрограммы при методе наискорейшего спуска. Если эти условия выполняются, осуществляется прекращение вычислений. В противном случае вычисляется новое направление

р[k+1] –H^-1(x[k])f’([k])

и осуществляется переход к следующей итерации.

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

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

Линейное программирование

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

f(x) с₁x₁ + с₂x₂+...+с_nx_n (7.17)

при ограничениях (7.18) :

a₁₁x₁ + … a_1nx_n b₁;

. . . . . . . . . . . . . . . . . . .

a_m1x₁ + … a_mnx_n b_m;

a_m+1x₁+… a_m+1,nx_n b_m+1;

. . . . . . . . . . . . . . . . . . . (7.18)

a_kx₁ + … a_knx_n b_m;

a_k+1 x₁ + … a_k+1nx_n b_m;

a_m+1x₁ + … a_m+1,nx_n b_m+1;

. . . . . . . . . . . . . . . . . .

a_lx₁ + … a_lnx_n b_l;

x_i 0; i 1, …, n.

Каждое из условий-неравенств определяет полупространство, ограниченное гиперплоскостью. Пересечение полупространств образует выпуклый п-мерный многогранник Q. Условия равенства выделяют из n-мерного пространства (п-l) -мерную плоскость, пересечение которой с областью Q дает выпуклый (n-l) -мерный многогранник G. Экстремальное значение линейной формы (если оно существует) достигается в некоторой вершине многогранника. При вырождении оно может достигаться во всех точках ребра или грани многогранника. В силу изложенного для решения задачу линейного программирования теоретически достаточно вычислить значения функции в вершинах многогранника и найти среди этих значений наибольшее или наименьшее. Однако в практических задачах количество вершин области G настолько велико, что просмотр их даже с использованием ЭВМ невозможен. Поэтому разработаны специальные численные методы решения задач линейного программирования, которые ориентируются в основном на две формы записи задач. Каноническая форма задачи линейного программирования:

f(x) с₁х₁ + ...+ с_nx_n > ?max(min);(7.19)

a₁₁x₁ +… a_1nx_n b₁;

. . . . . . . . . . . . . . . . . .(7.20)

a_mx₁ +… a_mnx_n b_m;

x_i 0; i 1, …, n.

или в матричной форме:

(с, х) ? > max(min);(7.21)

Ax b,

х 0.

Здесь А (а_ij) - (mхn) - матрица условий. Ее столбцы (a_1j, ..., а_mj)^T , j 1, ..., п, называются векторами условий. Вектор b (b₁, ..., b_m)^T носит название вектора правых частей, а с (с₁, …, с_n) - вектора коэффициентов линейной формы.

Задача линейного программирования с однотипными условиями

f(x) с₁х₁ + ...+ с_nx_n ? > max(min);(7.22)

a₁₁x₁ +… a_1nx_n b₁;

. . . . . . . . . . . . . . . . . .

a_mx₁ +…a_mnx_n b_m;

или в матричной форме:

(с, х) ? > max(min);(7.23)

Ax b,

Любую задачу можно привести к каждой из приведенных форм с помощью приемов, описанных ниже.

Переход к эквивалентной системе неравенств.

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

a₁₁x₁ +…a_1nx_n b₁;

можно заменить условием

‑a₁₁x₁ +…‑a_1nx_n -b₁.

Переход от ограничения - неравенства к равенству

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

a₁x₁ +…a_nx_n b.

эквивалентно двум ограничениям:

‑a₁₁x₁+…‑a_1nx_n+x_n+1 b; x_n+1 b₁.

Представление ограничения-равенства парой неравенств.

Ограничение

a_lx₁ +… a_nx_n b;

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

a₁₁x₁ +… a_1nx_n b₁.

a₁₁x₁ +…-a_1nx_n -b₁.

Переход к неотрицательным переменным

Если на знак переменной х_i не наложено ограничений, можно заменить ее разностью двух неотрицательных переменных:

x_i x_n+2 - x_n+1, x_n+1 0; x_n+2 0.

Переход от переменных, ограниченных снизу, к неотрицательным переменным

Если переменная ограничена снизу х_i b_i то, заменив ее по формуле х_i у_i + b_i переходим к задаче с неотрицательной переменной у_i 0.

Наиболее употребительным численным методом решения задач линейного программирования является симплекс-метод.

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

Транспортная задача линейного программирования