Ограничение (математика)

Условие задачи оптимизации, которому должно удовлетворять решение

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

Пример

Ниже приведена простая задача оптимизации:

${\displaystyle \min f(\mathbf {x} )=x_{1}^{2}+x_{2}^{4}}$

при условии

${\displaystyle x_{1}\geq 1}$

и

${\displaystyle x_{2}=1,}$

где обозначает вектор ( x ₁ , x ₂ ). ${\displaystyle \mathbf {x} }$

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

Без ограничений решением будет (0,0), где имеет наименьшее значение. Но это решение не удовлетворяет ограничениям. Решением задачи оптимизации с ограничениями, изложенной выше , является точка с наименьшим значением, удовлетворяющая двум ограничениям. ${\displaystyle f(\mathbf {x} )}$ ${\displaystyle \mathbf {x} =(1,1)}$ ${\displaystyle f(\mathbf {x} )}$

Терминология

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

Жесткие и мягкие ограничения.

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

Глобальные ограничения

Глобальные ограничения ^[2] — это ограничения, представляющие определенное отношение к ряду переменных, взятых вместе. Некоторые из них, такие как ограничение all Different, можно переписать как объединение атомарных ограничений на более простом языке: ограничение alldifferentдействует для n переменных и выполняется, если переменные принимают значения, которые попарно различны. Это семантически эквивалентно соединению неравенств . Другие глобальные ограничения расширяют выразительность структуры ограничений. В этом случае они обычно отражают типичную структуру комбинаторных задач. Например, ограничение выражает то, что последовательность переменных принимается детерминированным конечным автоматом . ${\displaystyle x_{1}...x_{n}}$ ${\displaystyle x_{1}\neq x_{2},x_{1}\neq x_{3}...,x_{2}\neq x_{3},x_{2}\neq x_{4}...x_{n-1}\neq x_{n}}$regular

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

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

• Алгебра ограничений
• Условия Каруша – Куна – Такера
• Множители Лагранжа
• Установлен уровень
• Линейное программирование
• Нелинейное программирование
• Ограничение
• Теории выполнимости по модулю

Рекомендации

1. Такаяма, Акира (1985). Математическая экономика (2-е изд.). Нью-Йорк: Издательство Кембриджского университета. п. 61. ИСБН 0-521-31498-4.
2. Росси, Франческа; Ван Бик, Питер; Уолш, Тоби (2006). «7». Справочник по программированию в ограничениях (1-е изд.). Амстердам: Эльзевир. ISBN 9780080463643. ОСЛК  162587579.
3. Росси, Франческа (2003). Принципы и практика программирования с ограничениями CP 2003 00: 9-я Международная конференция, CP 2003, Кинсейл, Ирландия, 29 сентября и 3 октября 2003 г. Труды . Берлин: Springer-Verlag Berlin Heidelberg. ISBN 9783540451938. ОСЛК  771185146.

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

• Беверидж, Гордон С.Г.; Шехтер, Роберт С. (1970). «Основные функции оптимизации». Оптимизация: теория и практика . Нью-Йорк: МакГроу-Хилл. стр. 5–8. ISBN 0-07-005128-3.

Внешние ссылки

• Часто задаваемые вопросы по нелинейному программированию. Архивировано 30 октября 2019 г. на Wayback Machine.
• Глоссарий по математическому программированию. Архивировано 28 марта 2010 г. в Wayback Machine.