Efficient curve fitting algorithms and their computational complexity.

This area involves development, implementation and testing of efficient algorithms for obtaining solutions to a class of curve fitting problems.  Given n data points or measurements, the problem is to find a best fit by n numbers which satisfy certain restrictions such as isotonicity, convexity, quasi-convexity.  Sometimes the condition of integrality may be imposed on the numbers.  Various distance functions are used as a measure of the distance between the data points and a best fit.  Algorithms to be developed for computing a best fit are inherently finite and have a definite mathematical content in their analysis.   Emphasis is placed on algorithms whose computational complexity can be determined and where this complexity shows that the algorithm is efficient.  When a best fit is not unique, the algorithm is designed to find one best fit which is least sensitive to perturbations of data.  Two examples of practical significance, isotonic and convex regression, are special cases of this problem.  These problems have applications to engineering, production, economics and statistical estimation.  There is a considerable literature on these problems.

In the past, whenever possible, these problems were formulated as linear and nonlinear programming problems and available mathematical programming algorithms were used.  This approach turned out to be rather slow.  This necessitated investigation of alternative methods for solution.  The goal of this project is to develop new and efficient algorithms for which reasonable complexity arguments can be presented or to extend and modify the currently known algorithms with increased efficiency in mind.  Methods for problem analysis and algorithm design involve iteractions of computer science, optimization and approximation theory.
 

Topics in optimization and approximation theory.

These topics involve analysis of a broad class of optimization problems on function spaces which may be infinite or finite dimensional.  In the former may be included certain minimum norm problems, and in the latter, certain polynomial approximation problems.  Principal interest lies in establishing existence and characterization of optimal solutions and determining their properties.  Analysis of the extremal structure of convex sets and cones is another topic of interest.