Шаг 1. Задать начальную точку х (0) и систему N линейно независимых направлений; возможен случай, когда s (i) = e (i) i = 1, 2, 3,..., N.

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

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

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

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

Из способа построения алгоритма следует, что в случае, когда целевая функция квадратична и обладает минимумом, точка минимума находится в результате реализации N циклов, включающих шаги 2, 3 и 4, где N - количество переменных. Если же функция не является квадратичной, то требуется более чем N циклов. Вместе с тем можно дать строгое доказательство того, что при некотором предположении метод Пауэлла сходится к точке локального мини­мума с суперлинейной скоростью (см. данное ниже определение).

Скорость сходимости. Рассматриваемый метод позволяет построить последовательность точек х (k) , которая сходится к решению x*. Метод называется сходящимся, если неравенство

≤ 1, где (3.39)

= x – х* , (3.40)

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

, (3.41)

где С - постоянная величина. Из формулы (3.39) следует, что при r = 1имеет место неравенство С ≤ 1. Если r = 1или r = 2, то алгоритм характеризуется линейной или квадратичной скоростью сходимости соответственно. При r = 1и С = 0 алгоритм характеризуется суперлинейной скоростью сходимости.

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

Найти точку минимума функции

f(x) = 2x + 4x x – 10x x + x ,

если задана начальная точка х (0) = T , в которой f (x (0)) = 314.

Шаг 1. s (1) = T , s (2) = T .

Шаг 2. (а) Найдем такое значение λ, при котором

f (x (0) + λs (2)) → min.

Получим: λ* - 0,81, откуда

x (l) = T - 0,81 T = T , f (x (l)) = 250.

(б) Найдем такое значение λ, при котором f (x (1) + λs (1)) → min.

λ* = – 3,26, x (2) = T , f (x (2)) = 1.10.

(в) Найдем такое значение λ, при котором f (x (2) + λs (2)) → min.

λ* = – 0.098, x (3) = T , f (x (3)) = 0.72.

Шаг 3. Положим s (3) = х (3) - x (1) = [-3.26,-0.098] T . После нормировки получим

s (3) = = [– 0,99955, – 0,03] T .

Положим s (1) = s (2) , s (2) = s (3) и перейдем к шагу 2 алгоритма.

Шаг 4. Найдем такое значение λ, при котором f (x (3) + λs (2)) → min.

λ* = – 0.734, x (4) = T , f (x (4)) = – 2,86.

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

Направления поиска, полученные в процессе реализации метода, показаны на рис. 3.13.

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

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

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

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

f(x) = 2x + 4x x – 10x x + x

Рис. 3.13. Решение задачи из примера 3.6 по методу сопряженных направлений Пауэлла.

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

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

x = x + α s (x ) (3.42)

где x - текущее приближение к решению х*; α - параметр характеризующий длину шага; s (x ) = s - направление поиска в N-мерном пространстве управляемых переменных x i , i = 1, 2, 3,..., N .Способ определения s(x) и α на каждой итерации связан с особенностями применяемого метода. Обычно выбор α осуществляется путем решения задачи минимизации f(x) в направлении s (x ). Поэтому при реализации изучаемых методов необходимо использовать эффективные алгоритмы одномерной минимизации.

3.3.1. Метод Коши

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

f(x) = f ()+ f() ∆x+ … (3.43)

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

s () = – f(), (3.44)

и второе слагаемое примет вид

–α f () f ().

Рассмотренный случай соответствует наискорейшему локальному спуску. Поэтому в основе простейшего градиентного метода лежит формула

x = x – α f (x ), (3.45)

где α - заданный положительный параметр. Метод обладает двумя недостатками: во-первых, возникает необходимость выбора подходящего значения α, и, во-вторых, методу свойственна медленная сходимость к точке минимума вследствие малости f в окрестности этой точки.

Таким образом, целесообразно определять значение α на каждой итерации

x = x – α f (x ), (3.46)

