구속조건(수학)

이 문서에는 참고 자료, 관련 읽기 또는 외부 링크가 포함되어 있지만 인라인 인용이 부족하여 출처가 불분명합니다. 좀 더 정밀한 인용문을 도입하여 이 글의 개선에 도움을 주시기 바랍니다.(2016년 9월) (이 템플릿메시지 삭제 방법 및 삭제 시기 확인)

수학에서 제약조건은 솔루션이 충족해야 하는 최적화 문제의 조건입니다.제약에는 주로 균등 제약, 불평등 제약 및 정수 제약 등 여러 가지 유형이 있습니다.모든 제약 조건을 만족시키는 후보 솔루션 집합을 실현 가능한 ^[1]집합이라고 합니다.

예

다음으로 간단한 최적화 문제를 나타냅니다.

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

의 영향을 받는.

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

그리고.

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

여기서x(\$displaystyle \mathbf {x})$는 벡터(x₁, x₂)를 나타냅니다.

이 예에서 첫 번째 행은 최소화할 함수(목적 함수, 손실 함수 또는 비용 함수라고 함)를 정의합니다.두 번째 줄과 세 번째 줄은 두 가지 제약을 정의하는데, 첫 번째 줄은 부등식 제약 조건이고 두 번째 줄은 등식 제약 조건입니다.이 두 가지 제약조건은 엄격한 제약조건이며, 이는 충족될 필요가 있음을 의미합니다. 즉, 실현 가능한 후보 솔루션 세트를 정의합니다.

제약조건이 없으면 해답은 (0,0)이 됩니다.여기서 f$)$ {$displaystyle$ f$(\mathbf {x})}$는 값이 가장 낮습니다.그러나 이 솔루션은 제약 조건을 충족시키지 못합니다.위에서 설명한 제한 최적화 문제의 해결 방법은 x = (1, 1){$displaystyle \mathbf {x}$= (1$,1$이며, 이는 두 제약을 충족하는 f$)$ {$displaystyle$ f$(\mathbf {x})}$의 최소값을 갖는 지점이다.

용어.

• 부등식 제약조건이 최적점에서 등식을 유지한다면, 제약조건은 구속력이 있다고 한다. 왜냐하면 그렇게 하면 목적함수의 값이 개선되더라도 제약조건의 방향으로 변경할 수 없기 때문이다.
• 부등식 제약이 최적점에서 엄격한 부등식으로 유지된다면(즉, 평등과 유지되지 않음), 제약 조건은 구속력의 방향으로 변경될 수 있기 때문에 구속력이 없다고 한다. 그러나 그렇게 하는 것이 최적이지는 않을 것이다.예를 들어, 볼록 최적화에서와 같은 특정 조건 하에서, 제약조건이 비결합적인 경우, 최적화 문제는 그 제약조건이 없는 경우에도 동일한 해결책을 가질 것이다.
• 제약조건이 특정 포인트에서 충족되지 않으면 해당 포인트는 실행 불가능하다고 합니다.

하드 및 소프트 제약

위의 설명에서와 같이, 이 문제가 제약조건을 만족시킬 것을 요구하는 경우, 그 제약조건을 하드 제약조건이라고 부르기도 한다.그러나, 유연한 제약 조건 만족 문제라 불리는 일부 문제에서는, 특정 제약 조건을 충족하는 것이 선호되지만 필수는 아니다. 이러한 비필수 제약 조건을 소프트 제약이라고 한다.예를 들어 선호 기반 계획에서는 소프트 제약이 발생합니다.MAX-CSP 문제에서는 다수의 제약조건을 위반할 수 있으며 솔루션의 품질은 충족된 제약조건의 수에 따라 측정된다.

글로벌 제약

전역 제약조건은^[2] 여러 변수에 대한 특정 관계를 나타내는 제약조건으로, 전체적으로 취합됩니다.제약 조건과 같은 일부는 더 간단한 언어로 원자 제약 조건의 결합으로 다시 쓰여질 수 있습니다:alldifferent제약조건은 n개의 변수 x 1 ... xn { $displaystyle$ x _ { $1$} 。$x_{n$ 각 변수가 쌍으로 다른 값을 취할 경우 충족됩니다.이는 부등식 x 1x x2, x 1 x x3. , x 2 x x 3, x 2x x4..x n - 1$n$ x nx x n x$_ {$ $2$ } \ $neq$ x $_$ { $2$} , $x _$ { { $1$} \ $neq$ x { { 3 } , $x$_ $neq$ { $3$} 의 결합과 의미적으로 $동등$합니다.$x_{n-1}\neq x_{n$ 기타 글로벌 제약에 의해 제약 프레임워크의 표현성이 확장됩니다.이 경우 보통 조합 문제의 전형적인 구조를 포착합니다.예를 들어,regular제약조건은 변수의 시퀀스가 결정론적 유한 오토마톤에 의해 받아들여진다는 것을 나타냅니다.

글로벌 제약은 제약 만족 문제의 모델링을 단순화하고, 제약 언어의 표현성을 확장하며, 제약 해결을 개선하기 위해 사용됩니다^[3]. 실제로 변수를 모두 고려함으로써, 실행 불가능한 상황을 해결 프로세스 초기에 볼 수 있습니다.글로벌 제약 조건의 대부분은 온라인 카탈로그에 참조됩니다.

「 」를 참조해 주세요.

레퍼런스

추가 정보

• Beveridge, Gordon S. G.; Schechter, Robert S. (1970). "Essential Features in Optimization". Optimization: Theory and Practice. New York: McGraw-Hill. pp. 5–8. ISBN 0-07-005128-3.

외부 링크

• 비선형 프로그래밍 FAQ
• 수학 프로그래밍 용어집