A quadratically convergent local algorithm on minimizing sums of the largest eigenvalues of a symmetric matrix

The authors extend and apply earlier results on minimizing sums of the largest eigenvalues of a symmetric matrix. An important application of this problem is the graph partitioning problem. Given ∈⩾0, an optimality condition is derived, which ensures that the objective function is within a ∈ error bound of the solution. It is shown that, in a neighborhood of the minimizer, the optimization problem under consideration can be equivalently formulated as a smooth constrained optimization problem. It is also shown that the algorithm proposed earlier on minimizing the largest eigenvalue of a symmetric matrix can be applied with only minor modification. This algorithm enjoys the property that, under some mild assumptions, if started close enough, then it will converge to the minimizer quadratically. Finally, the convergence property of the algorithm is illustrated by means of a numerical example