5
$\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.
Improve this question
$\endgroup$
7
  • $\begingroup$ Can you say anything about $A$? $\endgroup$
    – Richard
    Commented Aug 9, 2019 at 16:03
  • $\begingroup$ Unfortunately no, @Richard. $A$ does not have any particular structure. $\endgroup$
    – Kawhi
    Commented Aug 9, 2019 at 16:50
  • $\begingroup$ Can you provide how $f$ looks like? $\endgroup$
    – nicoguaro ♦
    Commented Aug 9, 2019 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
    Commented Aug 10, 2019 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
    Commented Aug 10, 2019 at 5:16

1 Answer 1

Reset to default
1
$\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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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