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

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

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

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

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

2  Вычислить

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

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

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

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

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

Используется квадратичная аппроксимация f(x). Разложим функцию в ряд Тейлора и оставим члены второго порядка:

Нужно, чтобы в каждой вновь получаемой точке x(k+1) градиент аппроксимирующего полинома был равен нулю: ; .

Метод Ньютона обладает медленной сходимостью вдали от точки минимума, но хорошо сходится вблизи неё.

    Модифицированный метод Ньютона

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

Введём параметр длинны шага α(k) , который определяется из задачи минимизации функции f(x(k+1)), теперь

.

Такая формула обеспечивает убывание функции от итерации к итерациии.

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

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

,

где:  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.

9.  Положить , перейти к п. 5.

  Достоинства метода:

·  простота;

·  убывание целевой функции;

·  быстрая сходимость как вдали от точки оптимума, так и вблизи неё:

·  отсутствие поиска вдоль прямой.

  Недостаток:

·  необходимость вычисления матрицы Гессе на каждой итерации.

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

Численная аппроксимация градиентов

Способ: конечная разность вперёд.

e(i) – единичный орт того направления, по которому берём производную.

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

  Способ: центральная конечная разность.

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

  Способ: разность вперёд.

Формула аналогична разности назад.

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

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

  Свойство квадратичной функции, на котором основаны методы.

  Пусть q(x) – квадратичная функция и есть две произвольные несовпадающие точки x(0) и x(1), тогда: .

g(x(0))=c∆x(0)+b, g(x(1))=c∆x(1)+b.

Найдём изменение градиента при переходе из x(0) в x(1):

Метод Флетчера-Ривса

Пусть дана целевая квадратичная функция  

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

.

В данном методе S(k) ищется по формуле:

,

где

.

Величины γi выбираются так, чтобы новое направление S(k) было сопряжено со всеми предыдущими направлениями. При этом критерием окончания поиска является выполнение условия: .

Определим γi.

Рассмотрим первое направление. k=1.

Наложим условия C-сопряжённости направлений S(1) и S(0):

На первой итерации

; ;  - константа.

Отсюда можем найти γ(0)

;

;

При соответствующем выборе α(0) и использовании условия  имеем .