图的最大二等分问题的投影梯度算法

摘要

本文基于图的最大二等分问题已有的半定规划松弛模型,给出了原问题的等价模型及其新的半定规划松弛模型,利用投影梯度算法求解该半定规划松弛模型,最后使用随机扰动算法求得原问题的近似最优解.理论和数值试验表明该方法不仅可以在较高的精度下求解中小规模的图的最大二等分问题,而且特别适合求解大规模的图的最大二等分问题.