Statistica Sinica 17(2007), 945-964

A FAST EM ALGORITHM FOR QUADRATIC

OPTIMIZATION SUBJECT TO CONVEX CONSTRAINTS

Ming Tan$^1$, Guo-Liang Tian$^1$, Hong-Bin Fang$^1$ and Kai Wang Ng$^2$

$^1$University of Maryland Greenebaum Cancer Center

and $^2$The University of Hong Kong

Abstract: Convex constraints (CCs) such as box constraints and linear inequality constraints appear frequently in statistical inference and in applications. The problems of quadratic optimization (QO) subject to CCs occur in isotonic regression, shape-restricted non-parametric regression, variable selection (via the lasso algorithm and bridge regression), limited dependent variables models, image reconstruction, and so on. Existing packages for QO are not generally applicable to CCs. Although EM-type algorithms may be applied to such problems (Tian, Ng and Tan (2005)), the convergence rate/speed of these algorithms is painfully slow, especially for high-dimensional data. This paper develops a fast EM algorithm for QO with CCs. We construct a class of data augmentation schemes indexed by a `working parameter' $r$ $(r\in{\cal R})$, and then optimize $r$ over ${\cal R}$ under several convergence criteria. In addition, we use Cholesky decomposition to reduce both the number of latent variables and the dimension, leading to further acceleration of the EM. Standard errors of the restricted estimators are calculated using a non-parametric bootstrapping procedure. Simulation and comparison are performed and a complex multinomial dataset is analyzed to illustrate the proposed methods.

Key words and phrases: Bootstrap, Cholesky decomposition, constrained optimization, convergence rate, data augmentation, EM algorithm, latent variables, working parameter.