Минимизация — математическая задача¶

Минимизация — это задача нахождения наименьшего (или наибольшего, если речь идёт о максимизации) значения целевой функции при заданных ограничениях. В широком смысле под «минимизацией» понимается процесс сведения к минимуму какого-либо измеримого показателя: затрат, ошибок, риска, объёма данных, энергопотребления. В математике, информатике и инженерии минимизация формализуется как оптимизационная задача.

¶Математическая постановка

Классическая задача минимизации формулируется так: требуется найти вектор переменных $x$, минимизирующий функцию $f(x)$ при ограничениях вида $g_i(x) \leq 0$ и $h_j(x) = 0$. Область допустимых решений, удовлетворяющая всем ограничениям, обозначается $D$. Если минимум достигается в точке $x^$, то $x^$ называют точкой минимума, а значение $f(x^*$ — минимумом функции.

Различают локальный минимум (значение функции не меньше в некоторой окрестности точки) и глобальный минимум (наименьшее значение на всём множестве $D$). Нахождение глобального минимума в общем случае является сложной задачей; для произвольных гладких функций она классифицируется как NP-трудная.

¶Основные методы

¶Аналитические методы

Для дифференцируемых функций необходимое условие локального минимума — равенство градиента нулю: $\nabla f(x^*) = 0$. Точки, где это условие выполняется, называют стационарными. Достаточное условие связано с положительной определённостью гессиана. Метод Лагранжа позволяет решать задачи с равенствами, сводя их к безусловной минимизации вспомогательной функции.

¶Численные методы

На практике чаще применяются итерационные алгоритмы:

• Градиентный спуск — последовательное движение вдоль антиградиента с шагом $\alpha$. Прост в реализации, но чувствителен к выбору шага и может застревать в локальных минимумах и на плато.
• Метод Ньютона — использует вторые производные (гессиан) для квадратичной аппроксимации функции; быстрее сходится, но требует вычисления и обращения гессиана.
• Квазиньютоновские методы (BFGS, L-BFGS) — аппроксимируют гессиан, не вычисляя его напрямую.
• Методы без градиента (покоординатный спуск, Nelder–Mead, дифференциальная эволюция) — применимы, когда градиент недоступен или функция недифференцируема.
• Стохастический градиентный спуск (SGD) — оценка градиента по подмножеству данных; основа обучения нейронных сетей.

¶Линейное программирование

Если целевая функция и ограничения линейны, задача решается методом симплекс-процедуры или внутренней точки за полиномиальное время. Линейное программирование находит применение в логистике, планировании производства и распределении ресурсов.

¶Минимизация в информатике

¶Минимизация логических функций

В цифровой электронике под минимизацией понимают упрощение булевой функции до наименьшего числа термов. Алгоритмы Квайна — МакКласки и Эшенауера — Бергмана строят минимальные ДНФ. Результат применяется при синтезе схем из логических элементов.

¶Минимизация автоматов

Задача приведения конечного автомата к минимальному эквивалентному автомату решается алгоритмом Мура с разбиением состояний на эквивалентные классы.

¶Минимизация кода и данных

Компиляторы выполняют минимизацию промежуточного представления: удаление недостижимого кода, свёртку констант, инлайн-развёртку. В теории информации минимизация — это сжатие данных без потерь или с потерями (LZW, LZ77, алгоритмы на основе Хаффмана и арифметического кодирования).

¶Применение

• Машинное обучение — минимизация функции потерь (кросс-энтропия, среднеквадратическая ошибка) является целью обучения модели. Регуляризация (L1, L2) — это минимизация обобщённой ошибки, а не только эмпирической.
• Оптимизация производства — минимизация себестоимости при заданном объёме выпуска.
• Транспорт и логистика — минимизация суммарного пробега (задача коммивояжёра, задача о назначениях).
• Управление запасами — минимизация затрат на хранение и дефицит (модель Уилсона).
• Инженерная механика — минимизация потенциальной энергии системы соответствует равновесному состоянию (принцип наименьшего действия).
• Криптография — сложность минимизации лежит в основе некоторых криптографических задач.

¶Связанные понятия

Максимизация сводится к минимизации с помощью замены $f(x) \to -f(x)$. Вариационное исчисление решает задачу минимизации функционалов. Выпуклая оптимизация — класс задач, где локальный минимум совпадает с глобальным; для таких задач разработаны эффективные методы (проецируемый градиент, метод внутренней точки).

¶Примечания

Термин «минимизировать это» без уточнения контекста не определяет конкретную задачу; выбор метода зависит от свойств целевой функции (гладкость, выпуклость, дискретность) и характера ограничений.

Источники:

• Ноздрин И. А. «Линейная алгебра и аналитическая геометрия»
• Немировский А. С., Юдин Д. Б. «Сложность задач и эффективность методов оптимизации»
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ»
• Болтянский В. Г., Немировский А. С. «Выпуклость и задачи комбинаторной оптимизации»