Оптимизация с ограничениями (Khmnbn[genx v kijguncyunxbn)

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

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

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

Общая форма

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

${\begin{array}{rcll}\min &~&f(\mathbf {x} )&\\{\text{при ограничениях}}&~&g_{i}(\mathbf {x} )=c_{i}&{\text{для }}i=1,\ldots ,n\quad {\text{Ограничения-равенства}}\\&~&h_{j}(\mathbf {x} )\geqslant d_{j}&{\text{для }}j=1,\ldots ,m\quad {\text{Ограничения-неравенства}}\end{array}}$

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

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

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

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

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

Метод подстановки

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

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

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

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

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

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

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

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

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

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

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

ККТ условия

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

Метод ветвей и границ

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

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

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

Вариант этого подхода, называемый методом Хансена, использует интервальные методы. Метод по умолчанию реализует прямоугольные ограничения.

Выбор ограничивающих функций

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

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

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

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

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

Сегментное исключение

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

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

См. также

• Метод наименьших квадратов с ограничениями
• Распределённая оптимизация в ограничениях
• Удовлетворение ограничений
• Программирование в ограничениях
• Целочисленное программирование
• Метод штрафов

Литература для дальнейшего чтения

• Dimitri P. Constrained Optimization and Lagrange Multiplier Methods. — New York: Academic Press, 1982. — ISBN 0-12-093480-9.
• Francesca Rossi, Peter van Beek, Toby Walsh. Chapter 1 – Introduction. — Elsevier, 2006. — Т. 2. — С. 3–12. — (Handbook of Constraint Programming). — doi:10.1016/s1574-6526(06)80005-2.

• Rina Dechter. Constraint Processing. — Morgan Kaufmann, 2003. — ISBN 1-55860-890-7.