论文部分内容阅读
有关半定规划问题的研究最早开始于二十世纪六、七十年代.半定规划作为线性规划的一种推广,它是建立在由半正定矩阵生成的锥上的一类凸最优化问题.半定规划在很多领域都有着广泛的应用,例如:最大特征值优化问题、组合优化问题、鲁棒优化、系统与控制论、统计学以及结构优化等领域.为了更好地解决半定规划问题,研究者们提出了半定规划的内点算法、谱丛算法、共轭梯度法以及外梯度法等很多有效、可靠的算法.这些算法的研究与提出推动了半定规划的发展.现在,半定规划已成为最优化领域的一个非常重要的研究课题. 文章首先介绍了半定规划的发展与研究现状、基本理论、几个相关算法以及变分不等式问题的相关知识与投影类算法;然后,在半定规划问题满足严格可行的约束条件下给出了问题的最优解存在的KKT条件,利用得到的KKT条件,将求解半定规划问题等价地转化为求解变分不等式问题;最后,借鉴变分不等式问题的投影算法提出了求解半定规划问题的一种新算法及其改进算法.本文主要做了以下两部分工作: 1.首先,文章借鉴变分不等式问题的投影算法,提出了求解半定规划问题的一种新的投影类算法;然后,在问题的最优解集Ω*非空和F伪单调的假设条件下证明了该算法是具有全局收敛性的;最后,给出了该算法针对测试问题的数值实验结果.实验结果表明了算法是可行的. 2.给出了针对第一种投影算法的一种改进算法,并证明了改进算法在相同的假设条件下同样具有全局收敛性.从改进算法的分析和证明中可知:与第一种算法相比,改进算法所产生的迭代点uk+1更接近最优解u*.