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

Сюда перенаправляются «Оптимизация» и «Оптимум». Чтобы узнать о других значениях, см. Оптимизация (значения) и Оптимум (значения) .

«Математическое программирование» перенаправляется сюда. Информацию о рецензируемом журнале см. в разделе «Математическое программирование» .

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Обозначения

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

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

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

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

Это обозначает минимальное значение целевой функции x ² + 1 , при выборе x из набора действительных чисел $\mathbb {R}$. Минимальное значение в этом случае равно 1, происходящему при x = 0 .

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

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

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

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

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

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

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

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

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

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

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

${\underset {x\in [-5,5],\;y\in \mathbb {R} }{\operatorname {arg\,max} }}\;x\cos y,$

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

${\underset {x,\;y}{\operatorname {arg\,max} }}\;x\cos y,\;{\text{subject to:}}\;x\in [-5,5],\;y\in \mathbb {R} ,$

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

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

История

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: условия Каруша – Куна – Такера

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

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

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

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

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

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

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

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

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

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

Более полный список см. в разделе Список алгоритмов оптимизации .

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

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

Основная статья: Итерационный метод

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

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

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

Эвристика

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

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

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

Приложения

Механика

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Геофизика

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

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

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

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

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

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

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

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

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

Решатели

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

См. также

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

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

• Бойд, Стивен П .; Ванденберге, Ливен (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» . Курс Стэнфордского университета .
• Варокво, Гаэль. «Математическая оптимизация: поиск минимумов функций» .