Methods for structured matrices with fixed eigenvalues

Several manifold optimization schemes are implemented for solving a class of structured matrix problem with prescribed spectrum.

Some manifold optimization schemes are implemented for solving an 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. The 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. Some numerical tests are presented to illustrate the effectiveness of the designed methods.

--------------------------------------------------README--------------------------------------------------

1. Problem and solvers

This package contains codes for solving the following problem

min F(X) s.t. X'*X = I; Po(\phi(X))-\phi(X) = 0; Ro(\phi(X))-C = 0,

where F(X)= -||Qo\phi(X)||_F^2, \phi(X) = X'*S*X, "o" denotes the Hadamard product

and P,Q,R,S,C are the matrices described in [REF]. This is an optimization model proposed to approximately solve the inverse eigenvalue problem addressed in [REF].

Solvers: fun.m Grad_cayley.m, Grad_qr.m, Pen_Approach.m, PenGrad_cayley.m, PenGrad_qr.m, RADMM.m

fun.m --- corresponds to an implementation of the objective function and its gradient.

Grad_cayley.m --- corresponds to an implementation of the spectral Riemannian gradient method based on the Cayley retraction to solve general smooth minimization problems over the orthogonal group.

Grad_qr.m --- corresponds to an implementation of the spectral Riemannian gradient method based on the QR retraction to solve general smooth minimization problems over the orthogonal group.

Pen_Approach.m --- corresponds to the algorithm defined by (3a)-(3b) in [REF].

PenGrad_cayley.m --- corresponds to the algorithm defined by (9a)-(9b)-(9c) in [REF], using the method Grad_cayley.m to solve the orthogonal constrained optimization sub-problem (9a).

PenGrad_qr.m --- corresponds to the algorithm defined by (9a)-(9b)-(9c) in [REF], using the method Grad_qr.m to solve the orthogonal constrained optimization sub-problem (9a).

RADMM.m --- corresponds to the algorithm defined by (26a)-(26b)-(26c)-(26d) in [REF] using the method Grad_qr.m to solve the orthogonal constrained optimization sub-problem (26a).

In particular, the package includes four scripts to test all the solvers. To reproduce the experiments in the paper, simply run Test1.m, Test2.m, Test3.m, and Test4.m

----------------------------------------------------------------------------------------------------

2. Reference

[REF] Jean-Paul Chehab, Harry Oviedo and Marcos Raydan. "Optimization schemes on manifolds for structured matrices with fixed eigenvalues". Technical report, 2024; url: https://hal.science/hal-04239863/

Jean-Paul Chehab <[e-mail]>

Harry Oviedo <[e-mail]>

Marcos Raydan <[e-mail]>

----------------------------------------------------------------------------------------------------

3. The Authors

We hope that the package is useful for your application. If you have any bug reports or comments, please feel free to email me: Harry Oviedo, [e-mail]

Enjoy it!

Jean-Paul Chehab, Harry Oviedo and Marcos Raydan.

----------------------------------------------------------------------------------------------------

Copyright (C) 2024, Jean-Paul Chehab, Harry Oviedo and Marcos Raydan. This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.