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

(15)

Тогда приходим к методу

(16)

При αk=0 метод переходит в метод Ньютона, при αk→∞ направление движения стремится к антиградиенту. Таким обра­зом, (16) представляет собой компромисс между этими двумя методами. За счет выбора αk можно добиться глобальной схо­димости метода.

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

Есть специальные модификации метода Ньютона, в которых матрица 2f(xk) заменяется на некоторую положительно опре­деленную, если сама 2f(xk) таковой не является.

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

Таким образом, попытки «слегка подправить» градиентный метод и метод Ньютона хотя и позволяют устранить некоторые их недостатки, но не меняют положение с наиболее серьезными их дефектами — медленной сходимостью градиентного метода и трудоемкостью метода Ньютона. 

5.9. Сравнение методов одномерного поиска

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

  Таблица 1. Сравнение методов одномерного поиска по значением коэффициента дробления интервала неопределенности f

Количество вычислений целевой функции N	Общий поиск	Деление отрезка пополам	Метод дихотомии	Метод золотого сечения	Метод Фибоначчи
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20	1,0 0,667 0,500 0,400 0,333 0,286 0,250 0,222 0,200 0,182 0,167 0,154 0,143 0,133 0,125 0,118 0,111 0,105 0,100 0,095	1,0 - 0,500 - 0,250 - 0,125 - 0,0625 - 0,0312 - 0,0156 - 0,00781 - 0,00391 - 0,00195 -	1,0 0,500 - 0,250 - 0,125 - 0,0625 - 0,0312 - 0,0156 - 0,00781 - 0,00391 - 0,00195 - 0,000976	1,0 0,618 0,382 0,236 0,146 0,090 0,056 0,345 0,0213 0,0132 0,00813 0,00502 0,00311 0,00192 0,00119 0,000733 0,000453 0,000280 0,000173 0,000107	1,0 0,500 0,333 0,200 0,125 0,077 0,048 0,0294 0,0182 0,0112 0,00694 0,00429 0,00265 0,00164 0,00101 0,000626 0,000387 0,000239 0,000148 0,0000913

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

Универсальность алгоритма означает, что его можно легко применить для решения самых разнообразных задач. В этом отношении метод Фибоначчи, уступает другим, так как нуждается в отдельном вычислении положения точек, в которых будет определяться значение целевой функции на каждом новом шаге. Этим приходится расплачиваться за повышение эффективности метода. С точки зрения универсальности малоэффективный метод общего поиска имеет по крайней мере одно преимущество - его можно с успехом применять и для неунимодальных функций, если они достаточно тучные. Нередко заранее не известно, есть ли рассмотренная целевая функция унимодальной. В таких случаях нужно использовать несколько разных алгоритмов и посмотреть, дают ли они все один и тот самый оптимум. Отсюда следует важный вывод, который нужно иметь в виду, решая задачи оптимизации: не существует универсального алгоритма, который позволял бы решать любые задачи. Решая сложные задачи оптимизации, нужно пользоваться разными методами, так как это позволяет увеличить судьбу удобных решений.

Пример 1. Одномерная минимизация в среде Mathcad

Для нахождения минимума одномерной функции в среде Mathcad используется функция root(f(var1, var2, ...),var1, [a, b]) – возвращает переменную var1, которая лежит между a и b, в которой решаемая функция равна нулю.

Параметры:

f – уравнение, которое следует решить;

var1 – корень уравнения;

[a, b] – отрезок, на котором ищется решение уравнения.

Например, необходимо найти минимум гладкой унимодальной функции у=х2+ех, используя необходимое условие минимума.

Определим целевую функцию

Определим первую производную целевой функции

Определим вторую производную целевой функции

Достаточное условие унимодальности (f''(x)>0) выполненная

 

Минимум гдадкой функции достигается в стационарной точке (f'(x)=0).

Решим уравнение f'(x)=0, используя функцию root; начальное приближение корня пусть равно нулю (х=0)

Точка минимума х=-0.351732

Значение функции в точке минимума

Подтвердим результаты вычислений графически

5.10. Многошаговые методы

В градиентном методе на каждом шаге никак не исполь­зуется информация, полученная на предыдущих итерациях. Естественно попытаться учесть «предысторию» процесса для ускорения сходимости. Такого рода методы, в которых новое приближение зависит от s предыдущих:

xk+1 = φk( xk+1,..., xk-s+1), (1)

называются s-шаговыми. Градиентный метод и метод Ньютона были одношаговыми, теперь рассмотрим многошаговые (s > 1) методы.

1. Метод тяжелого шарика. Одним из простейших многоша­говых методов является двухшаговый метод тяжелого шарика

(2)

где— некоторые параметры. Ясно, что при β = 0

метод (2) переходит в градиентный. Свое название метод полу­чил из-за следующей физической аналогии. Движение тела («тяжелого шарика») в потенциальном поле при наличии силы трения (или вязкости) описывается дифференциальным урав­нением второго порядка

(3)

Ясно, что из-за потери энергии на трение тело в конце концов окажется в точке минимума потенциала f(x). Таким образом, тяжелый шарик «решает» соответствующую задачу минимиза­ции. Если рассмотреть разностный аналог уравнения (3), то придем к итерационному методу (2).

Введение инерции движения (член в итерационный процесс может привести к ускорению сходимости. Это видно, например, из рис. 1 — вместо зигзагообразного движения в градиентном методе в данном случае получается более плав­ная траектория по «дну оврага».

Рис. 1. Метод тяжелого шарика (а) и градиентный метод (б).

Эти эвристические соображе­ния подкрепляются следующей теоремой

Теорема 1. Пусть х*— невырожденная точка минимума Тогда при

(4)

найдется ε > 0 такое, что при любых

метод (2) сходится к х* со скоростью геометри-

ческой прогрессии.

(5)

Величина q минимальна и равна

(6)

Схема доказательства. В данном случае непосред­ственно применить приемы исследования сходимости, описан­ные ранее, нельзя, так как все они рассчитаны на одношаговые процессы. Можно, однако, использовать способ увеличения размерности пространства, позволяющий свести многошаговый процесс к одношаговому. Введем 2п-мерный вектор zk = {xk — х*, xk-1 — х*}. Тогда итерационный процесс (2) может быть записан в форме

(7)

где квадратная матрица А размерности 2п×2п и имеет вид

(8)

Пусть— собственные значения

матрицы В. Toгдa собственные значения ρj, j= 1, .... 2п, ма­трицы А совпадают с собственными значениями матриц 2×2 вида