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

Оптимизация целевых функций с ограниченными переменными

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

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

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

Общая форма

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

${\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{Equality constraints}}\\&~&h_{j}(\mathbf {x} )\geq d_{j}&{\text{for }}j=1,\ldots ,m\quad {\text{Inequality constraints}}\end{array}}}$

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

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

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

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

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

Метод замещения

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

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

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

Неравенство ограничений

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

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

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

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

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

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

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

Условия ККТ

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

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

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

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

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

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

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

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

поиск русской матрешки

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

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

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

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

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

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

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

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

Ссылки

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

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

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