Solving Ellipsoidal Inclusion And Optimal Experimental Design Problems: Theory And Algorithms.
This thesis is concerned with the development and analysis of Frank-Wolfe type algorithms for two problems, namely the ellipsoidal inclusion problem of optimization and the optimal experimental design problem of statistics. These two problems are closely related to each other and can be solved simultaneously as discussed in Chapter 1 of this thesis. Chapter 1 introduces the problems in parametric forms. The weak and strong duality relations between them are established and the optimality criteria are derived. Based on this discussion, we define -primal feasible and -approximate optimal solutions: these solutions do not necessarily satisfy the optimality criteria but the violation is controlled by the error parameter can be arbitrarily small. Chapter 2 deals with the most well-known special case of the optimal experimental design problems: the D-optimal design problem and its dual, the Minimum-Volume Enclosing Ellipsoid (MVEE) problem. Chapter 3 focuses on another special case, the A-optimal design problem. In Chapter 4 we focus on a generalization of the optimal experimental design problem in which a subset but not all of parameters is being estimated. We focus on the following two problems: the Dk -optimal design problem and the Ak -optimal design problem, generalizations of the D-optimal and the A-optimal design problems, reand spectively. In each chapter, we develop first-order algorithms for the respective problem and discuss their global and local convergence properties. We present various initializations and provide some computational results which confirm the attractive features of the first-order methods discussed. Chapter 5 investigates possible combinatorial extensions of the previous problems. Special attention is given to the problem of finding the MinimumVolume Ellipsoid (MVE) estimator of a data set, in which a subset of a certain size is selected so that the minimum-volume ellipsoid enclosing these points has the smallest volume. We discuss how the algorithms in Chapter 2 can be adapted in order to attack this problem. Many efficient heuristics and a branchand-bound algorithm are developed.
dissertation or thesis