大规模半定规划问题的信赖域算法研究

Semidefinite programming problem, which is an important generalization of combinatorial optimization problem, has several applications in optimal control theory, engineering optimization, patteem recognition and so on. The study on solving large-scale semidefinite programming problems and their theory is not only important in mathematical theories but also useful in applications.. . When using many methods for solving semidefinite programs, one needs to solve a system of linear equations at each iteration. For problems of large size, solving the system of linear equations can be very expensive. Based on filter techniques and subspace methods, this project will consider trust region algorithms for large-scale semidefinite programming problems by using Lipschitz condition and Frechet derivative. More particularly, 1) trust region algorithms for large-scale semidefinite programming problems such as filter trust region methods, subspace trust region methods and filter-subspace trust region methods which combine filter techniques and subspace methods will be proposed and discussed; 2) according to the special requirements for solving practical applications on optimal control theory and pattem recognition, the algorithms will be corrected based on the effects of the practical applications.

半定规划问题是线性规划问题在组合优化中的重要推广，在最优控制论、工程优化和模式识别等实际问题中有广泛的应用。对大规模半定规划问题的算法及其相关理论的研究，不仅有重要的理论意义，而且也有非常重要的实际应用价值。.　　传统求解大规模半定规划问题的算法受到大型对称矩阵复杂数值计算的限制，算法设计过程中仅仅利用目标函数及其一阶导数（梯度）信息，导致精度不高。本项目拟基于过滤技巧和子空间方法，通过将大型实对称矩阵稀疏化，利用Lipschitz条件和Frechet-导数，研究将高维的大规模半定规划问题转化到一个低维子空间中求解。主要研究内容包括：1）研究大规模半定规划问题的过滤信赖域算法、子空间信赖域算法以及将过滤技巧和子空间方法结合起来的过滤-子空间信赖域算法；2）将算法应用到最优控制论和模式识别等实际问题，并依据实际应用效果对算法进行改进和完善。.

半定规划问题是一类非光滑的凸优化问题，理论上可以用凸优化的方法求解，但实际求解中因为很难用代数的方法表示约束条件中的矩阵不等式，以及半定规划问题与其对偶问题的对偶间隙的可能不存在性，使得求解凸优化问题的传统算法（如牛顿法、原始-对偶法等）对半定规划问题是无效的。..本项目在半定规划问题及其对偶问题满足Slater 条件下，给出半定规划问题及其对偶问题的最优性条件，研究求解半定规划问题的信赖域算法。根据半定规划问题的结构特点，利用过滤技巧，一方面避免了罚参数的选取；另一方面放宽了新迭代点的接受准则，由此得到的非单调信赖域算法在理论方面具有最优逼近。同时在此基础上，考虑到半定规划问题数据大、变量多的特性，借助子空间方法，将信赖域子问题转化到一个低维问题上进行求解，然后回代到原问题中，以减少存储量和计算量，提高算法的运行速度，进一步完善和改进半定规划问题的信赖域算法。