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

Изучение математических алгоритмов для задач оптимизации

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

Минимальный поиск Нелдера-Мида функции Симионеску . Вершины симплекса упорядочены по их значениям, причем 1 имеет наименьшее ( лучшее) значение. ${\displaystyle f(x)}$

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

В более общем подходе задача оптимизации состоит в максимизации или минимизации действительной функции путем систематического выбора входных значений из допустимого набора и вычисления значения функции. Обобщение теории и методов оптимизации на другие формулировки составляет большую область прикладной математики . ^[6]

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

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

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

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

Дано: функция f  : A → из некоторого множества A в действительные числа ${\displaystyle \mathbb {R} }$

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

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

Поскольку следующее справедливо

${\displaystyle f(\mathbf {x} _{0})\geq f(\mathbf {x} )\Leftrightarrow -f(\mathbf {x} _{0})\leq -f(\mathbf {x} ),}$

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

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

Обычно A — это некоторое подмножество евклидова пространства , часто определяемое набором ограничений , равенств или неравенств, которым должны удовлетворять члены A. Область A функции f называется пространством поиска или множеством выбора , в то время как элементы A называются потенциальными решениями или допустимыми решениями . ${\displaystyle \mathbb {R} ^{n}}$

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

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

Локальный минимум x * определяется как элемент, для которого существует некоторое δ > 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 \mathbb {R} }$

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

