Методы одномерной оптимизации

План лекции

1. Постановка задачи одномерной оптимизации

2. Унимодальные функции

3. Метод равномерного поиска

4. Метод дихотомии

5. Метод золотого сечения

6. Метод Фибоначчи

7. Сравнение методов

8. Программная реализация

1. Постановка задачи

Задача одномерной безусловной оптимизации:

$$f(x^*) = \min_{x \in [a, b]} f(x)$$

Дано:

• Функция $f(x)$, заданная на отрезке $[a, b]$
• Точность $\varepsilon > 0$

Найти:

• Приближённое значение $x^*$ — точки минимума
• Приближённое значение $f(x^*)$ — минимума функции

Предположения:

• $f(x)$ — унимодальная на $[a, b]$
• Вычисление $f(x)$ — единственная доступная операция

Прямые методы оптимизации

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

2. Унимодальные функции

Унимодальность: правило сужения

Правило сравнения: если $x_1 < x_2$, то:

Наглядно:

Это правило — основа всех прямых методов одномерной оптимизации.

3. Метод равномерного поиска

Идея: разбить отрезок $[a, b]$ на $n$ равных частей, вычислить $f(x)$ во всех точках, выбрать точку с наименьшим значением.

Шаг сетки: $h = \dfrac{b - a}{n}$

Пробные точки: $x_i = a + ih, \quad i = 0, 1, \ldots, n$

Оценка точности: $|x^* - \tilde{x}^*| \leq h = \dfrac{b - a}{n}$

Число вычислений функции: $N = n + 1$

Точность: $\varepsilon = \dfrac{b - a}{N - 1}$

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

Метод равномерного поиска: эффективность

Для достижения точности $\varepsilon$ требуется:

$$N = \frac{b - a}{\varepsilon} + 1$$

Пример: $[a, b] = [0, 10]$, $\varepsilon = 0.001$

$$N = \frac{10}{0.001} + 1 = 10001 \text{ вычислений}$$

Проблема: линейная сходимость — отрезок сокращается медленно.

Вопрос: можно ли достичь той же точности при меньшем числе вычислений? → Да, если вычисления выполнять адаптивно.

4. Метод дихотомии (половинного деления)

Идея: на каждой итерации делить отрезок пополам и сужать его по правилу унимодальности.

Алгоритм:

1. Вычислить $x_m = \dfrac{a + b}{2}$
2. Задать малое $\delta > 0$, вычислить $x_1 = x_m - \delta$, $x_2 = x_m + \delta$
3. Вычислить $f(x_1)$ и $f(x_2)$
4. Если $f(x_1) < f(x_2)$: $b \leftarrow x_m$ (минимум слева)
5. Если $f(x_1) > f(x_2)$: $a \leftarrow x_m$ (минимум справа)
6. Если $|b - a| < \varepsilon$: стоп, иначе → шаг 1

Сходимость: отрезок сокращается примерно в 2 раза за итерацию.

Метод дихотомии: иллюстрация

Пример: $f(x) = x^2 - 6x + 10$ на $[0, 4]$, $\delta = 0.01$, $x^* = 3$

Метод дихотомии: эффективность

Критерий останова: $|b - a| \leq \varepsilon$

Число итераций: $n \geq \log_2 \dfrac{b - a}{\varepsilon}$

Число вычислений функции: $N = 2n = 2\log_2 \dfrac{b-a}{\varepsilon}$

Пример: $[0, 10]$, $\varepsilon = 0.001$

$$N = 2 \log_2 \frac{10}{0.001} = 2 \cdot 13.29 \approx 27 \text{ вычислений}$$

Сравнение с равномерным поиском: 27 vs 10001 — в ~370 раз быстрее!

Улучшение: что если на каждой итерации одно из вычислений «переиспользовать»? → Метод золотого сечения.

5. Метод золотого сечения

Идея: выбирать пробные точки так, чтобы одно вычисление функции на каждой итерации было «бесплатным» (переиспользовалось).

Золотое сечение: $\varphi = \dfrac{1 + \sqrt{5}}{2} \approx 1.618$

Отношение отрезков: $\dfrac{\ell}{\ell_1} = \dfrac{\ell_1}{\ell_2} = \varphi$

