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

График z = f ( x , y ) = - ( x ² + y ²) + 4. Глобальный максимум при ( x, y, z ) = (0, 0, 4) обозначен синей точкой. .

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

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

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

Проблемы оптимизации [ править ]

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

Дано: функция F  : → ℝ из некоторого множества А с вещественными числами

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

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

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

${\displaystyle f\left(\mathbf {x} _{0}\right)\geq f\left(\mathbf {x} \right)\Leftrightarrow {\tilde {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} }$

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

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

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

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

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

Локальный минимум х * определяются как элемент , для которого существует некоторое б > 0 такое , что

${\displaystyle \forall \mathbf {x} \in A\;{\text{where}}\;\left\Vert \mathbf {x} -\mathbf {x} ^{\ast }\right\Vert \leq \delta ,\,}$

справедливо выражение f ( x *) ≤ f ( x ) ;

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

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

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

Обозначение [ править ]

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

Минимальное и максимальное значение функции [ править ]

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

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

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

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

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

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

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

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

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

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

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

Это представляет собой значение (или значения) аргумента x в интервале (−∞, −1], который минимизирует (или минимизирует) целевую функцию x ² + 1 (фактическое минимальное значение этой функции - это не то, что требует задача. В этом случае ответ будет x = −1 , поскольку x = 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{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,}$

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

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

История [ править ]

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

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

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

Основные подполя [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

Проблема осуществимости [ править ]

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

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

Существование [ править ]

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

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

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

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

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

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

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

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

Максимальная теорема о Клод Berge (1963) описывает непрерывность оптимального решения в зависимости от параметров , лежащих в основе.

Расчет оптимизации [ править ]

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

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

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

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

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

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

Алгоритмы оптимизации [ править ]

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

Итерационные методы [ править ]

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

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

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

Глобальная конвергенция [ править ]

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

Эвристика [ править ]

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

Приложения [ править ]

Механика [ править ]

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

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

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

Экономика и финансы [ править ]

Экономика достаточно тесно связана с оптимизацией агентов , что влиятельная определение Relatedly описывает Экономику ква науки как «изучение человеческого поведения как отношения между целями и ограниченными средствами» с альтернативным использованием. ^[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.
• Гилл, ЧП; Мюррей, В .; Райт, MH (1982). Практическая оптимизация . Лондон: Academic Press. ISBN 0-12-283952-8.
• Ли, Джон (2004). Первый курс комбинаторной оптимизации . Издательство Кембриджского университета. ISBN 0-521-01012-8.
• Нокедаль, Хорхе ; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин: Springer. ISBN 0-387-30303-0.
• Snyman, JA; Wilke, DN (2018). Практическая математическая оптимизация: основная теория оптимизации и градиентные алгоритмы (2-е изд.). Берлин: Springer. ISBN 978-3-319-77585-2.

Внешние ссылки [ править ]

Викискладе есть медиафайлы, связанные с математической оптимизацией .

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