An optimization method for bounding the eigenvalues of a unknown non symmetric matrix

Question

Given a positive objective function $f$ that acts on a real-valued matrix $A$, I am interested in the following problem

$$underset{A in mathbb{R}^{n times n}}{text{minimize}} quad f(A) quad text{subject to} quad b leq text{Re}(lambda_j) leq a, quad j=1,2,...n  ,$$

where $lambda_j in mathbb{C}$ are the eigenvalues of $A$, and $text{Re}(cdot)$ is the real part of a complex number. What optimization methods are available for approaching this task? I know there are several techniques for bounding the eigenvalues of symmetric matrices, but I wonder what happens in the non symmetric case (my $A$ is not necessarily symmetric)?

This question was posted originally in the math forum.

wyer33 · Answer

I believe it can be done with a semidefinite program by adding a multiplicative slack variable.  Basically,

$$
begin{array}{rcl}
minlimits_{A in mathbb{R}^{n times n}, Pin mathbb{R}^{ntimes n}} &&f(A)
text{st} && b I preceq PA + A^TP preceq a I
&& P succ 0
end{array}
$$

Essentially, this is the Lyapunov stability condition.  Of course, this problem is a pain to solve because the $PA$ term is quadratic, so we effectively have a nonlinear semidefinite program.

An optimization method for bounding the eigenvalues of a unknown non symmetric matrix

One Answer

Add your own answers!

Ask a Question