Коэффициент: $\alpha = \dfrac{\sqrt{5} - 1}{2} \approx 0.618$

Метод золотого сечения: алгоритм

Пробные точки:

$$x_1 = b - \alpha(b - a), \qquad x_2 = a + \alpha(b - a)$$

Алгоритм:

1. Вычислить $x_1$, $x_2$, $f(x_1)$, $f(x_2)$
2. Если $f(x_1) < f(x_2)$: $b \leftarrow x_2$, $x_2 \leftarrow x_1$, $f(x_2) \leftarrow f(x_1)$, вычислить новый $x_1$
3. Если $f(x_1) > f(x_2)$: $a \leftarrow x_1$, $x_1 \leftarrow x_2$, $f(x_1) \leftarrow f(x_2)$, вычислить новый $x_2$
4. Если $|b - a| < \varepsilon$: стоп, $x^* = \dfrac{a + b}{2}$
5. Иначе → шаг 2

Ключевое свойство: на каждой итерации — только 1 новое вычисление $f(x)$.

Метод золотого сечения: иллюстрация

Почему это работает: точка $x_1$ нового отрезка совпадает с точкой $x_2$ старого отрезка (и наоборот), поэтому значение $f$ уже известно.

Метод золотого сечения: эффективность

На каждой итерации отрезок сокращается в $\varphi \approx 1.618$ раз.

Число итераций: $n \geq \log_\varphi \dfrac{b - a}{\varepsilon} = \dfrac{\ln\frac{b-a}{\varepsilon}}{\ln \varphi}$

Число вычислений функции: $N = n + 1 \approx \dfrac{1}{\ln \varphi} \cdot \ln\dfrac{b-a}{\varepsilon} \approx 2.08 \ln\dfrac{b-a}{\varepsilon}$

Пример: $[0, 10]$, $\varepsilon = 0.001$

$$N \approx 2.08 \cdot \ln 10000 \approx 2.08 \cdot 9.21 \approx 19 \text{ вычислений}$$

Сравнение:

Метод золотого сечения: числовой пример

Пример: $f(x) = x^2 - 6x + 10$ на $[0, 10]$, $\varepsilon = 0.5$

Минимум в точке $x^* = 3$, $f(3) = 1$.

$|b - a| = 0.55 > 0.5$ → ещё одна итерация.

6. Метод Фибоначчи

Идея: для заданного числа вычислений $N$ минимизировать конечную длину отрезка неопределённости.

Числа Фибоначчи: $F_0 = 0$, $F_1 = 1$, $F_k = F_{k-1} + F_{k-2}$

$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots$$

Пробные точки на $k$-й итерации:

$$x_1 = a + \frac{F_{n-k-1}}{F_{n-k+1}} (b - a), \qquad x_2 = a + \frac{F_{n-k}}{F_{n-k+1}} (b - a)$$

Свойство: метод Фибоначчи оптимален — при заданном $N$ даёт наименьший конечный отрезок среди всех прямых методов.

Метод Фибоначчи: алгоритм

Вход: отрезок $[a, b]$, число вычислений $N$ (задаёт точность)

1. Определить $n = N - 1$ итераций
2. Вычислить $x_1$, $x_2$ с коэффициентами из чисел Фибоначчи
3. Вычислить $f(x_1)$, $f(x_2)$
4. Сужение отрезка (как в золотом сечении)
5. На последней итерации берём $x_1 = x_2 - \delta$ (т.к. $F_1 = F_2 = 1$)
6. Результат: $x^* = \dfrac{a + b}{2}$

Точность: $\varepsilon = \dfrac{b - a}{F_{n+1}}$

Число вычислений для заданной $\varepsilon$: $N = \min\{n : F_{n+1} \geq \dfrac{b-a}{\varepsilon}\}$

Метод Фибоначчи: иллюстрация

Пример: $[0, 10]$, $N = 10$ вычислений ($n = 9$ итераций)

$$F_{10} = 55, \quad \varepsilon = \frac{10}{55} \approx 0.182$$

Для той же точности методом золотого сечения: $N \approx 20$.

