4
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Can you say anything about $A$? $\endgroup$ – Richard Aug 9 '19 at 16:03
  • $\begingroup$ Unfortunately no, @Richard. $A$ does not have any particular structure. $\endgroup$ – Kawhi Aug 9 '19 at 16:50
  • $\begingroup$ Can you provide how $f$ looks like? $\endgroup$ – nicoguaro Aug 9 '19 at 23:09
  • $\begingroup$ Yes. $f$ could be as simple as $|AX-Y|_F^2$ where $X, Y$ are fixed known matrices and $|\cdot|_F$ is the Frobenius norm. $\endgroup$ – Kawhi Aug 10 '19 at 3:01
  • $\begingroup$ Out of curiosity, how big is $n$ generally or what is an upper bound for $n$? Further, how good does the result need to be? Can you do an approximation if it’s significantly faster to compute or do you really need to try and get the global optimum for a potentially general matrix $A$ (meaning no assumed structure)? $\endgroup$ – spektr Aug 10 '19 at 5:16
0
$\begingroup$

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

$$ \begin{array}{rcl} \min\limits_{A \in \mathbb{R}^{n \times n}, P\in \mathbb{R}^{n\times 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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.