Основы теории оптимизации (стр. 53 )

Эти задачи отличаются особым видом градиента и матрицы Гессе:

где  — матрица Якоби вектор-функции ,  — матрица Гессе для её компоненты .

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

Метод Гаусса — Ньютона

Метод Гаусса — Ньютона строится на предположении о том, что слагаемое доминирует над . Это требование не соблюдается, если минимальные невязки велики, то есть если норма сравнима с максимальным собственным значением матрицы . В противном случае можно записать:

Таким образом, когда норма близка к нулю, а матрица имеет полный столбцевой ранг, направление мало отличается от ньютоновского (с учётом Q( )), и метод может достигать квадратичной скорости сходимости, хотя вторые производные и не учитываются. Улучшением метода является алгоритм Левенберга — Марквардта, основанный на эвристических соображениях.

Обобщение на комплексную плоскость

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

Особый интерес представляет выбор начального приближения z0. Ввиду того, что функция может иметь несколько нулей, в различных случаях метод может сходиться к различным значениям, и вполне естественно возникает желание выяснить, какие области обеспечат сходимость к тому или иному корню. Этот вопрос заинтересовал Артура Кейли ещё в 1879 году, однако разрешить его смогли лишь в 70-х годах двадцатого столетия с появлением вычислительной техники. Оказалось, что на пересечениях этих областей (их принято называть областями притяжения) образуются так называемые фракталы — бесконечные самоподобные геометрические фигуры. Ввиду того, что Ньютон применял свой метод исключительно к полиномам, фракталы, образованные в результате такого применения, обрели название фракталов Ньютона или бассейнов Ньютона.

5.6. Метод Коши

Пусть в точке  требуется определить направление наискорейшего спуска (то есть направление наибольшего локального уменьшения f(x) ). Разложим f(x) в ряд Тейлора в окрестности точки  и отбросим члены второго порядка по ∆x и выше.

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

выбором S(k): , тогда второе слагаемое примет вид: .

Этот случай соответствует наискорейшему локальному спуску .

Недостатки:

·  остаётся вопрос выбора α;

·  вблизи точки минимума медленно сходится, так как .

α будем находить путём минимизации функции f(x(k+1)) в направлении .

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

Достоинсиво:

на каждой итерации  - выполняется свойство убывания функции на каждой итерации.

  Алгоритм метода:

1  Задать  - начальное приближение, параметр окончания работы алгоритма Коши, параметр окончания работы одномерного алгоритма, количество переменных  и максимальное количество итераций соответственно.

2  Вычислить

3  Если , то xk=x* иначе, если , то xk=x*. Перейти к п. 4.

4  Решить задачу минимизации функции f(x(k+1)) и найти  используя ε2

5  Вычислить следующее приближение по формуле

6  Если , то xk=x* иначе k=k+1 и перейти к п. 2.

5.7. Метод Марквардта

Это комбинация методов Ньютона и Коши. Вдали от точки минимума направление определяется по методу Коши, а в окрестности точки минимума – по методу Ньютона.

,

где:  H(k) – матрица Гессе (вторых производных;

  I – единичная матрица;

 λ(k) – параметр, определяющий направление поиска и длину шага.

При этом в формуле

 .

На начальном этапе λ(k) ≈104, при этом второй член в  много больше первого, поэтому поиск осуществляется по методу Коши. По мере приближения к точке оптимума λ(k) уменьшается и стремится к нулю. Таким образом вблизи точки оптимума первый член много больше второго и поиск осуществляется по методу Ньютона.

Если после первого шага f(x(1))< f(x(0)), то следует выбрать λ(1) <λ(0) и реализовать следующий шаг, в противном случае λ(0)=β∙ λ(0) , где β>1 и повторить предыдущий шаг.

  Алгоритм.

  1.  Задать x0 – начальное приближение, M – максимальное количество итераций, N – количество переменных и ε - параметр сходимости.

2.  При k=0 λ(k) =104

3.  Вычислить компоненты вектора .

4.  Если , то xk=x* иначе, если , то xk=x*. Перейти к п. 5.

5.  Вычислить S(k).

6.  Вычислить x(k+1)= x(k)+S(k)

7.  Если f(x(k +1))> f(x(k)), то перейти к п. 9, иначе перейти к п. 8.

8.  Положить , k=k+1, перейти к п. 3.