Лекция: Составить алгоритм поиска экстремума функции двух переменных
F (x1, x2) = x14 +x12 + x1x2 – 2 x22
методом «тяжелого шарика
Метод тяжелого шарика.
Градиентный метод решения задачи безусловной минимизации
| f(x) → min, | (1) |
где f: Rm → R, можно интерпретировать в терминах обыкновенных дифференциальных уравнений следующим образом. Рассмотрим дифференциальное уравнение
| px·+ f ′(x) = 0 | (2) |
(здесь точка над x обозначает производную по независимой переменной t, а f ′(x) как обычно обозначает градиент отображения f: Rm → R; предполагается, что p > 0). Простейший разностный аналог уравнения (2), а именно, явная схема Эйлера
|
и есть градиентный метод для задачи (1):
| (3) |
Рассмотрим теперь вместо уравнения (2) уравнение
| mx··+ px·+ f ′(x) = 0, |
| описывающее движение шарика массы m в потенциальном поле f ′ при наличии силы трения. Потери энергии на трение вынудят шарик спуститься в точку минимума потенциала f, а силы инерции не дадут ему осциллировать так, как это изображено на рис. 8. Это позволяет надеяться, что изменение уравнения (2) введением в него инерционного члена mx··улучшит сходимость градиентного метода (3). Конечно-разностный аналог уравнения, описыавющего движение шарика — это, например, уравнение |
|
После простых преобразований и очевидных обозначений мы получаем
| xn+1 = xn – αf ′(xn) + β(xn – xn–1). | (4) |
Итерационная формула (4) задает метод тяжелого шарика решения задачи безусловной оптимизации (см. рис. 14; ср. с рис. 8).
Рис. 14.
Можно доказать, что в условиях теоремы 3.7 метод тяжелого шарика при α = 2/(√Λ + √λ)2 и β = (√Λ – √λ)/(√Λ +√λ)2сходится со скоростью геометрической прогрессии со знаменателем q = (√Λ –√λ)/(√Λ + √λ).
Если теперь сравнить знаменатели qгм = (Λ – λ)/(Λ + λ) и qмтш = (√Λ – √λ)/(√Λ + √λ), характеризующие скорости сходимости градиентного метода и метода тяжелого шарика, соответственно, то для плохо обусловленных функций, т. е. для функций с μ = Λ /λ >> 1, очевидно, qгм ≈ 1– 2/μ, а qмтш ≈ 1 – 2/√μ. Поэтому для уменьшения погрешности в e ≈ 2.718 раз градиентный метод с постоянным оптимальным шагом требует –[ln(1 – 2/μ)]–1 ≈ μ)/2 итераций, а метод тяжелого шарика –ln(1 – 2/√μ)]–1 ≈ √μ/2. Для больших μ это весьма значительный выигрыш, поскольку объем вычислений в методе тяжелого шарика почти не отличается от объема вычислений в градиентном методе.