非线性半定规划问题的逐次线性化方法

摘要

半定规划是线性与非线性规划的一种推广，在组合优化、控制论、系统论、滤波器的设计、临床医学等方面都有很广泛的应用。研究非线性半定规划问题的算法及其理论具有重要的理论意义和应用价值。
　　 许多线性与非线性规划的算法被成功地推广应用于求解非线性半定规划问题，例如光滑与非光滑牛顿法、势下降方法、原始对偶内点法、序列半定规划方法和增广拉格朗日方法等，这些方法有一个共同点：借助于某个罚函数作为效益函数来判断当前尝试步是否可以接受，即要求效益函数值有充分下降，但罚因子的选取是一个复杂而困难的问题。Fletcher等人提出的过滤方法是不使用罚函数的一种新方法，其基本原理类似于多目标规划的处理方法，这种思想在处理非线性半定规划问题时，滤子集的存储是一个值得考虑的问题。
　　 本文对非线性不等式约束半定规划问题提出一种新的逐次线性化方法，新算法既不要求罚函数单调下降，也不使用过滤技巧，从而避免了迭代过程中滤子集的存储。另外，尝试步的接受准则仅仅依赖于目标函数和约束违反度，因此，罚函数中对应于成功迭代点的罚因子不需要单调增加。为了判断尝试步是否可以接受，新算法或者要求违反约束的度量有足够改善，或者在约束违反度的一个合理范围内要求目标函数值充分下降，在通常的假设条件下，分析了新算法的适定性及全局收敛性。最后，给出了非线性半定规划问题的数值试验结果，结果表明了新算法的有效性。