基于SDP松弛的二次优化求解算法分析与有效性证明

"这篇论文探讨了算法的有效性证明，特别是针对二次优化问题的SDP松弛求解算法。文章提到了Sturm和Zhang的工作，他们证明了无约束信赖域子问题的半正定松弛是紧的，即原问题的最优解可以从松弛问题的最优解中获取。然而，他们的证明没有提供一个简洁的矩阵分解方法。论文作者范丽君和艾文宝在此基础上提出了一个简单的矩阵分解方法，用于获取原问题的精确解或近似解，并通过Matlab实现。作者还提供了算法的有效性证明和初步的数值实验结果，显示该方法对大部分问题有效，特别是在解决等式约束优化问题的信赖域子问题（两球问题）时，效率超过95%。" 在非线性优化领域，信赖域方法是一种关键的数值计算技术，其核心在于求解信赖域子问题，这个子问题通常表现为二次优化问题。Sturm和Zhang的工作揭示了无约束信赖域子问题与半正定规划（SDP）之间的关系，他们证明了松弛问题的解可以直接转化为原二次优化问题的解。然而，他们的证明过程复杂，没有给出实际操作的分解步骤。 本文作者对此进行了改进，提出了一种基于简单矩阵分解的算法，能够直接求解或近似求解原问题。这种方法不仅理论上可行，而且通过Matlab实现，具有可操作性。作者通过数值实验验证了算法的有效性，结果显示该方法在处理等式约束的优化问题，即两球问题时，表现出很高的成功率，对超过95%的问题都能找到有效的解决方案。 此外，论文还强调了在大规模问题中，精确求解每个迭代步的信赖域子问题可能既不必要也不实际，因此寻找有效的近似求解策略至关重要。Powell的折线法和Dennis与Mei的双折线方法等都是这方面的重要研究，但Strum和Zhang的特征值分解方法虽然理论上完整，但在实际应用中可能存在复杂度问题。作者提出的简单矩阵分解方法则旨在简化这一过程，提高计算效率。 这篇论文不仅贡献了一个理论上的有效性证明，还提供了一个实用的算法，有助于提升信赖域方法在解决非线性优化问题时的效率，尤其是在面对等式约束时。这为后续研究和实际应用提供了有价值的参考。