LP형 문제

LP-type problem

알고리즘의 연구에서 LP형 문제(일반화된 선형 프로그램이라고도 함)는 특정 속성을 저차원 선형 프로그램과 공유하고 유사한 알고리즘으로 해결할 수 있는 최적화 문제다.LP형 문제에는 주어진 평면 점 집합을 포함하는 가장 작은 원을 찾는 문제와 같이 그 자체가 선형 프로그램이 아닌 중요한 최적화 문제가 많이 포함된다.문제를 정의하는 요소의 수에 선형인 시간 내에 무작위화된 알고리즘의 조합으로 문제를 해결할 수 있으며, 문제의 차원에 있어서는 보조적인 알고리즘을 조합하여 해결할 수 있다.

정의

LP형 문제는 Sharir & Welzl(1992)에 의해 원소의 유한 집합 S 입력으로 주어지는 문제, S의 부분 집합을 완전히 순서가 정해진 집합에서 값에 매핑하는 함수 f로 정의되었다.이 기능은 다음의 두 가지 주요 특성을 만족시키기 위해 필요하다.

  • 단조로움: 두 세트당 A ⊆ B ⊆ S, f(A) ≤ f(B) ≤ f(S)에 대해.
  • 지역성: 두 세트마다 A ⊆ B s S 및 S의 모든 요소 x에 대해, f(A) = f(B) = f(A ∪ {x}), f(A) = f(B { {x})이면 f(B ∪ {x}).

LP형 문제의 기본은 B형 문제의 모든 적절한 부분집합이 B형 자체보다 f의 작은 값을 갖는 속성을 가진 세트 B ⊆ S이며, LP형 문제의 치수(또는 결합 치수)는 기준의 최대 카디널리티로 정의된다.

최적화 알고리즘은 그 자체로 베이스가 되거나 하나의 요소를 기초로 하여 형성된 집합에서만 f 함수를 평가할 수 있다고 가정한다.또는 알고리즘을 두 개의 원시 연산, 즉 f(B) = f(B) = f(B ∪ {x})를 결정하는 위반 시험과 (동일한 입력으로) B ∪ {x}의 기초를 찾는 기초 계산으로 제한할 수 있다.알고리즘이 수행하는 과제는 이러한 제한된 평가 또는 원시 요소만을 사용하여 f(S)를 평가하는 것이다.

예제 및 응용 프로그램

Lp 볼

선형 프로그램은 n개의 선형 불평등 제약을 받는 d 비 음의 실제 변수의 시스템에 의해 정의될 수 있으며, 최소화할 비 음의 선형 목표 함수와 함께 정의될 수 있다.이는 S를 제약조건 집합으로 하고, f(A)를 (제약조건의 부분집합 A에 대해)를 A가 정의한 작은 선형 프로그램의 최소 목적 함수 값으로 정의함으로써 LP형 문제의 틀에 넣을 수 있다.적절한 일반적 위치 가정(여러 솔루션 포인트가 동일한 최적 목표 함수 값을 가지지 않도록 하기 위해)에 따라, 이는 LP 유형 문제의 단조성 및 위치성 요구사항을 만족하며, 변수 수 d와 동일한 조합 치수를 갖는다.[1]마찬가지로 정수 프로그램(선형 프로그램에서처럼 선형 제약 조건과 선형 목적 함수의 집합이 일치하지만 변수가 정수 값만 차지해야 한다는 추가적인 제한과 함께)은 LP형 문제의 단조성과 인접성 특성을 모두 만족하며, 동일한 일반적 위치는 a를 가정한다.s 선형 프로그램의 경우.벨(1977)과 스카프(1977)의 이론은 d 변수가 있는 정수 프로그램의 경우 결합 치수가 최대 2라는d 것을 보여준다.[1]

연산 기하학에서 많은 자연 최적화 문제는 LP 유형이다.

최소 원 문제
  • 가장 작은 원 문제는 평면에서 주어진 n개의 점 집합을 포함하는 원의 최소 반지름을 찾는 문제다.단일성(더 많은 점을 추가하면 원만 더 커질 수 있음)과 위치성(세트 A에 대한 가장 작은 원이 B와 x를 포함하는 경우, 동일한 원도 B ∪ {x}을(를) 만족한다.가장 작은 원은 항상 3개의 점들에 의해 결정되기 때문에, 가장 작은 원 문제는 2차원 유클리드 기하학을 사용하여 정의되었음에도 불구하고 조합 차원 3이 있다.[2]보다 일반적으로 d 치수의 점들을 가장 작게 감싸는 공은 결합 치수 d + 1의 LP형 문제를 형성한다.가장 작은 원 문제는 공 세트를 둘러싸는 가장 작은 공,[3] 각 공 세트에 닿거나 둘러싸는 가장 작은 공,[4] 가중치 있는 1-중심 문제,[5] 또는 브레그만 분비에 의해 정의된 거리 공간과 같은 비유클리드 공간에서 유사한 작은 둘러싸인 공 문제 등으로 일반화할 수 있다.[6]가장 작게 둘러싸인 타원체를 찾는 관련 문제도 LP형 문제지만 조합차원이 큰 d(d + 3)/2이다.[7]
  • K0, K1, ...를 d차원 유클리드 공간에서 n개의 볼록 집합의 연속체로 하고, 공통 교차점이 있는 이 순서의 가장 긴 접두사를 찾기를 원한다고 가정하자.이는 f(A) = -i, 여기서 K는i A의 교차 접두사에 속하지 않는 A의 첫 번째 멤버, f(A) = -n이 없는 경우 LP형 문제로 표현될 수 있다.이 시스템의 조합 치수는 d + 1이다.[8]
  • 축으로 정렬된 직사각형 상자 모음을 3차원 공간에 두고, 모든 상자를 절단하는 공간의 양의 옥탄트로 향하는 선을 찾기를 원한다고 가정합시다.이것은 조합 차원 4의 LP형 문제로 표현될 수 있다.[9]
  • 정점 집합으로 지정된 두 볼록 폴리탑 사이의 가장 가까운 거리를 찾는 문제는 LP형 문제로 나타낼 수 있다.이 공식에서, 세트 S는 양쪽 폴리탑에 있는 모든 정점의 집합이며, 함수 값 f(A)는 두 폴리탑에 있는 정점의 두 부분 집합 A의 볼록한 선체 사이의 가장 작은 거리를 부정하는 것이다.문제의 조합 치수는 두 개의 폴리토판이 분리되어 있는 경우 d + 1이고, 비어 있지 않은 교차점이 있는 경우 d + 2이다.[1]
  • Let S = {f0, f1, ...}은(는) 퀘이콘벡스 함수의 집합이다.그 다음 포인트별 최대값i f는i 그 자체로 퀘이콘벡스(quasiconvex)이며, maxi f의i 최소값을 찾는 문제는 LP형 문제다.최대 2d + 1에 조합 치수를 가지며, 여기서 d는 함수의 영역 치수를 가지지만, 충분히 매끄러운 기능의 경우 조합 치수는 최대 d + 1이다. 다른 많은 LP 유형 문제도 이와 같은 방법으로 퀘이콘벡스 함수를 사용하여 표현할 수 있다. 예를 들어, 가장 작은 동그라미 문제는 pr.각 기능이 주어진i 지점들 중 하나로부터 유클리드 거리를 측정하는 최대ii f의 최소화 문제.[10]

LP-type 문제도 theory,[11]유한 요소 법 meshes,[12]에 시설 위치를 해결하 꼭지점 배치를 개선한 특정 게임의 알고리즘 같은 경기에서 최적의 결과를 결정하기 위해 problems,[13]의 3차원 위치를 재구성한exponential-time 검색 algorithms,[14]의 시간 복잡도 분석한 사용되었습니다. 에서 개체ir 2차원 [15]영상

알고리즘

세이델

세이델(1991)은 LP형 문제 프레임워크에 적응할 수 있는 저차원 선형 프로그래밍 알고리즘을 제공했다.세이델의 알고리즘은 세트 S와 최적 기준에 속하는 것으로 알려진 원소의 별도 세트 X(초기적으로 비어 있음)를 입력하는 것으로 받아들인다.그런 다음 나머지 요소들을 무작위 순서로 하나씩 고려하여 각 요소에 대한 위반 테스트를 수행하고 결과에 따라 더 큰 일련의 알려진 기본 요소들을 가지고 동일한 알고리즘에 대한 재귀적 호출을 수행한다.다음과 같은 가성으로 표현할 수 있다.

S(B) ≠ f(B ∪ {x})의 임의 순열에서 함수 Seidel(S, f, f, X)은 R := x에 대한 빈 집합 B := X: if(B) ≠ f(B ∪ {x}):B := 세이델(R, f, basis(X ∪ {x}) R := R ∪ {x} 반환 B

조합 치수 d의 문제에서, 알고리즘의 반복에서 위반 시험은 x가 d - X 잔여 기본 요소 중 하나일 때만 실패하며, 최대 (d - X )/i) 확률로 발생한다.이 계산에 기초해 알고리즘에 의해 수행되는 전체 예상 위반 시험 횟수는 O(d!n)로, n 단위는 선형이지만 d 단위는 지수보다 낮음을 알 수 있다.

클락슨

클락슨(1995)은 무작위 샘플링 기법에 기초한 선형 프로그래밍을 위해 재귀 알고리즘과 반복 알고리즘이라는 두 개의 알고리즘을 정의하고, 재귀 알고리즘에서 반복 알고리즘을 호출하는 두 알고리즘의 조합을 제안한다.재귀 알고리즘은 크기가 입력 크기의 대략 제곱근인 무작위 샘플을 반복적으로 선택하고, 샘플링된 문제를 반복적으로 해결한 다음 위반 테스트를 사용하여 적어도 하나 이상의 기본 요소를 포함해야 하는 나머지 요소의 하위 집합을 찾는다.

함수 반복(S, f)은 X := 빈 세트 반복 R := 크기 d√n B :=R ∪ X의 기초가 되는 S의 임의 부분 집합 R := 재귀적으로 계산된 V := {x f(B) ∪ f(B x {x})} X := X ∪ V가 빈 리턴 B가 될 때까지 X ∪ V.

각 반복에서 V의 예상 크기는 O(√n)이며,[16] V가 비어 있지 않을 때마다 S의 최종 기초에 적어도 하나의 새로운 요소를 포함한다.따라서 알고리즘은 최대 반복으로 수행되며, 각각의 반복은 n개의 위반 테스트를 수행하고 O(d√n) 크기의 하위 문제에 대한 단일 재귀 호출을 수행한다.

클락슨의 반복 알고리즘은 S의 각 요소에 가중치를 부여하는데, 처음에는 모두 동일하다.그런 다음 무작위로 S로부터 9d2 원소의 세트 R을 선택하고, 이전 알고리즘에서와 같이 세트 B와 V를 계산한다.V의 총 중량이 S의 총 중량의 최대 2/(9d - 1)배인 경우 알고리즘은 V의 모든 원소의 중량을 두 배로 증가시키고, V가 비워질 때까지 이 과정을 반복하기 전과 같이 이 과정을 반복한다.각 반복에서 최적 기준의 중량은 S의 총 중량보다 더 큰 비율로 증가한다는 것을 보여줄 수 있으며, 이 경우 알고리즘은 O(log n) 반복 내에서 종료되어야 한다.

재귀 알고리즘을 사용하여 주어진 문제를 해결하고, 재귀 호출에 대한 반복 알고리즘으로 전환한 다음, 반복 알고리즘에 의한 호출에 대한 세이델의 알고리즘으로 다시 전환함으로써, O(dn + dO(1)! d log n) 위반 테스트를 이용하여 주어진 LP형 문제를 해결할 수 있다.

선형 프로그램에 적용하면 이 알고리즘은 이중 단순화 방법으로 해석할 수 있다.[17]위반 테스트 및 기본 계산 원시 요소 이외의 특정 추가 계산 원시 요소에서는 이 방법을 결정론적으로 만들 수 있다.[18]

마투셰크, 샤리르, 웰즐

마투셰크, 샤리르 & 웰즐(1996)은 다른 LP형 문제에서 항상 보유하지 않는 선형 프로그램의 추가 속성을 사용하는 알고리즘을 설명하며, 모든 베이스가 서로 동일한 카디널리티를 갖는다고 한다.LP형 문제가 이 속성을 가지고 있지 않은 경우, d 새로운 더미 요소를 추가하고 함수 f를 수정하여 이전 값 f(A)와 숫자 min(d, A)의 순서 쌍을 사전 편찬 방식으로 반환하도록 할 수 있다.

마투셰크, 샤리르 & 웰즐(1996)은 한 번에 하나씩 S의 원소를 추가하거나 원소 샘플을 찾기보다는 한 번에 하나씩 원소를 제거하는 알고리즘을 설명한다.각 단계에서 초기에는 더미 요소 집합이 될 수 있는 기초 C를 유지한다.다음과 같은 가성으로 설명할 수 있다.

함수 msw(S, f, C)는 S = C이면 반환 C는 S \ C = msw(S \ x, f, C)의 임의 요소 x를 선택하고 f(B) ≠ f(B ∪ {x})를 반환하면 B := b(B ∪ {x}) :=msw(S, f, B)를 반환하는 것이다.

알고리즘의 대부분의 재귀 호출에서 위반 테스트가 성공하고 if 문을 건너뛰게 된다.그러나 작은 확률로 위반 테스트가 실패하고 알고리즘은 추가 기본 계산을 한 다음 추가 재귀 호출을 한다.저자들이 보여주듯이 알고리즘에 대한 기대 시간은 n으로 선형이고 d log n의 제곱근은 지수적이다.이 방법을 클락슨의 재귀적 및 반복적 절차와 결합하면 이 두 가지 형태의 시간 의존성이 서로 분리될 수 있어 외부 재귀적 알고리즘에서 O(dn) 위반 시험을 수행하는 알고리즘과 알고리즘 하위 레벨 d의 d log d의 제곱근에서 지수적인 숫자를 얻을 수 있다.[19]

변형

특이치를 사용한 최적화

마투셰크(1995)는 설정된 S 및 목표함수 f와 함께 숫자 k가 주어지는 LP형 최적화 문제의 변형을 고려한다. 과제는 나머지 세트의 객관적 기능을 가능한 한 작게 만들기 위해 S에서 k 요소를 제거하는 것이다.예를 들어, 가장 작은 원 문제에 적용할 때, 이것은 주어진 평면 점 집합의 k를 제외한 모든 것을 포함하는 가장 작은 원을 제공할 것이다.그는 모든 비감속 LP형 문제(즉, 모든 베이스가 구별되는 값을 갖는 문제)에 대해 이 문제는 S의 서브셋에 의해 정의된 O(kd) LP형 문제 집합을 해결함으로써 O(nkd) 시간 내에 해결될 수 있음을 보여준다.

암묵적 문제

일부 기하학적 최적화 문제는 LP형식의 요소 수가 최적화 문제에 대한 입력 데이터 값의 수보다 유의하게 큰 LP형 문제로 표현될 수 있다.예를 들어, 평면에 있는 점들의 집합(각각 등속도로 이동)을 고려하십시오.어느 시점에서든 이 시스템의 직경은 두 지점 사이의 최대 거리다.지름이 최소화된 시간을 찾는 문제는 O(n2) 퀘이콘벡스 함수의 점 최대값을 각 점 쌍에 하나씩 최소화하는 것으로 공식화할 수 있으며, 시간 함수로서 쌍 사이의 유클리드 거리를 측정할 수 있다.따라서 O(n2) 요소 집합에서 조합 차원 2의 LP형 문제로 해결할 수 있지만, 이 집합은 입력점 수보다 상당히 크다.[20]

Chan(2004)은 일부 상수 k에 대해 각 LP형 요소가 입력값의 k-tuple에 의해 결정되는 것과 같이 암묵적으로 정의된 LP형 문제를 해결하기 위한 알고리즘을 설명한다.그의 접근법을 적용하기 위해서는 주어진 LP형 기준 B에 대해 B가 S에 의해 결정된 LP형 문제의 기준인지 여부를 결정하고 n개의 입력값 S를 설정할 수 있는 의사결정 알고리즘이 존재해야 한다.

Chan의 알고리즘은 다음 단계를 수행한다.

  • 입력 값 수가 일부 임계값 미만일 경우, 결정되는 LP 유형 요소 집합을 찾아 결과적으로 발생하는 명시적 LP 유형 문제를 해결하십시오.
  • 그렇지 않으면 입력 값을 같은 크기의 하위 집합 S의i k보다 큰 적절한 숫자로 분할하십시오.
  • 만약 f가 암묵적으로 정의된 LP형 문제를 해결하기 위한 객관적 함수라면, 서브셋i S의 컬렉션을 컬렉션의 유니언에 있는 f 값에 매핑하는 함수 g를 정의한다.그런 다음 서브셋 S와i 객관적 함수 g 자체의 집합은 해결해야 할 암묵적 문제와 동일한 차원의 LP형 문제를 정의한다.
  • 위반 시험의 선형 횟수와 다변량 기준 평가를 수행하는 클락슨의 알고리즘을 사용하여 g가 정의한 (명확한) LP형 문제를 해결한다.g에 대한 기본 평가는 Chan의 알고리즘에 대한 재귀적 호출을 통해 수행할 수 있으며, 위반 시험은 의사결정 알고리즘에 대한 호출을 통해 수행할 수 있다.

결정 알고리즘이 입력 크기 n의 함수로 적어도 다항식으로 성장하는 O(T(n)) 시간이 걸린다는 가정 하에 Chan은 명시적 LP 제형으로 전환하기 위한 임계값과 파티션의 서브셋 수를 암묵적 LP형 최적화 알고리즘도 실행할 수 있는 방법으로 선택할 수 있음을 보여준다.s 시간 O(T(n)).

예를 들어, 이동 지점의 최소 직경의 경우, 결정 알고리즘은 회전 캘리퍼스 기법을 사용하여 O(n log n) 시간에 해결할 수 있는 문제인, 정해진 시간에 점 집합의 직경을 계산하기만 하면 된다.따라서 Chan의 지름이 최소화된 시간을 찾기 위한 알고리즘도 O(n log n) 시간이 걸린다.Chan은 시간 O(nd − 1 + n log n)에서 d차원 유클리드 공간에서 주어진 n개의 점 집합 중에서 최대 Tukey 깊이의 점을 찾기 위해 이 방법을 사용한다.브라흐, 하인리히-리탄 & 모린(2003)이 볼록한 다각형의 균일한 분포에 대해 최대의 투키 깊이의 점을 찾기 위해 비슷한 기법을 사용하였다.

역사 및 관련 문제

선형 프로그래밍을 위한 선형 시간 알고리즘의 발견과 많은 경우에 동일한 알고리즘이 선형 프로그램이 아닌 기하학적 최적화 문제를 해결하는 데 사용될 수 있다는 관찰은 적어도 3변수 선형 프로그램과 가장 작은 선형 프로그램에 대해 선형 기대 시간 알고리즘을 부여한 메가도(1983, 1984년)에게 거슬러 올라간다.동그라미 문제그러나 메가도는 집합체 시스템의 추상적인 문제라기 보다는 볼록 최적화 문제로서 조합적으로 선형 프로그래밍의 일반화를 공식화하였다.마찬가지로, Dyer(1986)와 Clarkson(1988년 Clarkson 1995년 컨퍼런스 버전에서)은 그들의 방법이 선형 프로그램뿐만 아니라 볼록 프로그램에도 적용될 수 있다고 관찰했다.Dyer(1992)는 최소 둘러싸인 타원체 문제도 소수의 비선형 구속조건을 추가함으로써 볼록 최적화 문제로 공식화될 수 있다는 것을 보여주었다.저차원 선형 프로그래밍 및 관련 문제의 시간 범위를 개선하기 위한 무작위화의 사용은 클락슨과 데이어 앤 프리제(1989년)에 의해 개척되었다.

국소성과 단조성의 공리를 만족시키는 기능의 측면에서 LP형 문제의 정의는 샤리르 & 웰즐(1992)에서 나왔지만, 같은 시기에 다른 저자들은 선형 프로그램의 대체 결합 일반화를 공식화했다.예를 들어 게르트너(1995)가 개발한 프레임워크에서 함수 f는 S의 하위 집합에 대한 총 오더로 대체된다.LP형 문제에서 타이를 깨서 총주문을 만드는 것은 가능하지만 결합차원이 증가해야 한다.[21]또한, LP형 문제에서와 같이, 게르트너는 원소의 하위 집합에 대한 연산을 수행하기 위한 특정 원시성을 정의하지만, 그의 공식화에는 결합 치수의 아날로그가 없다.

는 하이퍼 큐브의 속성은 하이퍼 큐브(얼굴처럼 그 모든 하이퍼 큐브를 포함한)의 모든 얼굴은 독특한 싱크 대위에 꼭지점들이 가장자리가 둘 다 선형 프로그램과 선형 상호 보완성 문제의 또 다른 추상적 일반화, Stickney &amp에 의해 공식화된, 왓슨(1978년)과 나중에 여러 다른 작가들에 의해 공부한 우려 방향.재치외향적인 가장자리가 없다.이 유형의 방향은 해당 정점이 인접한 경우 및 인접한 경우에만 두 개의 서브셋이 서로 다른 방식으로 하이퍼큐브의 정점에 S의 서브셋을 대응하고, f(A) ≠ f(B)를 향한 인접 설정 A ⊆ B와 다른 W를 향한 가장자리 방향을 조정하여 LP형 문제로부터 형성될 수 있다.결과 방향은 그것이 지시된 ACyclick 그래프를 형성하는 추가적인 속성을 가지고 있는데, 여기서 무작위화된 알고리즘이 n의 제곱근에서 지수화된 다수의 단계에서 전체 하이퍼큐브의 고유한 싱크(LP형 문제의 최적 기반)를 찾을 수 있다는 것을 보여줄 수 있다.[22]

보다 최근에 개발된 위반자 공간의 골격은 모든 LP형 문제는 위반자 공간에 의해 모델링될 수 있지만 반드시 그 반대는 아니라는 점에서 LP형 문제를 일반화한다.위반자 공간은 LP형 문제와 유사하게 정의되는데, 객관적인 함수 값에 세트를 매핑하는 함수 f에 의해 정의되지만 f의 값은 순서가 정해지지 않는다.순서가 없음에도 불구하고 모든 S세트는 LP형 문제에 대한 클락슨의 알고리즘의 변화로 발견할 수 있는 베이스 세트(전체 세트와 동일한 값을 갖는 최소 세트)가 잘 정의되어 있다.실제로, 위반자 공간은 클락슨의 알고리즘으로 해결할 수 있는 시스템을 정확하게 특징짓는 것으로 나타났다.[23]

메모들

  1. ^ a b c 마투셰크, 샤리르 & 웰즐(1996년).
  2. ^ 비록 가장 작은 원문제는 처음에는 마투셰크, 샤리르 & 웰즐(1996)에 의해 LP형 문제로 언급되었지만, 몇몇 초기의 논문들은 메기도(1983년)와 웰즐(1991년)을 포함한 저차원 선형 프로그래밍의 아이디어를 바탕으로 이 문제에 대한 알고리즘을 기술했다.
  3. ^ 피셔&게르트너(2004년).
  4. ^ 뢰플러&반 크레벨드(2010년)
  5. ^ 다이어(1986년).
  6. ^ 닐슨 & 노크(2008).
  7. ^ 마투셰크, 샤리르 & 웰즐(1996);웰즐(1991년).
  8. ^ 찬(2004년).
  9. ^ 아멘타(1994년).
  10. ^ 아멘타, 베른&엡스타인(1999년), 엡스타인(2005년).
  11. ^ 할만(2007년).
  12. ^ 아멘타, 베른&엡스타인(1999년).
  13. ^ 푸에르토리코, 로드리게스-치아 & 타미르(2010년).
  14. ^ 엡스타인(2006년).
  15. ^ 리(2007)
  16. ^ V의 크기에 대한 꼬리 경계도 알려져 있다: Gaertner & Welzl(2001)을 참조하라.
  17. ^ 칼라이(1992년).
  18. ^ 샤젤 & 마투셰크(1996년).
  19. ^ 마투셰크, 샤리르 & 웰즐(1996년).선형 프로그래밍에 대한 매우 유사한 시간 제한도 칼라이(1992)에 의해 주어졌다.
  20. ^ 이 문제의 LP형식은 Chan(2004)에 의해 제시되었지만, 일찍이 Gupta, Janardan & Smid(1996)에 의해 다른 알고리즘 방법을 사용하여 연구되었다.성룡은 또한 클락슨이 O(n log n) 시간 알고리즘에 대해 미발표 원고를 인용하며, 암묵적 LP형 접근법으로 달성할 수 있는 시간과 일치한다.
  21. ^ 마투셰크(2009년).
  22. ^ 사보 & 웰즐(2001년).
  23. ^ 게르트너 외 (2008);Brise & Gaertner(2011).

참조