TitleOptimization models for shape-constrained function estimation problems involving nonnegative polynomials and their restrictions
NamePapp, Dávid (author), BEN-ISRAEL, ADI (chair), Alizadeh, Farid (internal member), Ruszczynski, Andrzej (internal member), Eckstein, Jonathan (internal member), Prekopa, Andras (internal member), Vizvari, Bela (outside member), Rutgers University, Graduate School - New Brunswick,
DescriptionIn this thesis function estimation problems are considered that involve constraints on the shape of the estimator or some other underlying function. The function to be estimated is assumed to be continuous on an interval, and is approximated by a polynomial spline of given degree. First the estimation of univariate functions is considered under constraints that can be represented by the nonnegativity of affine functionals of the estimated function. These include bound constraints, monotonicity, and convexity constraints. A general framework is presented in which arbitrary combination of such constraints can be modeled and handled in a both theoretically and practically efficient manner, using semidefinite programming. The approach is illustrated by a variety of applications in statistical estimation. Numerical results are compared to those obtained using methods previously proposed in the statistical literature. Next, multivariate problems are considered. Shape constraints that are tractable in the univariate case are intractable in the multivariate setting. Hence, instead of following the univariate approach, polyhedral and spectrahedral (semidefinite) approximations are proposed, which are obtained by replacing nonnegative splines by piecewise weighted-sum-of-squares polynomial splines. A decomposition method for solving very large scale multivariate problems is also investigated. In order to include more constraints in the same unified framework, the notion of weighted-sum-of-squares functions is generalized to weighted-sum-of-squares cones in finite-dimensional real linear spaces endowed with a bilinear multiplication. It is shown that such cones are semidefinite representable, and the representation is explicitly constructed. Finally, seeking a method to circumvent the use of semidefinite programming in the solution of optimization problems over nonnegative and weighted-sum-of-squares polynomials, we study the conditions of optimality, as well as barrier functions in such optimization problems. For univariate polynomials, a method based on fast Fourier transform is provided that accelerates the evaluation of the logarithmic barrier function (and its first two derivatives) of the moment cone. This reduces the running time of some interior point methods for semidefinite programming from O(n^6) to O(n^3) when solving problems involving polynomial nonnegativity constraints.
NoteIncludes bibliographical references
Noteby Dávid Papp
CollectionGraduate School - New Brunswick Electronic Theses and Dissertations
Organization NameRutgers, The State University of New Jersey
RightsThe author owns the copyright to this work.