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

История

Ферма и Лагранж вывели формулы поиска экстремумов с помощью анализа, Ньютон и Гаусс предложили итерационные методы приближения к оптимуму.

Термин «линейное программирование» для ряда задач оптимизации принадлежит Джорджу Б. Данцигу, хотя теоретическая база была заложена ранее, в частности Леонидом Канторовичем в 1939 году. («Программирование» в данном случае не связано с компьютерным программированием, а происходит от военной терминологии — обозначения расписаний подготовки и снабжения.) Данциг опубликовал симплекс-метод в 1947 году, а также фон Нейман и другие учёные в это же время исследовали теорию линейного программирования (например, двойственность)[7].

К видным учёным-теоретикам в области оптимизации относятся:

• Ричард Беллман;
• Димитрис Берцекас;
• Мишель Бьёрлер;
• Стивен Бойд;
• Роджер Флетчер;
• Мартин Грётшель;
• Рональд Ховард;
• Фриц Джон;
• Нарендра Кармаркар;
• Уильям Каруш;
• Леонид Хачиян;
• Бернард Купман;
• Гарольд Кун;
• Ласло Ловас;
• Дэвид Люэнбергер;
• Аркадий Немировский;
• Юрий Нестеров;
• Лев Понтрягин;
• Р. Тайрелл Рокафеллар;
• Наум Шор;
• Альберт Такер.

Основные направления

• Выпуклое программирование — частный случай, когда целевая функция выпукла (минимизация) или вогнута (максимизация), а множество ограничений образует выпуклое множество. Это либо частный случай нелинейного программирования, либо обобщение линейного и выпуклого квадратичного программирования.Линейное программирование (ЛП) — частный вид выпуклого программирования, где функция цели линейна, а ограничения — только линейные равенства/неравенства (множество решений образует многогранник или многогранное тело, если оно ограничено).
  Вторично-конусное программирование — выпуклый случай, включает некоторые типы квадратичных задач.
  Полуопределённое программирование — частная область выпуклой оптимизации, задачи в которой формулируются с полуопределёнными матрицами.
  Конусное программирование — обобщённая форма выпуклого программирования. ЛП, SOCP и SDP — подвиды конусных задач по соответствующему типу конусов.
  Геометрическое программирование — техника, позволяющая сводить задачи, где функции ограничений выражаются через позиномиалы и мониомы, к выпуклым.
  
• Целочисленное программирование — задачи линейного программирования с дополнительным ограничением: переменные принимают только целые значения. Это невыпуклый, и, как правило, более сложный для вычислений класс задач.
• Квадратичное программирование — функция цели содержит квадратные члены, множество решений — с линейными ограничениями. При определённых условиях задача выпуклая.
• Фракционное программирование — оптимизация отношения двух нелинейных функций; отдельный класс выпуклых фракционных задач может быть сведён к выпуклой оптимизации.
• Нелинейное программирование — наиболее общий случай: нелинейность может содержаться как в целевой функции, так и в ограничениях. Выпуклая или невыпуклая природа задачи определяет, насколько она труднорешаема.
• Стохастическое программирование — часть ограничений или параметров моделируются как случайные величины.
• Робастная оптимизация — моделирование неопределённости в данных задачи, построение решений, устойчивых к различным сценариям из множества неопределённости.
• Комбинаторная оптимизация — решения выбираются из дискретного (или сводимого к таковому) множества.
• Стохастическая оптимизация используется при наличии случайных шумов в измерениях функции или входных данных.
• Бесконечномерная оптимизация — класс задач, где допустимое множество решений — бесконечномерное пространство, например, пространство функций.
• Эвристические методы и метаэвристики — делают минимальные предположения о свойствах задачи и зачастую не гарантируют поиск глобального оптимального решения, но применяются для приближённых решений сложных задач.
• Задача удовлетворения ограничений — частный случай, когда функция цели постоянна (в используется в искусственном интеллекте, автоматизированном выводе).
• Внутри задач удовлетворения ограничений выделяют программирование с ограничениями — подход, в котором между переменными задаются ограничения, а не функции цели.
  
• Дизъюнктивное программирование — задачи, где достаточно выполнения по крайней мере одного ограничения из набора.
• Space mapping — концепция моделирования и оптимизации инженерных систем с использованием грубых (коarse) и точных (fine) моделей.

Части методов лежат в области динамической оптимизации (принятие решений с течением времени):

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

Многокритериальная оптимизация

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

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

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

Мультимодальная и глобальная оптимизация

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

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

Классификация точек и экстремумов

Задача достижимости

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

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

Существование решений

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

Необходимые условия оптимальности

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

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

Достаточные условия экстремума

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

Чувствительность и непрерывность решения

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

Теорема Берже о максимуме (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].