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

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

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.