Оптимизация — это метод систематического улучшения производительности системы или распределения ресурсов для достижения желаемых результатов.Альпинист видит перед собой три хребта, но ему нужен не самый высокий, а самый низкий перевал. Оптимизация математически ищет минимум (или максимум) целевой функции — числового показателя качества решения. Ограничения задают допустимую область: нельзя идти по воздуху или круче 45 градусов. Линейное программирование работает с прямыми склонами, где ответ лежит в вершине. Для гладких холмов используют градиентный спуск. Если ландшафт изрезан оврагами и скалами, в дело вступают эволюционные алгоритмы — они запускают целую толпу виртуальных альпинистов, и самые успешные маршруты скрещиваются и мутируют. Так находят путь в многомерных пространствах, где не нарисуешь карту. Когда шаг становится меньше миллиметра, поиск останавливается — перевал взят.
Корни уходят в вариационное исчисление XVII—XVIII веков, но современный этап начался в 1940-х годах с созданием линейного программирования и симплекс-метода. Развитие нелинейной оптимизации в 1960-х дало методы штрафов и сопряжённых градиентов. В 1980-х появились алгоритмы внутренней точки, совершившие переворот в решении больших задач. Сегодня оптимизация — основа всех технологий машинного обучения.
Большинство алгоритмов строят последовательность точек, сходящихся к минимуму. Градиентный спуск движется против градиента. В машинном обучении вычисляют градиент функции потерь на случайном подмножестве данных (batch), что позволяет оптимизировать миллиарды параметров. Регуляризация добавляет штрафы за сложность, чтобы избежать переобучения. Для задач с ограничениями применяют метод приведённого градиента или последовательное квадратичное программирование. Глобальная оптимизация использует байесовские методы и поиск с деревьями решений.
GPS-навигаторы прокладывают путь, авиакомпании составляют расписание рейсов, а инженеры рассчитывают обтекаемые формы — всё это работа алгоритмов оптимизации.
Задача коммивояжёра — посетить 100 городов кратчайшим путём — имеет больше вариантов, чем атомов во Вселенной. Но умные оптимизаторы находят решение за секунды.
| x | переменная | Входная последовательность — sequence |
| n | переменная | Индекс выходного элемента — index |
| i | переменная | Левый конец интервала — index |
| j | переменная | Правый конец интервала — index |
| k | переменная | Индекс суммирования — index |
| \sup | оператор | Берёт точную верхнюю грань множества — supremum |
| \sum_{k=i}^j | оператор | Суммирует члены от индекса i до j — finite summation |
| f | переменная | значение целевой функции — objective function value |
| g | переменная | основная целевая функция — primary objective function |
| h | переменная | штрафная функция — penalty function |
| λ | переменная | вес штрафа — penalty weight |
| \theta_k | переменная | Вектор параметров на итерации k — parameter vector |
| \theta_{k+1} | переменная | Обновленный вектор параметров на итерации k+1 — parameter vector |
| \alpha_k | переменная | Скорость обучения (величина шага) на итерации k — скорость обучения |
| f(\theta_k) | переменная | Целевая функция, вычисленная в точке \theta_k — objective function |
| \nabla_\theta | оператор | Вычисляет вектор частных производных по каждому параметру — gradient operator |
| Ψ | переменная | Волновая функция — волновая функция |
| t | переменная | Время — время с |
| τ | переменная | Временной шаг — time step с |
| e^{τW} | оператор | Применяет оператор эволюции для части W — exponential operator |
| e^{τT} | оператор | Применяет оператор эволюции для части T — exponential operator |
| g | переменная | функция, рост которой ограничивается |
| n | переменная | параметр размера входных данных |
| O | оператор | асимптотическая верхняя граница с точностью до постоянного множителя — big o notation |