Значение α вычисляется путем решения задачи минимизации f (x (k +1)) вдоль направления f (x ) с помощью того или иного метода одномерного поиска. Рассматриваемый градиентный метод носит название метода наискорейшего спуска, или метода Коши, поскольку Коши первым использовал аналогичный алгоритм для решения систем линейных уравнений.

Поиск вдоль прямой в соответствии с формулой (3.46) обеспечивает более высокую надежность метода Коши по сравнению с про­стейшим градиентным методом, однако скорость его сходимости при решении ряда практических задач остается недопустимо низкой. Это вполне объяснимо, поскольку изменения переменных непосредственно зависят от величины градиента, которая стремится к нулю в окрестности точки минимума, и отсутствует механизм ускорения движения к точке минимума на последних итерациях. Одно из глав­ных преимуществ метода Коши связано с его устойчивостью. Метод обладает важным свойством, которое заключается в том, что при достаточно малой длине шага итерации обеспечивают выполнение неравенства

f (x ) ≤ f (x ). (3.47)

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

Пример 3.7. Метод Коши

Рассмотрим функцию

f(x) = 8x + 4x x + 5x

и используем метод Коши для решения задачи ее минимизации.

Решение. Прежде всего вычислим компоненты градиента

= 16x + 4x , = 10x + 4x .

Для того чтобы применить метод наискорейшего спуска, зададим начальное приближение

x (0) = T

и с помощью формулы (3.46) построим новое приближение

x = x -α f (x )

f (x) = 8x + 4x x + 5x

Рис. 3.14. Итерации по методу Коши с использованием метода квадратичной интерполяции.

Таблица 3.1. Результаты вычислений по методу Коши

Выберем α таким образом, чтобы f (x (1)) → min.; α = 0,056. Следовательно, x (1) = [– 1,20, 2.16] T Далее найдем точку

x = x – α f (x ),

вычислив градиент в точке x и проведя поиск вдоль прямой.

В таблице 3.1 представлены данные, полученные при проведении итераций на основе одномерного поиска по методу квадратичной интерполяции . Последовательность полученных точек изображена на рис. 3.14.

Несмотря на то что метод Коши не имеет большого практического значения, он реализует важнейшие шаги большинства градиентных методов. Блок-схема алгоритма Коши приведена на рис. 3.15. Заметим, что работа алгоритма завершается, когда модуль градиента или модуль вектора ∆x становится достаточно малым.

Рис. 3.15. Блок-схема метода Коши.

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

Нетрудно видеть, что в методе Коши применяется «наилучшая» локальная стратегия поиска с использованием градиента. Однако* движение в направлении, противоположном градиенту, приводит в точку минимума лишь в том случае, когда линии уровня функции f представляют собой окружности. Таким образом, направление, противоположное градиенту, вообще говоря, не может служить приемлемым глобальным направлением поиска точек оптимума нелинейных функций. Метод Коши основывается на последовательной линейной аппроксимации целевой функции и требует вычисления значений функции и ее первых производных на каждой итерации. Для того чтобы построить более общую стратегию поиска, следует привлечь информацию о вторых производных целевой функции.

Опять разложим целевую функцию в ряд Тейлора

f(x)=f(x )+ f(x ) ∆x+½∆x f(x )∆x+O(∆x³).

Отбрасывая все члены разложения третьего порядка и выше, полу­чим квадратичную аппроксимацию f(x):

(x; x ) = f(x ) + f(x ) T ∆x + ½∆x f(x )∆x, (3.48)

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

(x; x ) = + f(x )+ f(x ) = 0, (3.49)

Метод деформируемого многогранника (метод Нелдера--Мида)

Данный метод состоит в том, что для минимизации функции п переменных f(х) в n-мерном пространстве строится многогранник, содержащий (п + 1) вершину. Очевидно, что каждая вершина соответствует некоторому вектору х. Вычисляются значения целевой функции f(х) в каждой из вершин многогранника, определяются максимальное из этих значений и соответствующая ему вершина х[h]. Через эту вершину и центр тяжести остальных вершин проводится проецирующая прямая, на которой находится точка х[q] с меньшим значением целевой функции, чем в вершине х[h] (Рис. 7.6). Затем исключается вершина х[h]. Из оставшихся вершин и точки x[q] строится новый многогранник, с которым повторяется описанная процедура. В процессе выполнения данных операций многогранник изменяет свои размеры, что и обусловило название метода.