Недостаток: нужно заранее знать $N$ (или $\varepsilon$), нельзя добавить вычислений «на ходу».

7. Сравнение методов

Сравнение: числовой пример

Задача: $[a, b] = [0, 10]$, $\varepsilon = 0.001$

Вывод: золотое сечение и Фибоначчи дают практически одинаковый результат, но золотое сечение не требует знания $N$ заранее — поэтому на практике предпочитают именно его.

Сравнение: сходимость (график)

На графике: длина отрезка неопределённости в зависимости от числа вычислений функции.

8. Программная реализация

import math

def golden_section(f, a, b, eps=1e-6):
    alpha = (math.sqrt(5) - 1) / 2  # ≈ 0.618
    x1 = b - alpha * (b - a)
    x2 = a + alpha * (b - a)
    f1, f2 = f(x1), f(x2)
    iterations = 0
    while abs(b - a) > eps:
        iterations += 1
        if f1 < f2:
            b, x2, f2 = x2, x1, f1
            x1 = b - alpha * (b - a)
            f1 = f(x1)
        else:
            a, x1, f1 = x1, x2, f2
            x2 = a + alpha * (b - a)
            f2 = f(x2)
    return (a + b) / 2, f((a + b) / 2), iterations

result = golden_section(lambda x: x**2 - 6*x + 10, 0, 10)
print(f"x*={result[0]:.6f}, f(x*)={result[1]:.6f}, iter={result[2]}")
# x*=3.000000, f(x*)=1.000000, iter=25

Программная реализация: дихотомия и Фибоначчи

def dichotomy(f, a, b, eps=1e-6, delta=1e-8):
    iterations = 0
    while (b - a) / 2 > eps:
        iterations += 1
        xm = (a + b) / 2
        if f(xm - delta) < f(xm + delta):
            b = xm
        else:
            a = xm
    return (a + b) / 2, f((a + b) / 2), iterations

def fibonacci_method(f, a, b, n=20):
    fib = [0, 1]
    for _ in range(2, n + 2):
        fib.append(fib[-1] + fib[-2])
    x1 = a + fib[n - 1] / fib[n + 1] * (b - a)
    x2 = a + fib[n] / fib[n + 1] * (b - a)
    f1, f2 = f(x1), f(x2)
    for k in range(1, n):
        if f1 < f2:
            b, x2, f2 = x2, x1, f1
            x1 = a + fib[n - k - 1] / fib[n - k + 1] * (b - a)
            f1 = f(x1)
        else:
            a, x1, f1 = x1, x2, f2
            x2 = a + fib[n - k] / fib[n - k + 1] * (b - a)
            f2 = f(x2)
    return (a + b) / 2, f((a + b) / 2)

Программная реализация: сравнение

f = lambda x: x**2 - 6*x + 10
a, b, eps = 0, 10, 1e-6

print("Метод золотого сечения:")
x, fx, n = golden_section(f, a, b, eps)
print(f"  x*={x:.8f}, f(x*)={fx:.8f}, вычислений={2+n}")

print("Метод дихотомии:")
x, fx, n = dichotomy(f, a, b, eps)
print(f"  x*={x:.8f}, f(x*)={fx:.8f}, вычислений={2*n}")

print("Метод Фибоначчи (n=25):")
x, fx = fibonacci_method(f, a, b, 25)
print(f"  x*={x:.8f}, f(x*)={fx:.8f}, вычислений=26")

# Золотое сечение:  27 вычислений
# Дихотомия:        42 вычислений
# Фибоначчи:        26 вычислений

Заключение

Ключевые выводы лекции

Вопросы для самоконтроля

1. Сформулируйте задачу одномерной безусловной оптимизации.
2. Что такое унимодальная функция? Сформулируйте правило сужения отрезка.
3. В чём суть метода равномерного поиска? Какова его сложность?
4. Опишите алгоритм метода дихотомии. Сколько вычислений $f(x)$ требуется?
5. Как выбираются пробные точки в методе золотого сечения? Почему одно вычисление «бесплатное»?
6. В чём преимущество метода Фибоначчи перед золотым сечением? В чём его недостаток?
7. Сравните все методы по числу вычислений функции.

Рекомендуемые ресурсы