${\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 году. ( В данном контексте программирование не относится к компьютерному программированию , а происходит от использования программы военными США для обозначения предлагаемых учебных и логистических графиков, которые были проблемами, которые Данциг изучал в то время.) Данциг опубликовал алгоритм Simplex в 1947 году, а Джон фон Нейман и другие исследователи работали над теоретическими аспектами линейного программирования (например, теорией двойственности ) примерно в то же время. ^[9]

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

• Ричард Беллман
• Димитрий Берцекас
• Мишель Бирлер
• Стивен П. Бойд
• Роджер Флетчер
• Мартин Грётшель
• Рональд А. Ховард
• Фриц Джон
• Нарендра Кармаркар
• Уильям Каруш
• Леонид Хачиян
• Бернард Купман
• Гарольд Кун
• Ласло Ловас
• Дэвид Люенбергер
• Аркадий Немировский
• Юрий Нестеров
• Лев Понтрягин
• Р. Тиррелл Рокафеллар
• Наум З. Шор
• Альберт Такер

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эвристика

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

• Дифференциальная эволюция
• Динамическая релаксация
• Эволюционные алгоритмы
• Генетические алгоритмы
• Подъем на холм с повторным запуском
• Меметический алгоритм
• Симплициальная эвристика Нелдера–Мида : популярная эвристика для приближенной минимизации (без вызова градиентов)
• Оптимизация роя частиц
• Имитация отжига
• Стохастическое туннелирование
• Поиск табу

Приложения

Механика

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

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

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

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

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

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

Начиная с 1970-х годов экономисты моделировали динамические решения с течением времени, используя теорию управления . ^[14] Например, динамические модели поиска используются для изучения поведения на рынке труда . ^[15] Важное различие существует между детерминированными и стохастическими моделями. ^[16] Макроэкономисты строят динамические стохастические модели общего равновесия (DSGE) , которые описывают динамику всей экономики как результат взаимозависимых оптимизирующих решений работников, потребителей, инвесторов и правительств . ^{[17] . [18] [19]}

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

Некоторые общие приложения методов оптимизации в электротехнике включают активную разработку фильтров, ^[20] уменьшение поля рассеяния в сверхпроводящих магнитных системах хранения энергии, проектирование пространственного картирования микроволновых структур, ^[21] антенны телефонов, ^{[22] [23] [24]} проектирование на основе электромагнитных полей. Электромагнитно-проверенная оптимизация проектирования микроволновых компонентов и антенн широко использовала соответствующую основанную на физике или эмпирическую суррогатную модель и методологии пространственного картирования с момента открытия пространственного картирования в 1993 году. ^{[25] [26]} Методы оптимизации также используются в анализе потока мощности . ^[27]

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

Оптимизация широко используется в гражданском строительстве. Управление строительством и транспортная инженерия являются одними из основных отраслей гражданского строительства, которые в значительной степени полагаются на оптимизацию. Наиболее распространенными проблемами гражданского строительства, которые решаются с помощью оптимизации, являются выемка и засыпка дорог, анализ жизненного цикла конструкций и инфраструктур, ^[28] выравнивание ресурсов , ^{[29] [30]} распределение водных ресурсов , управление дорожным движением ^[31] и оптимизация расписания.

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

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

Контрольная техника

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

Геофизика

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

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

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

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

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

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

Решатели

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

• кривая брахистохроны
• Подгонка кривой
• Детерминированная глобальная оптимизация
• Программирование целей
• Важные публикации по оптимизации
• Наименьшие квадраты
• Общество математической оптимизации (ранее Общество математического программирования)
• Алгоритмы математической оптимизации
• Программное обеспечение для математической оптимизации
• Оптимизация процесса
• Оптимизация на основе моделирования
• Тестовые функции для оптимизации
• Вариационное исчисление
• Проблема маршрутизации транспортных средств

Примечания

1. «Природа математического программирования». Архивировано 5 марта 2014 г. на Wayback Machine . Глоссарий математического программирования , INFORMS Computing Society.
2. "Математическое программирование: обзор" (PDF) . Получено 26 апреля 2024 г.
3. Мартинс, Жоаким РРА; Нинг, Эндрю (2021-10-01). Оптимизация инженерного проектирования. Cambridge University Press. ISBN 978-1108833417.
4. Du, DZ; Pardalos, PM; Wu, W. (2008). «История оптимизации». В Floudas, C. ; Pardalos, P. (ред.). Энциклопедия оптимизации . Бостон: Springer. С. 1538–1542.
5. "Математическая оптимизация". Engati . Получено 2024-08-24 .
6. "Открытый журнал математической оптимизации". ojmo.centre-mersenne.org . Получено 2024-08-24 .
7. Хартманн, Александр К; Ригер, Хайко (2002). Алгоритмы оптимизации в физике . Гражданин.
8. Эрвин Диверт, В. (2017), «Функции затрат», Новый экономический словарь Palgrave , Лондон: Palgrave Macmillan UK, стр. 1–12, doi : 10.1057/978-1-349-95121-5_659-2, ISBN 978-1-349-95121-5, получено 2024-08-18
9. Биксби, Роберт Э. (2012). «Краткая история вычислений линейного и смешанно-целочисленного программирования» (PDF) . Documenta Mathematica . Серия Documenta Mathematica. 2012 : 107–121. doi :10.4171/dms/6/16. ISBN 978-3-936609-58-5.
10. Абдулкадыров, Р.; Ляхов, П.; Бергерман, М.; Резников, Д. (февраль 2024 г.). «Распознавание спутниковых изображений с использованием ансамблевых нейронных сетей и разностного градиента положительно-отрицательного импульса». Хаос, солитоны и фракталы . 179 : 114432. Bibcode : 2024CSF...17914432A. doi : 10.1016/j.chaos.2023.114432.
11. Верещагин, А.Ф. (1989). «Моделирование и управление движением манипуляционных роботов». Советский журнал вычислительной техники и системных наук . 27 (5): 29–38.
12. Хаггаг, С.; Десокей, Ф.; Рамадан, М. (2017). «Космологическая инфляционная модель с использованием оптимального управления». Гравитация и космология . 23 (3): 236–239. Bibcode :2017GrCo...23..236H. doi :10.1134/S0202289317030069. ISSN  1995-0721. S2CID  125980981.
13. Лайонел Роббинс (1935, 2-е изд.) Эссе о природе и значении экономической науки , Macmillan, стр. 16.
14. Дорфман, Роберт (1969). «Экономическая интерпретация теории оптимального управления». American Economic Review . 59 (5): 817–831. JSTOR  1810679.
15. Сарджент, Томас Дж. (1987). «Поиск». Динамическая макроэкономическая теория . Издательство Гарвардского университета. С. 57–91. ISBN 9780674043084.
16. AG Malliaris (2008). "стохастическое оптимальное управление", Новый экономический словарь Palgrave , 2-е издание. Аннотация Архивировано 18 октября 2017 г. на Wayback Machine .
17. Чавес Маза, Мануэль; Федриани, Эухенио М.; Ордас Санс, Хосе Антонио (01 июля 2018 г.). «Факторы, имеющие значение для оптимизации общественных услуг, а также для предприятий и предприятий по обеспечению выживания». Инновар . 28 (69): 9–24. doi : 10.15446/innovar.v28n69.71693. ISSN  2248-6968.
18. Ротемберг, Хулио ; Вудфорд, Майкл (1997). «Основанная на оптимизации эконометрическая структура для оценки денежно-кредитной политики» (PDF) . NBER Macroeconomics Annual . 12 : 297–346. doi : 10.2307/3585236 . JSTOR  3585236.
19. Из Нового экономического словаря Пэлгрейва (2008), 2-е издание с аннотационными ссылками:
    • «численные методы оптимизации в экономике» Карла Шмеддерса
    • «выпуклое программирование» Лоуренса Э. Блюма
    • «Модель общего равновесия Эрроу–Дебре» Джона Джинакоплоса .
20. Де, Бишну Прасад; Кар, Р.; Мандал, Д.; Гошал, СП (2014-09-27). «Оптимальный выбор значений компонентов для разработки аналогового активного фильтра с использованием оптимизации симплексного роя частиц». Международный журнал машинного обучения и кибернетики . 6 (4): 621–636. doi :10.1007/s13042-014-0299-0. ISSN  1868-8071. S2CID  13071135.
21. Koziel, Slawomir; Bandler, John W. (январь 2008 г.). «Пространственное картирование с несколькими грубыми моделями для оптимизации микроволновых компонентов». IEEE Microwave and Wireless Components Letters . 18 (1): 1–3. CiteSeerX 10.1.1.147.5407 . doi :10.1109/LMWC.2007.911969. S2CID  11086218. 
22. Ту, Шэн; Чэн, Цинша С.; Чжан, Ифань; Бэндлер, Джон В.; Николова, Наталья К. (июль 2013 г.). «Оптимизация пространственного картирования антенн телефонов с использованием моделей с тонкими проводами». Труды IEEE по антеннам и распространению радиоволн . 61 (7): 3797–3807. Bibcode : 2013ITAP...61.3797T. doi : 10.1109/TAP.2013.2254695 .
23. Н. Фридрих, «Космическое картирование опережает электромагнитную оптимизацию при проектировании антенн мобильных телефонов», Microwaves&rf, 30 августа 2013 г.
24. Сервантес-Гонсалес, Хуан К.; Райас-Санчес, Хосе Э.; Лопес, Карлос А.; Камачо-Перес, Хосе Р.; Брито-Брито, Забдиэль; Чавес-Уртадо, Хосе Л. (февраль 2016 г.). «Оптимизация пространственного картографирования антенн мобильных телефонов с учетом электромагнитного воздействия компонентов мобильного телефона и человеческого тела». Международный журнал компьютерной техники ВЧ и СВЧ . 26 (2): 121–128. doi : 10.1002/mmce.20945 . S2CID  110195165.
25. Бэндлер, Дж. В.; Бернацкий, Р. М.; Чен, Шао Хуа; Гробельни, П. А.; Хеммерс, Р. Х. (1994). «Метод пространственного картирования для электромагнитной оптимизации». Труды IEEE по теории и технике микроволн . 42 (12): 2536–2544. Bibcode : 1994ITMTT..42.2536B. doi : 10.1109/22.339794.
26. Бэндлер, Дж. В.; Бернацкий, Р. М.; Шао Хуа Чэнь; Хеммерс, Р. Х.; Мэдсен, К. (1995). «Электромагнитная оптимизация с использованием агрессивного пространственного картирования». Труды IEEE по теории и технике микроволн . 43 (12): 2874–2882. Bibcode : 1995ITMTT..43.2874B. doi : 10.1109/22.475649.
27. Выпуклая релаксация оптимального потока мощности: Учебное пособие. Симпозиум iREP 2013 г. по динамике и управлению массовыми энергосистемами. doi :10.1109/IREP.2013.6629391.
28. Пирионеси, Сайед Мадех; Таваколан, Мехди (9 января 2017 г.). «Модель математического программирования для решения задач оптимизации затрат и безопасности (CSO) при обслуживании конструкций». Журнал гражданского строительства KSCE . 21 (6): 2226–2234. Bibcode : 2017KSJCE..21.2226P. doi : 10.1007/s12205-017-0531-z. S2CID  113616284.
29. Хегази, Тарек (июнь 1999 г.). «Оптимизация распределения и выравнивания ресурсов с использованием генетических алгоритмов». Журнал строительной инженерии и управления . 125 (3): 167–175. doi :10.1061/(ASCE)0733-9364(1999)125:3(167).
30. Пирионеси, С. Мадех; Нассери, Мехран; Рамезани, Абдолла (9 июля 2018 г.). «Пирионеси, SM, Нассери, M., & Рамезани, A. (2018). Выравнивание ресурсов в строительных проектах с разделением деятельности и ограничениями ресурсов: оптимизация с помощью имитации отжига». Канадский журнал гражданского строительства . 46 : 81–86. doi : 10.1139/cjce-2017-0670. hdl : 1807/93364 . S2CID  116480238.
31. Herty, M.; Klar, A. (2003-01-01). «Моделирование, имитация и оптимизация сетей транспортных потоков». Журнал SIAM по научным вычислениям . 25 (3): 1066–1087. Bibcode : 2003SJSC...25.1066H. doi : 10.1137/S106482750241459X. ISSN  1064-8275.
32. "Новая сила на политической сцене: сеофонисты". Архивировано из оригинала 18 декабря 2014 года . Получено 14 сентября 2013 года .
33. Papoutsakis, Eleftherios Terry (февраль 1984). «Уравнения и расчеты для ферментации маслянокислых бактерий». Биотехнология и биоинженерия . 26 (2): 174–187. doi :10.1002/bit.260260210. ISSN  0006-3592. PMID  18551704. S2CID  25023799.
34. Ван, Юн; Джоши, Трупти; Чжан, Сян-Сунь; Сюй, Донг; Чэнь, Луонань (24 июля 2006 г.). «Вывод сетей регуляции генов из нескольких наборов данных микрочипов». Биоинформатика . 22 (19): 2413–2420. doi :10.1093/bioinformatics/btl396. ISSN  1460-2059. PMID  16864593.
35. Ван, Руи-Шэн; Ван, Юн; Чжан, Сян-Сун; Чэнь, Луонань (2007-09-22). «Вывод сетей регуляции транскрипции из высокопроизводительных данных». Биоинформатика . 23 (22): 3056–3064. doi : 10.1093/bioinformatics/btm465 . ISSN  1460-2059. PMID  17890736.
36. Vo, Thuy D.; Paul Lee, WN; Palsson, Bernhard O. (май 2007 г.). «Системный анализ энергетического метаболизма проливает свет на пораженный комплекс дыхательной цепи при синдроме Лея». Молекулярная генетика и метаболизм . 91 (1): 15–22. doi :10.1016/j.ymgme.2007.01.012. ISSN  1096-7192. PMID  17336115.
37. Мендес, П.; Келл, Д. (1998). «Нелинейная оптимизация биохимических путей: приложения к метаболической инженерии и оценке параметров». Биоинформатика . 14 (10): 869–883. doi : 10.1093/bioinformatics/14.10.869 . ISSN  1367-4803. PMID  9927716.

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

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

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

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