Математическая оптимизация
Эта статья нуждается в дополнительных цитатах для проверки . ( февраль 2024 г. ) |
Математическая оптимизация (иначе пишется оптимизация ) или математическое программирование — это выбор лучшего элемента по некоторым критериям из некоторого набора доступных альтернатив. [1] [2] Обычно ее разделяют на два подполя: дискретную оптимизацию и непрерывную оптимизацию . Проблемы оптимизации возникают во всех количественных дисциплинах, от информатики до инженерии. [3] к исследованию операций и экономике , а разработка методов решения представляла интерес для математики на протяжении веков. [4]
В более общем подходе задача оптимизации состоит из максимизации или минимизации путем реальной функции систематического выбора входных значений из разрешенного набора и вычисления значения функции. Обобщение теории и методов оптимизации на другие формулировки составляет обширную область прикладной математики .
Проблемы оптимизации
[ редактировать ]Задачи оптимизации можно разделить на две категории в зависимости от того, ли переменные являются непрерывными или дискретными :
- Задача оптимизации с дискретными переменными известна как дискретная оптимизация , в которой объект , такой как целое число , перестановка или график, должен быть найден из счетного множества .
- Задача с непрерывными переменными известна как непрерывная оптимизация , в которой необходимо найти оптимальные аргументы из непрерывного набора. Они могут включать проблемы с ограничениями и мультимодальные проблемы.
Задачу оптимизации можно представить следующим образом:
- Дано функция → f : A : от некоторого набора A к действительным числам
- Ищется: элемент x0 f ∈ A такой, что f ( x0 ( ) ≤ f ( x ) для всех x ∈ A минимизация») или такой, что ( « x0 ) ≥ f ( x ) для всех x ∈ A («минимизация»). максимизация»).
Такая формулировка называется задачей оптимизации или задачей математического программирования (термин, не связанный напрямую с компьютерным программированием , но все еще используемый, например, в линейном программировании — см. Историю ниже). Многие реальные и теоретические проблемы могут быть смоделированы в этой общей структуре.
Поскольку справедливо следующее
достаточно решить только задачи минимизации. Однако и противоположная точка зрения, рассматривающая только задачи максимизации, также будет верна.
Проблемы, сформулированные с использованием этого метода в области физики, могут называть этот метод энергии минимизацией . [5] значении функции f как представляющей энергию системы моделируемой говоря о . В машинном обучении всегда необходимо непрерывно оценивать качество модели данных с помощью функции стоимости , где минимум подразумевает набор возможно оптимальных параметров с оптимальной (наименьшей) ошибкой.
Обычно A представляет собой некоторое подмножество евклидова пространства. , часто определяемый набором ограничений члены A. , равенств или неравенств, которым должны удовлетворять Область A функции f , а называется пространством поиска или множеством выбора элементы A называются кандидатами или возможными решениями .
Функцию f называют по-разному — целевой функцией , целевой функцией — функцией потерь или функцией затрат (минимизации), [6] функция полезности или функция приспособленности (максимизация) или, в некоторых областях, функция энергии или энергии функционал . Допустимое решение, которое минимизирует (или максимизирует, если это цель) целевую функцию, называется оптимальным решением .
В математике традиционные задачи оптимизации обычно формулируются в терминах минимизации.
Локальный минимум x * определяется как элемент, для которого существует некоторое δ > 0 такое, что
выражение f ( x *) ≤ f ( x ) справедливо;
то есть в некоторой области вокруг x * все значения функции больше или равны значению этого элемента. Аналогично определяются локальные максимумы.
Хотя локальный минимум не хуже любых близлежащих элементов, глобальный минимум не хуже любого возможного элемента.Обычно, если целевая функция не является выпуклой в задаче минимизации, может быть несколько локальных минимумов.В выпуклой задаче , если существует локальный минимум, который является внутренним (не на краю множества допустимых элементов), это также глобальный минимум, но невыпуклая задача может иметь более одного локального минимума, не все из которых требуют быть глобальными минимумами.
Большое количество алгоритмов, предложенных для решения невыпуклых задач, включая большинство коммерчески доступных решателей, не способны различать локально оптимальные решения и глобально оптимальные решения и будут рассматривать первые как фактические решения исходной задачи. Глобальная оптимизация — это раздел прикладной математики и численного анализа , который занимается разработкой детерминированных алгоритмов, способных гарантировать сходимость за конечное время к фактическому оптимальному решению невыпуклой задачи.
Обозначения
[ редактировать ]Задачи оптимизации часто выражаются специальными обозначениями. Вот несколько примеров:
Минимальное и максимальное значение функции
[ редактировать ]Рассмотрим следующие обозначения:
Это обозначает минимальное значение целевой функции x 2 + 1 , при выборе x из набора действительных чисел . Минимальное значение в этом случае равно 1, происходящему при x = 0 .
Аналогично, обозначения
запрашивает максимальное значение целевой функции 2 x , где x может быть любым действительным числом. В этом случае такого максимума не существует, поскольку целевая функция неограничена, поэтому ответ — « бесконечность » или « неопределено ».
Оптимальные входные аргументы
[ редактировать ]Рассмотрим следующие обозначения:
или эквивалентно
Это представляет собой значение (или значения) аргумента x в интервале ( −∞,−1] , которое минимизирует (или минимизирует) целевую функцию x. 2 + 1 (фактическое минимальное значение этой функции не соответствует задаче). В этом случае ответом будет x = −1 , поскольку x = 0 недопустимо, то есть не принадлежит допустимому множеству .
Сходным образом,
или эквивалентно
представляет пару { x , y } (или пары), которая максимизирует (или максимизирует) значение целевой функции x cos y с добавленным ограничением, что x лежит в интервале [−5,5] (опять же, фактический максимум значение выражения не имеет значения). В этом случае решениями являются пары вида {5, 2 k π } и {−5, (2 k + 1) π } , где k пробегает все целые числа .
Операторы arg min и arg max иногда также записываются как argmin и argmax и обозначают аргумент минимума и аргумент максимума .
История
[ редактировать ]Ферма и Лагранж нашли формулы для определения оптимума, основанные на исчислении, а Ньютон и Гаусс предложили итерационные методы движения к оптимуму.
Термин « линейное программирование » для некоторых случаев оптимизации был предложен Джорджем Б. Данцигом , хотя большая часть теории была введена Леонидом Канторовичем в 1939 году. ( Программирование в этом контексте не относится к компьютерному программированию , а происходит от использования программа для вооруженных сил США ссылки на предлагаемые графики обучения и материально-технического обеспечения , которые были проблемами, которые Данциг изучал в то время.) Данциг опубликовал симплексный алгоритм в 1947 году, а также Джон фон Нейман и другие исследователи работали над теоретическими аспектами линейного программирования. (как и теория дуальности ) примерно в то же время. [7]
Среди других известных исследователей математической оптимизации можно назвать следующих:
- Ричард Беллман
- Дмитрий Берцекас
- Майкл Бьерлер
- Стивен П. Бойд
- Роджер Флетчер
- Мартин Гретшель
- Рональд А. Ховард
- Фриц Джон
- Нарендра Кармаркар
- Уильям Каруш
- Леонид Хачиян
- Бернард Купман
- Гарольд Кун
- Ласло Ловаш
- Дэвид Люенбергер
- Аркадий Немировский
- Yurii Nesterov
- Лев Понтрягин
- Р. Тиррел Рокафеллар
- Наум З. Шор
- Альберт Такер
Основные подполя
[ редактировать ]- Выпуклое программирование изучает случай, когда целевая функция выпуклая (минимизация) или вогнутая (максимизация), а набор ограничений выпуклый . Это можно рассматривать как частный случай нелинейного программирования или как обобщение линейного или выпуклого квадратичного программирования.
- Линейное программирование (ЛП), разновидность выпуклого программирования, изучает случай, когда целевая функция f является линейной, а ограничения задаются с использованием только линейных равенств и неравенств. Такое множество ограничений называется многогранником или многогранником, если оно ограничено .
- Конусное программирование второго порядка (SOCP) представляет собой выпуклую программу и включает в себя определенные типы квадратичных программ.
- Полуопределенное программирование (SDP) — это область выпуклой оптимизации, в которой базовыми переменными являются полуопределенные матрицы . Это обобщение линейного и выпуклого квадратичного программирования.
- Коническое программирование — это общая форма выпуклого программирования. LP, SOCP и SDP можно рассматривать как конические программы с соответствующим типом конуса.
- Геометрическое программирование — это метод, с помощью которого объективные ограничения и ограничения-неравенства, выраженные в виде полиномов , а ограничения равенства в виде мономов, могут быть преобразованы в выпуклую программу.
- Целочисленное программирование изучает линейные программы, в которых некоторые или все переменные вынуждены принимать целочисленные значения. Это не выпукло и вообще гораздо сложнее, чем обычное линейное программирование.
- Квадратичное программирование позволяет целевой функции иметь квадратичные члены, в то время как допустимый набор должен быть задан с помощью линейных равенств и неравенств. Для конкретных форм квадратичного члена это разновидность выпуклого программирования.
- Дробное программирование изучает оптимизацию отношений двух нелинейных функций. Специальный класс вогнутых дробных программ можно преобразовать в задачу выпуклой оптимизации.
- Нелинейное программирование изучает общий случай, когда целевая функция или ограничения или и то, и другое содержат нелинейные части. Это может быть или не быть выпуклой программой. В общем, то, является ли программа выпуклой, влияет на сложность ее решения.
- Стохастическое программирование изучает случай, когда некоторые ограничения или параметры зависят от случайных величин .
- Надежная оптимизация , как и стохастическое программирование, представляет собой попытку уловить неопределенность в данных, лежащих в основе задачи оптимизации. Робастная оптимизация направлена на поиск решений, которые действительны при всех возможных реализациях неопределенностей, определяемых набором неопределенностей.
- Комбинаторная оптимизация занимается задачами, в которых множество допустимых решений дискретно или может быть сведено к дискретному .
- Стохастическая оптимизация используется при измерениях случайных (зашумленных) функций или случайных входных данных в процессе поиска.
- Бесконечномерная оптимизация изучает случай, когда множество возможных решений является подмножеством бесконечномерного пространства , например пространства функций.
- Эвристика и метаэвристика практически не делают предположений относительно оптимизируемой задачи. Обычно эвристика не гарантирует, что необходимо найти какое-либо оптимальное решение. С другой стороны, эвристики используются для поиска приближенных решений многих сложных задач оптимизации.
- Удовлетворение ограничений изучает случай, когда целевая функция f является постоянной (это используется в искусственном интеллекте , особенно в автоматизированных рассуждениях ).
- Программирование с ограничениями — это парадигма программирования, в которой отношения между переменными задаются в форме ограничений.
- Дизъюнктивное программирование используется там, где должно быть удовлетворено хотя бы одно ограничение, но не все. Это особенно полезно при планировании.
- Картирование пространства — это концепция моделирования и оптимизации инженерной системы с высокой (точной) точностью модели с использованием подходящей физически значимой грубой или суррогатной модели .
В ряде подполей методы предназначены в первую очередь для оптимизации в динамических контекстах (то есть принятия решений с течением времени):
- Вариационное исчисление — это раздел бесконечномерной оптимизации, связанный с поиском наилучшего способа достижения некоторой цели, например, поиском поверхности, границей которой является определенная кривая, но с наименьшей возможной площадью.
- Теория оптимального управления представляет собой обобщение вариационного исчисления, которое вводит политику управления.
- Динамическое программирование — это подход к решению задачи стохастической оптимизации со стохастическими, случайными и неизвестными параметрами модели. Он изучает случай, когда стратегия оптимизации основана на разбиении проблемы на более мелкие подзадачи. Уравнение, описывающее связь между этими подзадачами, называется уравнением Беллмана .
- Математическое программирование с равновесными ограничениями – это случаи, когда ограничения включают вариационные неравенства или дополнительности .
Многокритериальная оптимизация
[ редактировать ]Добавление более чем одной цели к задаче оптимизации усложняет задачу. Например, чтобы оптимизировать конструкцию конструкции, желательно, чтобы конструкция была одновременно легкой и жесткой. Когда две цели конфликтуют, необходимо найти компромисс. Может быть одна самая легкая конструкция, одна самая жесткая конструкция и бесконечное количество конструкций, которые представляют собой некоторый компромисс по весу и жесткости. Набор компромиссных планов, которые улучшают один критерий за счет другого, известен как набор Парето . Кривая, отображающая вес и жесткость лучших конструкций, известна как граница Парето .
План считается «оптимальным по Парето» (что эквивалентно «эффективному по Парето» или множеству Парето), если в нем не доминирует какой-либо другой план: если он хуже другого плана в некоторых отношениях и не лучше ни в каком отношении, тогда оно доминируется и не является оптимальным по Парето.
Выбор среди «оптимальных по Парето» решений для определения «предпочтительного решения» делегируется лицу, принимающему решение. Другими словами, определение проблемы как многокритериальной оптимизации сигнализирует о том, что некоторая информация отсутствует: желаемые цели заданы, но их комбинации не оцениваются относительно друг друга. В некоторых случаях недостающую информацию можно получить в ходе интерактивных сеансов с лицом, принимающим решения.
Задачи многокритериальной оптимизации были далее обобщены до задач векторной оптимизации , где (частичный) порядок больше не задается упорядочением Парето.
Мультимодальная или глобальная оптимизация
[ редактировать ]Проблемы оптимизации часто носят многомодальный характер; то есть у них есть несколько хороших решений. Все они могут быть глобально хорошими (с одинаковым значением функции затрат) или же может существовать сочетание хороших на глобальном уровне и локальных решений. Получение всех (или хотя бы некоторых из) множественных решений является целью мультимодального оптимизатора.
Классические методы оптимизации из-за их итеративного подхода не работают удовлетворительно, когда они используются для получения нескольких решений, поскольку не гарантируется, что разные решения будут получены даже с разными начальными точками при нескольких запусках алгоритма.
Общие подходы к задачам глобальной оптимизации , где могут присутствовать множественные локальные экстремумы, включают эволюционные алгоритмы , байесовскую оптимизацию и имитацию отжига .
Классификация критических точек и экстремумов
[ редактировать ]Проблема осуществимости
[ редактировать ]Проблема выполнимости , также называемая проблемой осуществимости , — это просто проблема поиска любого возможного решения вообще безотносительно к объективной ценности. Это можно рассматривать как особый случай математической оптимизации, когда целевое значение одинаково для каждого решения, и, следовательно, любое решение является оптимальным.
Многие алгоритмы оптимизации должны начинаться с осуществимой точки. Один из способов получить такую точку — ослабить условия осуществимости, используя слабую переменную ; при достаточном слабине возможна любая отправная точка. Затем минимизируйте эту резервную переменную до тех пор, пока резерв не станет нулевым или отрицательным.
Существование
[ редактировать ]Теорема о крайних значениях Карла Вейерштрасса гласит, что непрерывная вещественная функция на компакте достигает своего максимального и минимального значения. В более общем смысле, полунепрерывная снизу функция на компакте достигает минимума; полунепрерывная сверху функция на компакте достигает точки максимума или вида.
Необходимые условия оптимальности
[ редактировать ]Одна из теорем Ферма утверждает, что оптимум задач без ограничений находится в стационарных точках , где первая производная или градиент целевой функции равна нулю (см. тест первой производной ). В более общем смысле их можно найти в критических точках , где первая производная или градиент целевой функции равна нулю или не определена, или на границе множества выбора. Уравнение (или набор уравнений), утверждающее, что первая производная(-и) равна(-ют) нулю при внутреннем оптимуме, называется «условием первого порядка» или набором условий первого порядка.
Оптимумы задач с ограничениями равенства можно найти с помощью метода множителей Лагранжа . Оптимум задач с ограничениями равенства и/или неравенства можно найти с помощью « условий Каруша – Куна – Такера ».
Достаточные условия оптимальности
[ редактировать ]Хотя первый тест производной выявляет точки, которые могут быть экстремумами, этот тест не отличает точку, которая является минимумом, от точки, которая является максимумом, или от точки, которая не является ни тем, ни другим. Когда целевая функция дважды дифференцируема, эти случаи можно отличить, проверив вторую производную или матрицу вторых производных (называемую матрицей Гессе ) в задачах без ограничений, или матрицу вторых производных целевой функции и ограничений, называемых граничной Гессен в ограниченных задачах. Условия, которые отличают максимумы или минимумы от других стационарных точек, называются «условиями второго порядка» (см. « Тест второй производной »). Если решение-кандидат удовлетворяет условиям первого порядка, то удовлетворения условий второго порядка достаточно для установления хотя бы локальной оптимальности.
Чувствительность и непрерывность оптимума
[ редактировать ]Теорема о конверте описывает, как изменяется значение оптимального решения при изменении основного параметра . Процесс вычисления этого изменения называется сравнительной статикой .
Максимальная теорема Клода Бержа (1963) описывает непрерывность оптимального решения как функцию основных параметров.
Расчет оптимизации
[ редактировать ]Для задач без ограничений с дважды дифференцируемыми функциями некоторые критические точки можно найти, найдя точки, в которых градиент целевой функции равен нулю (то есть стационарные точки). В более общем смысле, нулевой субградиент подтверждает, что локальный минимум был найден для задач минимизации с выпуклыми функциями и другими локально липшицевыми функциями , которые встречаются при минимизации функции потерь нейронной сети. Положительно-отрицательная оценка импульса позволяет избежать локального минимума и сходится к глобальному минимуму целевой функции. [8]
Кроме того, критические точки можно классифицировать, используя определенность матрицы Гессе : если гессиан положительно определен в критической точке, то эта точка является локальным минимумом; если матрица Гессе отрицательно определена, то точка является локальным максимумом; наконец, если неопределенно, то точка является своего рода седловой точкой .
Задачи с ограничениями часто можно преобразовать в задачи без ограничений с помощью множителей Лагранжа . Лагранжева релаксация также может обеспечить приближенные решения сложных задач с ограничениями.
Если целевая функция является выпуклой функцией , то любой локальный минимум также будет глобальным минимумом. Существуют эффективные численные методы минимизации выпуклых функций, такие как методы внутренней точки .
Глобальная конвергенция
[ редактировать ]В более общем смысле, если целевая функция не является квадратичной функцией, то многие методы оптимизации используют другие методы, чтобы гарантировать, что некоторая подпоследовательность итераций сходится к оптимальному решению. Первый и до сих пор популярный метод обеспечения сходимости основан на поиске строк , который оптимизирует функцию по одному измерению. Второй и все более популярный метод обеспечения конвергенции использует доверительные регионы . используются как строковые поиски, так и доверительные области В современных методах недифференцируемой оптимизации . Обычно глобальный оптимизатор работает намного медленнее, чем продвинутые локальные оптимизаторы (такие как BFGS ), поэтому часто эффективный глобальный оптимизатор можно создать, запуская локальный оптимизатор из разных стартовых точек.
Методы вычислительной оптимизации
[ редактировать ]Для решения проблем исследователи могут использовать алгоритмы , завершающиеся за конечное число шагов, или итерационные методы , которые сходятся к решению (по некоторому заданному классу проблем), или эвристики , которые могут обеспечить приближенные решения некоторых проблем (хотя их итерации не обязательно сходятся).
Алгоритмы оптимизации
[ редактировать ]- Симплексный алгоритм Джорджа Данцига , предназначенный для линейного программирования.
- Расширения симплексного алгоритма, предназначенные для квадратичного программирования и дробно-линейного программирования.
- Варианты симплексного алгоритма, особенно подходящие для оптимизации сети.
- Комбинаторные алгоритмы
- Алгоритмы квантовой оптимизации
Итерационные методы
[ редактировать ]Итеративные методы, используемые для решения задач нелинейного программирования, различаются в зависимости от того, оценивают ли они гессиан , градиенты или только значения функций. Хотя оценка гессиана (H) и градиентов (G) повышает скорость сходимости, для функций, для которых эти величины существуют и изменяются достаточно плавно, такие оценки увеличивают вычислительную сложность (или вычислительные затраты) каждой итерации. В некоторых случаях вычислительная сложность может быть чрезмерно высокой.
Одним из основных критериев для оптимизаторов является количество требуемых вычислений функции, поскольку это часто уже требует больших вычислительных усилий, обычно гораздо больших, чем внутри самого оптимизатора, которому в основном приходится работать с N переменными. Производные предоставляют подробную информацию для таких оптимизаторов, но их еще сложнее вычислить, например, аппроксимация градиента требует как минимум N+1 оценок функции. Для аппроксимации 2-х производных (собранных в матрице Гессе) количество оценок функции имеет порядок N². Метод Ньютона требует производных 2-го порядка, поэтому для каждой итерации количество вызовов функций имеет порядок N², но для более простого оптимизатора чистого градиента это только N. Однако оптимизаторам градиента обычно требуется больше итераций, чем алгоритму Ньютона. Какой из них лучше по количеству вызовов функций, зависит от самой задачи.
- Методы оценки гессианов (или аппроксимации гессианов с использованием конечных разностей ):
- метод Ньютона
- Последовательное квадратичное программирование : метод Ньютона для решения задач с ограничениями малого и среднего масштаба . Некоторые версии могут решать задачи большого размера.
- Методы внутренней точки : это большой класс методов ограниченной оптимизации, некоторые из которых используют только информацию о (суб)градиенте, а другие требуют оценки гессианов.
- Методы, которые оценивают градиенты или каким-то образом аппроксимируют градиенты (или даже субградиенты):
- Методы координатного спуска : алгоритмы, которые обновляют одну координату на каждой итерации.
- Методы сопряженных градиентов : итерационные методы для решения больших задач. (Теоретически эти методы завершаются за конечное число шагов с квадратичными целевыми функциями, но это конечное завершение не наблюдается на практике на компьютерах конечной точности.)
- Градиентный спуск (альтернативно «крутейший спуск» или «крутейший подъем»): (медленный) метод, представляющий исторический и теоретический интерес, который возобновил интерес к поиску приблизительных решений огромных проблем.
- Субградиентные методы : итерационный метод для больших локально липшицевых функций с использованием обобщенных градиентов . Согласно Борису Т. Поляку, методы субградиентной проекции аналогичны методам сопряженных градиентов.
- Метод спуска пучка: итерационный метод для задач малого и среднего размера с локально липшицевыми функциями, особенно для задач выпуклой минимизации (аналогично методам сопряженных градиентов).
- Метод эллипсоида : итерационный метод для решения небольших задач с квазивыпуклыми целевыми функциями, представляющий большой теоретический интерес, особенно при установлении полиномиальной временной сложности некоторых задач комбинаторной оптимизации. Он имеет сходство с методами квазиньютона.
- Метод условного градиента (Франка – Вольфа) для приближенной минимизации специально структурированных задач с линейными ограничениями , особенно в транспортных сетях. Для общих задач без ограничений этот метод сводится к градиентному методу, который считается устаревшим (почти для всех задач).
- Квазиньютоновские методы : итерационные методы для задач среднего и большого размера (например, N<1000).
- Метод стохастической аппроксимации одновременных возмущений (SPSA) для стохастической оптимизации; использует случайное (эффективное) градиентное приближение.
- Методы, которые оценивают только значения функций: если задача непрерывно дифференцируема, то градиенты можно аппроксимировать с использованием конечных разностей, и в этом случае можно использовать метод на основе градиента.
- интерполяции Методы
- Методы поиска по шаблону , которые имеют лучшие свойства сходимости, чем эвристика Нелдера-Мида (с симплексами) , которая указана ниже.
- Зеркальный спуск
Эвристика
[ редактировать ]Помимо (конечно завершающихся) алгоритмов и (сходящихся) итерационных методов , существуют эвристики . Эвристика — это любой алгоритм, который не гарантирует (математически) нахождения решения, но который, тем не менее, полезен в определенных практических ситуациях. Список некоторых известных эвристик:
- Дифференциальная эволюция
- Динамическая релаксация
- Эволюционные алгоритмы
- Генетические алгоритмы
- Подъем в гору со случайным перезапуском
- Меметический алгоритм
- Симплициальная эвристика Нелдера – Мида : популярная эвристика для приблизительной минимизации (без вызова градиентов).
- Оптимизация роя частиц
- Имитация отжига
- Стохастическое туннелирование
- Табу-поиск
Приложения
[ редактировать ]Механика
[ редактировать ]Проблемы динамики твердого тела (в частности, динамики шарнирно-сочлененного твердого тела) часто требуют методов математического программирования, поскольку вы можете рассматривать динамику твердого тела как попытку решить обыкновенное дифференциальное уравнение на многообразии ограничений; [9] ограничения представляют собой различные нелинейные геометрические ограничения, такие как «эти две точки всегда должны совпадать», «эта поверхность не должна пересекать любую другую» или «эта точка всегда должна лежать где-то на этой кривой». Кроме того, задачу вычисления контактных сил можно решить путем решения линейной задачи дополнительности , которую также можно рассматривать как задачу QP (квадратичного программирования).
Многие проблемы проектирования также можно выразить в виде программ оптимизации. Это приложение называется оптимизацией дизайна. Одним из подмножеств является инженерная оптимизация , а другим недавним и растущим подвидом этой области является междисциплинарная оптимизация проектирования , которая, хотя и полезна во многих проблемах, в частности применяется к проблемам аэрокосмической техники .
Этот подход может быть применен в космологии и астрофизике. [10]
Экономика и финансы
[ редактировать ]Экономика настолько тесно связана с оптимизацией агентов , что влиятельное определение описывает экономику как науку как «изучение человеческого поведения как взаимосвязи между целями и ограниченными средствами» с альтернативными видами использования. [11] Современная теория оптимизации включает в себя традиционную теорию оптимизации, но также пересекается с теорией игр и изучением экономического равновесия . журнала экономической литературы Коды классифицируют математическое программирование, методы оптимизации и связанные темы под JEL:C61-C63 .
В микроэкономике проблема максимизации полезности и ее двойная проблема — проблема минимизации расходов — являются задачами экономической оптимизации. Предполагается, что, поскольку они ведут себя последовательно, потребители максимизируют свою полезность , в то время как фирмы обычно максимизируют свою прибыль . Кроме того, агенты часто моделируются как не склонные к риску , тем самым предпочитающие избегать риска. Цены на активы также моделируются с использованием теории оптимизации, хотя лежащая в основе математика основана на оптимизации случайных процессов , а не на статической оптимизации. Теория международной торговли также использует оптимизацию для объяснения моделей торговли между странами. Оптимизация портфелей является примером многоцелевой оптимизации в экономике.
С 1970-х годов экономисты моделировали динамические решения с течением времени, используя теорию управления . [12] Например, модели динамического поиска используются для изучения поведения на рынке труда . [13] Принципиальное различие существует между детерминистическими и стохастическими моделями. [14] Макроэкономисты строят модели динамического стохастического общего равновесия (DSGE) , которые описывают динамику всей экономики как результат взаимозависимых оптимизирующих решений работников, потребителей, инвесторов и правительств. [15] . [16] [17]
Электротехника
[ редактировать ]Некоторые распространенные применения методов оптимизации в электротехнике включают разработку активных фильтров , [18] уменьшение поля рассеяния в сверхпроводящих магнитных системах хранения энергии, пространственное картографирование микроволновых структур , [19] телефонные антенны, [20] [21] [22] конструкция, основанная на электромагнетизме. в 1993 году в оптимизации конструкции микроволновых компонентов и антенн, подтвержденной электромагнитным воздействием, широко использовались соответствующие физические или эмпирические суррогатные модели и методологии космического картографирования С момента открытия космического картографирования . [23] [24] Методы оптимизации также используются при анализе потоков мощности . [25]
Гражданское строительство
[ редактировать ]Оптимизация широко используется в гражданском строительстве. Управление строительством и транспортное проектирование являются одними из основных отраслей гражданского строительства, которые в значительной степени полагаются на оптимизацию. Наиболее распространенными проблемами гражданского строительства, которые решаются с помощью оптимизации, являются прорезка и засыпка дорог, анализ жизненного цикла конструкций и инфраструктуры, [26] выравнивание ресурсов , [27] [28] распределение водных ресурсов , дорожным движением управление [29] и оптимизация расписания.
Исследование операций
[ редактировать ]Другая область, в которой широко используются методы оптимизации, — это исследование операций . [30] В исследованиях операций также используется стохастическое моделирование и симуляция для поддержки более эффективного принятия решений. В исследованиях операций все чаще используется стохастическое программирование для моделирования динамических решений, адаптирующихся к событиям; такие проблемы можно решить с помощью методов крупномасштабной оптимизации и стохастической оптимизации .
Техника управления
[ редактировать ]Математическая оптимизация используется во многих современных конструкциях контроллеров. Контроллеры высокого уровня, такие как управление с прогнозированием модели (MPC) или оптимизация в реальном времени (RTO), используют математическую оптимизацию. Эти алгоритмы работают в режиме онлайн и неоднократно определяют значения переменных решения, таких как открытия дросселей на технологической установке, путем итеративного решения задачи математической оптимизации, включая ограничения и модель управляемой системы.
Геофизика
[ редактировать ]Методы оптимизации регулярно используются в задачах оценки геофизических параметров. Учитывая набор геофизических измерений, например сейсмических записей , обычно приходится определять физические свойства и геометрические формы подстилающих пород и жидкостей. Большинство задач геофизики нелинейны, при этом широко используются как детерминированные, так и стохастические методы.
Молекулярное моделирование
[ редактировать ]Методы нелинейной оптимизации широко используются в конформационном анализе .
Вычислительная системная биология
[ редактировать ]Методы оптимизации используются во многих аспектах вычислительной системной биологии, таких как построение моделей, оптимальный план эксперимента, метаболическая инженерия и синтетическая биология. [31] Линейное программирование было применено для расчета максимально возможных выходов продуктов ферментации. [31] и сделать вывод о сетях регуляции генов на основе нескольких наборов данных микрочипов. [32] а также сети регуляции транскрипции на основе данных с высокой пропускной способностью. [33] Нелинейное программирование использовалось для анализа энергетического метаболизма. [34] и применялся для метаболической инженерии и оценки параметров биохимических путей. [35]
Машинное обучение
[ редактировать ]Решатели
[ редактировать ]См. также
[ редактировать ]- Кривая брахистохроны
- Подгонка кривой
- Детерминированная глобальная оптимизация
- Целевое программирование
- Важные публикации по оптимизации
- Наименьшие квадраты
- Общество математической оптимизации (ранее Общество математического программирования)
- Алгоритмы математической оптимизации
- Программное обеспечение для математической оптимизации
- Оптимизация процесса
- Оптимизация на основе моделирования
- Тестовые функции для оптимизации
- Вариационное исчисление
- Проблема с маршрутом автомобиля
Примечания
[ редактировать ]- ^ « Природа математического программирования. Архивировано 5 марта 2014 г. в Wayback Machine », Глоссарий математического программирования , INFORMS Computing Society.
- ^ «Математическое программирование: обзор» (PDF) . Проверено 26 апреля 2024 г.
- ^ Мартинс, Хоаким РРА; Нин, Эндрю (01 октября 2021 г.). Оптимизация инженерного проектирования . Издательство Кембриджского университета. ISBN 978-1108833417 .
- ^ Ду, ДЗ; Пардалос, премьер-министр; Ву, В. (2008). «История оптимизации». Во Флудасе, К .; Пардалос, П. (ред.). Энциклопедия оптимизации . Бостон: Спрингер. стр. 1538–1542.
- ^ Хартманн, Александр К; Ригер, Хайко (2002). Алгоритмы оптимизации в физике . Гражданин.
- ^ В. Эрвин Диверт (2008). «Функции стоимости», Новый экономический словарь Пэлгрейва 2-го издания , содержание .
- ^ Биксби, Роберт Э (2012). «Краткая история вычислений в линейном и смешанно-целочисленном программировании» (PDF) . Документа Математика . 2012 : 107–121.
- ^ Абдулкадиров Р.; Ляхов П.; Бергерман, М.; Резников Д. (февраль 2024 г.). «Распознавание спутниковых изображений с использованием ансамблевых нейронных сетей и разностного градиента положительного и отрицательного импульса» . Хаос, солитоны и фракталы . 179 : 114432. doi : 10.1016/j.chaos.2023.114432 .
- ^ Верещагин, А.Ф. (1989). «Моделирование и управление движением манипуляционных роботов». Советский журнал компьютерных и системных наук . 27 (5): 29–38.
- ^ Хаггаг, С.; Десоки, Ф.; Рамадан, М. (2017). «Космологическая инфляционная модель с использованием оптимального управления». Гравитация и космология . 23 (3): 236–239. Бибкод : 2017GrCo...23..236H . дои : 10.1134/S0202289317030069 . ISSN 1995-0721 . S2CID 125980981 .
- ^ Лайонел Роббинс (1935, 2-е изд.) Очерк о природе и значении экономической науки , Macmillan, p. 16.
- ^ Дорфман, Роберт (1969). «Экономическая интерпретация теории оптимального управления». Американский экономический обзор . 59 (5): 817–831. JSTOR 1810679 .
- ^ Сарджент, Томас Дж. (1987). "Поиск" . Динамическая макроэкономическая теория . Издательство Гарвардского университета. стр. 57–91. ISBN 9780674043084 .
- ^ А.Г. Маллиарис (2008). «Стохастическое оптимальное управление», Новый экономический словарь Пэлгрейва , 2-е издание. Аннотация. Архивировано 18 октября 2017 г. в Wayback Machine .
- ^ Чавес Маса, Мануэль; Федриани, Эухенио М.; Ордас Санс, Хосе Антонио (01 июля 2018 г.). «Соответствующие факторы для оптимизации государственных услуг по поддержке предпринимателей и выживаемости компаний» . Инновации . 28 (69): 9–24. дои : 10.15446/innovar.v28n69.71693 . ISSN 2248-6968 .
- ^ Ротемберг, Хулио ; Вудфорд, Майкл (1997). «Эконометрическая основа оценки денежно-кредитной политики на основе оптимизации» (PDF) . Ежегодник макроэкономики NBER . 12 : 297–346. дои : 10.2307/3585236 . JSTOR 3585236 .
- ^ Из Нового экономического словаря Palgrave (2008), 2-е издание с реферативными ссылками:
• « Методы численной оптимизации в экономике » Карла Шмеддерса.
• « Выпуклое программирование » Лоуренса Э. Блюма.
• « Модель общего равновесия Эрроу-Дебре » Джона Геанакоплоса . - ^ Де, Бишну Прасад; Кар, Р.; Мандал, Д.; Гошал, СП (27 сентября 2014 г.). «Оптимальный выбор стоимости компонентов для конструкции аналогового активного фильтра с использованием симплексной оптимизации роя частиц». Международный журнал машинного обучения и кибернетики . 6 (4): 621–636. дои : 10.1007/s13042-014-0299-0 . ISSN 1868-8071 . S2CID 13071135 .
- ^ Козел, Славомир; Бэндлер, Джон В. (январь 2008 г.). «Картирование пространства с использованием нескольких грубых моделей для оптимизации микроволновых компонентов». Письма IEEE о микроволновых и беспроводных компонентах . 18 (1): 1–3. CiteSeerX 10.1.1.147.5407 . дои : 10.1109/LMWC.2007.911969 . S2CID 11086218 .
- ^ Ту, Шэн; Ченг, Цинша С.; Чжан, Ифань; Бэндлер, Джон В.; Николова, Наталья К. (июль 2013 г.). «Оптимизация пространственного картографирования антенн мобильных телефонов с использованием моделей тонких проводов» . Транзакции IEEE по антеннам и распространению . 61 (7): 3797–3807. Бибкод : 2013ITAP...61.3797T . дои : 10.1109/TAP.2013.2254695 .
- ^ Н. Фридрих, «Пространственное картографирование опережает электромагнитную оптимизацию при проектировании мобильных антенн», Micros&rf, 30 августа 2013 г.
- ^ Сервантес-Гонсалес, Хуан К.; Райас-Санчес, Хосе Э.; Лопес, Карлос А.; Камачо-Перес, Хосе Р.; Брито-Брито, Забдиэль; Чавес-Уртадо, Хосе Л. (февраль 2016 г.). «Оптимизация пространственного картографирования антенн мобильных телефонов с учетом электромагнитного воздействия компонентов мобильного телефона и человеческого тела» . Международный журнал компьютерной техники ВЧ и СВЧ . 26 (2): 121–128. doi : 10.1002/mmce.20945 . S2CID 110195165 .
- ^ Бэндлер, JW; Бернацкий, Р.М.; Чен, Шао Хуа; Гробельный, Пенсильвания; Хеммерс, Р.Х. (1994). «Техника космического картографирования для электромагнитной оптимизации». Транзакции IEEE по теории и технике микроволнового излучения . 42 (12): 2536–2544. Бибкод : 1994ITMTT..42.2536B . дои : 10.1109/22.339794 .
- ^ Бэндлер, JW; Бернацкий, Р.М.; Шао Хуа Чен; Хеммерс, Р.Х.; Мэдсен, К. (1995). «Электромагнитная оптимизация с использованием агрессивного космического картографирования». Транзакции IEEE по теории и технике микроволнового излучения . 43 (12): 2874–2882. Бибкод : 1995ITMTT..43.2874B . дои : 10.1109/22.475649 .
- ^ Выпуклая релаксация оптимального потока мощности: Учебное пособие . Симпозиум iREP 2013 по динамике и управлению энергосистемой. дои : 10.1109/IREP.2013.6629391 .
- ^ Пирионеси, Сайед Мадех; Таваколан, Мехди (9 января 2017 г.). «Модель математического программирования для решения задач оптимизации затрат и безопасности (CSO) при обслуживании сооружений». Журнал гражданского строительства KSCE . 21 (6): 2226–2234. дои : 10.1007/s12205-017-0531-z . S2CID 113616284 .
- ^ Хегази, Тарек (июнь 1999 г.). «Оптимизация распределения и выравнивания ресурсов с использованием генетических алгоритмов». Журнал строительной техники и менеджмента . 125 (3): 167–175. дои : 10.1061/(ASCE)0733-9364(1999)125:3(167) .
- ^ Пирионеси, С. Маде; Нассери, Мехран; Рамезани, Абдолла (9 июля 2018 г.). «Пиронези С.М., Нассери М. и Рамезани А. (2018). Выравнивание ресурсов в строительных проектах с разделением деятельности и ограничениями ресурсов: оптимизация моделирования отжига». Канадский журнал гражданского строительства . 46 : 81–86. doi : 10.1139/cjce-2017-0670 . hdl : 1807/93364 . S2CID 116480238 .
- ^ Херти, М.; Клар, А. (1 января 2003 г.). «Моделирование, моделирование и оптимизация сетей транспортных потоков» . Журнал SIAM по научным вычислениям . 25 (3): 1066–1087. Бибкод : 2003SJSC...25.1066H . дои : 10.1137/S106482750241459X . ISSN 1064-8275 .
- ^ «Новая сила на политической сцене: Сеофонистен» . Архивировано из оригинала 18 декабря 2014 года . Проверено 14 сентября 2013 г.
- ^ Перейти обратно: а б Папуцакис, Элефтериос Терри (февраль 1984 г.). «Уравнения и расчеты ферментации маслянокислых бактерий». Биотехнология и биоинженерия . 26 (2): 174–187. дои : 10.1002/бит.260260210 . ISSN 0006-3592 . ПМИД 18551704 . S2CID 25023799 .
- ^ Ван, Юн; Джоши, Трупти; Чжан, Сян-Сунь; Сюй, Донг; Чен, Луонань (24 июля 2006 г.). «Вывод о сетях регуляции генов на основе нескольких наборов данных микрочипов». Биоинформатика . 22 (19): 2413–2420. doi : 10.1093/биоинформатика/btl396 . ISSN 1460-2059 . ПМИД 16864593 .
- ^ Ван, Жуй-Шэн; Ван, Юн; Чжан, Сян-Сунь; Чен, Луонань (22 сентября 2007 г.). «Вывод о сетях регуляции транскрипции на основе данных высокой пропускной способности» . Биоинформатика . 23 (22): 3056–3064. doi : 10.1093/биоинформатика/btm465 . ISSN 1460-2059 . ПМИД 17890736 .
- ^ Во, Туи Д.; Пол Ли, Западная Нью; Палссон, Бернхард О. (май 2007 г.). «Системный анализ энергетического метаболизма выявляет пораженный комплекс дыхательной цепи при синдроме Ли». Молекулярная генетика и обмен веществ . 91 (1): 15–22. дои : 10.1016/j.ymgme.2007.01.012 . ISSN 1096-7192 . ПМИД 17336115 .
- ^ Мендес, П .; Келл, Д. (1998). «Нелинейная оптимизация биохимических путей: приложения к метаболической инженерии и оценке параметров» . Биоинформатика . 14 (10): 869–883. дои : 10.1093/биоинформатика/14.10.869 . ISSN 1367-4803 . ПМИД 9927716 .
Дальнейшее чтение
[ редактировать ]- Бойд, Стивен П .; Ванденберге, Ливен (2004). Выпуклая оптимизация . Кембридж: Издательство Кембриджского университета. ISBN 0-521-83378-7 .
- Гилл, ЧП; Мюррей, В.; Райт, Миннесота (1982). Практическая оптимизация . Лондон: Академическая пресса. ISBN 0-12-283952-8 .
- Ли, Джон (2004). Первый курс комбинаторной оптимизации . Издательство Кембриджского университета. ISBN 0-521-01012-8 .
- Носедаль, Хорхе ; Райт, Стивен Дж. (2006). Численная оптимизация (2-е изд.). Берлин: Шпрингер. ISBN 0-387-30303-0 .
Внешние ссылки
[ редактировать ]- «Дерево решений для оптимизации программного обеспечения» . Ссылки на исходники оптимизации
- «Глобальная оптимизация» .
- «EE364a: Выпуклая оптимизация I» . Курс Стэнфордского университета .
- Варокво, Гаэль. «Математическая оптимизация: поиск минимумов функций» .