Геометрическая интерпретация метода деформируемого многогранника

Метод Нелдера-Мида.

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

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

Вводится симплекс, координаты которого заданы таблицей (одна из вершин в начале координат)

Если, то, в частности, для имеем

Расположение симплекса показано на рис. 7.7.

Легко убедиться в том, что если координаты вершины симплекса задавать в соответствии с матрицей, то расстояние между любыми двумя верши-нами симплекса всегда будет равно выбранной константе t независимо от размерности задачи n. Действительно, расстояние между любой вершиной, и вершиной равно

С другой стороны, расстояние между любой парой вершин,также равно t.

Действительно,

Зададим начальную точку поиска вектором. Перенесем исходный симплекс таким образом, чтобы вершина, находившаяся в начале координат, оказалась в точке. Получим матрицу

Вычислим значения оптимизируемой функции в точках и перенумеруем точки так, чтобы выполнялись неравенства

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

Осуществим отражение вершины относительно центра тяжести. Получим точку. Если то получится зеркальное отражение. Сравним теперь между собой значения. Возможны следующие варианты:

В этом случае выполняется растяжение и отыскивается точка. Параметр обычно принимают равным 1.5. Полученная точка V заменяет, если В противном случае для замены используется точка.

В этом случае реализуется отражение. Точка заменяет.

В этом случае осуществляется сжатие и отыскивается точка. Параметр обычно принимают равным 0.5. Полученная точка заменяет.

При этом осуществляется редукция (уменьшение размера симплекса с подтягиванием всех вершин к). Координаты вершины нового симплекса рассчитываются по формуле

Критерий останова:

Критерий останова является составным. При этом его компоненты имеют различный вес в зависимости от того, каков характер оптимизируемой функции в окрестности экстремума. Если в районе экстремума оптимизируемая функция изменяется по типу ""глубокая впадина"", то больший вклад в численное значение критерия вносит первое слагаемое, а второе при этом быстро уменьшается. Напротив, если оптимизируемая функция изменяется по типу ""пологое плато"", то первое слагаемое быстро становится малым, и поэтому второе слагаемое вносит больший вклад в величину критерия.

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

Пусть координаты центра тяжести симплекса образуют вектор

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

Матрица координат указанного симплекса имеет вид:

Координаты центра тяжести этого симплекса образуют вектор

Теперь координаты точки найдем из равенства

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

"Метод сопряженных направлений"

Введение

сопряженный направление пауэлл квадратичный

Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходиться заниматься в повседневной жизни. Термином оптимизация в литературе обозначает процесс или последовательность операций, позволяющих получить уточненное решение. Хотя конечной целью оптимизации является отыскание наилучшего или оптимального решения, обычно приходится довольствоваться улучшением известных решений, а не доведением их до совершенства. Поэтому под оптимизацией понимают скорее стремление к совершенству, которое, возможно, и не будет достигнуто.

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

Цель данной курсовой работы:

проанализировать и обработать теоретические и экспериментальные данные по теме метод сопряженных направлений;

анализ собранной информации;

сравнительный анализ с другими методами;

разработка программы, реализующая данный метод.

Метод сопряженных направлений. Постановка задачи

Требуется найти безусловный минимум функции f(x) многих переменных, т.е. найти точку

Определение. Пусть H - симметрическая матрица размера n x n. Векторы называются H-сопряженными или просто сопряженными, если при всех.

Стратегия поиска

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

Для квадратичных функций последовательностью n2 одномерных поисков приводит к точке минимума (если все операции выполнены точно). Построение сопряженного направления для квадратичной функции при n = 2 изображено на рисунке 1.1. Оно проходит через точки 1 и 3.

Рисунок 1.1 - Построение сопряженного направления для квадратичной функции

