2
$\begingroup$

There is a $4×4$ matrix $Q$ where $c,d,e,m,n$ are variables. How to get the maximum value of the minimum eigenvalue of $Q$?

$Q=$ $$\\\left( \begin{array}{cccc} \frac{12058305}{23104}-304 c & -849 c-152 d+\frac{48384453663}{28094464} & e & m \\ -849 c-152 d+\frac{48384453663}{28094464} & -\frac{441999 c}{152}-1698 d-2 e+4824 & -76 c^2-\frac{441999 d}{304}-m-\frac{4431}{2} & n \\ e & -76 c^2-\frac{441999 d}{304}-m-\frac{4431}{2} & -304 c d-2 n-2169 & \frac{513}{2}-76 d^2 \\ m & n & \frac{513}{2}-76 d^2 & 81 \\ \end{array} \right)$$

Q={{12058305/23104-304 c,48384453663/28094464-849 c-152 d,e,m},{48384453663/28094464-849 c-152 d,-((441999 c)/152)-2 (-2412+849 d+e),-(4431/2)-76 c^2-(441999 d)/304-m,n},{e,-(4431/2)-76 c^2-(441999 d)/304-m,-2169-304 c d-2 n,513/2-76 d^2},{m,n,513/2-76 d^2,81}}

$\endgroup$
2
  • $\begingroup$ Welcome to the Mathematica Stack Exchange. Once you get the expression for eigenvalue in terms of your parameters, you will need to run Minimize and in order to do that you will need constraints on variables. Please include such constraints. $\endgroup$
    – Syed
    Commented Apr 20, 2022 at 15:33
  • $\begingroup$ @Moo $c,d,e,m,n \in \mathbb{R}$ $\endgroup$
    – lapcal
    Commented Apr 20, 2022 at 16:03

2 Answers 2

7
$\begingroup$

It is unlikely that you will get an answer to your question which relies on off-the-shelf algorithms, such as the ones in Mathematica. For what it is worth, an approximate answer which seems to be very close to the global maximum is:

