Разработка и оптимизация ИИС

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

Разработка и оптимизация ИИС

План лекции

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

2. Необходимые сведения: градиент и гессиан

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

4. Метод наискорейшего спуска

5. Метод Ньютона

6. Метод сопряжённых направлений

7. Метод покоординатного спуска

8. Метод шаблонного поиска (Хука-Дживса)

9. Поиск по шаблону (гиперкуб)

10. Метод симплексного поиска (Нелдера-Мида)

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

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

Методы многомерной оптимизации
Разработка и оптимизация ИИС

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

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

f(x∗)=min⁡x∈Rnf(x)f(\mathbf{x}^*) = \min_{\mathbf{x} \in \mathbb{R}^n} f(\mathbf{x})

Дано:

  • Функция f(x)=f(x1,x2,…,xn)f(\mathbf{x}) = f(x_1, x_2, \ldots, x_n)
  • Начальная точка x(0)\mathbf{x}^{(0)}
  • Точность ε>0\varepsilon > 0

Найти:

  • Приближённое значение x∗\mathbf{x}^* — точки минимума
  • Приближённое значение f(x∗)f(\mathbf{x}^*)

Общая схема итерационных методов:

x(k+1)=x(k)+αkp(k)\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \alpha_k \mathbf{p}^{(k)}

где p(k)\mathbf{p}^{(k)} — направление поиска, αk\alpha_k — длина шага.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Критерии останова

Критерий Условие
По аргументу ∣x(k+1)−x(k)∣<ε|\mathbf{x}^{(k+1)} - \mathbf{x}^{(k)}| < \varepsilon
По функции ∣f(x(k+1))−f(x(k))∣<ε|f(\mathbf{x}^{(k+1)}) - f(\mathbf{x}^{(k)})| < \varepsilon
По градиенту ∣∇f(x(k))∣<ε|\nabla f(\mathbf{x}^{(k)})| < \varepsilon
Комбинированный любой из выше + ограничение итераций

Важно: выбор критерия влияет на качество результата и время работы.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

2. Градиент и гессиан

Градиент — вектор частных производных, указывающий направление наибольшего роста:

∇f(x)=(∂f∂x1,∂f∂x2,…,∂f∂xn)T\nabla f(\mathbf{x}) = \left(\frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial x_2}, \ldots, \frac{\partial f}{\partial x_n}\right)^T

Свойства градиента:

  • ∇f(x)\nabla f(\mathbf{x}) перпендикулярен линиям уровня f(x)=constf(\mathbf{x}) = \text{const}
  • −∇f(x)-\nabla f(\mathbf{x}) указывает направление наискорейшего убывания
  • В точке минимума: ∇f(x∗)=0\nabla f(\mathbf{x}^*) = \mathbf{0}
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Гессиан

Гессиан — матрица вторых производных:

H(x)=∇2f(x)=(∂2f∂x12⋯∂2f∂x1∂xn⋮⋱⋮∂2f∂xn∂x1⋯∂2f∂xn2)H(\mathbf{x}) = \nabla^2 f(\mathbf{x}) = \begin{pmatrix} \dfrac{\partial^2 f}{\partial x_1^2} & \cdots & \dfrac{\partial^2 f}{\partial x_1 \partial x_n} \\ \vdots & \ddots & \vdots \\ \dfrac{\partial^2 f}{\partial x_n \partial x_1} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2} \end{pmatrix}

Свойства гессиана:

  • Симметричная матрица (H=HTH = H^T)
  • В точке минимума H(x∗)H(\mathbf{x}^*) — положительно определённая (zTHz>0\mathbf{z}^T H \mathbf{z} > 0 для всех z≠0\mathbf{z} \neq \mathbf{0})
  • Определяет кривизну функции в данной точке
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Градиент и линии уровня: иллюстрация

center

Ключевой факт: антиградиент −∇f-\nabla f — локально наилучшее направление спуска.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

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

Идея: двигаться в направлении антиградиента с постоянным шагом α\alpha.

x(k+1)=x(k)−α∇f(x(k))\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} - \alpha \nabla f(\mathbf{x}^{(k)})

Алгоритм:

  1. Задать x(0)\mathbf{x}^{(0)}, α\alpha, ε\varepsilon
  2. Вычислить g(k)=∇f(x(k))\mathbf{g}^{(k)} = \nabla f(\mathbf{x}^{(k)})
  3. Если ∥g(k)∥<ε\|\mathbf{g}^{(k)}\| < \varepsilon: стоп
  4. x(k+1)=x(k)−αg(k)\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} - \alpha \mathbf{g}^{(k)}
  5. k←k+1k \leftarrow k + 1 → шаг 2

