Введение

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

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

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

Методы растворения

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

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

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

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

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

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

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

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

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

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

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

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

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

Условия ККТ

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

Разделенный и связанный

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

Функции ограничения первого выбора

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

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

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

В частности, оценка стоимости решения, имеющего в качестве неназначенных переменных , добавляется к стоимости, вытекающей из назначенных переменных. По сути, это соответствует игнорированию назначенных переменных и решению задачи только на неназначенных, за исключением того, что последняя задача уже решена. Более точно, стоимость мягких ограничений, содержащих как назначенные, так и неназначенные переменные, оценивается вышеуказанным образом (или любым другим произвольным методом); стоимость же мягких ограничений, содержащих только неназначенные переменные, оценивается с использованием оптимального решения соответствующей подзадачи, которое уже известно на данный момент. Существует сходство между методом поиска «русские куклы» и динамическим программированием. Как и динамическое программирование, метод «русские куклы» решает подзадачи для решения исходной задачи. Однако, в то время как динамическое программирование напрямую комбинирует результаты, полученные для подзадач, чтобы получить результат исходной задачи, метод «русские куклы» использует их только в качестве границ в процессе поиска.

Удаление из ковша

Алгоритм устранения букета может быть адаптирован для оптимизации ограничений. Действительно, данную переменную можно удалить из задачи, заменив все мягкие ограничения, содержащие её, новым мягким ограничением. Стоимость этого нового ограничения вычисляется, исходя из максимального значения для каждого значения удаляемой переменной. Формально, если – переменная, которую необходимо удалить, – мягкие ограничения, содержащие её, а – переменные этих ограничений, исключая , то новое мягкое ограничение определяется следующим образом:

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