Ограниченная оптимизация

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

Связь с проблемами удовлетворения ограничений

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

Общая форма

Общую задачу минимизации с ограничениями можно записать следующим образом: ^[2]

{\begin{array}{rcll}\min &~&f(\mathbf {x} )&\\\mathrm {subject~to} &~&g_{i}(\mathbf {x} )=c_{i}&{\text{for }}i=1,\ldots ,n\quad {\text{Equality constraints}}\\&~&h_{j}(\mathbf {x} )\geq d_{j}&{\text{for }}j=1,\ldots ,m\quad {\text{Inequality constraints}}\end{array}}

где $g_{i}(\mathbf {x} )=c_{i}~\mathrm {for~} i=1,\ldots ,n$ и $h_{j}(\mathbf {x} )\geq d_{j}~\mathrm {for~} j=1,\ldots ,m$ являются ограничениями, которые должны соблюдаться (они называются жесткими ограничениями ), и $f(\mathbf {x} )$ – это целевая функция, которую необходимо оптимизировать с учетом ограничений.

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

Методы решения

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

Ограничения равенства

Метод замены

Для очень простых задач, например, для функции двух переменных, на которую распространяется одно ограничение равенства, наиболее практично применить метод подстановки. ^[4] Идея состоит в том, чтобы заменить ограничение целевой функцией, чтобы создать составную функцию , включающую в себя эффект ограничения. Например, предположим, что цель состоит в том, чтобы максимизировать $f(x,y)=x\cdot y$ при условии $x+y=10$ . Ограничение подразумевает $y=10-x$ , который можно подставить в целевую функцию для создания $p(x)=x(10-x)=10x-x^{2}$ . Необходимое условие первого порядка дает ${\frac {\partial p}{\partial x}}=10-2x=0$ , которое можно решить для $x=5$ и, следовательно, $y=10-5=5$ .

Множитель Лагранжа

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

Ограничения неравенства

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

Линейное программирование

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

Нелинейное программирование

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

Квадратичное программирование

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

Условия ККТ

Допуская ограничения-неравенства, подход ККТ к нелинейному программированию обобщает метод множителей Лагранжа. Его можно применять в условиях дифференцируемости и выпуклости.

Ветвь и граница

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

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

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

Вариант этого подхода, называемый методом Хансена, использует интервальные методы . ^[5] По своей сути он реализует прямоугольные ограничения.

Ограничивающие функции первого выбора

Один из способов оценки этой верхней границы частичного решения — рассматривать каждое мягкое ограничение отдельно. Для каждого мягкого ограничения предполагается максимально возможное значение для любого присвоения неназначенным переменным. Сумма этих значений является верхней границей, поскольку мягкие ограничения не могут принимать более высокое значение. Это точно, потому что максимальные значения мягких ограничений могут быть получены из разных оценок: мягкое ограничение может быть максимальным для $x=a$ в то время как другое ограничение является максимальным для $x=b$ .

Поиск русской куклы

Этот метод ^[6] запускает алгоритм ветвей и границ на $n$ проблемы, где $n$ это количество переменных. Каждая такая задача представляет собой подзадачу, полученную отбрасыванием последовательности переменных $x_{1},\ldots ,x_{i}$ из исходной задачи вместе с содержащими их ограничениями. После задачи о переменных $x_{i+1},\ldots ,x_{n}$ решена, ее оптимальную стоимость можно использовать в качестве верхней границы при решении других задач,

В частности, оценка стоимости решения, имеющего $x_{i+1},\ldots ,x_{n}$ поскольку неназначенные переменные добавляются к стоимости, полученной из оцениваемых переменных. Практически это соответствует игнорированию оцениваемых переменных и решению проблемы с неназначенными, за исключением того, что последняя проблема уже решена. Точнее, стоимость мягких ограничений, содержащих как назначенные, так и неназначенные переменные, оценивается, как указано выше (или с использованием произвольного другого метода); вместо этого стоимость мягких ограничений, содержащих только неназначенные переменные, оценивается с использованием оптимального решения соответствующей проблемы, которое уже известно на данный момент.

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

