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

正函数或平方和函数的优化及其在约束逼近和形状约束学习中的应用

• 批准号: 0935305
• 负责人: Farid Alizadeh
• 金额: $ 32.5万
• 依托单位: Rutgers University Newark
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-01 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0935305&HistoricalAwards=false
• 关键词: Optimization; Over; Positive; Sum; Square

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.

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