基于二次规划的大规模非线性半定规划问题的理论、算法研究及软件设计

Our project aims at the research on several important classes of large scale nonlinear semidefinite programming problems (SDPs) based on quadratic programmings: (1).SDPs whose objective is a covex quadratic function with an entropy term; (2).SDPs whose objective is a convex quadratic function with a log-determinant term; (3).quadratic SDPs with rank constraints. These problems can find wide applications in the areas of information, statistics, finance, image processing, and so on. They are also similar to each other in the problem types and the ways in which to solve them though they have different appearances. In order to solve these problems, we will fully take advantage of the characteristics of the problems themselves, design efficient numerical algorithms whose complexity is O(1/k^2) with the idea of the combination of the first-order and second-order methods,and make application software. The research on these special large scale nonlinear SDPs will definitely provide new tools, methods and ideas for more general nonlinear SDPs.

本项目拟研究几类重要的基于二次规划的大规模非线性半定规划问题：(1).凸二次目标函数加上entropy项的半定规划问题；(2).凸二次目标函数加上log-determinant项的半定规划问题；(3).带秩约束的二次半定规划问题。这些问题在信息、统计、金融、图像处理等领域有着广泛的应用。几类问题之间虽然形式各有差别，但从问题类型和解决途径上又有不少相似之处。为了求解这些问题，我们将充分挖掘问题本身的特点，拟采用不精确的一阶和二阶方法混合使用的办法，设计复杂度为O(1/k^2)的高效数值算法，编写应用软件。对这几类特殊大规模非线性半定规划问题的研究，必能为更一般的非线性半定规划问题的解决提供新的工具、方法和思想。

本项目主要研究了几类重要的基于二次规划的大规模非线性半定规划问题：(1).利用加速邻近梯度法和对偶Newton-CG方法相结合的方法解决了目标函数为线性函数加上熵项的半定规划问题；(2).利用邻近增广拉格朗日方法和Newton-CG增广拉格朗日方法相结合的方法解决了凸二次目标函数加上log-determinant项的半定规划问题；(3).用邻近增广拉格朗日罚方法解决了带秩约束的二次半定规划问题。这些问题在信息、统计、金融、图像处理等领域有着广泛的应用。(4).应用自适应投影和收缩算法求解凸函数和二次函数求和的问题。(5).应用（majorized）Newton-CG增广拉格朗日方法解决了接触力学中的实际优化问题。几类问题之间虽然形式各有差别，但从问题类型和解决途径上又有不少相似之处。对这几类特殊大规模非线性半定规划问题的研究，必能为更一般的非线性半定规划问题的解决提供新的工具、方法和思想。.除此之外，我们还利用Faà di Bruno公式及其相关的组合工具，结合差商、插值等数值逼近中相关的理论和技巧解决了一类二元递归序列的显式表达问题；利用Faà di Bruno公式及其推广解决了特殊函数逼近问题中一类指数函数与其导数互相线性表示的问题，并解决了该类函数高阶求导和卷积问题。