Описание алгоритма метода напряженных направлений

Шаг 1. Задать начальную точку х 0 , число ε>0 для окончания алгоритма, начальные направления поиска

Положим d0 = dn , i = 0, у0 = х0, k= 0.

Шаг 2. Найти yi+1 = y i +ti di где шаг ti находится в результате поиска ми-нимума функции f(yi+tidi) по ti одним из методов одномерной минимизации.

Шаг 3. Проверить выполнение условий:

а)если i < n -1, положить i= i +1 и перейти к шагу 2;

б)если I = n -1, проверить успешность поиска по n первым направлениям.

Если у n = у, то поиск завершить: х* =yn, иначе положить i=i+1 и перей-ти к шагу 2;

в) если i = n, проверить успешность поиска по n последним направле-ниям. Если y n+1 = у 1, поиск завершить: х* = у n+1, иначе перейти к шагу 4 для построения сопряженного направления.

Шаг 4. Положить хk+1 = уn+1 и проверить условие окончания:

а)если |||хk+1 - хk || | < ε, то поиск завершить: х* = хk+1;

б)иначе положить: d0 = dn = уn+1 - у1 (новое направление);

(исключается старое направление).

Если при этом rang (,...,)= п, то новая система направлений линей-но независима. В этом случае положить: di =di , i = 0,1,...,n; k =k +1, i = 0, у0 = xk+i и перейти к шагу 2.

Если rang(,...,)< n, то новая система направлений линейно зави-сима. Тогда следует продолжать поиск в старых направлениях Для этого поло-жить: di =di , i = 0,1,...,n; у0 = xk+1, k = k + 1, i = 0 и перейти к шагу 2.

Входные данные

Задать начальную точку, к примеру, число ε > 0 для окончания алгоритма, к примеру ε =0,1, начальные направления поиска:

Положить d0 = d2= , i = 0, у0 = х0, k= 0.

Пример поиска минимума функции методом Пауэлла

Пример. Найти минимум функции f(x) = 4(х1 -5)2 +(х2 -6) → min мето-дом Пауэлла.

□ 1. Зададим начальную точку х = (8,9)T, ε=0,1. По-ложим d0=dn= d2 ; у0 = х0 , i=0, k = 0.

Получаем у1 = у0 +t0d0 = (8,9)T + t0(0,1)T = (8,9 + t0)T - Найдем мини-мум функции f(8,9 + t0) = 36 + (3 + t0)2 по t0. Очевидно, t0 = -3, а у1 = (8,6)T.

Имеем i = 0 < 2 = n, поэтому i = i + 1 = 1 и перейдем к шагу 2.

21.Получаем у2 = у1 + t1d1 = (8,6)T + ti(l,0)T = (8 + t1,6)T. Найдем минимум функции f(8 + t1 , 6) = 4(3 +t1)2 по t1. Очевидно, он достигается при t1 =-3. Тогда у2 =

Метод ПауэлаМетод ориентирован на решение задач с квадратичными целевыми функциями, т.е.
функциями вида:
f(x) = a + bTx + 1/2xTCx,
где Q(x) = xTCx – квадратичная форма.
Т.к. в окрестности точки оптимума любую нелинейную функцию можно аппроксимировать
квадратичной функцией (поскольку линейный член разложения Тейлора обращается в нуль),
то метод может быть применен и для нелинейной целевой функции общего вида.
Метод Пауэлла использует свойство квадратичной функции, заключающееся в том, что
любая прямая, которая проходит через точку минимума функции х*, пересекает под равными
углами касательные к поверхностям равного уровня функции в точках пересечения.

Метод Пауэла

Метод Пауэла

Метод Пауэла

Алгоритм метода Пауэлла

Алгоритм метода Пауэлла

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

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

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

Для применения метода на практике его необходимо дополнить процедурами проверки сходимости и линейной независимости системы направлений. Если целевая функция квадратична и обладает минимумом, то точка минимума находится в результате реализации 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 2 W(x k) -1 DW(x k). (13.12)

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

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

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