Введение

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

Обозначение

Проблемы оптимизации часто выражаются с помощью специальной нотации. Вот несколько примеров:

Оптимизация для нескольких целей

Добавление более одной цели к задаче оптимизации усложняет ее. Например, при оптимизации конструкторского решения желательно получить конструкцию, которая была бы одновременно легкой и жесткой. Когда две цели противоречат друг другу, необходимо найти компромисс. Может существовать одно самое легкое решение, одно самое жесткое решение и бесконечное множество решений, представляющих собой компромисс между весом и жесткостью. Множество компромиссных решений, улучшающих один критерий за счет ухудшения другого, называется множеством Парето. Кривая, построенная на основе зависимости веса от жесткости для наилучших решений, называется границей Парето. Решение считается "Парето-оптимальным" (эквивалентно "Парето-эффективным" или принадлежащим множеству Парето), если оно не доминируется каким-либо другим решением: если оно хуже другого решения по некоторым параметрам и не лучше ни по одному, то оно доминируется и не является Парето-оптимальным. Выбор среди "Парето-оптимальных" решений для определения "предпочтительного решения" передается лицу, принимающему решения. Иными словами, формулировка задачи как многокритериальной оптимизации указывает на отсутствие некоторой информации: желаемые цели заданы, но их комбинации не оценены относительно друг друга. В некоторых случаях недостающую информацию можно получить в ходе интерактивных сессий с лицом, принимающим решения. Задачи многокритериальной оптимизации были обобщены до задач векторной оптимизации, где (частичный) порядок больше не определяется порядком Парето.

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

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

Проблема осуществимости

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

Существование

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

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

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

Достаточные условия для оптимальности

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

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

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

Расчет оптимизации

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

Глобальная конвергенция

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

Методы вычислительной оптимизации

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

Механика

Проблемы в динамике жестких тел (в частности, в артикулированной динамике жестких тел) часто требуют применения методов математического программирования, поскольку динамику жестких тел можно рассматривать как задачу решения обыкновенного дифференциального уравнения на многообразии ограничений. Эти ограничения представляют собой различные нелинейные геометрические ограничения, такие как "эти две точки должны всегда совпадать", "эта поверхность не должна проникать в другие", или "эта точка должна всегда находиться на этой кривой". Кроме того, вычисление контактных сил можно выполнить, решив задачу линейной комплементарности, которую также можно сформулировать как задачу квадратичного программирования (QP). Многие задачи проектирования также могут быть представлены в виде задач оптимизации. Это направление называется оптимизацией проектирования. Одним из разделов является инженерная оптимизация, а другим, более новым и быстро развивающимся разделом, является многодисциплинарная оптимизация проектирования, которая, хотя и полезна во многих задачах, особенно широко применяется в задачах аэрокосмической техники. Этот подход может быть использован в космологии и астрофизике.

Экономика и финансы

Экономика тесно связана с оптимизацией действий экономических агентов, что нашло отражение в влиятельном определении, описывающем экономику как науку, изучающую «человеческое поведение как связь между целями и ограниченными ресурсами» с учетом альтернативных вариантов их использования. Современная теория оптимизации включает в себя как традиционную теорию оптимизации, так и пересекается с теорией игр и изучением экономического равновесия. Журнал экономической литературы классифицирует математическое программирование, методы оптимизации и связанные с ними темы под кодами JEL: C61 C63. В микроэкономике задача максимизации полезности и ее двойственная задача – задача минимизации затрат – являются задачами экономической оптимизации. При условии их последовательного поведения, предполагается, что потребители максимизируют свою полезность, а фирмы обычно максимизируют свою прибыль. Кроме того, агенты часто моделируются как не склонные к риску, стремясь его избегать. Цены на активы также моделируются с использованием теории оптимизации, хотя лежащая в основе математика опирается на оптимизацию стохастических процессов, а не на статическую оптимизацию. Теория международной торговли также использует оптимизацию для объяснения моделей торговли между странами. Оптимизация портфеля является примером многокритериальной оптимизации в экономике. С 1970-х годов экономисты моделируют динамические решения во времени с использованием теории управления. Например, динамические модели поиска используются для изучения поведения на рынке труда. Важное различие заключается между детерминированными и стохастическими моделями. Макроэкономисты строят динамические стохастические модели общего равновесия (DSGE), описывающие динамику всей экономики как результат взаимозависимых оптимизирующих решений работников, потребителей, инвесторов и правительств.

Электротехника

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

Гражданское строительство

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

Исследования операций

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

Инженерные средства управления

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

Геофизика

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

Молекулярная модель

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

Биология вычислительных систем

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