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

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

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

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

Общая форма [ править ]

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

{\ displaystyle {\ begin {array} {rcll} \ min & ~ & f (\ mathbf {x}) & \\\ mathrm {subject ~ to} & ~ & g_ {i} (\ mathbf {x}) = c_ { i} & {\ text {for}} i = 1, \ ldots, n \ quad {\ text {Ограничения равенства}} \\ & ~ & h_ {j} (\ mathbf {x}) \ geqq d_ {j} & {\ text {for}} j = 1, \ ldots, m \ quad {\ text {Ограничения неравенства}} \ end {array}}}

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

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

Способы решения [ править ]

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

Ограничения равенства [ править ]

Метод подстановки [ править ]

Для очень простых задач, скажем, функции двух переменных с одним ограничением равенства, наиболее практично применять метод подстановки. ^[3] Идея состоит в том, чтобы подставить ограничение в целевую функцию, чтобы создать составную функцию, которая учитывает эффект ограничения. Например, предположим, что целью является максимизация предмета . Ограничение подразумевает , что можно подставить в целевую функцию для создания . Первый порядок необходимое условие дает , что может быть решено , и, следовательно, . ${\ Displaystyle е (х, у) = х \ 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 .

Условия ККТ [ править ]

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

Ветвь и переплет [ править ]

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

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

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

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

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

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

Поиск матрешки [ править ]

Этот метод ^[5] запускает алгоритм ветвей и границ для задач, где - количество переменных. Каждая такая задача - это подзадача, полученная путем удаления последовательности переменных из исходной задачи вместе с ограничениями, содержащими их. После решения задачи о переменных ее оптимальную стоимость можно использовать в качестве верхней границы при решении других задач, $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 использует их только как границы во время поиска.

Устранение ведра [ править ]

Устранение ковша Алгоритм может быть адаптирован для ограничения оптимизации. Данную переменную действительно можно удалить из проблемы, заменив все мягкие ограничения, содержащие ее, новым мягким ограничением. Стоимость этого нового ограничения вычисляется с учетом максимального значения для каждого значения удаленной переменной. Формально, если это переменная, которая должна быть удалена, мягкие ограничения, содержащие ее, и их переменные, за исключением того , что новое мягкое ограничение определяется следующим образом: $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}).

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

См. Также [ править ]

Метод наименьших квадратов с ограничениями
Оптимизация распределенных ограничений
Проблемы удовлетворения ограничений (CSP)
Ограниченное программирование
Целочисленное программирование
Штрафной метод
Превосходство

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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

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

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

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

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

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

[1]