연속 시뮬레이션 최적화에서의 동시 근사 최적 영역 식별: 미니맥스 복잡도 및 적응형 샘플링

시뮬레이션 최적화는 일반적으로 단일 추정된 최적 지점을 반환합니다. 그러나 결정이 자원 비용과 같이 시뮬레이션과는 독립적으로 평가되는 기준에 의존하는 경우, 의사결정자는 대신 기대 성능이 최적값의 허용 오차 범위 내에 있는 설계들의 집합을 필요로 하며, 종종 트레이드오프를 살펴본 후에만 이 허용 오차를 선택합니다. 우리는 연속적인 설계 공간에서 이러한 근사 최적 영역들을, 주어진 최대 $T$까지 모든 허용 오차에 대해 동시에 식별하는 방법을 연구하며, 이때 영역 추정 오차는 $\eta$ 이하입니다. 우리는 영역 식별이 최적화의 부산물이 아님을 보여줍니다. 구체적으로, $\alpha>\nu$일 때, 심지어 최적 설계를 미리 주어진 경우에도, 임의의 절차는 최소한 $\Omega\bigl(\eta^{-(2+d/\nu)}\min{1,KT^{d/\alpha}}\bigr)$개의 시뮬레이션 평가를 필요로 합니다. 여기서 $d$는 차원(dimension), $\nu$는 매끄러움(smoothness)을 나타내고, $(K,\alpha)$는 근사 최적 설계의 기하학적 구조를 설명하는 커버링 파라미터입니다.

우리는 SASORI를 제안하며, 이는 동일한 평가로부터 추정된 최적 지점과 모든 허용 오차에 대한 영역들을 반환하여 이 하한 경계와 로그 인자를 제외하고 일치합니다. SASORI는 또한 영역 추정 오차와 누적 후회(cumulative regret) 사이의 최적 트레이드오프를 달성하며, 허용 오차가 0일 때 미니맥스-최적 시뮬레이션 최적화 절차로 축소됩니다.

수치 실험은 우리가 제안한 방법의 효과성을 보여줍니다.