Проблема: выбор α\alpha

  • Слишком большой α\alpha → расходимость
  • Слишком малый α\alpha → медленная сходимость
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Градиентный спуск: иллюстрация

center

Заметно «зигзагообразное» движение, особенно при вытянутых линиях уровня.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

4. Метод наискорейшего спуска

Идея: на каждой итерации выбирать оптимальный шаг αk\alpha_k в направлении антиградиента.

αk=arg⁡min⁡α>0f(x(k)−α∇f(x(k)))\alpha_k = \arg\min_{\alpha > 0} f(\mathbf{x}^{(k)} - \alpha \nabla f(\mathbf{x}^{(k)}))

Это одномерная задача оптимизации → решаем методами из лекции 4 (золотое сечение и др.)

Алгоритм:

  1. Задать x(0)\mathbf{x}^{(0)}, ε\varepsilon
  2. p(k)=−∇f(x(k))\mathbf{p}^{(k)} = -\nabla f(\mathbf{x}^{(k)})
  3. αk=arg⁡min⁡αφ(α)=f(x(k)+αp(k))\alpha_k = \arg\min_\alpha \varphi(\alpha) = f(\mathbf{x}^{(k)} + \alpha \mathbf{p}^{(k)}) — одномерный поиск
  4. x(k+1)=x(k)+αkp(k)\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \alpha_k \mathbf{p}^{(k)}
  5. Если ∥∇f(x(k+1))∥<ε\|\nabla f(\mathbf{x}^{(k+1)})\| < \varepsilon: стоп, иначе → шаг 2
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Наискорейший спуск: иллюстрация

center

Преимущество перед фиксированным шагом: меньше итераций, автоматическая адаптация.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Наискорейший спуск: числовой пример

Пример: f(x1,x2)=x12+4x22f(x_1, x_2) = x_1^2 + 4x_2^2, x(0)=(4,4)\mathbf{x}^{(0)} = (4, 4)

∇f=(2x18x2)\nabla f = \begin{pmatrix} 2x_1 \\ 8x_2 \end{pmatrix}

Итер. x1x_1 x2x_2 ∇f\nabla f αk\alpha_k ff
0 4.000 4.000 (8.0, 32.0) — 80.0
1 2.462 −0.308 (4.9, −2.5) 0.193 6.15
2 0.529 0.619 (1.1, 5.0) 0.385 1.80
3 0.326 −0.041 (0.7, −0.3) 0.193 0.110
4 0.070 0.082 (0.1, 0.7) 0.385 0.032
5 0.043 −0.005 (0.1, 0.0) 0.193 0.002
Методы многомерной оптимизации
Разработка и оптимизация ИИС

5. Метод Ньютона

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

Разложение Тейлора второго порядка:

f(x)≈f(x(k))+∇f(x(k))T(x−x(k))+12(x−x(k))TH(x(k))(x−x(k))f(\mathbf{x}) \approx f(\mathbf{x}^{(k)}) + \nabla f(\mathbf{x}^{(k)})^T (\mathbf{x} - \mathbf{x}^{(k)}) + \frac{1}{2} (\mathbf{x} - \mathbf{x}^{(k)})^T H(\mathbf{x}^{(k)}) (\mathbf{x} - \mathbf{x}^{(k)})

Минимум квадратичной аппроксимации:

x(k+1)=x(k)−H−1(x(k))∇f(x(k))\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} - H^{-1}(\mathbf{x}^{(k)}) \nabla f(\mathbf{x}^{(k)})

Свойства:

  • Квадратичная сходимость вблизи минимума
  • Не требует выбора шага (α=1\alpha = 1)
  • Требует вычисления и обращения гессиана
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Метод Ньютона: алгоритм

Алгоритм:

  1. Задать x(0)\mathbf{x}^{(0)}, ε\varepsilon
  2. Вычислить g(k)=∇f(x(k))\mathbf{g}^{(k)} = \nabla f(\mathbf{x}^{(k)})
  3. Если ∥g(k)∥<ε\|\mathbf{g}^{(k)}\| < \varepsilon: стоп
  4. Вычислить H(k)=∇2f(x(k))H^{(k)} = \nabla^2 f(\mathbf{x}^{(k)})
  5. Решить H(k)p(k)=−g(k)H^{(k)} \mathbf{p}^{(k)} = -\mathbf{g}^{(k)} (система линейных уравнений)
  6. x(k+1)=x(k)+p(k)\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \mathbf{p}^{(k)}
  7. k←k+1k \leftarrow k + 1 → шаг 2

