Semidefinite Programming Methods for Moment and Optimization Problems

矩量和优化问题的半定规划方法

• 批准号: 1417985
• 负责人: Jiawang Nie
• 金额: $ 21万
• 依托单位: University of California-San Diego
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-07-01 至 2018-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1417985&HistoricalAwards=false
• 关键词: Semidefinite; Programming; Methods; Moment; Optimization

This project targets at solving moment and optimization problems. A moment is the integral of a polynomial over a set with densities. Optimization is about making a decision so that an objective is optimized. An exemplary question is how to find the lowest valley of an area full of uneven mountains. Semidefinite programming is an efficient tool for solving moment and optimization problems, because it provides mathematically easy descriptions for complicated sets. The research results made in the project will produce plenty of mathematical methods for solving various computational problems. This project works on moment and optimization problems. A moment is the integral of a monomial with respect to a measure. Moment problems are about existences and constructions of measures satisfying some given properties. Optimization problems are about minimizing functions, typically nonlinear and nonconvex, globally over given sets. We propose semidefinite programming methods for solving these two kinds of problems. For moment problems, semidefinite programming can be applied to describe the set of moments of desired measures. For optimization problems, global optimum can be computed by minimizing linear functions in moment variables, subject to semidefinite programming constraints. These two kinds of problems are closely connected to each other by semidefinite programming. The main task of moment problems is to determine whether a given sequence can be represented as moments of a measure supported in a prescribed set. In optimization, we are mostly interested in computing global minimizers of nonlinear nonconvex functions. An efficient tool for unifying moment and optimization problems is semidefinite programming. The underlying mathematics includes convex geometry, duality theory, complex and real algebraic geometry, matrix theory, optimization theory, and scientific computing. The PI has expertise on the proposed subjects. Novel methods and tools for overcoming research challenges are proposed with supporting evidences. The research results produced by the project could not only make significant advances in the PI's field, but also generate novel methods for many other areas in computational mathematics. Moment and optimization problems have broad applications in science and engineering. Typical applications include: matrix theory, computational algebra, convex algebraic geometry, tensor computations. The moment and optimization problems in such applications have their own special features and properties. Education is an important part of the project. The students will get trained by taking advanced courses as well as conducting research activities. Achievements produced by the project will be disseminated to the scientific community timely in various outlets.

这个项目的目标是解决瞬间和优化问题。矩是具有密度的集合上的多项式的积分。优化就是做出决策，从而使目标最优化。一个典型的问题是，如何在一个布满崎岖山脉的地区找到最低的山谷。半定规划是解决矩和优化问题的有效工具，因为它为复杂集合提供了简单的数学描述。该项目的研究成果将为解决各种计算问题提供丰富的数学方法。该项目致力于矩和优化问题。矩是关于度量的单项式的积分。矩问题是关于满足一定性质的测度的存在性和构造问题。最优化问题是关于在给定的集合上全局最小化函数，通常是非线性和非凸函数。我们提出了求解这两类问题的半定规划方法。对于矩问题，可以用半定规划来描述期望测度的矩集合。对于优化问题，在半定规划约束下，可以通过最小化矩变量中的线性函数来计算全局最优解。半定规划将这两类问题紧密地联系在一起。矩问题的主要任务是确定给定序列是否可以表示为在规定集合中支持的度量的矩。在最优化中，我们最感兴趣的是计算非线性非凸函数的全局极小值。半定规划是统一矩问题和优化问题的有效工具。基础数学包括凸几何、对偶理论、复代数几何和实代数几何、矩阵理论、最优化理论和科学计算。私隐专员公署在建议的课题上有专业知识。提出了克服研究挑战的新方法和工具，并提供了支持证据。该项目产生的研究成果不仅可以在PI领域取得重大进展，而且还可以为计算数学的许多其他领域产生新的方法。矩问题和最优化问题在科学和工程中有着广泛的应用。典型的应用包括：矩阵理论、计算代数、凸代数几何、张量计算。这类应用中的矩问题和优化问题有其自身的特点和性质。教育是该项目的重要组成部分。学生将通过参加高级课程和开展研究活动进行培训。该项目产生的成果将通过各种渠道及时传播给科学界。