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 具有所提议主题的专业知识。提出了克服研究挑战的新方法和工具并提供了支持证据。该项目产生的研究成果不仅可以在 PI 领域取得重大进展，而且还可以为计算数学的许多其他领域提供新颖的方法。 矩和优化问题在科学和工程中有着广泛的应用。典型应用包括：矩阵论、计算代数、凸代数几何、张量计算。此类应用中的矩和优化问题有其自身的特殊特征和性质。教育是该项目的重要组成部分。学生将通过参加高级课程以及开展研究活动来接受培训。项目取得的成果将通过各种渠道及时向科学界传播。