제약 조건

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

제약 조건은 최적화 문제에서 해의 범위를 제한하는 조건이다. 결합, 비결합, 실현 불가능과 같은 용어를 사용하여 제약 조건을 설명하며, 강제 제약 조건과 유연 제약 조건으로 분류할 수 있다. 또한, 여러 변수 간의 관계를 나타내는 전역 제약 조건이 있으며, 제약 만족 문제의 모델링과 해결을 돕는다.

제약 조건

📚 더 읽어볼만한 페이지

수학적 최적화 - 제약된 최적화
제약된 최적화는 제약 조건을 만족하는 해 중에서 목적 함수를 최적화하는 해를 찾는 문제로, 자원 할당, 스케줄링 등에 활용되며, 다양한 제약 조건과 해법을 통해 해결될 수 있습니다.
수학적 최적화 - 모서리해
모서리 해는 경제학에서 소비자가 예산 제약 하에 효용을 극대화할 때, 두 상품 중 하나만 소비하는 경우를 의미하며, 이는 소비자의 극단적인 선택이나 완전 대체재 관계에서 가격이 낮은 상품만 구매하는 경우 등에 나타나는 현상입니다.

1. 개요
2. 용어
3. 강제 제약 조건과 유연 제약 조건
- 3.1. 강제 제약 조건 (Hard Constraints)
- 3.2. 유연 제약 조건 (Soft Constraints)
4. 전역 제약 조건 (Global Constraints)
- 4.1. Alldifferent 제약 조건
- 4.2. 정규 제약 조건 (Regular Constraint)
5. 예시

2. 용어

* 부등식 제약 조건이 최적점에서 '등식'으로 성립하는 경우, 결합이라고 한다. 목적 함수의 값을 개선하더라도 해당 제약 조건의 방향으로 점을 변경할 수 없기 때문이다.
* 부등식 제약 조건이 최적점에서 '엄격한 부등식'으로 성립하는 경우(즉, 등식으로 성립하지 않는 경우), 비결합이라고 한다. 최적화하는 것이 아니더라도 해당 제약 조건의 방향으로 점을 변경할 수 있기 때문이다. 볼록 최적화와 같은 특정 조건에서는, 비결합 제약 조건이 없어도 최적화 문제는 동일한 해를 갖는다.
* 주어진 점에서 제약 조건이 충족되지 않으면, 해당 점은 실현 불가능이라고 한다.

2.1. 목적 함수 (Objective Function)

최소화하거나 최대화하고자 하는 함수를 의미한다. 손실 함수(Loss Function) 또는 비용 함수(Cost Function)라고도 불린다.

다음은 최적화 문제의 한 예이다.

: $\min f(\mathbf x) = x_1^2+x_2^4$

여기서 $\mathbf x$ 는 벡터 (x₁, x₂)를 나타낸다. 위의 식에서 첫 번째 줄은 최소화할 함수(목적 함수, 손실 함수 또는 비용 함수)를 정의한다.

2.2. 제약 조건 (Constraints)

제약 조건은 해가 만족시켜야 하는 조건들을 의미한다.

* 등식 제약 조건 (Equality Constraints): 반드시 등식으로 성립해야 하는 제약 조건이다.
* 부등식 제약 조건 (Inequality Constraints): 부등식으로 표현되는 제약 조건이다.

제약 조건이 있는 최적화 문제의 예시는 다음과 같다.

: $\min f(\mathbf x) = x_1^2+x_2^4$

제약 조건:

: $x_1 \ge 1$

그리고

: $x_2 = 1,$

여기서 $\mathbf x$ 는 벡터 (x₁, x₂)를 나타낸다.

위 예시에서 첫 번째 줄은 최소화할 함수(목적 함수)를 정의한다. 두 번째 및 세 번째 줄은 두 가지 제약 조건을 정의하며, 그 중 첫 번째는 부등식 제약 조건이고 두 번째는 등식 제약 조건이다. 이 두 제약 조건은 하드 제약 조건으로, 반드시 충족되어야 한다.

제약 조건이 없으면 해는 (0,0)이 되며, 여기서 $f(\mathbf x)$ 는 가장 낮은 값을 갖는다. 그러나 이 해는 제약 조건을 충족하지 않는다. 위에 제시된 제약 최적화 문제의 해는 $\mathbf x = (1,1)$ 이며, 두 제약 조건을 모두 충족하는 $f(\mathbf x)$ 의 가장 작은 값을 갖는 점이다.

2.3. 결합 제약 조건 (Binding Constraints)

부등식 제약 조건이 최적점에서 '등식'으로 성립하는 경우, 제약 조건은 결합이라고 한다. 목적 함수의 값을 개선하더라도 해당 제약 조건의 방향으로 점을 변경할 수 없기 때문이다.

2.4. 비결합 제약 조건 (Non-binding Constraints)

