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

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

Пример

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

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

при условии

x_{1}\geq 1

и

x_{2}=1,

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

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

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

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

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

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

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

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

Глобальные ограничения ^[2] ограничения, представляющие определенное отношение к ряду переменных, взятых вместе. Некоторые из них, такие как alldifferent ограничение можно переписать как объединение атомарных ограничений на более простом языке: alldifferent ограничение действует для n переменных $x_{1}...x_{n}$ и выполняется, если переменные принимают значения, которые попарно различны. Оно семантически эквивалентно конъюнкции неравенств $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] упростить моделирование задач удовлетворения ограничений , расширить выразительность языков ограничений, а также улучшить разрешение ограничений : действительно, рассматривая переменные в целом, невозможные ситуации можно увидеть на более ранних этапах процесса решения. Многие глобальные ограничения включены в онлайн-каталог.

См. также

Ссылки

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

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

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

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

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

[1] Такаяма, Акира (1985). Математическая экономика (2-е изд.). Нью-Йорк: Издательство Кембриджского университета. п. 61 . ISBN 0-521-31498-4 .

[2] Росси, Франческа; Ван Бик, Питер; Уолш, Тоби (2006). «7». Справочник по программированию в ограничениях (1-е изд.). Амстердам: Эльзевир. ISBN 9780080463643 . OCLC 162587579 .

[3] Росси, Франческа (2003). Принципы и практика программирования с ограничениями CP 2003 00: 9-я Международная конференция, CP 2003, Кинсейл, Ирландия, 29 сентября и 3 октября 2003 г. Труды . Берлин: Springer-Verlag Berlin Heidelberg. ISBN 9783540451938 . OCLC 771185146 .

[1]

[2]

[3]