信赖域方法与二次优化的SDP松弛算法

"0-本特利3500资料" 这篇文档主要讨论的是求解优化问题的算法，特别是针对带有等式约束的问题。算法的核心是通过松弛问题来找到原问题的最优解。文档中提到了算法2.3.1，这是一个从松弛问题的最优解到原问题最优解的转换算法。 在算法2.3.1中，首先给定一个半正定矩阵*X*，其第一列元素记为*x_0*。然后根据*X*和单位矩阵*I*之间的关系进行判断，以决定算法的下一步。如果*X*的负惯性指数小于1，进入步骤5；等于1，则进入步骤2；否则进入步骤4。 步骤2涉及检查松弛问题的某个条件，如果满足该条件，则继续到步骤5，否则进入步骤3。在步骤3中，计算*T_xx*（可能为残差项）并更新向量，寻找矩阵B对角线元素最大的列，标记为*m_x*，然后求解满足特定方程的α值。 步骤4直接设置φ=x作为解。最后，在步骤5输出解*x*。 文档还提到了等式约束优化的信赖域子问题，这个问题常被称为“两球问题”。为了解决这类问题，文献中提到了使用二次优化问题的半正定规划（SDP）松弛求解算法。Sturm和Zhang的工作展示了无约束信赖域子问题的SDP松弛是紧的，意味着可以通过松弛问题的解获取原问题的最优解。 文章作者范丽君和艾文宝进一步发展了这一理论，提出了一种简单的矩阵分解方法，用于获得原问题的精确解或近似解，并实现了Matlab软件的编程。他们证明了这种方法的有效性，尤其是在解决等式约束优化问题的信赖域子问题（两球问题）上，初步的数值实验表明，该方法对超过95%的两球问题都能有效求解。 关键词包括信赖域方法、信赖域子问题、SDP松弛以及二次优化。这种方法对于大规模非线性优化问题的求解具有重要意义，因为它提供了一种有效近似解的途径，降低了计算复杂性。