Semidefinite Programming Methods for Moment and Optimization Problems

点击翻译按钮获取中文摘要

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.