sol = {c -> -4.84816358599152`, d -> 0.3008466924271099`, e -> -1172.3619400404964`, m -> -357.535888933738`, n -> -1267.447358996882`}

which is such that

Min[Eigenvalues[Q /. sol]]

is

3.55232

As for why this is close to the optimum consider the following identity:

$$ \begin{bmatrix} a_1 & a_2 \\ a_2 & a_3 \end{bmatrix} = \begin{bmatrix} c \\ d \end{bmatrix} \begin{bmatrix} c & d \end{bmatrix} = \begin{bmatrix} c^2 & c d\\ c d & d^2 \end{bmatrix} $$

A relaxation of this into the matrix inequality

$$ \begin{bmatrix} a_1 & a_2 \\ a_2 & a_3 \end{bmatrix} \succeq \begin{bmatrix} c \\ d \end{bmatrix} \begin{bmatrix} c & d \end{bmatrix} $$

can be restated as the linear matrix inequality

$$ S(c,d,a1,a2,a3) = \begin{bmatrix} a_1 & a_2 & c\\ a_2 & a_3 & d \\ c & d & 1 \end{bmatrix} \succeq 0. $$

Now let $Q(c,d,e,m,n,c^2,c d, d^2)$ denote the original matrix $Q$. An upper bound to the maximum of the minimum eigenvalue is given by the solution to the semidefinite program

$$ \max_{c,d,e,m,n,a1,a2,a3} \{ \rho : \quad Q(c,d,e,m,n,a1,a2,a3) - \rho I \succeq 0, \quad S(c,d,a1,a2,a3) \succeq 0 \}. $$

This is a semidefinite program and it can be solved in Mathematica as follows:

Qr = (Q /. {c^2 -> a1, c d -> a2, d^2 -> a3}) - \[Rho] IdentityMatrix[4];
Sr = {{a1, a2, c}, {a2, a3, d}, {c, d, 1}};
sol = SemidefiniteOptimization[-\[Rho], VectorGreaterEqual[{Qr, 0}, {"SemidefiniteCone", 4}] && VectorGreaterEqual[{Sr, 0}, {"SemidefiniteCone", 3}], Variables[Qr]]

which is such that

\[Rho] /. sol

evaluates to

3.55235

The gap between the relaxation and the solution provided before is of order of $10^{-5}$. Beware not to use any other components of the relaxation solution since they are not feasible to the original problem. Its value is only in certifying the (near) global optimality of the other solution.

$\endgroup$
6
  • $\begingroup$ How is it made? $\endgroup$
    – user64494
    Commented Apr 22, 2022 at 8:38
  • $\begingroup$ In this particular case the relaxation {{c^2,c d},{c d, d^2}} >= {{c},{d}} . {{c, d}} can be cast as a semidefinite constraint that provides an upper bound to the cost which is equal to the value above up to six decimals. For calculating a solution there is a number of alternatives, from branch and bound, to more polynomials relaxations. The one I calculated uses an iterative scheme that works well on such small problems. $\endgroup$ Commented Apr 22, 2022 at 15:24
  • $\begingroup$ @MauriciodeOliveira Thanks. I got an idea from another post, use Q={{12058305/23104-304 c,48384453663/28094464-849 c-152 d,e,m},{48384453663/28094464-849 c-152 d,-((441999 c)/152)-2 (-2412+849 d+e),-(4431/2)-76 c^2-(441999 d)/304-m,n},{e,-(4431/2)-76 c^2-(441999 d)/304-m,-2169-304 c d-2 n,513/2-76 d^2},{m,n,513/2-76 d^2,81}}; obj[vals:{_?NumberQ..}]:=Min[Eigenvalues[Q/.Thread[Variables[Q]->vals]]]; NMaximize[obj[Variables[Q]],Variables[Q]], but the result seems to be very different from yours. $\endgroup$
    – lapcal
    Commented Apr 22, 2022 at 16:13
  • $\begingroup$ @lapcal this problem is very deceptive. The objective function is not convex and not differentiable and local optimization methods such as the ones implemented by NMaximize will invariably get stuck at the multitude of local optima. I will add the part with the relaxation to the answer because that is something that you can actually do in Mathematica these days. It is also a certificate of global optimality for the provided solution. $\endgroup$ Commented Apr 22, 2022 at 19:31
  • $\begingroup$ @MauriciodeOliveira Thanks a lot! I wonder if your method also works for matrices with more nonlinear elements, for this problem, $c^2,c d,d^2$ are nonlinear elements, if there are more nonlinear elements, for example, {a^2, a b, b^2, a c, b c, c^2, a d, b d, c d, d^2, a e, b e, c e, d e, e^2}, is the method still similar to the original problem? $\endgroup$
    – lapcal
    Commented Apr 23, 2022 at 14:07
1
$\begingroup$

A direct way to do it is as follows.

Q = {{12058305/23104 - 304 c, 48384453663/28094464 - 849 c - 152 d, e,
 m}, {48384453663/28094464 - 849 c - 152 d, -((441999 c)/152) - 
 2 (-2412 + 849 d + e), -(4431/2) - 76 c^2 - (441999 d)/304 - m, 
n}, {e, -(4431/2) - 76 c^2 - (441999 d)/304 - m, -2169 - 
 304 c d - 2 n, 513/2 - 76 d^2}, {m, n, 513/2 - 76 d^2, 81}};
f[c_, d_, e_, m_, n_] := Min[Eigenvalues[Q]];
NMaximize[{Evaluate[f[c, d, e, m, n]],  Norm[{c, d, e, m, n}] <= 3*10^3}, {c, d, e, m, n}, 
Method -> {"DifferentialEvolution", "ScalingFactor" -> 5.25}]

{3.55232, {c -> -10.0958, d -> 2.09738, e -> -2966.73, m -> -297.416, n -> -331.612}}

The execution takes several minutes.

$\endgroup$
1
  • $\begingroup$ NMaximize[Evaluate[f[c, d, e, m, n]], {c, d, e, m, n}, Method -> {"DifferentialEvolution", "ScalingFactor" -> 5.25}] results in {-199.035, {c -> 1.54486, d -> -3.20649, e -> 208.165, m -> 0.209532, n -> -810.512}}. $\endgroup$
    – user64494
    Commented Apr 23, 2022 at 5:56

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.