Математическая оптимизация (иначе пишется оптимизация ) или математическое программирование — это выбор лучшего элемента по некоторому критерию из некоторого набора доступных альтернатив. [1] Обычно его разделяют на два подполя: дискретную оптимизацию и непрерывную оптимизацию . Проблемы оптимизации возникают во всех количественных дисциплинах, от информатики и инженерии [2] до исследования операций и экономики , а разработка методов решения на протяжении веков представляла интерес для математики . [3]
В более общем подходе задача оптимизации состоит из максимизации или минимизации реальной функции путем систематического выбора входных значений из разрешенного набора и вычисления значения функции. Обобщение теории и методов оптимизации на другие формулировки составляет обширную область прикладной математики . В более общем смысле оптимизация включает в себя поиск «наилучших доступных» значений некоторой целевой функции с учетом определенной области (или входных данных), включая множество различных типов целевых функций и различных типов областей.
Задачи оптимизации можно разделить на две категории в зависимости от того, являются ли переменные непрерывными или дискретными :
Задачу оптимизации можно представить следующим образом:
Такая формулировка называется задачей оптимизации или задачей математического программирования (термин, не связанный напрямую с компьютерным программированием , но все еще используемый, например, в линейном программировании — см. Историю ниже). Многие реальные и теоретические проблемы могут быть смоделированы в этой общей структуре.
Поскольку справедливо следующее
достаточно решить только задачи минимизации. Однако и противоположная точка зрения, рассматривающая только задачи максимизации, также будет верна.
Проблемы, сформулированные с использованием этого метода в области физики , могут называть этот метод минимизацией энергии , говоря о значении функции f как представляющей энергию моделируемой системы . В машинном обучении всегда необходимо непрерывно оценивать качество модели данных с помощью функции стоимости , где минимум подразумевает набор возможных оптимальных параметров с оптимальной (наименьшей) ошибкой.
Обычно A — это некоторое подмножество евклидова пространства , часто определяемое набором ограничений , равенств или неравенств, которым должны удовлетворять члены A. Область A функции f называется пространством поиска или множеством выбора , а элементы A называются кандидатами или возможными решениями .
Функцию f называют по-разному целевой функцией , целевой функцией — функцией потерь или функцией затрат (минимизация), [4] — функцией полезности или функцией пригодности (максимизация) или, в некоторых областях, энергетической функцией или энергетическим функционалом . Допустимое решение, которое минимизирует (или максимизирует, если это цель) целевую функцию, называется оптимальным решением .
В математике традиционные задачи оптимизации обычно формулируются в терминах минимизации.
Локальный минимум x * определяется как элемент, для которого существует некоторое δ > 0 такое, что
выражение f ( x *) ≤ f ( x ) справедливо;
то есть в некоторой области вокруг x * все значения функции больше или равны значению этого элемента. Аналогично определяются локальные максимумы.
Хотя локальный минимум не хуже любых близлежащих элементов, глобальный минимум не хуже любого возможного элемента. Обычно, если целевая функция не является выпуклой в задаче минимизации, может быть несколько локальных минимумов. В выпуклой задаче , если существует локальный минимум, который является внутренним (не на краю множества допустимых элементов), это также глобальный минимум, но невыпуклая задача может иметь более одного локального минимума, не все из которых требуют быть глобальными минимумами.
Большое количество алгоритмов, предложенных для решения невыпуклых задач, включая большинство коммерчески доступных решателей, не способны различать локально оптимальные решения и глобально оптимальные решения и будут рассматривать первые как фактические решения исходной задачи. Глобальная оптимизация — это раздел прикладной математики и численного анализа , который занимается разработкой детерминированных алгоритмов, способных гарантировать сходимость за конечное время к фактическому оптимальному решению невыпуклой задачи.
Задачи оптимизации часто выражаются специальными обозначениями. Вот некоторые примеры:
Рассмотрим следующие обозначения:
Это обозначает минимальное значение целевой функции x 2 + 1 при выборе x из множества действительных чисел . Минимальное значение в этом случае равно 1, происходящему при x = 0 .
Аналогично, обозначения
запрашивает максимальное значение целевой функции 2 x , где x может быть любым действительным числом. В этом случае такого максимума не существует, поскольку целевая функция неограничена, поэтому ответ — « бесконечность » или « неопределено ».
Рассмотрим следующие обозначения:
или эквивалентно
Это представляет собой значение (или значения) аргумента x в интервале ( −∞,−1] , которое минимизирует (или минимизирует) целевую функцию x 2 + 1 (фактическое минимальное значение этой функции не соответствует задаче). В этом случае ответом будет x = −1 , поскольку x = 0 недопустимо, то есть не принадлежит допустимому множеству .
Сходным образом,
или эквивалентно
представляет пару { x , y } (или пары), которая максимизирует (или максимизирует) значение целевой функции x cos y с добавленным ограничением, что x лежит в интервале [−5,5] (опять же, фактический максимум значение выражения не имеет значения). В этом случае решениями являются пары вида {5, 2 k π } и {−5, (2 k + 1) π } , где k пробегает все целые числа .
Операторы arg min и arg max иногда также записываются как argmin и argmax и обозначают аргумент минимума и аргумент максимума .
Ферма и Лагранж нашли формулы для определения оптимума, основанные на исчислении, а Ньютон и Гаусс предложили итерационные методы движения к оптимуму.
Термин « линейное программирование » для некоторых случаев оптимизации был предложен Джорджем Б. Данцигом , хотя большая часть теории была введена Леонидом Канторовичем в 1939 году. ( Программирование в этом контексте не относится к компьютерному программированию , а происходит от использования программа вооруженных сил США для ссылки на предлагаемые графики обучения и материально-технического обеспечения , которые были проблемами, которые Данциг изучал в то время.) Данциг опубликовал симплексный алгоритм в 1947 году, а также Джон фон Нейман и другие исследователи работали над теоретическими аспектами линейного программирования. (как и теория дуальности ) примерно в то же время. [5]
Среди других известных исследователей математической оптимизации можно назвать следующих:
В ряде подполей методы предназначены в первую очередь для оптимизации в динамических контекстах (то есть принятия решений с течением времени):
Добавление более чем одной цели к задаче оптимизации усложняет задачу. Например, чтобы оптимизировать конструкцию конструкции, желательно, чтобы конструкция была одновременно легкой и жесткой. Когда две цели конфликтуют, необходимо найти компромисс. Может быть одна самая легкая конструкция, одна самая жесткая конструкция и бесконечное количество конструкций, которые представляют собой некоторый компромисс по весу и жесткости. Набор компромиссных планов, которые улучшают один критерий за счет другого, известен как набор Парето . Кривая, отображающая вес и жесткость лучших конструкций, известна как граница Парето .
План считается «оптимальным по Парето» (что эквивалентно «эффективному по Парето» или множеству Парето), если в нем не доминирует какой-либо другой план: если он хуже другого плана в некоторых отношениях и не лучше ни в каком отношении, тогда оно доминируется и не является оптимальным по Парето.
Выбор среди «оптимальных по Парето» решений для определения «предпочтительного решения» делегируется лицу, принимающему решение. Другими словами, определение проблемы как многокритериальной оптимизации сигнализирует о том, что некоторая информация отсутствует: желаемые цели заданы, но их комбинации не оцениваются относительно друг друга. В некоторых случаях недостающую информацию можно получить в ходе интерактивных сеансов с лицом, принимающим решения.
Задачи многокритериальной оптимизации были далее обобщены до задач векторной оптимизации , где (частичный) порядок больше не задается упорядочением Парето.
Проблемы оптимизации часто носят многомодальный характер; то есть у них есть несколько хороших решений. Все они могут быть глобально хорошими (с одинаковым значением функции затрат) или же может существовать сочетание хороших на глобальном уровне и локальных решений. Получение всех (или хотя бы некоторых из) множественных решений является целью мультимодального оптимизатора.
Классические методы оптимизации из-за их итеративного подхода не работают удовлетворительно, когда они используются для получения нескольких решений, поскольку не гарантируется, что разные решения будут получены даже с разными начальными точками при нескольких запусках алгоритма.
Общие подходы к задачам глобальной оптимизации , где могут присутствовать множественные локальные экстремумы, включают эволюционные алгоритмы , байесовскую оптимизацию и имитацию отжига .
Проблема выполнимости , также называемая проблемой осуществимости , — это просто проблема поиска любого возможного решения вообще безотносительно к объективной ценности. Это можно рассматривать как особый случай математической оптимизации, когда целевое значение одинаково для каждого решения, и, следовательно, любое решение является оптимальным.
Многие алгоритмы оптимизации должны начинаться с осуществимой точки. Один из способов получить такую точку — ослабить условия осуществимости, используя слабую переменную ; при достаточном слабине возможна любая отправная точка. Затем минимизируйте эту резервную переменную до тех пор, пока резерв не станет нулевым или отрицательным.
Теорема Карла Вейерштрасса о крайних значениях гласит, что непрерывная вещественная функция на компакте достигает своего максимального и минимального значения. В более общем смысле, полунепрерывная снизу функция на компакте достигает минимума; полунепрерывная сверху функция на компакте достигает точки максимума или вида.
Одна из теорем Ферма утверждает, что оптимум задач без ограничений находится в стационарных точках , где первая производная или градиент целевой функции равна нулю (см. тест первой производной ). В более общем смысле их можно найти в критических точках , где первая производная или градиент целевой функции равна нулю или не определена, или на границе множества выбора. Уравнение (или набор уравнений), утверждающее, что первая производная(-и) равна(-ют) нулю при внутреннем оптимуме, называется «условием первого порядка» или набором условий первого порядка.
Оптимумы задач с ограничениями равенства можно найти с помощью метода множителей Лагранжа . Оптимум задач с ограничениями равенства и/или неравенства можно найти с помощью « условий Каруша – Куна – Такера ».
Хотя первый тест производной выявляет точки, которые могут быть экстремумами, этот тест не отличает точку, которая является минимумом, от точки, которая является максимумом, или от точки, которая не является ни тем, ни другим. Когда целевая функция дважды дифференцируема, эти случаи можно отличить, проверив вторую производную или матрицу вторых производных (называемую матрицей Гессе ) в задачах без ограничений, или матрицу вторых производных целевой функции и ограничений, называемых граничной Гессен в ограниченных задачах. Условия, которые отличают максимумы или минимумы от других стационарных точек, называются «условиями второго порядка» (см. « Тест второй производной »). Если решение-кандидат удовлетворяет условиям первого порядка, то удовлетворения условий второго порядка достаточно для установления хотя бы локальной оптимальности.
Теорема о конверте описывает, как изменяется значение оптимального решения при изменении основного параметра . Процесс вычисления этого изменения называется сравнительной статикой .
Максимальная теорема Клода Бержа (1963) описывает непрерывность оптимального решения как функцию основных параметров.
Для задач без ограничений с дважды дифференцируемыми функциями некоторые критические точки можно найти, найдя точки, в которых градиент целевой функции равен нулю (то есть стационарные точки). В более общем смысле, нулевой субградиент подтверждает, что локальный минимум был найден для задач минимизации с выпуклыми функциями и другими локально липшицевыми функциями , которые встречаются при минимизации функции потерь нейронной сети. Положительно-отрицательная оценка импульса позволяет избежать локального минимума и сходится к глобальному минимуму целевой функции. [6]
Кроме того, критические точки можно классифицировать, используя определенность матрицы Гессе : если гессиан положительно определен в критической точке, то эта точка является локальным минимумом; если матрица Гессе отрицательно определена, то точка является локальным максимумом; наконец, если неопределенно, то точка является своего рода седловой точкой .
Задачи с ограничениями часто можно преобразовать в задачи без ограничений с помощью множителей Лагранжа . Лагранжева релаксация также может обеспечить приближенные решения сложных задач с ограничениями.
Если целевая функция является выпуклой функцией , то любой локальный минимум также будет глобальным минимумом. Существуют эффективные численные методы минимизации выпуклых функций, такие как методы внутренней точки .
В более общем смысле, если целевая функция не является квадратичной функцией, то многие методы оптимизации используют другие методы, чтобы гарантировать, что некоторая подпоследовательность итераций сходится к оптимальному решению. Первый и до сих пор популярный метод обеспечения сходимости основан на поиске строк , который оптимизирует функцию по одному измерению. Второй и все более популярный метод обеспечения конвергенции использует доверительные регионы . В современных методах недифференцируемой оптимизации используются как поиск по строкам, так и доверительные области . Обычно глобальный оптимизатор работает намного медленнее, чем продвинутые локальные оптимизаторы (такие как BFGS ), поэтому часто эффективный глобальный оптимизатор можно создать, запуская локальный оптимизатор из разных стартовых точек.
Для решения проблем исследователи могут использовать алгоритмы , завершающиеся за конечное число шагов, или итерационные методы , которые сходятся к решению (для некоторого заданного класса проблем), или эвристики , которые могут обеспечить приближенные решения некоторых проблем (хотя их итерации не обязательно сходятся).
Итеративные методы , используемые для решения задач нелинейного программирования, различаются в зависимости от того, оценивают ли они гессиан , градиенты или только значения функций. Хотя оценка гессианов (H) и градиентов (G) повышает скорость сходимости, для функций, для которых эти величины существуют и изменяются достаточно плавно, такие оценки увеличивают вычислительную сложность (или вычислительные затраты) каждой итерации. В некоторых случаях вычислительная сложность может быть чрезмерно высокой.
Одним из основных критериев для оптимизаторов является количество требуемых вычислений функции, поскольку это часто уже требует больших вычислительных усилий, обычно гораздо больших, чем внутри самого оптимизатора, которому в основном приходится работать с N переменными. Производные предоставляют подробную информацию для таких оптимизаторов, но их еще сложнее вычислить, например, аппроксимация градиента требует как минимум N+1 оценок функции. Для аппроксимации 2-х производных (собранных в матрице Гессе) количество оценок функции имеет порядок N². Метод Ньютона требует производных 2-го порядка, поэтому для каждой итерации количество вызовов функций имеет порядок N², но для более простого оптимизатора чистого градиента это только N. Однако оптимизаторам градиента обычно требуется больше итераций, чем алгоритму Ньютона. Какой из них лучше по количеству вызовов функций, зависит от самой задачи.
Помимо (конечно завершающихся) алгоритмов и (сходящихся) итерационных методов , существуют эвристики . Эвристика — это любой алгоритм, который не гарантирует (математически) нахождения решения, но который, тем не менее, полезен в определенных практических ситуациях. Список некоторых известных эвристик:
Проблемы динамики твердого тела (в частности, динамики шарнирно-сочлененного твердого тела) часто требуют методов математического программирования, поскольку вы можете рассматривать динамику твердого тела как попытку решить обыкновенное дифференциальное уравнение на многообразии ограничений; [7] ограничения представляют собой различные нелинейные геометрические ограничения, такие как «эти две точки всегда должны совпадать», «эта поверхность не должна пересекать любую другую» или «эта точка всегда должна лежать где-то на этой кривой». Кроме того, задачу вычисления контактных сил можно решить путем решения линейной задачи дополнительности , которую также можно рассматривать как задачу QP (квадратичного программирования).
Многие проблемы проектирования также можно выразить в виде программ оптимизации. Это приложение называется оптимизацией дизайна. Одним из подмножеств является инженерная оптимизация , а другим недавним и растущим подвидом этой области является междисциплинарная оптимизация проектирования , которая, хотя и полезна во многих проблемах, в частности применяется к проблемам аэрокосмической техники .
Этот подход может быть применен в космологии и астрофизике. [8]
Экономика настолько тесно связана с оптимизацией агентов , что влиятельное определение описывает экономику как науку как «изучение человеческого поведения как взаимосвязи между целями и ограниченными средствами» с альтернативными видами использования. [9] Современная теория оптимизации включает в себя традиционную теорию оптимизации, но также пересекается с теорией игр и изучением экономического равновесия . Коды журнала экономической литературы классифицируют математическое программирование, методы оптимизации и связанные темы под JEL:C61-C63 .
В микроэкономике проблема максимизации полезности и ее двойная проблема — проблема минимизации расходов — являются задачами экономической оптимизации. Предполагается, что, поскольку они ведут себя последовательно, потребители максимизируют свою полезность , в то время как фирмы обычно максимизируют свою прибыль . Кроме того, агенты часто моделируются как не склонные к риску , тем самым предпочитающие избегать риска. Цены на активы также моделируются с использованием теории оптимизации, хотя лежащая в основе математика основана на оптимизации случайных процессов , а не на статической оптимизации. Теория международной торговли также использует оптимизацию для объяснения моделей торговли между странами. Оптимизация портфелей является примером многоцелевой оптимизации в экономике.
С 1970-х годов экономисты моделировали динамические решения с течением времени, используя теорию управления . [10] Например, модели динамического поиска используются для изучения поведения на рынке труда . [11] Принципиальное различие существует между детерминистическими и стохастическими моделями. [12] Макроэкономисты строят модели динамического стохастического общего равновесия (DSGE) , которые описывают динамику всей экономики как результат взаимозависимых оптимизирующих решений работников, потребителей, инвесторов и правительств. [13] [14]
Некоторые распространенные применения методов оптимизации в электротехнике включают проектирование активных фильтров , [15] уменьшение поля рассеяния в сверхпроводящих магнитных системах хранения энергии, проектирование пространственных карт микроволновых структур, [16] телефонные антенны, [17] [18] [19] электромагнетизм. -основанный дизайн. С момента открытия космического картографирования в 1993 году , с момента открытия космического картографирования в 1993 году , при оптимизации конструкции СВЧ-компонентов и антенн широко использовались соответствующие физические или эмпирические суррогатные модели и методологии космического картографирования . [20] [21] Методы оптимизации также используются в энергетике. анализ потока . [22]
Оптимизация широко используется в гражданском строительстве. Управление строительством и транспортное проектирование являются одними из основных отраслей гражданского строительства, которые в значительной степени полагаются на оптимизацию. Наиболее распространенными проблемами гражданского строительства, которые решаются с помощью оптимизации, являются прорезка и засыпка дорог, анализ жизненного цикла конструкций и инфраструктуры, [23] выравнивание ресурсов , [24] [25] распределение водных ресурсов , управление дорожным движением [26] и график. оптимизация.
Другая область, в которой широко используются методы оптимизации, — это исследование операций . [27] В исследованиях операций также используется стохастическое моделирование и симуляция для поддержки более эффективного принятия решений. В исследованиях операций все чаще используется стохастическое программирование для моделирования динамических решений, адаптирующихся к событиям; такие проблемы можно решить с помощью методов крупномасштабной оптимизации и стохастической оптимизации .
Математическая оптимизация используется во многих современных конструкциях контроллеров. Контроллеры высокого уровня, такие как управление с прогнозированием модели (MPC) или оптимизация в реальном времени (RTO), используют математическую оптимизацию. Эти алгоритмы работают в режиме онлайн и неоднократно определяют значения переменных решения, таких как открытия дросселей на технологической установке, путем итеративного решения задачи математической оптимизации, включая ограничения и модель управляемой системы.
Методы оптимизации регулярно используются в задачах оценки геофизических параметров. Учитывая набор геофизических измерений, например сейсмических записей , обычно приходится определять физические свойства и геометрические формы подстилающих пород и жидкостей. Большинство задач геофизики нелинейны, при этом широко используются как детерминированные, так и стохастические методы.
Методы нелинейной оптимизации широко используются в конформационном анализе .
Методы оптимизации используются во многих аспектах вычислительной системной биологии, таких как построение моделей, оптимальный план эксперимента, метаболическая инженерия и синтетическая биология. [28] Линейное программирование применялось для расчета максимально возможных выходов продуктов ферментации [28] и для вывода о сетях регуляции генов на основе нескольких наборов данных микрочипов [29] , а также о сетях регуляции транскрипции на основе данных с высокой пропускной способностью. [30] Нелинейное программирование использовалось для анализа энергетического метаболизма [31] и применялось для метаболической инженерии и оценки параметров биохимических путей. [32]