Модификация с шагом: x(k+1)=x(k)+αkp(k)\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \alpha_k \mathbf{p}^{(k)} — повышает устойчивость.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Метод Ньютона: иллюстрация

center

Для квадратичных функций метод Ньютона находит минимум за один шаг.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Метод Ньютона: числовой пример

Пример: f(x1,x2)=x12+4x22f(x_1, x_2) = x_1^2 + 4x_2^2, x(0)=(4,4)\mathbf{x}^{(0)} = (4, 4)

∇f=(2x18x2),H=(2008),H−1=(1/2001/8)\nabla f = \begin{pmatrix} 2x_1 \\ 8x_2 \end{pmatrix}, \quad H = \begin{pmatrix} 2 & 0 \\ 0 & 8 \end{pmatrix}, \quad H^{-1} = \begin{pmatrix} 1/2 & 0 \\ 0 & 1/8 \end{pmatrix}

Итер. x1x_1 x2x_2 ∇f\nabla f ff
0 4.000 4.000 (8.0, 32.0) 80.0
1 0.000 0.000 (0.0, 0.0) 0.0

Один шаг! Для квадратичной функции метод Ньютона точен за одну итерацию.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Сравнение: наискорейший спуск vs Ньютона на квадратичной функции

center

Метод Итераций Вычислений ∇f\nabla f Вычислений HH
Наискорейший спуск 5+ 10+ 0
Ньютон 1 1 1
Методы многомерной оптимизации
Разработка и оптимизация ИИС

6. Метод сопряжённых направлений

Проблема наискорейшего спуска: зигзагообразность в оврагах.

Идея: строить направления p(0),p(1),…\mathbf{p}^{(0)}, \mathbf{p}^{(1)}, \ldots, сопряжённые относительно гессиана:

p(i)THp(j)=0,i≠j\mathbf{p}^{(i)T} H \mathbf{p}^{(j)} = 0, \quad i \neq j

Метод сопряжённых градиентов (Fletcher-Reeves):

p(0)=−∇f(x(0))\mathbf{p}^{(0)} = -\nabla f(\mathbf{x}^{(0)})

p(k+1)=−∇f(x(k+1))+βkp(k)\mathbf{p}^{(k+1)} = -\nabla f(\mathbf{x}^{(k+1)}) + \beta_k \mathbf{p}^{(k)}

βk=∥∇f(x(k+1))∥2∥∇f(x(k))∥2\beta_k = \frac{\|\nabla f(\mathbf{x}^{(k+1)})\|^2}{\|\nabla f(\mathbf{x}^{(k)})\|^2}

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Метод сопряжённых градиентов: свойства

Для квадратичной функции nn переменных:

  • Метод сходится не более чем за nn итераций
  • Не требует вычисления и хранения гессиана

Для произвольных функций:

  • Периодический рестарт (каждые nn шагов)
  • Линейная сходимость (медленнее Ньютона, но быстрее градиентного спуска)
Метод Память Скорость Сложность итерации
Градиентный спуск O(n)O(n) Линейная 1 умножение матрицы
Сопряжённые градиенты O(n)O(n) Суперлинейная 1 умножение матрицы
Ньютон O(n2)O(n^2) Квадратичная Обращение HH
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Метод сопряжённых градиентов: иллюстрация

center

Направления не повторяются и не зигзагируют — прямой путь к минимуму.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

7. Метод покоординатного спуска (Гаусса-Зейделя)

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

xi(k+1)=arg⁡min⁡xif(x1(k+1),…,xi−1(k+1),xi,xi+1(k),…,xn(k))x_i^{(k+1)} = \arg\min_{x_i} f(x_1^{(k+1)}, \ldots, x_{i-1}^{(k+1)}, x_i, x_{i+1}^{(k)}, \ldots, x_n^{(k)})

Алгоритм:

  1. Задать x(0)\mathbf{x}^{(0)}, ε\varepsilon
  2. Для i=1,2,…,ni = 1, 2, \ldots, n:
    • Одномерная минимизация ff по xix_i (методы лекции 4)
  3. Если критерий останова выполнен: стоп
  4. k←k+1k \leftarrow k + 1 → шаг 2

Достоинства: простота, не требует производных.

Недостатки: медленная сходимость при связи между переменными (овраги).

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Покоординатный спуск: иллюстрация

center

Движение параллельно осям координат — шаги перпендикулярны друг другу.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

8. Метод шаблонного поиска (Хука-Дживса)

Идея: чередовать локальное исследование окрестности с ускоряющими «прыжками» в удачном направлении.

