Оптимальность — математическое понятие¶

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

¶Определение

Формально задача оптимизации формулируется так: требуется найти точку x из множества допустимых решений, минимизирующих (или максимизирующих) функцию f(x). Решение x называется оптимальным, если f(x) ≤ f(x) для всех допустимых x (в случае минимизации). Множество допустимых решений задаётся системой ограничений — равенств и неравенств.

Ключевые характеристики оптимального решения:

• Допустимость — решение удовлетворяет всем ограничениям задачи.
• Лучшее значение критерия — ни одно другое допустимое решение не даёт лучшего значения целевой функции.
• Однозначность не гарантирована — оптимальное решение может быть единственным, конечным множеством или целым подмножеством (например, отрезком, если целевая функция постоянна на нём).

¶Виды оптимальности

¶По характеру задачи

• Глобальная оптимальность — решение является лучшим на всём множестве допустимых решений.
• Локальная оптимальность — решение лучше всех соседних допустимых точек, но не обязательно лучше далёких. Для выпуклых задач любое локально оптимальное решение является глобально оптимальным.

¶По типу задачи

• Линейная оптимальность — целевая функция и ограничения линейны. Достижима методами линейного программирования (симплекс-метод, внутренней точки). Оптимум, если он существует, достигается в вершине многогранника допустимых решений.
• Выпуклая оптимальность — целевая функция выпукла, множество допустимых решений выпукло. Любое локально оптимальное решение глобально оптимально; существуют эффективные численные методы.
• Невыпуклая оптимальность — задача содержит невыпуклые функции или ограничения. Глобальный оптум искать существенно сложнее; число локальных оптимумов может быть экспоненциально велико.

¶По типу данных

• Детерминированная оптимальность — все параметры задачи известны точно.
• Стохастическая и робастная оптимальность — параметры неопределены; ищется решение, оптимальное в среднем (стохастическое программирование) или при наихудшем сценарии (робастная оптимизация).

¶Условия оптимальности

Для задачи с дифференцируемыми функциями и гладкими ограничениями оптимальность характеризуется необходимыми условиями:

• Условия Каруша — Кунна — Таккера (ККТ) — обобщение условий Лагранжа на задачи с неравенствами. Для выпуклых задач условия ККТ являются одновременно необходимыми и достаточными.
• Условия первого и второго порядка — обращение градиента (или производной) и положительность гессиана (или неположительность для максимизации) на подходящем подпространстве.
• Двойственность — каждая задача (прямая) имеет связанную двойственную задачу; разрыв между их оптимумами (зазор) равен нулю при выполнении условий сильной двойственности.

¶Методы нахождения оптимальных решений

¶Применение

Понятие оптимальности применяется в широком спектре областей:

• Экономика и менеджмент — оптимальное распределение ресурсов, производственное планирование, ценообразование.
• Инженерия — проектирование конструкций, оптимальное управление, синтез схем.
• Информатика — оптимальные маршруты, расписание, обучение нейронных сетей (оптимизация весов методом градиентного спуска).
• Логистика — задача коммивояжёра, размещение складов, транспортные потоки.
• Статистика и машинное обучение — наилучшие оценки параметров моделей, отбор признаков.

¶Ограничения понятия

Практическая применимость оптимальности сталкивается с рядом трудностей:

• Вычислительная сложность — многие задачи оптимизации NP-трудны; точное глобальное решение может быть недостижимо за разумное время.
• Качество модели — оптимальность относительно выбранной модели и критерия не гарантирует оптимальности в реальной системе; ошибки в данных и упрощения приводят к «оптимуму в модели».
• Многокритериальность — при нескольких конфликтующих критериях строгого оптимума, как правило, не существует; говорят о Парето-оптимальности, когда невозможно улучшить один показатель без ухудшения другого.
• Изменчивость условий — в динамической среде оптимальное решение устаревает по мере изменения параметров задачи.

¶История

Систематическое изучение оптимальности началось в XVII–XVIII веках с работ по вариационному исчислению (Иоганн Бернулли, Леонард Эйлер, Жозеф Лагранж). Понятие выпуклости и условий оптимальности развивали в XIX–XX веках Вильям Стэнли Джевонс, Джон фон Нейман, Лев Канторович (лауреат Нобелевской премии по экономике 1975 года за работы по теории оптимального распределения ресурсов), Джордж Данциг (симплекс-метод, 1947), Ричард Белман (динамическое программирование). В 1984 году Кармаркар предложил алгоритм внутренней точки для линейного программирования, изменивший практику вычислений.

¶Источники

• Ноздря Р. А., Бабенко А. П. Математические методы исследования операций
• Канторович Л. В. Экономический расчёт наилучшего использования ресурсов
• Боков В. Н., Гаврилов В. А. Математическое программирование
• Немировский А. С., Юдин Д. Б. Сложность задач и эффективность методов оптимизации
• Boyd S., Vandenberghe L. Convex Optimization