Математическая оптимизация - Mathematical optimization

График данного z = f (Икс, у) = −(Икс² + у²) + 4. Глобальный максимум в (х, у, г) = (0, 0, 4) обозначается синей точкой.

Минимальный поиск Нелдера-Мида Функция Симионеску. Вершины симплекса упорядочены по их значениям, причем 1 имеет наименьшее значение (FX лучшее значение.

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

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

Проблемы оптимизации

Задачу оптимизации можно представить следующим образом:

Данный: а функция ж : А → ℝ от некоторых набор А к действительные числа

Искал: элемент Икс₀ ∈ А такой, что ж(Икс₀) ≤ ж(Икс) для всех Икс ∈ А («минимизация») или такой, что ж(Икс₀) ≥ ж(Икс) для всех Икс ∈ А («максимизация»).

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

Поскольку верно следующее

${ displaystyle f left ( mathbf {x} _ {0} right) geq f left ( mathbf {x} right) Leftrightarrow { тильда {f}} left ( mathbf {x} _ {0} right) leq { tilde {f}} left ( mathbf {x} right)}$

с участием

${ displaystyle { tilde {f}} left ( mathbf {x} right): = - f left ( mathbf {x} right), , { tilde {f}} ,: , A rightarrow mathbb {R}}$

решать задачи минимизации удобнее. Однако верна и обратная точка зрения.

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

Обычно А есть некоторые подмножество из Евклидово пространство ℝ^п, часто указывается набором ограничения, равенства или неравенства, которые члены А должны удовлетворить. В домен А из ж называется пространство поиска или набор выбора, а элементы А называются возможные решения или возможные решения.

Функция ж называется по-разному целевая функция, а функция потерь или функция стоимости (минимизация),^[3] а вспомогательная функция или фитнес-функция (максимизация) или, в некоторых областях, функция энергии или энергия функциональный. Возможное решение, которое минимизирует (или максимизирует, если это цель) целевую функцию, называется Оптимальное решение.

В математике обычные задачи оптимизации обычно формулируются в терминах минимизации.

А местный минимум Икс* определяется как элемент, для которого существует δ > 0 такой, что

${ displaystyle forall mathbf {x} in A ; { text {where}} ; left Vert mathbf {x} - mathbf {x} ^ { ast} right Vert leq дельта, ,}$

выражение ж(Икс*) ≤ ж(Икс) держит;

то есть в каком-то регионе вокруг Икс* все значения функции больше или равны значению в этом элементе. Аналогично определяются локальные максимумы.

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

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

Обозначение

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

Минимальное и максимальное значение функции

Рассмотрим следующие обозначения:

${ Displaystyle мин _ {х in mathbb {R}} ; влево (х ^ {2} +1 вправо)}$

Это означает минимум ценность целевой функции Икс² + 1, при выборе Икс из набора действительные числа ℝ. Минимальное значение в этом случае - 1, встречается при х = 0.

Аналогично обозначение

${ Displaystyle макс _ {х в mathbb {R}} ; 2x}$

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

Оптимальные входные аргументы

Рассмотрим следующие обозначения:

${ 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].}$

Это представляет собой значение (или значения) аргумент Икс в интервал (−∞,−1] который минимизирует (или минимизирует) целевую функцию Икс² + 1 (фактическое минимальное значение этой функции - это не то, чего требует проблема). В этом случае ответ будет Икс = −1, поскольку Икс = 0 недопустима, то есть не принадлежит возможный набор.

Так же,

${ 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},}$

представляет {Икс, у} пара (или пары), которая максимизирует (или максимизирует) значение целевой функции Икс потому что у, с добавленным ограничением, которое Икс лежать в интервале [−5,5] (опять же, фактическое максимальное значение выражения не имеет значения). В этом случае решениями являются пары вида {5, 2kπ} и {−5, (2k + 1)π}, где k колеблется во всех целые числа.

Операторы аргумент мин и arg max иногда также пишутся как аргмин и argmax, и стоять за аргумент минимума и аргумент максимума.

История

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

Период, термин "линейное программирование "в некоторых случаях оптимизации было связано с Джордж Б. Данциг, хотя большая часть теории была введена Леонид Канторович в 1939 г. (Программирование в этом контексте не относится к компьютерное программирование, но происходит из-за использования программа вооруженными силами США для обозначения предлагаемого обучения и логистика расписания, которые были проблемами, которые изучал Данциг в то время.) Данциг опубликовал Симплексный алгоритм в 1947 г. и Джон фон Нейман разработал теорию двойственность в том же году.^{[нужна цитата ]}

