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

редактировать
«Математическое программирование» перенаправляется сюда. Для рецензируемого журнала см. Математическое программирование. «Оптимизация» и «Оптимальный» редирект сюда. Чтобы узнать о других значениях, см. Оптимизация (значения) и Оптимум (значения). График z = f ( x, y) = - ( x ² + y ²) + 4. Глобальный максимум при ( x, y, z) = (0, 0, 4) обозначен синей точкой.. Минимальный поиск Нелдера-Мида функции Симионеску. Вершины симплекса упорядочены по их значениям, где 1 имеет наименьшее ( наилучшее fx) значение.

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

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

СОДЕРЖАНИЕ

  • 1 Проблемы оптимизации
  • 2 Обозначения
    • 2.1 Минимальное и максимальное значение функции
    • 2.2 Оптимальные входные аргументы
  • 3 История
  • 4 основных подполя
    • 4.1 Многоцелевая оптимизация
    • 4.2 Мультимодальная или глобальная оптимизация
  • 5 Классификация критических точек и экстремумов
    • 5.1 Проблема осуществимости
    • 5.2 Существование
    • 5.3 Необходимые условия оптимальности
    • 5.4 Достаточные условия оптимальности
    • 5.5 Чувствительность и непрерывность оптимумов
    • 5.6 Расчет оптимизации
  • 6 Методы вычислительной оптимизации
    • 6.1 Алгоритмы оптимизации
    • 6.2 Итерационные методы
    • 6.3 Глобальная конвергенция
    • 6.4 Эвристика
  • 7 приложений
    • 7.1 Механика
    • 7.2 Экономика и финансы
    • 7.3 Электротехника
    • 7.4 Гражданское строительство
    • 7.5 Исследование операций
    • 7.6 Техника управления
    • 7.7 Геофизика
    • 7.8 Молекулярное моделирование
    • 7.9 Вычислительная системная биология
    • 7.10 Машинное обучение
  • 8 Решателей
  • 9 См. Также
  • 10 заметок
  • 11 Дальнейшее чтение
  • 12 Внешние ссылки

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

Основная статья: Проблема оптимизации

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

Дано: функция F  : → ℝ из некоторого множества А с вещественными числами
Искал: элемент x 0 ∈ A такой, что f ( x 0) ≤ f ( x) для всех x ∈ A («минимизация») или такой, что f ( x 0) ≥ f ( x) для всех x ∈ A (« максимизация ").

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

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

ж ( Икс 0 ) ж ( Икс ) ж ~ ( Икс 0 ) ж ~ ( Икс ) {\ 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}}

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

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

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

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

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

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

Икс А куда Икс - Икс * δ , {\ displaystyle \ forall \ mathbf {x} \ in A \; {\ text {where}} \; \ left \ Vert \ mathbf {x} - \ mathbf {x} ^ {\ ast} \ right \ Vert \ leq \ дельта, \,}

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

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

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

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

Обозначение

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

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

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

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

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

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

Максимум Икс р 2 Икс {\ Displaystyle \ макс _ {х \ в \ mathbb {R}} \; 2x}

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

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

Основная статья: Arg max

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

а р грамм м я п Икс ( - , - 1 ] Икс 2 + 1 , {\ displaystyle {\ underset {x \ in (- \ infty, -1]} {\ operatorname {arg \, min}}} \; x ^ {2} +1,}

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

а р грамм м я п Икс Икс 2 + 1 , при условии: Икс ( - , - 1 ] . {\ displaystyle {\ underset {x} {\ operatorname {arg \, min}}} \; x ^ {2} +1, \; {\ text {при условии:}} \; x \ in (- \ infty, -1].}

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

Сходным образом,

а р грамм м а Икс Икс [ - 5 , 5 ] , у р Икс потому что у , {\ displaystyle {\ underset {x \ in [-5,5], \; y \ in \ mathbb {R}} {\ operatorname {arg \, max}}} \; x \ cos y,}

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

а р грамм м а Икс Икс , у Икс потому что у , при условии: Икс [ - 5 , 5 ] , у р , {\ displaystyle {\ underset {x, \; y} {\ operatorname {arg \, max}}} \; x \ cos y, \; {\ text {при условии:}} \; 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 году, а Джон фон Нейман разработал теорию двойственности в том же году.

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

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

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

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

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

Основная статья: Многоцелевая оптимизация

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: условия Каруша – Куна – Таккера См. Также: Критическая точка (математика), Дифференциальное исчисление, Градиент, Матрица Гессе, Положительно определенная матрица, Липшицева непрерывность, Теорема Радемахера, Выпуклая функция и Выпуклый анализ.

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

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

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

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

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

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

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

См. Также: Список алгоритмов оптимизации.

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

Основная статья: Итерационный метод Смотрите также: метод Ньютона в оптимизации, метод Quasi-Newton, различие конечного, теория приближений, и численный анализ

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

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

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

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

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

Эвристика

Основная статья: эвристический алгоритм

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

Приложения

Механика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Геофизика

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

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

Основная статья: Молекулярное моделирование

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

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

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

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

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

Основная статья: Машинное обучение § Оптимизация

Решатели

Основная статья: Список программного обеспечения для оптимизации

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

Примечания

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

  • Бойд, Стивен П. ; Ванденберге, Ливен (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.

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

Последняя правка сделана 2024-01-01 11:35:01
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте