Ctrl+K

Локальная минимизация по одной переменной

Локальная минимизация по одной переменной#

.

Цель семинара - научиться минимизировать произвольно заданную непрерывную функцию.

Начнём с локальных методов от одной переменной - наиболее показательный раздел.

Данная задача также называется задачей оптимизации. Понятно, что эта задача аналогична поиску максимума.

image.png

Дихотомия#

Пусть имеем не слишком осциллирующую непрерывную функцию \(f:[a, b] \rightarrow \mathbb{R}\). Алгоритм дихотомии выглядит следующим образом:

Алгоритм дихотомии

  1. Возьмём \([a, b]\) за начальную локализацию минимума. Фиксируем малый \(\varepsilon > 0\).

  2. Пусть текущая локализация минимума - отрезок \([a_n, b_n]\). Берём точку \(c_n = \frac{a_n + b_n}{2}\) и смотрим, в какую сторону от неё функция уменьшается. Иными словами, считаем \(f_\text{left} = f(c_n - \varepsilon)\) и \(f_\text{right} = f(c_n + \varepsilon)\).

  3. Если \(f_\text{left} < f_\text{right}\), то локальный минимум слева и \([a_{n+1}, b_{n+1}] = [a_n, c_n]\). Иначе, локальный минимум справа и \([a_{n+1}, b_{n+1}] = [c_n, b_n]\).

  4. Если длина \([a_{n+1}, b_{n+1}]\) меньше \(\varepsilon\), останавливаемся и выдаём среднюю точку. Иначе, на шаг 1.

Метод прост и красив, но требует много вычислений функции (что может быть очень дорого). Так же для метода не нужна дифференциируемость \(f\) и ошибка уменьшается экспонциально от количества шагов:

\[r \sim 2^{-n}\]

Метод чисел Фиббоначи (золотого сечения)#

Если операция вычисления непрерывной функции \(f:[a, b] \rightarrow \mathbb{R}\) является очень дорогой по времени, разумно использовать следующий алгоритм чисел Фиббоначи, использующий вызовы функции с предыдущих итераций. В нём мы заранее фиксируем \(N\) - количество вызовов функции \(f\).

В алгоритме используются \(F_n\) - стандартные числа Фиббоначи \((1, 1, 2, 3, 5, ...)\).

Алгоритм чисел Фиббоначи

  1. Задаются начальные границы отрезка \(a, b\) и число итераций \(N\). Счётчик \(n = N\).

    • Рассчитывают начальные точки деления: \(x_1=a+(b-a) \frac{F_{n-2}}{F_n}, \quad x_2=a+(b-a) \frac{F_{n-1}}{F_n}\)

    • И значения в них целевой функции: \(f_1=f\left(x_1\right), f_2=f\left(x_2\right)\).

  2. Уменьшаем счётчик \(n = N - 1\)

    • Если \(f_1>f_2\), то сужаем отрезок слева \(a=x_1, \; x_1=x_2\). И модифицированный шаг 1: \(x_2=b-\left(x_1-a\right), \; f_1=f_2, \; f_2=f\left(x_2\right)\)

    • Иначе, сужаем отрезок справа \(b=x_2, \; x_2=x_1\). Модифицированный шаг 1: \(x_1=a+\left(b-x_2\right), \; f_2=f_1, \; >f_1=f\left(x_1\right)\).

  3. Если \(n=1\), то останавливаемся и выдаём \(\frac{x_1 + x_2}{2}\).

    • Иначе, на шаг 2.

Ошибку в вычислении минимума от числа итераций \(N\) можно оценить как

\[ \varepsilon_N \approx \cfrac{(\sqrt{5}-1) / 2)^N(b-a)}{2} \]

Несложно обобщить данный метод на произвольной число итераций с учётом \(\Phi=\lim _{n \rightarrow \infty} \frac{F_{n+1}}{F_n}\) (это соответствует \(N = \infty\) в алгоритме). В таком случае критерием остановки будет \(x_2 - x_1 < \varepsilon\). Такой метод называется методом золотого сечения.

На практике рекомендуется использовать реализованный кем-то другим алгоритм Брента - он использует параболическую интерполяцию (аппроксимацию по трём точкам) для ускорения сходимости метода золотого сечения.

import numpy as np
from scipy.optimize import minimize_scalar # За нас всё уже реализовали :)

def f(x):
    return np.cos(x)

res = minimize_scalar(f) # По умолчанию использует метод Брента

print(res)

res.x, res.fun, res.nit # Сошёлся за 8 итераций!

 message: 
          Optimization terminated successfully;
          The returned value satisfies the termination criteria
          (using xtol = 1.48e-08 )
 success: True
     fun: -1.0
       x: 3.1415926536439596
     nit: 8
    nfev: 12

(3.1415926536439596, -1.0, 8)
Содержание