Другие известные исследователи в области математической оптимизации включают следующее:

Основные подполя

• Выпуклое программирование исследует случай, когда целевая функция выпуклый (минимизация) или вогнутый (максимизация) и набор ограничений выпуклый. Это можно рассматривать как частный случай нелинейного программирования или как обобщение линейного или выпуклого квадратичного программирования.
  • Линейное программирование (LP), разновидность выпуклого программирования, изучает случай, когда целевая функция ж является линейным, а ограничения задаются с использованием только линейных равенств и неравенств. Такой набор ограничений называется многогранник или многогранник если это ограниченный.
  • Программирование конуса второго порядка (SOCP) - это выпуклая программа, включающая определенные типы квадратичных программ.
  • Полуопределенное программирование (SDP) - это подполе выпуклой оптимизации, где базовые переменные полуопределенный матрицы. Это обобщение линейного и выпуклого квадратичного программирования.
  • Коническое программирование является общей формой выпуклого программирования. LP, SOCP и SDP можно рассматривать как конические программы с соответствующим типом конуса.
  • Геометрическое программирование это метод, при котором объективные ограничения и ограничения неравенства выражаются как многочлены и ограничения равенства как мономы можно преобразовать в выпуклую программу.
• Целочисленное программирование изучает линейные программы, в которых некоторые или все переменные вынуждены принимать целое число ценности. Это не выпуклое и в общем случае намного сложнее, чем обычное линейное программирование.
• Квадратичное программирование позволяет целевой функции иметь квадратичные члены, в то время как допустимый набор должен быть задан линейными равенствами и неравенствами. Для конкретных форм квадратичного члена это тип выпуклого программирования.
• Дробное программирование изучает оптимизацию соотношений двух нелинейных функций. Особый класс вогнутых дробных программ можно преобразовать в задачу выпуклой оптимизации.
• Нелинейное программирование изучает общий случай, когда целевая функция или ограничения или и то, и другое содержат нелинейные части. Это может быть или не быть выпуклой программой. В целом, выпуклость программы влияет на сложность ее решения.
• Стохастическое программирование изучает случай, когда некоторые ограничения или параметры зависят от случайные переменные.
• Надежная оптимизация это, как и стохастическое программирование, попытка уловить неопределенность в данных, лежащих в основе проблемы оптимизации. Устойчивая оптимизация направлена ​​на поиск решений, которые действительны при всех возможных реализациях неопределенностей, определенных набором неопределенностей.
• Комбинаторная оптимизация занимается проблемами, в которых набор возможных решений дискретен или может быть сведен к дискретный один.
• Стохастическая оптимизация используется со случайными (зашумленными) измерениями функций или случайными входными данными в процессе поиска.
• Бесконечномерная оптимизация исследует случай, когда множество допустимых решений является подмножеством бесконечногоразмерный пространство, такое как пространство функций.
• Эвристика и метаэвристика делать мало предположений или вообще не делать никаких предположений об оптимизируемой проблеме. Обычно эвристика не гарантирует, что будет найдено какое-либо оптимальное решение. С другой стороны, эвристика используется для поиска приближенных решений многих сложных задач оптимизации.
• Удовлетворение ограничений изучает случай, когда целевая функция ж постоянно (используется в искусственный интеллект, особенно в автоматическое рассуждение ).
  • Ограниченное программирование представляет собой парадигму программирования, в которой отношения между переменными устанавливаются в форме ограничений.
• Дизъюнктивное программирование используется там, где должно выполняться хотя бы одно ограничение, но не все. Это особенно полезно при планировании.
• Картирование космоса представляет собой концепцию моделирования и оптимизации инженерной системы для достижения высокой (точной) точности модели с использованием подходящего физически значимого грубого или суррогатная модель.

В ряде подполей методы предназначены в первую очередь для оптимизации в динамических контекстах (то есть для принятия решений с течением времени):

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

Многоцелевая оптимизация

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

Дизайн считается «оптимальным по Парето» (эквивалентно «эффективным по Парето» или в наборе Парето), если в нем не преобладает какой-либо другой дизайн: если он хуже другого дизайна в некоторых отношениях и не лучше ни в каком отношении, тогда он доминирует и не является оптимальным по Парето.

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

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

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

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

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

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

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

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

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

