Одномерная оптимизация
min f(x), x ∈ [a, b] ⊂ ℝ
Метод золотого сечения
1D
Сужение отрезка неопределённости в отношении золотого сечения. Каждый шаг требует лишь одного нового вычисления функции.
Золотое число φ
\[ \varphi = \frac{1+\sqrt{5}}{2} \approx 1.618 \]
Точки разбиения
\[ x_1 = a + \frac{b - a}{\varphi^2}, \quad x_2 = a + \frac{b - a}{\varphi} \]
Правило обновления
Если \(f(x_1) \leq f(x_2)\): \(b \leftarrow x_2\)
Если \(f(x_1) > f(x_2)\): \(a \leftarrow x_1\)
Если \(f(x_1) > f(x_2)\): \(a \leftarrow x_1\)
Сходимость: после \(n\) итераций \(\;\ell_n = \varphi^{-n}(b - a)\). Сжатие~≈~61.8% на шаг.
Метод дихотомии (деление пополам)
1D
Делит текущий отрезок на две равные части с небольшим смещением \(\delta\), позволяющим различать две точки.
Точки разбиения
\[ x_1 = \frac{a+b}{2} - \delta, \quad x_2 = \frac{a+b}{2} + \delta \]
Правило обновления
Если \(f(x_1) < f(x_2)\): \(b \leftarrow x_2\)
Если \(f(x_1) \geq f(x_2)\): \(a \leftarrow x_1\)
Если \(f(x_1) \geq f(x_2)\): \(a \leftarrow x_1\)
Длина отрезка после n шагов
\[ \ell_n = \frac{b - a}{2^n} + 2\delta \]
Параметр: \(\delta \ll \varepsilon\) — малое число. На каждом шаге требуется 2 вычисления функции.
Метод Фибоначчи
1D
Оптимальный метод для фиксированного числа вычислений \(n\). Разбивает отрезок в пропорциях чисел Фибоначчи \(F_k\).
Числа Фибоначчи
\[ F_1=1,\; F_2=1,\; F_k = F_{k-1}+F_{k-2} \]
Точки на k-м шаге (k = 1 … n−2)
\[ x_1^{(k)} = a + \frac{F_{n-k-1}}{F_{n-k+1}}(b-a) \]
\[ x_2^{(k)} = a + \frac{F_{n-k}}{F_{n-k+1}}(b-a) \]
Итоговая длина
\[ \ell_n = \frac{b - a}{F_{n+1}} \]
Эффективность: ровно \(n\) вычислений функции; сжатие лучше, чем у золотого сечения при том же \(n\).
Многомерная безусловная оптимизация
min f(x), x ∈ ℝⁿ
Метод градиентного спуска
nD
Итерационный спуск вдоль антиградиента. Шаг \(\alpha_k\) подбирается из условия достаточного убывания или аналитически.
Итерационная формула
\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} - \alpha_k \nabla f\!\left(\mathbf{x}^{(k)}\right) \]
Точный шаг (line search)
\[ \alpha_k = \arg\min_{\alpha \geq 0}\; f\!\left(\mathbf{x}^{(k)} - \alpha \nabla f\!\left(\mathbf{x}^{(k)}\right)\right) \]
Условие первого порядка (стационарность)
\[ \nabla f(\mathbf{x}^*) = \mathbf{0} \]
Скорость сходимости: линейная (геометрическая прогрессия). Для сильно выпуклой \(f\) с константой \(\mu\) и \(L\)-гладким градиентом: \(\|\mathbf{x}^{(k)}-\mathbf{x}^*\| \leq \left(\frac{L-\mu}{L+\mu}\right)^k \|\mathbf{x}^{(0)}-\mathbf{x}^*\|\).
Метод Ньютона
nD
Использует квадратичное приближение функции через матрицу Гессе. Квадратичная сходимость вблизи минимума.
Ньютоновское направление
\[ \mathbf{d}^{(k)} = -\left[H\!\left(\mathbf{x}^{(k)}\right)\right]^{-1} \nabla f\!\left(\mathbf{x}^{(k)}\right) \]
Итерация
\[ \mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \mathbf{d}^{(k)} \]
Матрица Гессе
\[ H_{ij} = \frac{\partial^2 f}{\partial x_i \,\partial x_j} \]
Квадратичная сходимость: \(\|\mathbf{x}^{(k+1)}-\mathbf{x}^*\| \leq C\,\|\mathbf{x}^{(k)}-\mathbf{x}^*\|^2\). Дорог: требует \(O(n^3)\) на обращение гессиана.
Сопряжённые градиенты (Флетчер–Ривз)
nD
Строит последовательность взаимно сопряжённых направлений без хранения гессиана. Для квадратичных задач — за \(n\) шагов.
Инициализация (k = 0)
\[ \mathbf{d}^{(0)} = -\nabla f\!\left(\mathbf{x}^{(0)}\right) \]
Коэффициент Флетчера–Ривза
\[ \beta_k^{\text{FR}} = \frac{\left\|\nabla f\!\left(\mathbf{x}^{(k+1)}\right)\right\|^2}{\left\|\nabla f\!\left(\mathbf{x}^{(k)}\right)\right\|^2} \]
Обновление направления
\[ \mathbf{d}^{(k+1)} = -\nabla f\!\left(\mathbf{x}^{(k+1)}\right) + \beta_k^{\text{FR}}\,\mathbf{d}^{(k)} \]
Перезапуск: каждые \(n\) шагов или при \(\beta_k < 0\). Память \(O(n)\), в отличие от квази-ньютоновских методов с \(O(n^2)\).
Метод координатного спуска
nD
Последовательная минимизация по каждой координате. Не требует градиента — достаточно одномерных минимизаций.
Шаг по i-й оси (\(i = 1,\ldots,n\))
\[ x_i^{(k+1)} = \arg\min_{t \in \mathbb{R}}\; f\!\left(x_1^{(k+1)},\ldots,x_{i-1}^{(k+1)},\, t,\, x_{i+1}^{(k)},\ldots, x_n^{(k)}\right) \]
Направление поиска
\[ \mathbf{e}_i = (0,\ldots,0,\underbrace{1}_{i},0,\ldots,0)^\top \]
Условие останова
\[ \left\|\mathbf{x}^{(k+1)} - \mathbf{x}^{(k)}\right\| < \varepsilon \]
Применение: LASSO (L1-регуляризация), блочный координатный спуск в задачах машинного обучения. Может «застрять» на нединтересных ребрах уровневых кривых.
Условная оптимизация
min f(x) s.t. g(x)=0, h(x)≤0
Метод множителей Лагранжа
constrained
Для задач с условиями-равенствами. Вводятся множители \(\lambda_i\), превращающие ограничения в часть целевой функции.
Функция Лагранжа
\[ \mathcal{L}(\mathbf{x},\boldsymbol{\lambda}) = f(\mathbf{x}) + \sum_{i=1}^{m} \lambda_i\, g_i(\mathbf{x}) \]
Условия стационарности (необходимые)
\[ \nabla_{\mathbf{x}}\,\mathcal{L} = \nabla f(\mathbf{x}) + \sum_{i=1}^{m}\lambda_i \nabla g_i(\mathbf{x}) = \mathbf{0} \]
\[ \nabla_{\boldsymbol{\lambda}}\,\mathcal{L} = g_i(\mathbf{x}) = 0, \quad i=1,\ldots,m \]
Матрица Гессе по x (второй порядок)
\[ \nabla^2_{\mathbf{x}\mathbf{x}}\,\mathcal{L}(\mathbf{x}^*,\boldsymbol{\lambda}^*) \succ 0 \text{ на подпространстве ограничений} \]
Геометрический смысл: в точке минимума градиент \(\nabla f\) является линейной комбинацией градиентов активных ограничений.
Метод штрафных функций
constrained
Ограничения «штрафуются» добавлением к целевой функции члена, растущего при их нарушении. Задача сводится к безусловной.
Внешний штраф (равенства)
\[ \Phi(\mathbf{x},\,\rho) = f(\mathbf{x}) + \rho \sum_{i=1}^{m} g_i^2(\mathbf{x}), \quad \rho \to +\infty \]
Штраф для неравенств
\[ \Phi(\mathbf{x},\,\rho) = f(\mathbf{x}) + \rho \sum_{j=1}^{p} \max\!\bigl(0,\, h_j(\mathbf{x})\bigr)^2 \]
Барьерная функция (interior point)
\[ \Phi_B(\mathbf{x},\,\mu) = f(\mathbf{x}) - \mu \sum_{j=1}^{p} \ln\!\bigl(-h_j(\mathbf{x})\bigr), \quad \mu \to 0^+ \]
Алгоритм: 1) выбрать малое \(\rho_0\); 2) минимизировать \(\Phi(\cdot,\rho_k)\) безусловным методом; 3) увеличить \(\rho_{k+1} = c\,\rho_k\) (обычно \(c = 5\text{–}10\)); 4) повторять до выполнения ограничений.
Условия Куна–Таккера (KKT)
constrained
Необходимые (и для выпуклых задач достаточные) условия оптимальности при смешанных ограничениях.
Обобщённая функция Лагранжа
\[ \mathcal{L} = f(\mathbf{x}) + \sum_{i=1}^{m}\lambda_i g_i(\mathbf{x}) + \sum_{j=1}^{p}\mu_j h_j(\mathbf{x}) \]
KKT-условия
\[ \nabla_{\mathbf{x}}\,\mathcal{L} = \mathbf{0} \]
\[ g_i(\mathbf{x}^*) = 0, \quad i=1,\ldots,m \]
\[ h_j(\mathbf{x}^*) \leq 0, \quad \mu_j \geq 0 \]
\[ \mu_j\, h_j(\mathbf{x}^*) = 0 \quad \text{(дополняющая нежёсткость)} \]
Двойственная задача (Лагранжева релаксация)
\[ d(\boldsymbol{\lambda},\boldsymbol{\mu}) = \min_{\mathbf{x}}\,\mathcal{L}(\mathbf{x},\boldsymbol{\lambda},\boldsymbol{\mu}), \quad \max_{\boldsymbol{\lambda},\,\boldsymbol{\mu} \geq 0} d(\boldsymbol{\lambda},\boldsymbol{\mu}) \]
Дополняющая нежёсткость: \(\mu_j h_j = 0\) означает, что либо ограничение активно (\(h_j = 0\)), либо его множитель равен нулю (\(\mu_j = 0\)).
Метаэвристики
Stochastic & population-based methods
Генетический алгоритм
GA
Эволюционный поиск. Популяция особей-решений эволюционирует через отбор, скрещивание и мутацию.
Вероятность отбора (roulette wheel)
\[ P(i) = \frac{F_i}{\displaystyle\sum_{j=1}^{N} F_j}, \qquad F_i = f_{\max} - f(\mathbf{x}_i) + \varepsilon \]
Одноточечное скрещивание (crossover)
Потомок: \(\; \mathbf{c} = (\underbrace{a_1, \ldots, a_k}_{\text{от }A},\; \underbrace{b_{k+1},\ldots,b_n}_{\text{от }B})\)
Битовая мутация с вероятностью p_m
\[ c_i \leftarrow \begin{cases} 1 - c_i, & \text{с вероятностью } p_m \\ c_i, & \text{иначе} \end{cases} \]
Основные операторы: Selection → Crossover → Mutation → Replacement. Параметры: размер популяции \(N\), вероятность кроссовера \(p_c \approx 0.7{-}0.9\), мутации \(p_m \approx 0.001{-}0.01\).
Метод роя частиц (PSO)
PSO
Популяция «частиц» движется в пространстве поиска, притягиваясь к лучшим известным позициям.
Обновление скорости
\[ \mathbf{v}_i^{(k+1)} = w\,\mathbf{v}_i^{(k)} + c_1 r_1 \!\left(\mathbf{p}_i - \mathbf{x}_i^{(k)}\right) + c_2 r_2 \!\left(\mathbf{g} - \mathbf{x}_i^{(k)}\right) \]
Обновление позиции
\[ \mathbf{x}_i^{(k+1)} = \mathbf{x}_i^{(k)} + \mathbf{v}_i^{(k+1)} \]
Обновление личного и глобального лучших
\[ \mathbf{p}_i \leftarrow \mathbf{x}_i^{(k+1)} \text{ если } f(\mathbf{x}_i^{(k+1)}) < f(\mathbf{p}_i) \]
\[ \mathbf{g} \leftarrow \arg\min_{i}\, f(\mathbf{p}_i) \]
Гиперпараметры: \(w\) — инерционный вес (≈0.7), \(c_1\) — когнитивный (≈1.5), \(c_2\) — социальный (≈1.5), \(r_1, r_2 \sim \mathcal{U}(0,1)\).
Ничего не найдено по запросу «»