Оптимизация (математика)

Рассмотрим запись:

${\displaystyle \min _{x\in \mathbb {R} }\;(x^{2}+1)}$

Она означает минимальное значение целевой функции x² + 1 при выборе x из множества вещественных чисел ${\displaystyle \mathbb {R} }$. В этом случае минимум равен 1, достигается при {{{1}}}.

Аналогично,

${\displaystyle \max _{x\in \mathbb {R} }\;2x}$

означает поиск максимального значения функции 2x, где x — любое вещественное число. Максимум не существует, так как функция неограниченна — ответ «бесконечность» или «не определено».

Запись

${\displaystyle {\underset {x\in (-\infty ,-1]}{\operatorname {arg\,min} }}\;x^{2}+1}$

или эквивалентно

${\displaystyle {\underset {x}{\operatorname {arg\,min} }}\;x^{2}+1,\;{\text{при}}\;x\in (-\infty ,-1]}$

означает те значения аргумента x из промежутка (−∞,−1] которые минимизируют функцию x² + 1 (само минимальное значение не спрашивается). В данном случае ответ — {{{1}}}, так как {{{1}}} не принадлежит допустимому множеству.

Аналогично,

${\displaystyle {\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\,x\cos y}$

или эквивалентно

${\displaystyle {\underset {x,\,y}{\operatorname {arg\,max} }}\,x\cos y,\;{\text{при}}\;x\in [-5,5],\;y\in \mathbb {R} }$

означает нахождение пар {x, y} максимизирующих x\cos y, при дополнительном условии x ∈ [-5, 5]. Решения — пары {5, 2k\pi} и {–5, (2k + 1)\pi}, где k пробегает все целые числа.

Операторы arg min и arg max иногда также записываются слитно: argmin и argmax, и обозначают «аргумент минимума» и «аргумент максимума».

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

Решение считается оптимальным по Парето, если оно не доминируется никаким другим (то есть не уступает другому по всем критериям и превосходит по какому-то одному). Выбор между решениями на множестве Парето осуществляется лицом, принимающим решение, и отражает дополнительные предпочтения, которые явным образом не указаны в задаче.

Многокритериальные задачи обобщаются до векторной оптимизации, где частичный порядок может быть шире, чем порядок Парето.

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

Классические методы (градиентные, итерационные) редко находят разные экстремумы при разных начальных условиях, поэтому для поиска всех решений обычно применяют методы глобальной оптимизации: эволюционные алгоритмы, байесовскую оптимизацию, метод имитации отжига и др.

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

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

Теорема Вейерштрасса утверждает: непрерывная вещественная функция на компакте достигает максимума и минимума. Более общий вариант: нижнеполунепрерывная функция на компакте достигает минимума; верхнеполунепрерывная — максимума.

Теорема Ферма: экстремумы неконстреинтных задач достигаются в стационарных точках, где первая производная или градиент функции цели равны нулю (см. признак первого порядка). В иных случаях — в критических точках, где производная не существует, либо на границе допустимого множества. Описание этих условий называют условиями первого порядка.

Для задач с равенствами ограничения используются множители Лагранжа, а при наличии и равенств, и неравенств — условия Каруша-Куна-Такера.

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

Теорема об огибающей описывает, как меняется значение оптимального решения при изменении параметров (раздел сравнительная статика).

Теорема Берже о максимуме (1963) описывает непрерывность оптимальных решений как функции параметров.

Для неконстреинтных задач с дважды дифференцируемыми функциями критические точки ищутся как места, где градиент равен нулю. Для выпуклых функций и локально липшицевых функций наличие нулевого субградиента означает достижение локального минимума. Модификация (положительно-отрицательный момент) может ускорить реальную сходимость к глобальному минимуму^[8].

Тип критической точки анализируется через определённость матрицы Гессе: если она положительно определена — точка локальный минимум, отрицательно определена — максимум, не определена — седловая точка.

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

Если функция цели выпуклая, то локальный минимум всегда глобален. Для таких задач существуют эффективные численные методы, например методы внутренней точки.

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

• Симплекс-метод Данцига, предназначен для линейного программирования
• Обобщения симплекс-метода для квадратичного программирования и линейно-фракционного программирования
• Варианты симплекс-метода, адаптированные для сетевой оптимизации
• Комбинаторные алгоритмы
• Квантовые алгоритмы оптимизации

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

Главный критерий эффективности — число вычислений функции, так как зачастую именно оно доминирует в суммарных вычислениях. Градиенты дают много информации, но их вычисление зачастую сложно (градиент — минимум N+1 вычисление функции; аппроксимация Гессе ~N²). Например, метод Ньютона требует второго порядка производных; простые градиентные методы — только N (но обычно больше итераций). Лучший вариант зависит от конкретной задачи.

Методы:

• Использующие Гессе (или приблизительные Гессе через конечные разности):
  • Метод Ньютона.
  • Последовательное квадратичное программирование — метод Ньютона для малых/средних задач с ограничениями; отдельные версии для задач большой размерности.
  • Методы внутренней точки — широкий класс методов для ограниченных задач; отдельные варианты используют только градиенты/субградиенты, другие — Гессе.
• Градиентные методы и методы с аппроксимацией градиента (или субградиента):
  • Координатный спуск — поочерёдное обновление каждой переменной.
  • Метод сопряжённых градиентов — для больших задач; теоретически конечен для квадратичных функций, но не реализуется на практике на машинах с конечной точностью.
  • Градиентный спуск (или метод наискорейшего спуска) — исторический (медленный) метод, возрождается для гигантских задач.
  • Субградиентный метод — итерационный подход для крупномасштабных задач с липшицевыми функциями (по Борису Поляку схожи с методами сопряжённых градиентов).
  • Bundle-метод спуска — для малых и средних задач с не-гладкими функциями, прежде всего выпуклых.
  • Эллипсоидный метод — для малых задач с квазивыпуклой функцией, важен теоретически (доказательство полиномиальной сложности для ряда комбинаторных задач). Связан с квазиньютоновскими методами.
  • Условный градиент (Франка — Вульфа) — для задач специальной структуры с линейными ограничениями.
  • Квазиньютоновские методы — для средних и больших задач (например, N<1000).
  • Simultaneous perturbation stochastic approximation — стохастическая оптимизация, эффективное случайное приближение градиента.
• Только значения функции (градиенты аппроксимируются разностями):
  • Интерполяционные методы.
  • Методы поиска по образцу — с лучшей сходимостью, чем Нелдер — Мид.
  • Метод зеркального спуска.

Помимо явно сходящихся алгоритмов и итерационных методов, применяются эвристики — алгоритмы без гарантированной сходимости, но полезные в практике. Известные примеры:

При расчётах динамики твёрдых тел и, в частности, динамики сочленённых систем часто применяют математическое программирование: например, динамика тела как решение ОДУ на многообразии ограничений^[9]; ограничения — различные нелинейные геометрические условия («точки совпадают», «поверхности не пересекаются» и т. д.). Добавление контактных сил сводят к решению задач о линейной комплементарности, эквивалентных квадратичным задачам оптимизации.

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

Методы оптимизации применяются и в космологии, астрофизике^[10].

Экономика тесно связана с оптимизацией: классическое определение предмета экономики — «наука о человеческом поведении как отношении между целями и ограниченными ресурсами» с альтернативными способами использования^[11]. Современная теория оптимизации включает методы экономического равновесия, входит в сферу игровой теории. В JEL кодах математическое программирование и оптимизационные методы — C61-C63.

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

С 1970-х годов динамическое принятие решений моделируется с помощью оптимального управления^[12]. Например, модели поиска работы — предмет экономики труда^[13][14][15].

В электротехнике оптимизационные методы применяют для проектирования фильтров^[16], защиты от магнитных полей, space mapping — проектирования СВЧ-структур^[17], проектирования антенн^[18][19], моделирования электромагнитных устройств^[20][21]. Применяют и в анализе потоков мощности^[22].

В гражданском строительстве оптимизация востребована для управления строительством, транспортных задач (проектирование и содержание дорожных сетей, анализ жизненного цикла объектов^[23], распределение ресурсов, управление водными ресурсами, управление движением^[24], оптимального планирования строительства и др.

Исследование операций использует оптимизационные методы повсеместно^[25]. Помимо классических техник, активно применяются стохастическое программирование, моделирование и имитация, крупномасштабная оптимизация.

Оптимизация используется в проектировании современных систем управления. Высокоуровневые регуляторы типа предиктивное управление моделью или оптимизация в реальном времени решают задачи непосредственно в ходе работы процесса с учётом ограничений и моделей системы.

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

Для конформационного анализа молекул широко применяются нелинейные методы оптимизации.

Алгоритмы оптимизации используются в построении биологических моделей, планировании экспериментов, метаболической инженерии и синтетической биологии^[26]. Линейное программирование применяется для расчёта максимальных выходов продуктов^[26] для вывода генетических регуляторных сетей по данным микромассивов^[27], и анализа транскрипционных сетей^[28]. Нелинейное программирование — при анализе энергетического обмена^[29], в метаболической инженерии и параметрической идентификации^[30].