Локальный оптимум

Локальный оптимум — это точка в пространстве параметров (переменных) целевой функции, в которой значение функции является наилучшим (минимальным или максимальным) по сравнению со всеми значениями в некоторой её малой окрестности, но при этом может не быть наилучшим на всей допустимой области определения. В математическом анализе и теории оптимизации локальный оптимум является фундаментальным понятием, противопоставляемым глобальному оптимуму.

Определение и формализация

Пусть задана функция \( f: D \to \mathbb{R} \), где \( D \subseteq \mathbb{R}^n \) — область определения. Точка \( x^ \in D \) называется точкой локального минимума, если существует такое число \( \delta > 0 \), что для всех \( x \in D \), удовлетворяющих условию \( \|x - x^\| < \delta \), выполняется неравенство:

\[ f(x^*) \le f(x). \]

Если неравенство строгое (\( f(x^) < f(x) \)) для всех \( x \neq x^ \) в указанной окрестности, то говорят о строгом локальном минимуме. Аналогично определяется локальный максимум (с заменой знака неравенства). Общее название — локальный экстремум.

Для функций одной переменной (\( n = 1 \)) окрестность представляет собой интервал (\( x^ - \delta, x^ + \delta \)). Для функций многих переменных — открытый шар радиуса \( \delta \) с центром в точке \( x^* \).

Необходимые условия локального экстремума

Для дифференцируемых функций существуют классические условия, позволяющие идентифицировать точки, подозрительные на локальный экстремум.

Условие первого порядка (необходимое условие Ферма)

Если функция \( f \) дифференцируема в точке \( x^ \) и \( x^ \) является точкой локального экстремума, то градиент функции в этой точке равен нулю:

\[ \nabla f(x^*) = 0. \]

