반전 설정

In mathematics, set inversion is the problem of characterizing the preimage X of a set Y by a function f, i.e., X = f ⁻¹(Y ) = {x ∈ Rⁿ f(x) ∈ Y }. It can also be viewed as the problem of describing the solution set of the quantified constraint "Y(f (x))", where Y( y) is a constraint, e.g. an inequality, describing the set Y.

대부분의 애플리케이션에서 f는 R에서ⁿ R까지의^p 함수이며, 세트 Y는 R의^p 상자(즉, R의 p 간격의 데카르트 제품)이다.

f가 비선형일 경우 분기 및 바인딩 알고리즘과 결합된 구간 분석을 사용하여 설정 반전 문제를 해결할^[1] 수 있다.^[2]

주요 아이디어는 겹치지 않는 박스로 만든 R^p 포장을 만드는 것이다.각 상자[x]에 대해 다음 테스트를 수행하십시오.

1. f ([x]) ⊂ Y인 경우, 우리는 [x] ⊂ X;
2. f ([x]) ∩ Y = ∅이면, 우리는 [x] ∩ X = ∅;
3. 그렇지 않으면 상자 [x]는 폭이 주어진 정밀도보다 작은 경우를 제외하고 이등분된다.

두 개의 첫 번째 테스트를 확인하기 위해서는 f에 대한 간격 확장 (또는 포함 함수)[f ]이 필요하다.분류된 박스는 하위 패빙(즉, 겹치지 않는 박스의 결합)에 저장된다.이 알고리즘은 계약자에 의한 포함 시험을 대체함으로써 보다 효율적으로 만들 수 있다.

예

X = f ⁻¹([4,9]) 세트 여기서 f(x₁, x₂) = x + x가²
₁ 그림에²
₂ 표시된다.

예를 들어, [-2,1]² + [4,5]² = [0,4] + [16,25] = [16,29]가 구간[4,9]을 교차하지 않기 때문에 [-2,1] × [4,5] 상자는 X 밖에 있다고 결론짓는다.[-1,1]² + [2,455]² = [0,1] + [4,5] = [4,6]이 [4,9] 안에 있으므로 [-1,1] × [2,455] 전체 상자가 X 안에 있다고 결론짓는다.

적용

Set inversion은 주로 경로 계획, 비선형 매개변수 집합 추정,^[3][4] 국산화^[5][6] 또는 선형 동적 시스템의 안정성 영역의 특성화에 사용된다.^[7]

참조