Многие алгоритмы оптимизации нужно начинать с возможной точки. Один из способов получить такую ​​точку - это Расслабьтесь условия выполнимости с использованием слабая переменная; при достаточном провисе возможна любая отправная точка. Затем минимизируйте эту переменную резерва, пока резерв не станет нулевым или отрицательным.

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

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

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

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

Оптиму задач с ограничениями на равенство можно найти с помощью Множитель Лагранжа метод. Оптимумы проблем с ограничениями равенства и / или неравенства могут быть найдены с помощью 'Условия Каруша – Куна – Таккера. '.

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

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

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

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

В максимальная теорема из Клод Берже (1963) описывает непрерывность оптимального решения как функцию основных параметров.

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

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

Кроме того, критические точки можно классифицировать с помощью определенность из Матрица Гессе: Если гессен положительный определен в критической точке, то точка является локальным минимумом; если матрица Гессе отрицательно определена, то точка является локальным максимумом; наконец, если неопределенное, то дело в каком-то точка перевала.

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

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

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

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

Алгоритмы оптимизации

• Симплексный алгоритм из Джордж Данциг, предназначен для линейное программирование.
• Расширения симплексного алгоритма, предназначенные для квадратичное программирование и для дробно-линейное программирование.
• Варианты симплексного алгоритма, особенно подходящие для оптимизация сети.
• Комбинаторные алгоритмы
• Алгоритмы квантовой оптимизации

Итерационные методы

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

Одним из основных критериев для оптимизаторов является просто количество требуемых вычислений функций, поскольку это часто уже требует больших вычислительных усилий, обычно гораздо больших усилий, чем в самом оптимизаторе, который в основном должен работать с N переменными. Производные предоставляют подробную информацию для таких оптимизаторы, но их еще труднее вычислить, например аппроксимация градиента требует как минимум N + 1 оценок функции. Для приближений 2-х производных (собранных в матрице Гессе) количество вычислений функции находится в порядке N². Для метода Ньютона требуются производные 2-го порядка, поэтому для каждой итерации количество вызовов функций порядка N², но для более простого оптимизатора чистого градиента это только N. Однако оптимизаторам градиента обычно требуется больше итераций, чем алгоритму Ньютона. Какой из них лучше всего с точки зрения количества вызовов функций, зависит от самой проблемы.

• Методы оценки гессенских (или приближенных гессенских) конечные разности ):
  • Метод Ньютона
  • Последовательное квадратичное программирование: Метод на основе Ньютона для малых и средних масштабов сдержанный проблемы. Некоторые версии могут обрабатывать проблемы большого размера.
  • Методы внутренней точки: Это большой класс методов ограниченной оптимизации. Некоторые методы внутренней точки используют только информацию о (под) градиенте, а другие требуют оценки Гессе.
• Методы, которые оценивают градиенты или каким-то образом приближают градиенты (или даже субградиенты):
  • Координатный спуск методы: алгоритмы, которые обновляют одну координату на каждой итерации.
  • Методы сопряженных градиентов: Итерационные методы для больших проблем. (Теоретически эти методы завершаются конечным числом шагов с квадратичными целевыми функциями, но это конечное завершение не наблюдается на практике на компьютерах конечной точности.)
  • Градиентный спуск (альтернативно, «крутой спуск» или «самый крутой подъем»): (медленный) метод, представляющий исторический и теоретический интерес, который возродил интерес к поиску приблизительных решений огромных проблем.
  • Субградиентные методы - Итерационный метод для больших локально Липшицевы функции с помощью обобщенные градиенты. Следуя Борису Т. Поляку, методы проекции субградиента аналогичны методам сопряженных градиентов.
  • Пакетный метод спуска: итерационный метод для задач малого и среднего размера с локально липшицевыми функциями, особенно для выпуклая минимизация проблемы. (Аналогично методам сопряженных градиентов)
  • Эллипсоидный метод: Итерационный метод решения небольших проблем с квазивыпуклый целевые функции и представляют большой теоретический интерес, особенно в установлении полиномиальной временной сложности некоторых задач комбинаторной оптимизации. Он имеет сходство с методами квазиньютона.
  • Метод условного градиента (Франк – Вульф) для приближенной минимизации специально структурированных задач с линейные ограничения, особенно с транспортными сетями. Для общих задач без ограничений этот метод сводится к градиентному методу, который считается устаревшим (почти для всех задач).
  • Квазиньютоновские методы: Итерационные методы для средних и больших задач (например, N <1000).
  • Стохастическая аппроксимация одновременных возмущений (SPSA) метод стохастической оптимизации; использует случайное (эффективное) приближение градиента.
