Оптимизация

Введение в оптимизацию

GPT-4 не «думает». Это спуск с горы в пространстве 1.7 триллиона измерений. Adam-оптимизатор находит дно за 3 месяца на 25000 GPU H100. Стоимость одного такого спуска - 100 миллионов долларов. Градиентный спуск придумал Коши в 1847 году - он искал минимумы функций одной переменной. Через 177 лет та же идея обучает GPT-4. Маршруты UPS для 60 000 водителей. Airline revenue management. Портфель Марковица. Одна математика, разные масштабы.

**SGD / Adam в нейросетях** - каждая обученная модель: от GPT-4 до ResNet - результат оптимизации loss function; Adam использует экспоненциальные скользящие моменты градиентов
**Логистика UPS** - «ORION» система оптимизирует маршруты 60 000 водителей ежедневно; экономит 100 миллионов миль в год
**Airline revenue management** - авиакомпании решают задачу ценообразования в реальном времени, балансируя загрузку и выручку
**Портфель Марковица** - хедж-фонды оптимизируют портфели, балансируя доходность и риск; это QP-задача с ограничениями

Целевая функция

GPT-4 не «думает». Это спуск с горы в пространстве 1.7 триллиона измерений. Adam-оптимизатор находит дно за 3 месяца на 25000 GPU H100. Стоимость одного такого спуска - 100 миллионов долларов. Градиентный спуск придумал Коши в 1847 году - он искал минимумы функций одной переменной. Через 177 лет та же идея обучает GPT-4. Оптимизация - это **поиск входных значений, при которых целевая функция принимает наилучшее значение**.

**Целевая функция** (objective function) - это f(x), значение которой хотим минимизировать (min) или максимизировать (max). Аргумент x может быть числом, вектором или даже функцией. Задачу максимизации всегда можно свести к минимизации: max f(x) = min(-f(x)).

Область	Целевая функция	Что оптимизируем
Machine Learning	Loss function (MSE, Cross-Entropy)	Минимизируем ошибку модели
Логистика UPS	Стоимость маршрута	Минимизируем расходы на доставку
Финансы (Марковиц)	Риск портфеля	Максимизируем доходность при фиксированном риске
Инженерия	Вес конструкции	Минимизируем материал при сохранении прочности

Ключевой момент: оптимизация - не про «найти ответ», а про «найти **лучший** ответ». Калькулятор решает уравнение. Оптимизатор ищет экстремум. Adam-оптимизатор за 3 месяца на 25000 GPU - тот же принцип, что минимизация функции одной переменной из учебника Коши 1847 года.

Нейросеть обучается минимизировать loss function. Что является аргументом x целевой функции?

Ограничения и допустимое множество

В реальном мире нельзя оптимизировать без ограничений. Бюджет конечен, время ограничено, законы физики не обойти. **Ограничения** (constraints) определяют область, в которой ищем решение - **допустимое множество** (feasible set). UPS оптимизирует маршруты 60 000 водителей с ограничением: водитель работает не более 10 часов. Это и есть constrained optimization.

**Ограничения-равенства** h(x) = 0 задают поверхность в пространстве параметров (например, «сумма весов = 1»). **Ограничения-неравенства** g(x) ≤ 0 задают область (например, «вес каждой акции от 0 до 1»). Пересечение всех ограничений - **допустимое множество** (feasible set).

Оптимум задачи с ограничениями часто лежит **на границе** допустимого множества, а не внутри. Поэтому просто приравнять градиент к нулю недостаточно - нужны специальные методы (Lagrange multipliers, KKT conditions).

Задача **без ограничений** (unconstrained) - частный случай, когда допустимое множество = всё пространство. Gradient descent в ML обычно решает именно такую задачу (хотя regularization можно рассматривать как мягкое ограничение).

Фабрика производит стулья (x₁) и столы (x₂). Ограничение: x₁ + 2x₂ ≤ 100 (часы работы). Какой тип ограничения?

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

Горный ландшафт. Стоишь в долине - кругом только подъёмы. Это **локальный минимум**. Но за горизонтом есть долина глубже - **глобальный минимум**. Как понять, нашёл ли настоящее дно, не обследовав весь ландшафт? Именно это каждый раз спрашивает себя инженер, глядя на loss curve обучения нейросети.

**Локальный минимум** - точка x*, где f(x*) ≤ f(x) для всех x в некоторой окрестности. **Глобальный минимум** - точка x*, где f(x*) ≤ f(x) для **всех** допустимых x. Для произвольной функции найти глобальный минимум - NP-трудная задача.

Спасительное свойство - **выпуклость** (convexity). Если функция выпуклая («чаша»), то любой локальный минимум автоматически является глобальным. Нет ловушек, нет обмана. Именно поэтому выпуклая оптимизация - золотой стандарт: решение гарантированно оптимально. Линейная регрессия с MSE - выпуклая задача, поэтому Adam находит глобальный минимум. Нейросети - невыпуклые, и это принципиально.

Выпуклость и Machine Learning