Для функции одной переменной это означает равенство нулю первой производной: \( f'(x^*) = 0 \). Точки, удовлетворяющие этому условию, называются стационарными или критическими (первого рода). Однако выполнение этого условия не гарантирует наличие экстремума — точка может быть седловой (для \( n > 1 \)) или точкой перегиба (для \( n = 1 \)).

Условие второго порядка (достаточное условие)

Пусть функция \( f \) дважды непрерывно дифференцируема в окрестности стационарной точки \( x^ \), и \( H(x^) \) — её матрица Гессе (матрица вторых частных производных) в этой точке. Тогда:

• Если \( H(x^) \) положительно определена (все собственные значения положительны), то \( x^ \) — точка строгого локального минимума.
• Если \( H(x^) \) отрицательно определена (все собственные значения отрицательны), то \( x^ \) — точка строгого локального максимума.
• Если \( H(x^) \) неопределена (имеет как положительные, так и отрицательные собственные значения), то \( x^ \) — седловая точка, и экстремума нет.
• Если \( H(x^*) \) вырождена (хотя бы одно собственное значение равно нулю), то требуется дополнительное исследование производных более высокого порядка.

Для функции одной переменной условие второго порядка сводится к знаку второй производной: если \( f'(x^) = 0 \) и \( f''(x^) > 0 \) — минимум; если \( f''(x^) < 0 \) — максимум; если \( f''(x^) = 0 \) — случай неопределённости.

Связь с глобальным оптимумом

Глобальный оптимум — это наилучшее значение функции на всей области определения \( D \). Каждая точка глобального оптимума является также и точкой локального оптимума (при условии, что она не является изолированной точкой области). Обратное, вообще говоря, неверно: функция может иметь множество локальных оптимумов, среди которых лишь один (или несколько) являются глобальными.

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

Примеры

1. Функция одной переменной: \( f(x) = x^3 - 3x \). Её производная \( f'(x) = 3x^2 - 3 \). Стационарные точки: \( x_1 = -1 \) (максимум, \( f''(-1) = -6 < 0 \)) и \( x_2 = 1 \) (минимум, \( f''(1) = 6 > 0 \)). Оба являются локальными экстремумами. Глобального максимума на всей числовой прямой не существует (функция уходит в \( +\infty \) при \( x \to +\infty \)), глобальный минимум также отсутствует (функция уходит в \( -\infty \) при \( x \to -\infty \)).

1. Функция многих переменных: \( f(x, y) = x^2 - y^2 \). Градиент \( \nabla f = (2x, -2y) \) равен нулю только в точке \( (0, 0) \). Матрица Гессе в этой точке: \( \begin{bmatrix} 2 & 0 \\ 0 & -2 \end{bmatrix} \). Её собственные значения: \( 2 > 0 \) и \( -2 < 0 \). Следовательно, точка \( (0, 0) \) является седловой, а не локальным экстремумом.

1. Функция с несколькими локальными минимумами: \( f(x) = \sin(x) + 0.1x \). Эта функция имеет бесконечно много точек локального минимума и максимума, чередующихся друг с другом. Глобальный минимум на всей числовой прямой не существует из-за линейного члена, но на ограниченном отрезке, например \( [0, 10] \), можно найти как локальные, так и глобальный минимум.

Значение в прикладных задачах

Понятие локального оптимума имеет первостепенное значение в различных областях науки и техники:

• Машинное обучение: При обучении нейронных сетей используется функция потерь (например, среднеквадратичная ошибка или кросс-энтропия), которая является невыпуклой функцией многих переменных (весов сети). Процесс обучения, основанный на градиентном спуске, часто останавливается в одном из локальных минимумов. Для преодоления этой проблемы применяются стохастические методы, методы импульса, а также различные техники регуляризации и инициализации весов.
• Экономика и теория игр: В задачах поиска равновесия (например, равновесия Нэша) часто требуется найти локальный оптимум функции выигрыша каждого игрока.
• Инженерное проектирование: При оптимизации формы деталей, параметров схем или траекторий движения механизмов инженеры сталкиваются с многомодальными функциями (имеющими много локальных экстремумов). Для поиска глобального оптимума в таких задачах применяют эвристические алгоритмы (генетические алгоритмы, имитация отжига, роевой интеллект).
• Физика и химия: В квантовой химии при расчёте конформаций молекул ищут локальные минимумы потенциальной энергии, соответствующие устойчивым состояниям молекулы. Переход между локальными минимумами (через седловые точки) описывает химические реакции.

Методы преодоления проблемы локальных оптимумов

Поскольку нахождение глобального оптимума для сложных функций является NP-трудной задачей в общем виде, разработаны методы, повышающие вероятность нахождения глобального решения или хотя бы «хорошего» локального:

• Многократный запуск (multi-start): Запуск градиентного метода из множества случайных начальных точек с последующим выбором наилучшего найденного решения.
• Эвристические и метаэвристические алгоритмы: Генетические алгоритмы, имитация отжига, метод роя частиц. Эти методы не гарантируют нахождения глобального оптимума, но часто позволяют избежать «застревания» в плохих локальных минимумах.
• Глобальная оптимизация на основе выпуклых релаксаций: Для некоторых классов задач (например, полиномиальных) можно построить выпуклую аппроксимацию исходной задачи, глобальный оптимум которой даёт нижнюю границу для исходной задачи.
• Методы доверительных областей и продолжения: Модификации градиентных методов, которые на ранних этапах «сглаживают» функцию, чтобы алгоритм мог выйти из мелких локальных минимумов.

Источники

1. Канторович Л. В., Акилов Г. П. Функциональный анализ. — М.: Наука, 1984.
2. Бертсекас Д. Нелинейное программирование. — М.: Бином. Лаборатория знаний, 2015.
3. Нейлор Т., Селл К. Алгоритмы оптимизации. — М.: Мир, 1985.
4. Рудин У. Основы математического анализа. — М.: Мир, 1976.
5. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. — М.: Мир, 1985.