Лаб. работа “Методы одномерной оптимизации”
Постановка задачи
Найти точку минимума функции с заданной погрешностью
\[ f(x)=(x-8)^2-7 \]
Локализация экстремума
Определим отрезок, на котором находится точка минимума
Функция имеет единственную точку минимума на отрезке \([0;20]\)
Теоретические сведения
Общая постановка задачи одномерной оптимизации
Задача одномерной минимизации заключается в нахождении точки \(x^*\), в которой унимодальная функция \(f(x)\) достигает своего минимального значения на заданном отрезке \([a, b]\):
\[ x^* = \arg\min_{x \in [a, b]} f(x) \]
Под унимодальностью понимается свойство функции, при котором на отрезке \([a, b]\) существует единственная точка минимума \(x^*\), и функция монотонно убывает при \(x < x^*\) и монотонно возрастает при \(x > x^*\).
Все методы одномерной оптимизации основаны на процедуре уточнения отрезка неопределенности — интервала, гарантированно содержащего точку минимума.
Метод оптимального пассивного поиска
Метод оптимального пассивного поиска относится к классу пассивных стратегий, при которых все точки вычисления значений функции выбираются заранее, до начала оптимизации.
Основная идея
Пусть требуется найти минимум унимодальной функции \(f(x)\) на отрезке \([a, b]\) с точностью \(\varepsilon\). Выберем \(N\) точек \(x_1, x_2, \ldots, x_N\) на этом отрезке. После вычисления значений функции во всех точках, минимум найдем среди вычисленных значений.
Оптимальное распределение точек
Для обеспечения точности \(\varepsilon\) необходимо расположить точки на расстоянии \(2\varepsilon\) друг от друга. Первую точку размещаем на расстоянии \(\varepsilon\) от левого конца отрезка:
\[ x_1 = a + \varepsilon \]
Последующие точки размещаем с шагом \(2\varepsilon\):
\[ x_i = x_{i-1} + 2\varepsilon, \quad i = 2, 3, \ldots, N \]
Количество точек
Необходимое количество точек \(N\) определяется из условия охвата всего отрезка:
\[ N = \frac{b - a}{2\varepsilon} \]
Оценка погрешности
Максимальная погрешность метода оптимального пассивного поиска не превышает \(\varepsilon\):
\[ |x_{opt} - x^*| \leq \varepsilon \]
Достоинства и недостатки
Достоинства: - Простота реализации - Возможность параллельного вычисления значений функции - Не требует вычисления производных
Недостатки: - Большое количество вычислений функции - Неэффективное использование информации о поведении функции
Метод дихотомии
Метод дихотомии (метод деления отрезка пополам) относится к классу последовательных стратегий, где точки вычисления выбираются на основе результатов предыдущих вычислений.
Основная идея
На каждой итерации отрезок неопределенности \([a, b]\) делится пополам. В центре отрезка выбираются две симметричные точки на малом расстоянии \(\delta\) от середины:
\[ c = \frac{a + b}{2}, \quad x_1 = c - \delta, \quad x_2 = c + \delta \]
Параметр \(\delta\) — малое число (\(\delta \ll \varepsilon\)), необходимое для того, чтобы различать значения функции в близких точках.
Алгоритм
- Вычислить значения функции \(f(x_1)\) и \(f(x_2)\) в точках \(x_1\) и \(x_2\)
- Сравнить значения функции:
- Если \(f(x_1) < f(x_2)\), то минимум находится на левой половине отрезка. Новый отрезок: \([a, x_2]\)
- Если \(f(x_1) > f(x_2)\), то минимум находится на правой половине отрезка. Новый отрезок: \([x_1, b]\)
- Если \(f(x_1) = f(x_2)\), то минимум находится в центре. Новый отрезок: \([x_1, x_2]\)
- Проверить условие остановки: \(b - a < \varepsilon\)
- Если условие не выполнено, вернуться к шагу 1
Условие сходимости
Итерации продолжаются до тех пор, пока длина отрезка неопределенности не станет меньше заданной точности:
\[ b - a < \varepsilon \]
В качестве приближения точки минимума принимается середина финального отрезка.
Количество вычислений функции
На каждой итерации выполняются два вычисления функции. Количество итераций можно оценить как:
\[ n \approx \log_2\left(\frac{b - a}{\varepsilon}\right) \]
Общее количество вычислений функции: \(N \approx 2n\).
Достоинства и недостатки
Достоинства: - Простота алгоритма - Быстрая сходимость по сравнению с пассивным поиском - Гарантированная сходимость для унимодальных функций
Недостатки: - Два вычисления функции на каждой итерации - Требует выбора параметра \(\delta\)
Метод золотого сечения
Метод золотого сечения — один из наиболее эффективных методов одномерной оптимизации. Он использует пропорции золотого сечения для разбиения отрезка.
Золотое сечение
Золотым сечением называется деление отрезка на две части так, что отношение длины всего отрезка к большей части равно отношению большей части к меньшей:
\[ \frac{a + b}{a} = \frac{a}{b} = \tau \]
Отсюда получаем характеристическое уравнение:
\[ \tau^2 - \tau - 1 = 0 \]
Положительный корень этого уравнения:
\[ \tau = \frac{1 + \sqrt{5}}{2} \approx 1.618034 \]
Обратное значение:
\[ \frac{1}{\tau} = \frac{\sqrt{5} - 1}{2} \approx 0.618034 \]
Основная идея
Пусть отрезок неопределенности \([a, b]\). Выберем две внутренние точки:
\[ x_1 = b - \frac{b - a}{\tau}, \quad x_2 = a + \frac{b - a}{\tau} \]
Эти точки обладают важным свойством: каждая из них делит отрезок в одном и том же отношении золотого сечения. Это означает, что на следующей итерации одна из точек может быть повторно использована.
Алгоритм
- Вычислить начальные точки: \[ x_1 = b - \frac{b - a}{\tau}, \quad x_2 = a + \frac{b - a}{\tau} \]
- Вычислить значения функции \(f(x_1)\) и \(f(x_2)\)
- Сравнить значения функции:
- Если \(f(x_1) < f(x_2)\), новый отрезок: \([a, x_2]\), при этом \(x_1\) становится внутренней точкой нового отрезка
- Если \(f(x_1) \geq f(x_2)\), новый отрезок: \([x_1, b]\), при этом \(x_2\) становится внутренней точкой нового отрезка
- На каждой последующей итерации вычисляется только одно новое значение функции
- Проверить условие остановки: \(b - a < \varepsilon\)
- Если условие не выполнено, вернуться к шагу 3
Эффективность метода
Ключевое преимущество метода золотого сечения — на каждой итерации после первой выполняется только одно вычисление функции вместо двух.
Количество вычислений функции
Количество итераций:
\[ n \approx \frac{\ln(\frac{b - a}{\varepsilon})}{\ln(\tau)} \approx 1.44 \ln\left(\frac{b - a}{\varepsilon}\right) \]
Общее количество вычислений функции: \(N \approx n + 1\).
Достоинства и недостатки
Достоинства: - Одно вычисление функции на каждой итерации (после первой) - Высокая скорость сходимости - Не требует настройки параметров - Гарантированная сходимость для унимодальных функций
Недостатки: - Более сложная реализация по сравнению с методом дихотомии
Метод Фибоначчи
Метод Фибоначчи — оптимальный метод одномерной оптимизации в смысле минимизации количества вычислений функции для заданного числа итераций.
Числа Фибоначчи
Последовательность Фибоначчи определяется рекуррентным соотношением:
\[ F_0 = 0, \quad F_1 = 1, \quad F_n = F_{n-1} + F_{n-2}, \quad n \geq 2 \]
Первые числа Фибоначчи: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
Основная идея
Метод использует числа Фибоначчи для оптимального разбиения отрезка неопределенности. Если заранее известно количество итераций \(n\), метод Фибоначчи минимизирует конечную длину отрезка неопределенности.
Алгоритм
Пусть задано количество итераций \(n\). Начальный отрезок \([a_0, b_0]\).
- Вычислить \(n\) чисел Фибоначчи: \(F_0, F_1, \ldots, F_n\)
- Вычислить начальные точки: \[ x_1 = a_0 + \frac{F_{n-1}}{F_n}(b_0 - a_0), \quad x_2 = a_0 + \frac{F_{n-2}}{F_n}(b_0 - a_0) \]
- Вычислить значения функции \(f(x_1)\) и \(f(x_2)\)
- На \(k\)-й итерации (\(k = 1, 2, \ldots, n-1\)):
- Если \(f(x_1) < f(x_2)\), новый отрезок: \([a_k, x_2]\), вычислить новую точку \(x_1\)
- Если \(f(x_1) \geq f(x_2)\), новый отрезок: \([x_1, b_k]\), вычислить новую точку \(x_2\)
- На последней итерации принять \(x^* = \frac{a_n + b_n}{2}\)
Формулы для точек
На \(k\)-й итерации точки вычисляются по формулам:
\[ x_1 = a_k + \frac{F_{n-k-1}}{F_{n-k}}(b_k - a_k), \quad x_2 = a_k + \frac{F_{n-k}}{F_{n-k+1}}(b_k - a_k) \]
Оптимальность метода
Метод Фибоначчи является оптимальным в том смысле, что для заданного количества вычислений функции \(n\) он минимизирует длину финального отрезка неопределенности.
Связь с методом золотого сечения
При \(n \to \infty\) метод Фибоначчи стремится к методу золотого сечения, так как:
\[ \lim_{n \to \infty} \frac{F_{n-1}}{F_n} = \frac{1}{\tau} \]
Достоинства и недостатки
Достоинства: - Оптимальная скорость сходимости - Минимальное количество вычислений функции для заданной точности
Недостатки: - Требует предварительного задания количества итераций - Необходимо вычислять числа Фибоначчи - Более сложная реализация
Сравнительная характеристика методов
| Метод | Вычислений функции на итерацию | Сходимость | Особенности |
|---|---|---|---|
| Оптимальный пассивный поиск | Все заранее | Медленная | Простота, параллелизация |
| Дихотомия | 2 | Средняя | Простота реализации |
| Золотое сечение | 1 (после первой) | Быстрая | Оптимальный баланс |
| Фибоначчи | 1 (после первой) | Быстрая | Теоретически оптимален |
Практическая реализация методов
Метод оптимального пассивного поиска в MS Excel
Для решения задачи методом оптимального пассивного поиска будем использовать MsExcel или LibreOffice.
Зададим исходные данные
Необходимо выбрать погрешность поиска точки минимума. От выбора погрешности зависит количество точек, в которых нужно будет найти значение функции.
Выберем погрешность \(\epsilon = 0.5\). Количество точек найдем по формуле \(N=\frac{x_{max}-x_{min}}{2\epsilon}=\frac{20-0}{2\times 0.5}=20\)
Выберем точки \(x_i,\ i=1..N\), в которых нужно найти значение функции. Согласно методу оптимального пассивного поиска, точка \(x_1\) должна иметь координату \(x_{min}+\epsilon\). Остальные точки находятся по формуле: \(x_i=x_{i-1}+2\epsilon,\ i=2..N\).
Найдем значение функции для всех \(x_i\):
Построим график \(f(x)\) по полученным данным. Нужно вставить диаграмму точечного типа, а затем выбрать данные для нее.
Определим точку минимума и минимальное значение функции. Напишем формулы, которые найдут эти значения автоматически. Для этого нам потребуются функции МИН, ПОИСКПОЗ и ИНДЕКС.
Таким образом мы получили следующее решение:
\[ x_{opt}=7.5,\ f(x_{opt})=-6.75 \]
Найденное значение \(x_{opt}\) отличается от истинной точки минимума \(x^*=8\) на величину, не превышающую \(\epsilon\), следовательно, мы выполнили условие задачи.
Метод дихотомии
Для решения задачи методом дихотомии необходимо реализовать алгоритм на языке Python.
Итеративная реализация
import matplotlib.pyplot as plt
import numpy as np
def f(x):
"""Целевая функция"""
return (x - 8)**2 - 7
def dichotomy_iterative(f, a, b, epsilon, delta, visualize=True):
"""
Метод дихотомии (итеративная реализация)
Параметры:
f - целевая функция
a, b - границы отрезка
epsilon - точность
delta - малое смещение от центра
visualize - строить ли визуализацию
Возвращает:
x_opt - найденная точка минимума
f_opt - значение функции в точке минимума
iterations - количество итераций
history - история сужения отрезка
"""
iterations = 0
history = [(a, b)] # История для визуализации
if visualize:
# Подготовка графика
fig, axes = plt.subplots(2, 1, figsize=(12, 10))
# Верхний график - функция с точками
x_points = np.linspace(a, b, 500)
y_points = f(x_points)
axes[0].set_ylim(-10, 10)
axes[0].plot(x_points, y_points, 'b-', linewidth=2, label='f(x)')
axes[0].grid(True, alpha=0.3)
axes[0].set_xlabel('x')
axes[0].set_ylabel('f(x)')
axes[0].set_title('Метод дихотомии: поиск минимума')
# Нижний график - сужение отрезка
axes[1].set_xlim(0, 20)
axes[1].set_ylim(-1, 21)
axes[1].set_xlabel('Номер итерации')
axes[1].set_ylabel('Отрезок [a, b]')
axes[1].set_title('Сужение отрезка неопределенности')
axes[1].grid(True, alpha=0.3)
while b - a >= epsilon:
iterations += 1
# Вычисляем точки
c = (a + b) / 2
x1 = c - delta
x2 = c + delta
# Вычисляем значения функции
f1 = f(x1)
f2 = f(x2)
if visualize:
# Отображаем точки на графике функции
axes[0].plot([x1, x2], [f1, f2], 'ro', markersize=8)
axes[0].annotate(f'iter {iterations}', (x1, f1),
xytext=(5, 5), textcoords='offset points', fontsize=8)
axes[0].plot([a, b], [f(c), f(c)], 'g--', alpha=0.5)
# Отображаем отрезок на нижнем графике
axes[1].plot([iterations, iterations], [a, b], 'b-', linewidth=2)
axes[1].plot(iterations, a, 'go', markersize=6)
axes[1].plot(iterations, b, 'ro', markersize=6)
# Сравниваем значения и сужаем отрезок
if f1 < f2:
b = x2
elif f1 > f2:
a = x1
else:
a = x1
b = x2
history.append((a, b))
# Результат
x_opt = (a + b) / 2
f_opt = f(x_opt)
if visualize:
axes[0].plot(x_opt, f_opt, 'g*', markersize=20, label=f'x_opt = {x_opt:.6f}')
axes[0].legend()
# Добавляем текст с результатами
result_text = f'Результат:\nx_opt = {x_opt:.6f}\nf_opt = {f_opt:.6f}\nИтерации: {iterations}'
axes[1].text(0.5, 0.8, result_text, transform=axes[1].transAxes,
fontsize=12, verticalalignment='center',
bbox=dict(boxstyle='round', facecolor='wheat', alpha=0.5))
plt.tight_layout()
plt.savefig('dichotomy_visualization.png', dpi=300, bbox_inches='tight')
plt.show()
return x_opt, f_opt, iterations, history
# Параметры задачи
a = 0
b = 20
epsilon = 0.001
delta = 0.00001
# Запуск метода
x_opt, f_opt, iterations, history = dichotomy_iterative(f, a, b, epsilon, delta)
print(f"Результат метода дихотомии (итеративный):")
print(f"x_opt = {x_opt:.9f}")
print(f"f_opt = {f_opt:.9f}")
print(f"Количество итераций: {iterations}")
print(f"Финальный отрезок: [{history[-1][0]:.6f}, {history[-1][1]:.6f}]")
print(f"Длина отрезка: {history[-1][1] - history[-1][0]:.6f}")Результат работы программы:
Результат метода дихотомии (итеративный):
x_opt = 8.000185105
f_opt = -6.999999966
Количество итераций: 15
Финальный отрезок: [7.999870, 8.000500]
Длина отрезка: 0.000630
Рекурсивная реализация
def dichotomy_recursive(f, a, b, epsilon, delta, count=0, history=None):
"""
Метод дихотомии (рекурсивная реализация)
Параметры:
f - целевая функция
a, b - границы отрезка
epsilon - точность
delta - малое смещение от центра
count - счетчик итераций
history - история сужения отрезка
Возвращает:
(x_opt, f_opt, count, history) - точка минимума, значение функции,
количество вычислений, история
"""
if history is None:
history = [(a, b)]
# Проверка условия остановки
if b - a < epsilon:
x_opt = (a + b) / 2
f_opt = f(x_opt)
return x_opt, f_opt, count, history
# Вычисляем точки
c = (a + b) / 2
x1 = c - delta
x2 = c + delta
# Вычисляем значения функции
f1 = f(x1)
f2 = f(x2)
count += 2
# Сравниваем значения и рекурсивно вызываем функцию
if f2 < f1:
history.append((x1, b))
return dichotomy_recursive(f, x1, b, epsilon, delta, count, history)
else:
history.append((a, x2))
return dichotomy_recursive(f, a, x2, epsilon, delta, count, history)
# Запуск рекурсивного метода
x_opt_rec, f_opt_rec, count_rec, history_rec = dichotomy_recursive(f, a, b, epsilon, delta)
print(f"\nРезультат метода дихотомии (рекурсивный):")
print(f"x_opt = {x_opt_rec:.9f}")
print(f"f_opt = {f_opt_rec:.9f}")
print(f"Количество вычислений функции: {count_rec}")
print(f"Финальный отрезок: [{history_rec[-1][0]:.6f}, {history_rec[-1][1]:.6f}]")Результат работы рекурсивной реализации:
Результат метода дихотомии (рекурсивный):
x_opt = 8.000185105
f_opt = -6.999999966
Количество вычислений функции: 30
Финальный отрезок: [7.999870, 8.000500]
Визуализация процесса оптимизации
При запуске программы создается график, показывающий:
- Верхний график: функция \(f(x)\) с отмеченными точками вычислений на каждой итерации
- Нижний график: последовательное сужение отрезка неопределенности
Метод золотого сечения
Задание для самостоятельной реализации
Реализуйте метод золотого сечения на языке Python для нахождения минимума функции \(f(x) = (x-8)^2 - 7\) на отрезке \([0, 20]\) с точностью \(\varepsilon = 0.001\).
Требования к реализации
Функция золотого сечения: Напишите функцию
golden_section(f, a, b, epsilon), которая реализует итеративный алгоритм метода золотого сечения.Параметры функции:
f— целевая функцияa, b— границы отрезкаepsilon— требуемая точность
Алгоритм:
- Вычислить коэффициент золотого сечения: \(\tau = \frac{1 + \sqrt{5}}{2}\)
- На первой итерации вычислить две точки: \[ x_1 = b - \frac{b - a}{\tau}, \quad x_2 = a + \frac{b - a}{\tau} \]
- На каждой последующей итерации вычислять только одну новую точку
- Сравнивать значения функции и сужать отрезок неопределенности
- Продолжать до выполнения условия: \(b - a < \varepsilon\)
Возвращаемые значения:
x_opt— найденная точка минимумаf_opt— значение функции в точке минимумаiterations— количество итерацийevaluations— количество вычислений функцииhistory— список кортежей(a, b, x1, x2)для каждой итерации
Визуализация: Добавьте построение графика, аналогичного визуализации метода дихотомии, с отображением:
- Функции с отмеченными точками вычислений
- Последовательного сужения отрезка неопределенности
Ожидаемый результат
При правильной реализации должны получиться значения, близкие к:
x_opt ≈ 7.9995
f_opt ≈ -7.0000
Количество итераций: ~20-22
Количество вычислений функции: ~21-23
Контрольные вопросы
- Почему метод золотого сечения требует только одно вычисление функции на каждой итерации (после первой)?
- Каким свойством обладают точки \(x_1\) и \(x_2\) в методе золотого сечения?
- Сравните эффективность методов дихотомии и золотого сечения по количеству вычислений функции.
Метод Фибоначчи
Задание для самостоятельной реализации
Реализуйте метод Фибоначчи на языке Python для нахождения минимума функции \(f(x) = (x-8)^2 - 7\) на отрезке \([0, 20]\) с точностью \(\varepsilon = 0.001\).
Требования к реализации
Генерация чисел Фибоначчи: Напишите вспомогательную функцию
fibonacci_numbers(n), которая возвращает список из \(n+1\) чисел Фибоначчи:Определение количества итераций: Найдите минимальное \(n\) такое, что: \[ \frac{b - a}{F_n} < \varepsilon \] где \(F_n\) — \(n\)-е число Фибоначчи.
Функция метода Фибоначчи: Напишите функцию
fibonacci_search(f, a, b, epsilon), которая реализует алгоритм метода Фибоначчи.Алгоритм:
- Вычислить необходимое количество итераций \(n\) и сгенерировать числа Фибоначчи
- На первой итерации вычислить две точки: \[ x_1 = a + \frac{F_{n-1}}{F_n}(b - a), \quad x_2 = a + \frac{F_{n-2}}{F_n}(b - a) \]
- На каждой последующей итерации вычислять только одну новую точку
- Сравнивать значения функции и сужать отрезок неопределенности
- На последней итерации принять \(x^* = \frac{a + b}{2}\)
Возвращаемые значения:
x_opt— найденная точка минимумаf_opt— значение функции в точке минимумаiterations— количество итерацийevaluations— количество вычислений функцииhistory— список кортежей с историей сужения отрезка
Визуализация: Добавьте построение графика, аналогичного визуализации метода дихотомии.
Ожидаемый результат
При правильной реализации должны получиться значения, близкие к:
x_opt ≈ 7.9995
f_opt ≈ -7.0000
Количество итераций: ~20-22
Количество вычислений функции: ~21-23
Дополнительное задание
Сравните результаты методов золотого сечения и Фибоначчи: - Постройте график зависимости длины отрезка неопределенности от номера итерации для обоих методов - Сравните количество вычислений функции для достижения одной и той же точности - Объясните, почему результаты методов должны быть близки при большом количестве итераций
Контрольные вопросы
- В каком смысле метод Фибоначчи является оптимальным?
- Какое ограничение имеет метод Фибоначчи по сравнению с методом золотого сечения?
- Что происходит с отношением \(\frac{F_{n-1}}{F_n}\) при \(n \to \infty\)?
- Почему метод Фибоначчи дает результат, близкий к методу золотого сечения?
Сравнительный анализ методов
После реализации всех методов рекомендуется провести сравнительный анализ эффективности. Постройте таблицу со следующими характеристиками для каждого метода:
| Метод | Количество итераций | Количество вычислений функции | Точность | Время выполнения |
|---|---|---|---|---|
| Оптимальный пассивный поиск | ||||
| Дихотомия (итеративная) | ||||
| Дихотомия (рекурсивная) | ||||
| Золотое сечение | ||||
| Фибоначчи |
Варианты индивидуальных заданий
Реализуйте все методы одномерной оптимизации для вашей функции. Найдите точку минимума с точностью \(\varepsilon = 0.001\) на указанном отрезке.
- \(f(x) = x^2 + 3x + 2\), отрезок \([-3, 1]\)
- \(f(x) = e^{0.5x} - 2x\), отрезок \([0, 5]\)
- \(f(x) = \sin(2x) + x\), отрезок \([0, \pi]\)
- \(f(x) = -\ln(2x + 1)+x\), отрезок \([0, 3]\)
- \(f(x) = 2x^3 - 5x^2 + x + 3\), отрезок \([0, 2]\)
- \(f(x) = -\sqrt{3x} + x\), отрезок \([0, 5]\)
- \(f(x) = \cos(2x) + \frac{1}{x+1}\), отрезок \([0, \pi]\)
- \(f(x) = x \cdot \ln(0.5x + 1)\), отрезок \([0, 5]\)
- \(f(x) = 3x^3 - 2x^2 + 4x - 1\), отрезок \([0, 1]\)
- \(f(x) = \frac{1}{2}x^2 - 2x + 4\), отрезок \([0, 5]\)
- \(f(x) = e^{-0.5x} + \cos(x)\), отрезок \([0, \pi]\)
- \(f(x) = \frac{1}{x^2} + 2x + 1\), отрезок \([0.5, 3]\)
- \(f(x) = \tan(0.5x) + x^2\), отрезок \([0, 1]\)
- \(f(x) = \frac{1}{x} + \sqrt{2x}\), отрезок \([0.5, 3]\)
- \(f(x) = \sinh(0.5x) + 0.5x\), отрезок \([0, 2]\), где \(\sinh(x)=\frac{e^x-e^{-x}}{2}\)













