Algorithms for computing D-optimal designs

Abstract

Finding analytical solution for a locally D-optimal design of non-linear models is a difficult problem even for a relatively simple model. A number of numerical methods for computing D-optimal designs have been proposed but few exhibited satisfying speed with theoretical convergence at the same time. In this thesis, we compare two algorithms, particle swarm optimization (PSO) and second-order cone programming (SOCP) for computing locally D-optimal design. PSO is a heuristic algorithm capable of finding optimal design points and weights simultaneously, but lacks the theoretical guarantee of convergence toward an optimal design. SOCP is a convex optimization method that is guaranteed to find the optimal design weights for discretized design points. We demonstrate that PSO often fails to reproduce known D-optimal designs for non-linear models consistently, and propose an SOCP-based algorithm for k-point design in which at most k design points are selected among a large number of candidate points. We show that this SOCP-based method is competent in computing D-optimal designs compared to PSO, in terms of both speed and accuracy.

비선형 모형에 대한 국소 D-최적실험설계를 해석적으로 구하는 것은 비교적 간단한 모형에 대해서도 쉽지 않다고 알려져 있다. D-최적실험설계를 구하기 위한 여러 수치적 방법들이 제안되어 왔지만, 그 중 이론적인 수렴 성질과 준수한 연산 속도를 동시에 지니는 방법은 많지 않았다. 이 논문에서는 국소 D-최적실험설계를 찾는 두 개의 알고리즘, 입자 군집 최적화와 이차원추계획법을 비교한다. 입자 군집 최적화는 직관적인 아이디어에 기반을 둔 알고리즘으로 최적 설계 지점과 가중치를 동시에 구할 수 있지만, 최적 설계로 수렴하는 것이 이론적으로 보장되지 않는다. 반면, 이차원추계획법은 이산형 설계 공간에 대해 최적 가중치를 찾을 수 있는 볼록 최적화 방법이다. 이 논문에서는 D-최적실험설계가 알려져 있는 비선형 모형들에 대해 입자 군집 최적화가 최적 설계를 찾지 못하는 경우가 종종 있음을 보이고, 설계 후보 지점 중 최대 k 개 지점에 대해서만 양의 가중치를 갖도록 하는 이차원추계획법 기반 k-점 설계 알고리즘을 제안하였다. 나아가, 이차원추계획법에 기반을 둔 방법들이 입자 군집 최적화와 비교해 속도와 정확도 모두에서 경쟁력을 지니고 있음을 검증하였다.