Два этапа на каждой итерации:

  1. Исследующий поиск (exploratory move) — пробные шаги по каждой координате
  2. Шаблонное перемещение (pattern move) — прыжок в направлении общего улучшения
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Шаблонный поиск: алгоритм

Параметры: начальная точка x(0)\mathbf{x}^{(0)}, начальный шаг Δ\Delta, коэффициент ускорения γ≥1\gamma \geq 1 (обычно 2), коэффициент сжатия β∈(0,1)\beta \in (0, 1) (обычно 0.5)

Исследующий поиск вокруг точки x\mathbf{x}:

  • Для каждой координаты i=1,…,ni = 1, \ldots, n:
    • Пробуем xi+Δx_i + \Delta: если ff улучшилась — принимаем
    • Иначе пробуем xi−Δx_i - \Delta: если ff улучшилась — принимаем
    • Иначе оставляем xix_i без изменений
  • Если хотя бы одна координата изменилась → поиск успешен

Шаблонное перемещение:

xнов=2xтек−xстар\mathbf{x}_{\text{нов}} = 2\mathbf{x}_{\text{тек}} - \mathbf{x}_{\text{стар}}

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Шаблонный поиск: полный алгоритм

  1. Задать x(0)\mathbf{x}^{(0)}, Δ\Delta, γ\gamma, β\beta, ε\varepsilon
  2. Исследующий поиск из x(0)\mathbf{x}^{(0)} → базовая точка xb\mathbf{x}_b
  3. Шаблонное перемещение: xp=2xb−xпред\mathbf{x}_p = 2\mathbf{x}_b - \mathbf{x}_{\text{пред}}
  4. Исследующий поиск из xp\mathbf{x}_p → xp′\mathbf{x}_p'
  5. Если f(xp′)<f(xb)f(\mathbf{x}_p') < f(\mathbf{x}_b): успех
    • xпред←xb\mathbf{x}_{\text{пред}} \leftarrow \mathbf{x}_b, xb←xp′\mathbf{x}_b \leftarrow \mathbf{x}_p'
    • → шаг 3
  6. Если неудача:
    • Δ←β⋅Δ\Delta \leftarrow \beta \cdot \Delta (уменьшаем шаг)
    • Если Δ<ε\Delta < \varepsilon: стоп
    • Иначе: xпред←xb\mathbf{x}_{\text{пред}} \leftarrow \mathbf{x}_b → шаг 3
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Шаблонный поиск: иллюстрация

center

Зелёные стрелки — исследующий поиск, красные — шаблонное перемещение. Метод быстро «скользит» по оврагам.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Шаблонный поиск: свойства

Достоинства:

  • Не требует производных — только значения f(x)f(\mathbf{x})
  • Простая реализация
  • Эффективен на гладких функциях с оврагами
  • Шаблонное перемещение ускоряет сходимость

Недостатки:

  • Чувствителен к выбору Δ\Delta
  • На негладких функциях может застревать
  • Не гарантирует нахождение глобального минимума

Применение: настройка параметров моделей, задачи с дорогостоящими вычислениями ff.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

9. Поиск по шаблону (гиперкуб)

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

Шаблон — гиперкуб: набор из 2n2^n вершин, полученных сдвигом по всем координатам на ±Δ\pm \Delta:

xs=x+Δ⋅(s1,s2,…,sn),si∈{−1,+1}\mathbf{x}_{\mathbf{s}} = \mathbf{x} + \Delta \cdot (s_1, s_2, \ldots, s_n), \quad s_i \in \{-1, +1\}

Всего 2n2^n комбинаций знаков s=(s1,…,sn)\mathbf{s} = (s_1, \ldots, s_n).

Размерность nn Число вершин 2n2^n Фигура
2 4 Квадрат
3 8 Куб
4 16 Тессеракт
nn 2n2^n Гиперкуб
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Поиск по шаблону: алгоритм

Параметры: начальная точка x(0)\mathbf{x}^{(0)}, размер шаблона Δ\Delta, коэффициент сжатия β∈(0,1)\beta \in (0, 1) (обычно 0.5), точность ε\varepsilon

Алгоритм:

  1. Задать x(0)\mathbf{x}^{(0)}, Δ\Delta, β\beta, ε\varepsilon
  2. Вычислить ff во всех 2n2^n вершинах шаблона вокруг x(k)\mathbf{x}^{(k)}
  3. Найти лучшую точку xbest=arg⁡min⁡f(xi±)\mathbf{x}_{\text{best}} = \arg\min f(\mathbf{x}_i^{\pm})
  4. Если f(xbest)<f(x(k))f(\mathbf{x}_{\text{best}}) < f(\mathbf{x}^{(k)}):
    • x(k+1)←xbest\mathbf{x}^{(k+1)} \leftarrow \mathbf{x}_{\text{best}}
    • k←k+1k \leftarrow k + 1 → шаг 2
  5. Если f(xbest)≥f(x(k))f(\mathbf{x}_{\text{best}}) \geq f(\mathbf{x}^{(k)}):
    • Δ←β⋅Δ\Delta \leftarrow \beta \cdot \Delta (уменьшаем шаблон)
    • Если Δ<ε\Delta < \varepsilon: стоп, x∗=x(k)\mathbf{x}^* = \mathbf{x}^{(k)}
    • Иначе → шаг 2
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Поиск по шаблону: иллюстрация

center

На каждой итерации проверяются 2n2^n вершин гиперкуба (для R2\mathbb{R}^2 — 4 вершины квадрата). При неудаче шаблон сжимается.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Поиск по шаблону: числовой пример

Пример: f(x1,x2)=x12+4x22f(x_1, x_2) = x_1^2 + 4x_2^2, x(0)=(4,4)\mathbf{x}^{(0)} = (4, 4), Δ=1\Delta = 1, β=0.5\beta = 0.5

Итер. x\mathbf{x} Δ\Delta Пробные точки ff в них Лучшая fbestf_{\text{best}}
1 (4, 4) 1.0 (5,5),(3,5),(5,3),(3,3) 125,45,65,25 (3,3) 25 < 80 ✓
2 (3, 3) 1.0 (4,4),(2,4),(4,2),(2,2) 80,37,37,20 (2,2) 20 < 25 ✓
3 (2, 2) 1.0 (3,3),(1,3),(3,1),(1,1) 25,13,10,5 (1,1) 5 < 20 ✓
4 (1, 1) 1.0 (2,2),(0,2),(2,0),(0,0) 20,16,4,0 (0,0) 0 < 5 ✓
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Поиск по шаблону: свойства

Достоинства:

  • Максимальная простота реализации
  • Не требует производных
  • Гарантированная сходимость при Δ→0\Delta \to 0
  • Естественно параллелизуется (все 2n2n точек независимы)

Недостатки:

  • Медленная сходимость (линейная)
  • При неудаче — только сжатие, нет «прыжка» (в отличие от Хука-Дживса)
  • Неэффективен в вытянутых оврагах

Сравнение с Хуком-Дживсом: поиск по шаблону — это только «исследующий поиск» без шаблонного перемещения. Проще, но медленнее.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

10. Метод регулярного симплекса (Спендли, Хекст, Химсворт)

Регулярный симплекс в Rn\mathbb{R}^n — n+1n + 1 точек, равноудалённых друг от друга.

Для R2\mathbb{R}^2: равносторонний треугольник. Для R3\mathbb{R}^3: правильный тетраэдр.

Отличие от Нелдера-Мида: размер симплекса не изменяется — нет операций растяжения и сжатия.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Построение начального регулярного симплекса

Зададим начальную точку x0\mathbf{x}_0 и длину ребра aa.

Формулы для вершин (nn — размерность, pp, qq — параметры):

p=an2(n+1+n−1),q=an2(n+1−1)p = \frac{a}{n\sqrt{2}} \left(\sqrt{n+1} + n - 1\right), \qquad q = \frac{a}{n\sqrt{2}} \left(\sqrt{n+1} - 1\right)

xi=x0+q⋅1+p⋅ei,i=1,…,n\mathbf{x}_i = \mathbf{x}_0 + q \cdot \mathbf{1} + p \cdot \mathbf{e}_i, \quad i = 1, \ldots, n

Для R2\mathbb{R}^2 (a=1a = 1): p=32≈0.866p = \frac{\sqrt{3}}{2} \approx 0.866, q=3−122≈0.259q = \frac{\sqrt{3} - 1}{2\sqrt{2}} \approx 0.259

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Регулярный симплекс: алгоритм

  1. Построить регулярный симплекс {x0,x1,…,xn}\{\mathbf{x}_0, \mathbf{x}_1, \ldots, \mathbf{x}_n\}
  2. Вычислить значения f(xi)f(\mathbf{x}_i) во всех вершинах
  3. Найти наихудшую вершину xh\mathbf{x}_h: f(xh)=max⁡if(xi)f(\mathbf{x}_h) = \max_i f(\mathbf{x}_i)
  4. Отразить xh\mathbf{x}_h через центроид остальных вершин:

    xr=2n∑i≠hxi−xh\mathbf{x}_r = \frac{2}{n} \sum_{i \neq h} \mathbf{x}_i - \mathbf{x}_h

  5. Если f(xr)≥f(xh)f(\mathbf{x}_r) \geq f(\mathbf{x}_h) (новая точка хуже всех):
    • Редукция: уменьшить размер симплекса вдвое, центр — в лучшей вершине
  6. Заменить xh\mathbf{x}_h на xr\mathbf{x}_r
  7. Проверить критерий останова, иначе → шаг 2
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Регулярный симплекс: иллюстрация

center

Регулярный симплекс «шагает» по поверхности, отражая наихудшую вершину.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Регулярный симплекс: свойства

Достоинства:

  • Простой алгоритм (только одна операция — отражение)
  • Симплекс сохраняет форму — равномерное покрытие пространства
  • Не требует производных
  • Предсказуемое поведение

Недостатки:

  • Не адаптирует размер симплекса (в отличие от Нелдера-Мида)
  • Медленнее Нелдера-Мида на сложных поверхностях
  • Редукция — «грубый» механизм при неудачном отражении

Историческая роль: метод Spendley et al. (1962) → развитие → Нелдер-Мид (1965) добавил операции деформации.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

12. Метод симплексного поиска (Нелдера-Мида)

Симплекс в Rn\mathbb{R}^n — множество из n+1n + 1 точек (вершин), не лежащих в одной гиперплоскости.

Для R2\mathbb{R}^2: треугольник из 3 вершин.

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

Метод не использует производных — только значения функции в вершинах.

Отличие от регулярного симплекса: размер симплекса адаптируется (растяжение при успехе, сжатие при неудаче).

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Нелдер-Мид: операции над симплексом

Пусть xh\mathbf{x}_h — наихудшая вершина (f(xh)f(\mathbf{x}_h) максимальна), xl\mathbf{x}_l — лучшая, xc\mathbf{x}_c — центроид остальных вершин.

Отражение (reflection): xr=xc+α(xc−xh)\mathbf{x}_r = \mathbf{x}_c + \alpha(\mathbf{x}_c - \mathbf{x}_h), α=1\alpha = 1

center

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Нелдер-Мид: полный алгоритм

Параметры: α\alpha (отражение, 1), γ\gamma (растяжение, 2), β\beta (сжатие, 0.5), σ\sigma (глобальное сжатие, 0.5)

  1. Построить начальный симплекс
  2. Упорядочить вершины: f(x1)≤f(x2)≤…≤f(xn+1)f(\mathbf{x}_1) \leq f(\mathbf{x}_2) \leq \ldots \leq f(\mathbf{x}_{n+1})
  3. Вычислить xc\mathbf{x}_c — центроид лучших nn вершин
  4. Отражение: xr=xc+α(xc−xn+1)\mathbf{x}_r = \mathbf{x}_c + \alpha(\mathbf{x}_c - \mathbf{x}_{n+1})
    • Если f(x1)≤f(xr)<f(xn)f(\mathbf{x}_1) \leq f(\mathbf{x}_r) < f(\mathbf{x}_n): заменить xn+1\mathbf{x}_{n+1} на xr\mathbf{x}_r
    • Если f(xr)<f(x1)f(\mathbf{x}_r) < f(\mathbf{x}_1) → растяжение (шаг 5)
    • Если f(xr)≥f(xn)f(\mathbf{x}_r) \geq f(\mathbf{x}_n) → сжатие (шаг 6)
  5. Растяжение: xe=xc+γ(xr−xc)\mathbf{x}_e = \mathbf{x}_c + \gamma(\mathbf{x}_r - \mathbf{x}_c)
    • Если f(xe)<f(xr)f(\mathbf{x}_e) < f(\mathbf{x}_r): заменить на xe\mathbf{x}_e, иначе на xr\mathbf{x}_r
  6. Сжатие: xs=xc+β(xn+1−xc)\mathbf{x}_s = \mathbf{x}_c + \beta(\mathbf{x}_{n+1} - \mathbf{x}_c)
    • Если f(xs)<f(xn+1)f(\mathbf{x}_s) < f(\mathbf{x}_{n+1}): заменить на xs\mathbf{x}_s, иначе → глобальное сжатие
  7. Глобальное сжатие: все вершины, кроме лучшей, приближаются к x1\mathbf{x}_1:

    xi=x1+σ(xi−x1)\mathbf{x}_i = \mathbf{x}_1 + \sigma(\mathbf{x}_i - \mathbf{x}_1)

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Нелдер-Мид: иллюстрация

center

Симплекс деформируется и «скатывается» к минимуму, адаптируясь к форме поверхности.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

Нелдер-Мид: свойства

Достоинства:

  • Не требует производных
  • Работает с негладкими и зашумлёнными функциями
  • Хорош для малой размерности (n<20n < 20)
  • Встроен в SciPy (scipy.optimize.fmin)

Недостатки:

  • Медленная сходимость при большой размерности
  • Не гарантирует нахождение глобального минимума
  • Чувствителен к начальному симплексу

Применение: подгонка параметров, задачи где производные недоступны (экспериментальные данные).

Методы многомерной оптимизации
Разработка и оптимизация ИИС

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

Метод Направление Шаг Градиент Гессиан Сходимость
Градиентный (фикс. шаг) −∇f-\nabla f Постоянный Да Нет Линейная
Наискорейший спуск −∇f-\nabla f Оптимальный Да Нет Линейная
Ньютон −H−1∇f-H^{-1}\nabla f 1 (или подбор) Да Да Квадратичная
Сопряжённые градиенты Сопряжённые Оптимальный Да Нет Суперлинейная
Покоординатный По осям Оптимальный Нет Нет Линейная
Хук-Дживс Локальное + шаблон Адаптивный Нет Нет Суперлинейная
Поиск по шаблону Гиперкуб (2n2n точек) Адаптивный Нет Нет Линейная
Нелдер-Мид Симплекс Адаптивный Нет Нет Линейная
Регулярный симплекс Симплекс (фикс.) Постоянный Нет Нет Линейная
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Выбор метода на практике

Метод Ньютона:

  • Малая размерность (n<100n < 100)
  • Гессиан легко вычисляется
  • Нужна высокая точность

Сопряжённые градиенты:

  • Средняя размерность (n∼100n \sim 100–10610^6)
  • Гессиан вычислить дорого
  • HH — разреженная или произведение

Градиентный спуск:

  • Большая размерность (n>106n > 10^6)
  • Машинное обучение (SGD)
  • Гессиан невычислим

Покоординатный спуск:

  • Нет производных
  • Простая реализация

Хук-Дживс / Нелдер-Мид:

  • Нет производных
  • Негладкие или зашумлённые функции
  • Малая размерность (n<20n < 20)
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Чувствительность к форме функции

Чувствительность к оврагам

Вытянутые овраги — худший случай для градиентных методов. Ньютон и сопряжённые градиенты справляются лучше.

Методы многомерной оптимизации
Разработка и оптимизация ИИС

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

import numpy as np

def gradient_descent(grad_f, x0, alpha=0.01, eps=1e-6, max_iter=1000):
    x = np.array(x0, dtype=float)
    for i in range(max_iter):
        g = grad_f(x)
        if np.linalg.norm(g) < eps:
            break
        x = x - alpha * g
    return x, i + 1

def steepest_descent(f, grad_f, x0, eps=1e-6, max_iter=100):
    from scipy.optimize import minimize_scalar
    x = np.array(x0, dtype=float)
    for i in range(max_iter):
        g = grad_f(x)
        if np.linalg.norm(g) < eps:
            break
        phi = lambda a: f(x - a * g)
        alpha = minimize_scalar(phi).x
        x = x - alpha * g
    return x, i + 1
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Программная реализация: Ньютон и сопряжённые градиенты

def newton_method(f, grad_f, hess_f, x0, eps=1e-6, max_iter=100):
    x = np.array(x0, dtype=float)
    for i in range(max_iter):
        g = grad_f(x)
        if np.linalg.norm(g) < eps:
            break
        H = hess_f(x)
        p = np.linalg.solve(H, -g)
        x = x + p
    return x, i + 1

def conjugate_gradient(grad_f, x0, eps=1e-6, max_iter=100):
    x = np.array(x0, dtype=float)
    g = grad_f(x)
    p = -g
    for i in range(max_iter):
        if np.linalg.norm(g) < eps:
            break
        phi = lambda a: f(x + a * p)  # f должна быть определена
        from scipy.optimize import minimize_scalar
        alpha = minimize_scalar(phi).x
        x = x + alpha * p
        g_new = grad_f(x)
        beta = np.dot(g_new, g_new) / np.dot(g, g)
        p = -g_new + beta * p
        g = g_new
    return x, i + 1
Методы многомерной оптимизации
Разработка и оптимизация ИИС

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

f = lambda x: x[0]**2 + 4*x[1]**2
grad_f = lambda x: np.array([2*x[0], 8*x[1]])
hess_f = lambda x: np.array([[2, 0], [0, 8]])
x0 = [4.0, 4.0]

x, n = gradient_descent(grad_f, x0, alpha=0.05, eps=1e-6)
print(f"Градиентный спуск:    x={x}, итераций={n}")

x, n = steepest_descent(f, grad_f, x0)
print(f"Наискорейший спуск:   x={x}, итераций={n}")

x, n = newton_method(f, grad_f, hess_f, x0)
print(f"Метод Ньютона:        x={x}, итераций={n}")

# Градиентный спуск:    x=[0.000 0.000], итераций≈200
# Наискорейший спуск:   x=[0.000 0.000], итераций≈6
# Метод Ньютона:        x=[0.000 0.000], итераций=1
Методы многомерной оптимизации
Разработка и оптимизация ИИС

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

from scipy.optimize import minimize

f = lambda x: x[0]**2 + 4*x[1]**2
x0 = [4.0, 4.0]

result = minimize(f, x0, method='Nelder-Mead',
                  options={'xatol': 1e-6, 'fatol': 1e-6})
print(f"Нелдер-Мид: x={result.x}, f={result.fun:.8f}, итер={result.nit}")

result = minimize(f, x0, method='powell',
                  options={'xtol': 1e-6, 'ftol': 1e-6})
print(f"Поуэлл (шаблонный): x={result.x}, f={result.fun:.8f}, итер={result.nit}")

# Нелдер-Мид:      x=[0.000 0.000], f=0.00000000, итер≈63
# Поуэлл:         x=[0.000 0.000], f=0.00000000, итер≈5
Методы многомерной оптимизации
Разработка и оптимизация ИИС

Заключение

Методы многомерной оптимизации
Разработка и оптимизация ИИС

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

  • Многомерная оптимизация: min⁡f(x)\min f(\mathbf{x}), x∈Rn\mathbf{x} \in \mathbb{R}^n
  • Общая схема: x(k+1)=x(k)+αkp(k)\mathbf{x}^{(k+1)} = \mathbf{x}^{(k)} + \alpha_k \mathbf{p}^{(k)}
  • Градиентный спуск — прост, но медленный и зигзагообразный
  • Наискорейший спуск — адаптивный шаг, но та же проблема с оврагами
  • Метод Ньютона — квадратичная сходимость, но требует гессиана
  • Сопряжённые градиенты — компромисс: быстро, без гессиана
  • Покоординатный спуск — прост, но чувствителен к оврагам
  • Шаблонный поиск (Хук-Дживс) — безградиентный, эффективен в оврагах
  • Поиск по шаблону (гиперкуб) — простейший безградиентный метод
  • Регулярный симплекс — фиксированный размер, только отражение
  • Симплексный поиск (Нелдер-Мид) — безградиентный, работает с негладкими функциями
Методы многомерной оптимизации
Разработка и оптимизация ИИС

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

  1. Сформулируйте задачу многомерной безусловной оптимизации.
  2. Что такое градиент и гессиан функции? Каковы их свойства?
  3. В чём разница между градиентным спуском и наискорейшим спуском?
  4. Почему метод Ньютона сходится за один шаг для квадратичной функции?
  5. Что такое сопряжённость направлений? В чём преимущество метода сопряжённых градиентов?
  6. Опишите метод покоординатного спуска. Когда он эффективен?
  7. В чём суть метода шаблонного поиска (Хука-Дживса)? Каковы его этапы?
  8. Опишите поиск по шаблону с гиперкубом. Чем он отличается от Хука-Дживса?
  9. В чём отличие регулярного симплекса от метода Нелдера-Мида?
  10. Опишите операции метода Нелдера-Мида: отражение, растяжение, сжатие.
  11. Сравните все методы по скорости сходимости и вычислительной сложности.
Методы многомерной оптимизации
Разработка и оптимизация ИИС

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

Основная литература:

  1. Алексеев, Д. С. Технологии интеллектуального анализа данных.
  2. Серебряная, Л. В. Методы и алгоритмы принятия решений.

Дополнительная литература:

  1. Банди, Б. Методы оптимизации: вводный курс.
  2. Нocтер, Дж. Э., Райт, С. Дж. Численная оптимизация.

Онлайн-ресурсы:

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

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

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

Шаблонный поиск Хука-Дживса — безградиентный метод, сочетающий исследующий поиск и ускоряющее перемещение по шаблону.

Поиск по шаблону с гиперкубом — простейший безградиентный метод, проверяющий окрестность текущей точки по всем вершинам гиперкуба.

Метод регулярного симплекса — предшественник Нелдера-Мида (1962). Симплекс фиксированного размера, только одна операция — отражение.