부등식 제약 조건이 최적점에서 '엄격한 부등식'으로 성립하는 경우(즉, 등식으로 성립하지 않는 경우), 제약 조건은 비결합이라고 한다. 왜냐하면, 최적화하는 것이 아니더라도 해당 제약 조건의 방향으로 점을 변경할 수 있기 때문이다. 볼록 최적화와 같은 특정 조건에서는, 제약 조건이 비결합인 경우, 해당 제약 조건이 없어도 최적화 문제는 동일한 해를 갖는다.

2.5. 실현 불가능 (Infeasible)

주어진 점에서 제약 조건이 충족되지 않는 경우, 해당 점은 실현 불가능이라고 한다.

2.6. 실현 가능 영역 (Feasible Region)

모든 제약 조건을 만족하는 해들의 집합을 실현 가능이라고 한다.

3. 강제 제약 조건과 유연 제약 조건

문제에서 제약 조건을 반드시 충족해야 한다면, 그러한 제약 조건을 강제 제약 조건이라고 부른다. 그러나 유연한 제약 만족 문제처럼 특정 제약 조건을 충족하는 것이 권장되지만 필수는 아닌 경우도 있다. 이러한 비필수 제약 조건은 약한 제약 조건이라고 한다.

3.1. 강제 제약 조건 (Hard Constraints)

이 예에서 첫 번째 줄은 최소화할 함수(목적 함수, 손실 함수 또는 비용 함수라고 함)를 정의한다. 두 번째 및 세 번째 줄은 두 가지 제약 조건을 정의하며, 그 중 첫 번째는 부등식 제약 조건이고 두 번째는 등식 제약 조건이다. 이 두 제약 조건은 하드 제약 조건으로, 반드시 충족되어야 함을 의미하며, 이는 후보 해의 실행 가능 집합을 정의한다.

문제에서 제약 조건을 반드시 충족해야 한다면, 그러한 제약 조건을 강제 제약 조건이라고 부른다.

3.2. 유연 제약 조건 (Soft Constraints)

만약 문제에서 제약 조건을 반드시 충족해야 하는 것은 아니지만, 충족되면 더 좋은 해로 간주되는 경우가 있는데, 이러한 제약 조건을 유연 제약 조건이라고 부른다. 이러한 유연 제약 조건은 선호 기반 계획에서 주로 사용된다. MAX-CSP 문제에서는 여러 제약 조건을 위반할 수 있으며, 해의 품질은 충족된 제약 조건의 수로 측정된다.

4. 전역 제약 조건 (Global Constraints)

전역 제약 조건은 여러 변수 간의 특정 관계를 전체적으로 나타내는 제약 조건이다. 어떤 전역 제약 조건은 더 간단한 언어의 원자 제약 조건의 결합으로 다시 쓸 수 있지만, 다른 전역 제약 조건은 제약 조건 프레임워크의 표현력을 확장한다. 이러한 경우, 전역 제약 조건은 일반적으로 조합 문제의 전형적인 구조를 포착한다.

전역 제약 조건은 제약 만족 문제의 모델링을 단순화하고, 제약 조건 언어의 표현력을 확장하며, 제약 해결을 개선하는 데 사용된다. 변수를 전체적으로 고려함으로써 해결 과정에서 실행 불가능한 상황을 더 빨리 확인할 수 있기 때문이다. 많은 전역 제약 조건이 [https://sofdem.github.io/gccat/ 온라인 카탈로그]에 참조되어 있다.

4.1. Alldifferent 제약 조건

전역 제약 조건은 여러 변수에 대한 특정 관계를 전체적으로 나타내는 제약 조건이다. 그중 일부는 `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$ 의 결합과 의미론적으로 동일하다.

4.2. 정규 제약 조건 (Regular Constraint)

정규 제약 조건은 변수 시퀀스가 결정적 유한 오토마톤에 의해 허용됨을 나타내는 제약 조건이다.

5. 예시

다음은 간단한 최적화 문제이다.

: $\min f(\mathbf x) = x_1^2+x_2^4$

제약 조건:

: $x_1 \ge 1$

그리고

: $x_2 = 1,$

여기서 $\mathbf x$ 는 벡터 (x₁, x₂)를 나타낸다.

이 예에서 첫 번째 줄은 최소화할 함수(목적 함수, 손실 함수 또는 비용 함수라고도 함)를 정의한다. 두 번째 및 세 번째 줄은 두 가지 제약 조건을 정의하며, 그 중 첫 번째는 부등식 제약 조건이고 두 번째는 등식 제약 조건이다. 이 두 제약 조건은 하드 제약 조건으로, 반드시 충족되어야 함을 의미하며, 이는 후보 해의 실행 가능 집합을 정의한다.

제약 조건이 없으면 해는 (0, 0)이 되며, 여기서 $f(\mathbf x)$ 는 가장 낮은 값을 갖는다. 그러나 이 해는 제약 조건을 충족하지 않는다. 위에 제시된 제약 최적화 문제의 해는 $\mathbf x = (1,1)$ 이며, 두 제약 조건을 모두 충족하는 $f(\mathbf x)$ 의 가장 작은 값을 갖는 점이다.