Оптимизация

Оптимизация — раздел прикладной и теоретической математики, связанный с поиском наилучшего решения в заданном множестве допустимых вариантов. В базовой формулировке требуется найти точку, в которой целевая функция достигает минимума или максимума при возможных ограничениях. В математическом виде задача оптимизации обычно записывают как задача минимизации целевой функции при наличии равенств и неравенств; общие признаки оптимума связаны с условием стационарности и вторыми производными, например $\nabla f(x)=0$ и проверкой знака матрицы вторых производных $\nabla^2 f(x)\succ 0$. Оптимизация служит фундаментом для теорий принятия решений, численных методов и машинного обучения. {IMAGE_0}

С практической точки зрения задачи оптимизации делятся на линейные и нелинейные, выпуклые и невыпуклые, непрерывные и дискретные (комбинаторные). Линейное программирование — важный частный случай: минимизация линейной функции при линейных ограничениях, что формализуется как $\min\; c^T x \quad \text{s.t. } A x \le b,\; x\ge0$. Для задач с ограничениями вводят функцию Лагранжа и получают условия типа множителей Лагранжа; Лагранжиан часто записывают в виде $L(x,\lambda)=f(x)+\lambda^\top g(x)$. Для выпуклых задач достаточно первых условий для гарантии глобального минимума, а в негладких или невыпуклых ситуациях применяют численные методы: градиентные спуски, проекционные методы, комбинированные эвристики. Популярный итеративный метод градиентного спуска описывается обновлением $x_{k+1}=x_k-\alpha \nabla f(x_k)$.

На практике оптимизация встречается повсюду: распределение ресурсов и планирование в экономике, настройка гиперпараметров в машинном обучении, проектирование конструкций в технике, маршрутное планирование и многое другое. Математические формулы помогают формально понять структуру задачи и выбрать подходящий метод решения: общая задача с ограничениями записывается как $\begin{aligned} &\min_x f(x) \\ &\text{при } g_i(x)=0,\; h_j(x)\le 0 \end{aligned}$, а для квадратичных задач часто используется компактная запись целевой функции вида $f(x)=\frac{1}{2}x^\top Q x + b^\top x + c$, что позволяет применять эффективные аналитические и численные методы.