Optimization schemes on manifolds for structured matrices with fixed eigenvalues

Abstract Several manifold optimization schemes are presented and analyzed for solving a specialized inverse structured symmetric matrix problem with prescribed spectrum. Some entries in the desired matrix are assigned in advance and cannot be altered. The rest of the entries are free, some of them preferably away from zero. The reconstructed matrix must satisfy these requirements and its eigenvalues must be the given ones. This inverse eigenvalue problem is related to the problem of determining the graph, with weights on the undirected edges, of the matrix associated with its sparse pattern. Our optimization schemes are based on considering the eigenvector matrix as the only unknown and iteratively moving on the manifold of orthogonal matrices, forcing the additional structural requirements through a change of variables and a convenient differentiable objective function in the space of square matrices. We propose Riemannian gradient-type methods combined with two different well-known retractions, and with two well-known constrained optimization strategies: penalization and augmented Lagrangian. We also present a block alternating technique that takes advantage of a proper separation of variables. Convergence properties of the penalty alternating approach are established. Finally, we present initial numerical results to demonstrate the effectiveness of our proposals.