Линейная регрессия с MSE loss - выпуклая задача, поэтому gradient descent гарантированно находит глобальный минимум. Нейросети - невыпуклые, и инженеры полагаются на эвристики (random initialization, Adam) и надеются на «достаточно хороший» локальный минимум. Исследования 2014-2015 годов (Dauphin, Choromanska) показали: в высокоразмерных пространствах плохие локальные минимумы редки. Большинство критических точек - седловые, а не ловушки.

Функция f(x) = x⁴ - 2x² + 1. Что можно сказать о её экстремумах?

Классификация задач оптимизации

Не все задачи оптимизации одинаковы. От типа задачи зависит, какой метод решения применим и насколько он эффективен. Маршрут как непрерывные координаты - одна задача. Выбор из конечного набора складов - совсем другая. Airline revenue management (цены на билеты в реальном времени) - третья. Обучение GPT-4 - четвёртая, с 1.7 триллиона параметров.

Тип	Целевая функция	Ограничения	Сложность	Пример
Линейная (LP)	Линейная: c^Tx	Линейные: Ax ≤ b	Полиномиальная	Распределение ресурсов
Квадратичная (QP)	Квадратичная: x^TQx + c^Tx	Линейные	Полиномиальная (если Q ≥ 0)	Портфель Марковица
Выпуклая	Выпуклая функция	Выпуклое множество	Полиномиальная	SVM, Ridge regression
Нелинейная	Произвольная гладкая	Произвольные	Зависит от задачи	Обучение нейросетей
Комбинаторная	На дискретном множестве	Дискретные	Часто NP-трудная	TSP, scheduling

**Ключевой принцип:** чем больше структуры в задаче, тем эффективнее метод. LP решается за полиномиальное время. Выпуклая задача - gradient descent находит глобальный оптимум. Нелинейная - только локальный. Комбинаторная - часто приходится жертвовать оптимальностью ради скорости.

В machine learning большинство задач - **нелинейные** (обучение нейросетей), но отдельные компоненты бывают выпуклыми (линейная регрессия, SVM). Тип задачи определяет выбор алгоритма и ожидания от результата.

Почему deep learning работает несмотря на невыпуклость?

Долгое время считалось, что невыпуклость loss-функции нейросетей - фатальная проблема. Но исследования 2014-2015 годов (Dauphin, Choromanska) показали: в высокоразмерных пространствах плохие локальные минимумы редки. Большинство критических точек - седловые, а не ловушки. Gradient descent с momentum умеет от них убегать. Именно поэтому Adam-оптимизатор работает на практике - хотя теория гарантий не даёт.

Gradient descent всегда находит глобальный минимум

Gradient descent находит глобальный минимум только для выпуклых функций. Для невыпуклых - только локальный.

Gradient descent следует направлению наискорейшего спуска и останавливается, когда градиент близок к нулю. Для выпуклой функции такая точка единственна и глобальна. Для невыпуклой - gradient descent застревает в ближайшем локальном минимуме или седловой точке, не зная о существовании лучших решений. Adam добавляет адаптивный momentum, что помогает выходить из седловых точек - но гарантий глобальности не даёт.

Ключевые идеи

**Целевая функция** f(x) - то, что минимизируем или максимизируем; x - параметры, которые подбираем; Коши 1847 → Adam optimizer, 1.7 триллиона параметров
**Ограничения** (равенства и неравенства) определяют допустимое множество - область поиска оптимума; оптимум часто лежит на границе
**Выпуклость** - ключевое свойство: для выпуклых функций локальный минимум = глобальный, gradient descent гарантированно работает; нейросети невыпуклы, но это не проблема в высоких измерениях
Тип задачи (LP, QP, выпуклая, нелинейная, комбинаторная) определяет выбор метода и гарантии результата

Связанные темы

Оптимизация - фундамент для множества дисциплин:

Градиентный спуск — Основной алгоритм решения задач непрерывной оптимизации
Линейное программирование — Важнейший частный случай с полиномиальными алгоритмами
Machine Learning — Обучение модели = оптимизация loss function

Вопросы для размышления

Почему в deep learning инженеров устраивает локальный минимум, хотя теоретически глобальный лучше?
Можно ли любую задачу максимизации свести к минимизации? А задачу с ограничениями - к задаче без ограничений?
Если бы все задачи оптимизации были выпуклыми, как бы это изменило computer science?

Связанные уроки

opt-02 — Градиентный спуск - основной алгоритм решения непрерывных задач оптимизации, естественное продолжение этого урока.
ml-01-intro — Обучение ML-моделей - прямое приложение оптимизации: loss function minimization через gradient descent.
calc-06-derivative-intro — Производная - математический фундамент градиентного спуска; условие f'(x)=0 определяет критические точки.
sci-01 — Численные методы и оптимизация тесно связаны: AlphaFold2 применяет gradient descent в пространстве химических конфигураций белков.
prob-01-intro — Стохастическая оптимизация (SGD) использует случайные выборки - та же идея, что в Monte Carlo: случайность как способ исследовать большое пространство.
calc-19-gradient