大规模矩阵锥约束优化问题的理论、算法及其应用

大规模矩阵锥约束优化问题是最优化研究领域中的重要问题之一，在数值优化、鲁棒优化、投资组合优化以及统计学理论等领域有着极其广泛和重要的应用。现有的方法只能处理在对于中小规模的对称矩阵问题，因此深入研究大规模的矩阵（特别是非对称矩阵）锥约束优化问题的算法及其相关理论和软件设计有着重大意义。本项目以扰动分析和变分分析理论为基础，运用投影算子的方向可微性和强半光滑性，研究大规模部分阵完成问题的半光滑牛顿增广拉格朗日算法，大规模低秩近似矩阵问题的基于增广拉格朗日方法的算法，和对于一般闭凸锥约束优化问题的增广拉格朗日方法，并编写上述算法的matlab软件。

大规模矩阵锥约束优化问题是最优化研究领域中的重要问题之一，在数值优化、鲁棒优化、投资组合优化以及统计学理论等领域有着极其广泛和重要的应用。该项目主要深入研究了大规模矩阵锥约束优化问题中几类典型模型的理论、算法和应用。.首先，虽然内点算法是求解半正定规划问题重要方法之一，但是该算法需要迭代点是问题的严格可行点，这在编程实现内点算法时产生了困难。通过增加一个简单的人工变量，构造出以单位元素I为严格可行初始点的半正定规划问题；并且仅通过求解两维的半正定规划问题就可改进构造问题的势能函数的界值，大大降低了求解的计算量。分别对半正定规划的原始问题和对偶问题提出的相应的算法，使得最优解能够同时满足问题的可行性和最优性条件。我们分析了算法的收敛性和对三种算法的数值实验结果进行了比较。同时，课题组还讨论了组合优化问题中的设施选址问题中两目录分割问题的半正定松弛模型的近似算法。在不相交的情况下，运用不均匀旋转和半正定松弛的技巧，用半正定松弛问题的最优解和整个权重的比值来表示性能曲线，此曲线的最低点就显示了近似比为0.7317和相交2-CSP问题的近似比为0.6338，是目前最好的结果。.接着，研究大规模凸的二次约束二次半正定规划问题，给出了在原点Lipschitz连续性的等价条件、Robinson约束规范、强二阶充分条件、以及约束非退化准则的显示表达式；并证明了子问题的广义Hessian矩阵的正定性确保了使用非精确半光滑牛顿-共轭梯度法求解时具有超线性收敛率。在编写Matlab程序进行数值实验，利用所提出的半光滑牛顿-共轭梯度增广拉格朗日方法对鲁棒的估计协方差矩阵的数学模型进行了实验，得到了稳定和有效的数值结果。.项目组成员还共同研究了带线性耦合约束的极小化可分凸函数与光滑凸函数和的规划问题。通过利用块坐标下降方法的超线性收敛性，克服交替方向法对于超过3个乘子的问题不收敛的缺陷，提出了一个新的替换近似块乘子极小化算法，并在收缩型方法框架下证明了所提出的算法收敛性，得到了在最坏情况为O(1/K) 收敛率，K是指算法迭代步数。初步的数值实验已表明了所提出的算法的有效性。