非线性半定规划的非退化性与强适性内点方法研究

Semidefinite programming (SDP) has extensive applications in practical fields, such as automatic control, digital image processing, etc., and has attracted great interests of many researchers in linear and nonlinear programming area. Interior-point approach has succeeded in solving SDP, some new interior-point methods for nonlinear SDP have been developed. Based on our completed research works and obtained results, this project is to propose a new kind of nondegeneracy condition which can be examined easily and a class of robust interior-point methods, establish the global and local convergence theories, and apply these methods to problems such as matrix completion arising from the digital image restoration and matrix inequalities from automatical control. Comparing with the existing methods, these robust methods are expected to have the following characteristics: Firstly, their global convergences are not dependent on any constraint nondegeneracy condition such as the strict feasibility of primal and dual problems for linear semidefinite programming; Secondly, for nonlinear SDP, the subproblems do not have any positive semidefinite constraint, thus is suitable for large-scale nonlinear SDP and may be helpful to improve the efficiency of existing methods for SDP; Thirdly, they can always find some points in sense, which can help us to improve the modeling of practical problems. We hope that the research of this project will be useful to further unveil some essential facts about SDP (such as the conditions on strong duality), and develop some more efficient algorithms for nonlinear SDP and conic programming.

半定规划是当前线性和非线性规划领域的一个研究热点，它在自动控制和数字图象处理等领域有着广泛的应用。内点方法已经在求解线性半定规划方面取得了成功，一些求解非线性半定规划的内点方法正在被开发。本项目旨在已有研究工作的基础上，结合半定规划具有半定约束和大规模的特点，发展一类新的更具强适性的非线性半定规划内点方法，建立其相关的全局和局部收敛性理论，并应用于矩阵还原等数字图象恢复问题。在此基础上，研究并提出线性和非线性半定规划新的易于检验的非退化性条件。算法的强适性主要体现在三个方面：一是算法及其理论不要求任何约束非退化性假设；二是对于非线性半定规划，算法的子问题不含有半定约束，因此有利于求解大规模非线性半定规划和改进算法效率；三是它总可以找到半定规划有意义的稳定点。希望通过本项目的研究，有助于进一步揭示半定规划问题的本质（如保证强对偶性条件等），并开发更加有效的求解非线性半定规划和锥规划的算法。

内点方法是一类重要的求解不等式约束最优化的方法，它已经在求解大规模线性和非线性最优化的理论和应用方面取得了巨大成功。半定规划是一类矩阵最优化问题，它是一类具有特殊结构的大规模不等式约束最优化问题，也是当前最优化领域的一个研究热点，在自动控制和数字图象处理等领域有着广泛的应用。近年来，内点方法已被应用于求解线性和非线性半定规划问题。.本项目在已有研究工作的基础上，针对半定规划是对称矩阵优化和大规模优化的特点，主要进行了下列四项研究工作：一是研究开发了一类新的求解非线性规划的强收敛原始对偶内点方法，该方法不依赖于互补约束，因此不需要引入对称化算子可以直接应用于求解非线性半定规划问题。二是深入研究了约束梯度线性无关假设对非线性约束优化算法及其理论的影响，建立了强适性算法的全局和局部收敛性理论。三是研究改进和推广了一些大规模最优化问题的一阶算法，证明了算法的全局收敛性，进行了数值测试和比较试验。四是研究并提出了可用于求解特殊结构半定规划的惯性邻近Peaceman-Rachford分裂方法。.本项目研究主要取得如下进展：一是新开发的内点方法不需要为保证内点而截断搜索方向，并具有快速探测问题不可行性的能力；二是改进的谱投影梯度法已被证明可用于有效求解张量特征值问题；三是给出了加速邻近梯度法的更一般形式及保证快速收敛的充分条件；四是我们的惯性邻近Peaceman-Rachford（PR）分裂方法包含了严格压缩PR分裂方法和半邻近PR分裂方法作为特殊情形，数值实验表明，与严格压缩PR分裂方法和惯性交替方向乘子法比较起来，我们的方法随着最小二乘半定规划维数的增加优势更加明显。