• Методы, которые оценивают только значения функций: если проблема непрерывно дифференцируема, то градиенты могут быть аппроксимированы с использованием конечных разностей, и в этом случае можно использовать метод на основе градиента.
  • Интерполяция методы
  • Поиск по шаблону методы, которые имеют лучшие свойства сходимости, чем Эвристика Нелдера – Мида (с симплексами), который указан ниже.

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

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

Эвристика

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

Приложения

Механика

Проблемы в динамика твердого тела (в частности, динамика сочлененного твердого тела) часто требует методов математического программирования, поскольку вы можете рассматривать динамику твердого тела как попытку решить обыкновенное дифференциальное уравнение на ограничительном многообразии;^[5] ограничения - это различные нелинейные геометрические ограничения, такие как «эти две точки всегда должны совпадать», «эта поверхность не должна пересекать никакую другую» или «эта точка всегда должна лежать где-то на этой кривой». Кроме того, задача вычисления контактных сил может быть решена путем решения задача линейной дополнительности, который также можно рассматривать как задачу QP (квадратичного программирования).

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

Этот подход может быть применен в космологии и астрофизике.^[6]

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

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

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

С 1970-х годов экономисты моделируют динамические решения с течением времени, используя теория управления.^[8] Например, динамический поиск моделей используются для изучения поведение на рынке труда.^[9] Принципиальное различие заключается между детерминированными и стохастическими моделями.^[10] Макроэкономисты строить динамическое стохастическое общее равновесие (DSGE) модели, которые описывают динамику всей экономики как результат взаимозависимых оптимизационных решений работников, потребителей, инвесторов и правительств.^[11][12]

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

Некоторые распространенные применения методов оптимизации в электротехника включают активный фильтр дизайн,^[13] уменьшение паразитного поля в сверхпроводящих магнитных накопителях энергии, космическое отображение дизайн из микроволновая печь конструкции,^[14] телефонные антенны,^[15][16][17] конструкция на основе электромагнетизма. При оптимизации конструкции микроволновых компонентов и антенн, подтвержденной с помощью электромагнитных полей, широко использовались соответствующие физические или эмпирические методы. суррогатная модель и космическое отображение методологии с момента открытия космическое отображение в 1993 г.^[18][19]

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

Оптимизация широко используется в гражданском строительстве. Управление строительством и транспортная техника относятся к основным отраслям гражданского строительства, которые сильно зависят от оптимизации. Наиболее частые проблемы гражданского строительства, которые решаются с помощью оптимизации, - это прокладка и насыпка дорог, анализ жизненного цикла конструкций и инфраструктур,^[20] выравнивание ресурсов,^[21][22] распределение водных ресурсов, движение управление^[23] и оптимизация расписания.

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

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

Техника управления

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

Геофизика

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

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

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

Вычислительная системная биология

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

Машинное обучение

Решатели

Смотрите также

Заметки

дальнейшее чтение

• Бойд, Стивен П.; Ванденберге, Ливен (2004). Выпуклая оптимизация. Кембридж: Издательство Кембриджского университета. ISBN  0-521-83378-7.
• Gill, P.E .; Мюррей, В .; Райт, М. Х. (1982). Практическая оптимизация. Лондон: Academic Press. ISBN  0-12-283952-8.
• Ли, Джон (2004). Первый курс комбинаторной оптимизации. Издательство Кембриджского университета. ISBN  0-521-01012-8.
• Нокедаль, Хорхе; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин: Springer. ISBN  0-387-30303-0.
• Snyman, J. A .; Уилке, Д. Н. (2018). Практическая математическая оптимизация: базовая теория оптимизации и градиентные алгоритмы (2-е изд.). Берлин: Springer. ISBN  978-3-319-77585-2.

внешние ссылки

• «Дерево решений для программного обеспечения для оптимизации». Ссылки на исходные коды оптимизации
• «Глобальная оптимизация».
• "EE364a: выпуклая оптимизация I". Курс Стэнфордского университета.
• Вароко, Гаэль. «Математическая оптимизация: поиск минимумов функций».