A fast em algorithm for quadratic optimization subject to Convex constraints

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 ε R), and then optimize r over 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.