Устранение ведра

Алгоритм исключения сегментов можно адаптировать для оптимизации ограничений. Данную переменную действительно можно удалить из задачи, заменив все содержащие ее мягкие ограничения новым мягким ограничением. Стоимость этого нового ограничения вычисляется, предполагая максимальное значение для каждого значения удаленной переменной. Формально, если $x$ переменная, которую нужно удалить, $C_{1},\ldots ,C_{n}$ являются мягкими ограничениями, содержащими его, и $y_{1},\ldots ,y_{m}$ являются их переменными, кроме $x$ новое мягкое ограничение определяется следующим образом:

C(y_{1}=a_{1},\ldots ,y_{n}=a_{n})=\max _{a}\sum _{i}C_{i}(x=a,y_{1}=a_{1},\ldots ,y_{n}=a_{n}).

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

См. также

Ссылки

^ Росси, Франческа; ван Бик, Питер; Уолш, Тоби (1 января 2006 г.), Росси, Франческа; ван Бик, Питер; Уолш, Тоби (ред.), «Глава 1 – Введение» , Основы искусственного интеллекта , Справочник по программированию с ограничениями, том. 2, Elsevier, стр. 3–12, номер документа : 10.1016/s1574-6526(06)80005-2 , получено 4 октября 2019 г.
^ Мартинс, JRRA; Нин, А. (2021). Оптимизация инженерного проектирования . Издательство Кембриджского университета. ISBN 978-1108833417 .
^ Венью Сунь; Я-Сян Юань (2010). Теория и методы оптимизации: нелинейное программирование , Springer, ISBN 978-1441937650 . п. 541
^ Проссер, Майк (1993). «Ограниченная оптимизация путем замены». Базовая математика для экономистов . Нью-Йорк: Рутледж. стр. 338–346. ISBN 0-415-08424-5 .
^ Лидер Джеффри Дж. (2004 г.). Численный анализ и научные вычисления . Эддисон Уэсли. ISBN 0-201-73499-0 .
^ Верфайи, Жерар, Мишель Леметр и Томас Шикс. « Поиск русской куклы для решения задач оптимизации ограничений ». AAAI/IAAI, Vol. 1. 1996.

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

Берцекас, Дмитрий П. (1982). Оптимизация с ограничениями и методы множителей Лагранжа . Нью-Йорк: Академическая пресса. ISBN 0-12-093480-9 .
Дектер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN 1-55860-890-7 .

[1] Росси, Франческа; ван Бик, Питер; Уолш, Тоби (1 января 2006 г.), Росси, Франческа; ван Бик, Питер; Уолш, Тоби (ред.), «Глава 1 – Введение» , Основы искусственного интеллекта , Справочник по программированию с ограничениями, том. 2, Elsevier, стр. 3–12, номер документа : 10.1016/s1574-6526(06)80005-2 , получено 4 октября 2019 г.

[edo2021-2] Мартинс, JRRA; Нин, А. (2021). Оптимизация инженерного проектирования . Издательство Кембриджского университета. ISBN 978-1108833417 .

[3] Венью Сунь; Я-Сян Юань (2010). Теория и методы оптимизации: нелинейное программирование , Springer, ISBN 978-1441937650 . п. 541

[4] Проссер, Майк (1993). «Ограниченная оптимизация путем замены». Базовая математика для экономистов . Нью-Йорк: Рутледж. стр. 338–346. ISBN 0-415-08424-5 .

[5] Лидер Джеффри Дж. (2004 г.). Численный анализ и научные вычисления . Эддисон Уэсли. ISBN 0-201-73499-0 .

[6] Верфайи, Жерар, Мишель Леметр и Томас Шикс. « Поиск русской куклы для решения задач оптимизации ограничений ». AAAI/IAAI, Vol. 1. 1996.

[1]

[2]

[3]

[4]

[5]

[6]