An extension of the mixed primal-dual bases algorithm to the case of more constraints than dimensions

The problem of minimizing a quadratic function with linear inequality constraints is considered with applications to nonparametric regression with shape assumptions. For many problems, the set defined by the constraints is a closed convex cone. The mixed primal-dual bases algorithm (Fraser and Massam, 1989, Scand, J. Statist. 16, 65-75) for regression under inequality constraints finds a least-squares regression estimate over such a cone in a finite number of steps, with the restriction that the number of constraints does not exceed the number of dimensions in the space. Some applications, however, require more constraints than dimensions, and the main purpose of this payer is to extend the algorithm to this more general case. Properties of the constraint cone and its polar cone are presented in the generality necessary in this situation. One surprising result is that the number of generators of the constraint cone can be much larger than the number of generators for the polar cone. Applications are presented for least-squares regression, and regression in which a roughness penalty term is included in the function to minimize. (C) 1999 Elsevier Science B.V. All rights reserved.