Optimization Over Positive or Sum-of-Square Functions with Applications to Constrained Approximation and Shape Constrained Learning

这个项目的主要焦点将是现代和复杂的最优化理论在有约束的统计学习、回归和密度估计问题上的应用。要研究的函数约束类都将涉及基础函数的某个区域或其某个线性泛函的非负性。无论是单变量还是多变量病例，都将得到彻底调查。约束估计问题的研究将在几个函数空间中进行，包括单变量情况下的多项式、多项式样条、小波和更一般的Chebychev系统，以及多变量情况下的多项式、小波和样条。特别是，将探索非负性约束的近似的各种策略。这类问题的主要工具是一般的凸锥优化模型，如半定规划和二阶锥规划。将形状约束和非负约束转化为二次曲线优化问题，并在可能的情况下，开发出具有良好理论和数值性能的高效内点算法。在多元情形下，内斯特罗夫关于平方和函数的半定规划特征将被用作建立多元估计和学习问题的方法的基础。观察到上述最抽象形式的显式问题相当于在某些定义良好的闭线性函数空间中搜索非负函数的锥体，例如具有显式正交基的Soblev-Hilbert空间，并从这种基的有限子集开始，通过添加更多的基的元素来逐次精化逼近，直到达到期望的精度。然而，在每个近似有限维空间中选择哪个非负锥序列是非常重要的，这一问题将被深入研究。两个有趣的理论问题与本项目将研究的约束学习和估计问题有关。一个问题是哪些锥体具有双线性互补条件。在对称锥类(包括半正定矩阵和二阶锥)之外，将研究此类锥的存在问题。这个项目产生的第二个理论问题是刻画要求在给定凸锥内的向量值函数的问题，例如，以对称矩阵为系数的多项式要求是半正定的。这类问题在多元形状约束问题中有一定的应用。我们将研究它们的特征，以及有效的优化算法的设计。这个项目的目标的成功完成将在统计学习理论和现代二次曲线优化问题之间产生强大的协同作用。通过统计学习，预计新的算法方法将影响到生物学、计量经济学、金融和管理科学等多个领域。所有这些领域都有许多问题，其中回归、密度估计或分类必须使用一个或多个形状和非负性约束来执行。为该项目开发的任何有用软件都将以开放源码格式提供给社区。这个项目的主要教育影响将是培养和发展具有多学科专业知识的研究生，包括数学编程、统计学习、信号处理、数据可视化和软件工程。预计研究生的工作将最终获得运筹学博士学位。

The main focus of this project will be on applications of modern and sophisticated optimization theory to the problems of statistical learning, regression, and density estimation, with constraints. Classes of functional constraints to be investigated will all involve nonnegativity over a domain of the underlying function or some linear functional of it. Both univariate and multivariate cases will be thoroughly investigated. The research in onstrained estimation problems will be carried out in several functional spaces including polynomials, polynomial splines, wavelets, and more general Chebychev systems, for the univariate case, and polynomials, wavelets, and splines for ultivariate case. In particular various strategies for approximation of nonnegativity constraints will be explored. The main tool for such problems is general convex conic optimization models such as semidefinite and second order cone programming. The shape and nonnegativity constraints will be formulated as conic optimization problems, and when possible, tailor made efficient interior point algorithms with good theoretical and numerical properties will be developed. In the multivariate case, Nesterov's semidefinite programming characterization of sum-of-squares functions will be used as a foundation to build methods for multivariate estimation and learning problems. Observing that the explicit problems above in the most abstract form amount to searching in the cone of nonnegative functions in some well-defined closed linear function space such as Sobolev-Hilbert spaces with an explicit orthonormal basis, and starting from a finite subset of such basis, the approximations are refined successively by adding more elements of the basis until the desired accuracy is achieved. However, the question of which sequence of nonnegative cones within each approximating finite dimensional space should be chosen is of fundamental importance, and will be thoroughly investigated.Two interesting theoretical questions are related to the research on constrained learning and estimation problems which will be investigated in this project. One is the question of which cones have bilinear complementarity conditions. The question of existence of such cones beyond the class of symmetric cones (which include positive semidefinite matrices and second order cones) will be investigated. The second theoretical question which arises from this project is the question of characterizing vector valued functions which are required to be in a given convex cone, for example, polynomials with symmetric matrices as coefficients which are required to be positive semidefinite. Such problems have applications in multivariate shape onstrained problems. The characterization, as well as design of efficient optimization algorithms for them will be investigated. Successful completion of the goals of this project will create strong synergy between statistical learning theory and modern conic optimization problems. Through statistical learning, it is expected that new algorithmic methods impact fields as diverse as biology, econometrics, finance and management science, among others. All such fields have numerous problems where regression, density estimation or classificationhas to be carried out with one or many shape and nonnegativity constraints. Any useful software developed for this project will be made available to the community in the open source format. Both C and C++ libraries, as well as MATLAB-like and R based software will be created and published in open sourceformat.The main educational impact of this project will be training and development of graduate students with expertise in multitudes of disciplines, including mathematical programming, statistical learning, signal processing, data visualization and software engineering. It is expected that the graduate students work will culminate in PhD degrees in operations research.