Semidefinite programming algorithms for convex optimization over nonnegative polynomials with applications in control and signal processing.

用于非负多项式凸优化的半定规划算法及其在控制和信号处理中的应用。

• 批准号: 0524663
• 负责人: Lieven Vandenberghe
• 金额: $ 24万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-09-15 至 2009-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0524663&HistoricalAwards=false
• 关键词: Semidefinite; programming; algorithms; convex; optimization

Semidefinite programming algorithms for convex optimization over nonnegative polynomials with applications in control andsignal processing During the last .fteen years semide.nite programming has developed into an important numerical tool for a variety of engineering applications, in particular in control and signal processing. At the same time, advances in semide.nite programming algorithms have resulted in several high-quality and freely available semide.nite programming software packages. These general-purpose solvers exploit some (sparse) problem structure, and can solve fairly large problem instances. However, for control and signal processing applications, which often involve matrix variables and dense linear matrix inequality constraints, there remains a substantial gap between the capabilities of the best solvers and the requirements for applications in practice. The main goal of this proposal is to narrow this gap, by developing fast algorithms for some speci.c classes of semide.nite programs that are important in control and signal processing. The proposal focuses on semide.nite programs in which the coe.cient matrices can be expressed as di.erent linear combinations of a small set of low-rank matrices. This type ofstructure is common and includes the important class of semide.nite programs derived from sum-of-squares representations of nonnegative polynomials. A second goal of the project is to investigate new applications of semide.nite programming to graphical modeling and time series analysis, and in particular the estimation of linear models with conditional independence constraints on pairs of variables.Intellectual merit The project will result in improved algorithms and software for solving important classes of semide.nite programming problems, by combining techniques from system theory (nonnegative polynomials), numerical analysis (discrete transforms and orthogonal polynomials) and optimization (interior-point methods).Broader impacts Software based on the research results will be made freely available, which will contribute to a more widespread adoption of semide.nite programming techniques. The results will be integrated in the graduate optimization sequence in the Electrical Engineering Department at UCLA. We also plan to o.er undergraduate research opportunitiesvia summer internships. The undergraduate student researchers will be recruited through the Center of Excellence in Engineering and Diversity (CEED) at UCLA, with the goal ofincreasing the number of CEED undergraduates interested in graduate study.

非负多项式凸优化的半定规划算法及其在控制和信号处理中的应用。十五年半。在各种工程应用中，特别是在控制和信号处理方面，计算机编程已经发展成为一种重要的数值工具。与此同时，进步在半。Nite编程算法已经产生了一些高质量和免费的半成品。夜间编程软件包。这些通用求解器利用一些（稀疏的）问题结构，可以解决相当大的问题实例。然而，对于经常涉及矩阵变量和密集线性矩阵不等式约束的控制和信号处理应用，最佳解算器的能力与实际应用要求之间仍然存在很大差距。本提案的主要目标是通过为某些特定的半线程类开发快速算法来缩小这一差距。在控制和信号处理中很重要的程序。该提案侧重于半ide。晚上的节目，其中coe。客户矩阵可以表示为di。一组低秩矩阵的事件线性组合。这种类型的结构是常见的，包括重要的半脂类。非负多项式的平方和表示得到了非负多项式的非程序。该项目的第二个目标是研究semi的新应用。对图形化建模和时间序列分析，特别是对变量对具有条件独立约束的线性模型的估计。该项目将改进算法和软件来解决重要的半胱氨酸类问题。通过结合系统理论（非负多项式），数值分析（离散变换和正交多项式）和优化（内点法）的技术来解决Nite规划问题。更广泛的影响基于研究结果的软件将免费提供，这将有助于更广泛地采用semi。夜间编程技术。结果将被整合到加州大学洛杉矶分校电气工程系的研究生优化序列中。我们还计划通过暑期实习为本科生提供研究机会。这些本科生研究人员将通过加州大学洛杉矶分校卓越工程与多样性中心（CEED）招募，目的是增加对研究生学习感兴趣的CEED本科生的数量。