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

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

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

Задача ограниченной оптимизации (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}$ при условии ${ displaystyle x + y = 10}$ . Ограничение подразумевает ${ displaystyle y = 10-x}$ , который можно подставить в целевую функцию для создания ${ Displaystyle р (х) = х (10-х) = 10x-х ^ {2}}$ . Необходимое условие первого порядка дает ${ displaystyle { frac { partial p} { partial x}} = 10-2x = 0}$ , которое можно решить за ${ displaystyle x = 5}$ и следовательно, ${ displaystyle y = 10-5 = 5}$ .

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

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

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

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

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

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

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

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

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

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

Условия ККТ

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

Ветвь и переплет

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

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

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

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

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

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

Поиск матрешки

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

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

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

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

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

{ Displaystyle 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}).}

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

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

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

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

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

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

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

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

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

[1]

[2]

[3]

[4]

[5]