2
$\begingroup$

Say I wish to find the minimum value of the determinant of a symmetric matrix under the condition that the matrix be positive definite. So I attempt:

M = {{a,0},{0,b}}

FindMinimum[{Det[M],a>=1,b>=1,PositiveDefiniteMatrixQ[M]},{a,b}]

This returns an error that Constraints in {False} are not all equality or inequality constraints..., suggesting to me that the PositiveDefiniteMatrixQ is being evaluated immediately for arbitrary a,b and not evaluated each iteration for a,b values.

Then I might try to delay the evaluation of PositiveDefiniteMatrixQ with Delayed, which returns a similar error Constraints in {Delayed[PositiveDefiniteMatrixQ[M]],a>=1,b>=1} are not all equality or inequality constraints.

How can I impose such a constraint on the FindMinimum function?


The specific problem I am trying to minimise involves two coupled matrices, one 2x2 and one 4x4. Simplified as far as possible while still exhibiting an issue with the Thread[Eigenvalues[B] > 0] approach:

A = {{a, 0}, {0, d^2*b + a - 2 d*c*Sign[d]}};
B = {{a, 0, c, 0}, {0, a, 0, -c}, {c, 0, b, 0}, {0, -c, 0, b}};

min = FindMinimum[{
    Det[A],
    a^2 + b^2 - 2 c^2 >= 0,
    Thread[Eigenvalues[B] > 0],
    a >= 1, b >= 1, -1 < d < 1}, 
    {a, b, c, {d, 0}}]

Thread[Eigenvalues[B /. min[[2]]] > 0]
$\endgroup$
  • 1
    $\begingroup$ if M is symmetric, you can use FindMinimum[{Det[M], a >= 1, b >= 1, Thread[Eigenvalues[M] > 0]}, {a, b}]? $\endgroup$ – kglr Feb 20 at 16:33
  • $\begingroup$ For your given matrix M, the eigenvalues are $a$ and $b$ and the Det[M] is $a b$. Since you are constraining $a$ and $b$ to be >=1, the minimum is clearly at $a=b=1$. $\endgroup$ – bill s Feb 20 at 16:42
  • $\begingroup$ @kglr It is symmetric, so I can use that approach. However, for the found minimum values Thread[...] returns {True,True,False,False} (for a 4x4 matrix) so the constraint is not being respected $\endgroup$ – Cailean Wilkinson Feb 20 at 17:01
  • $\begingroup$ @bills Yes, but that's a simplified case for demonstration. My actual matrix has a more complex (but symmetric) form and a longer list of constraints. $\endgroup$ – Cailean Wilkinson Feb 20 at 17:02
  • $\begingroup$ Cailean, can you update your question with (1) the information that M is symmetric and (2) the 4X4 example you mention in the comment? $\endgroup$ – kglr Feb 20 at 17:09
2
$\begingroup$

One simple way to do this, is to just introduce a function that returns a huge number when the constraint is not met:

ClearAll[det2];
det2[mat_?PositiveSemidefiniteMatrixQ] := Det[mat];
det2[_?(MatrixQ[#, NumericQ] &)] := 10^100;

FindMinimum[{det2[M], a >= 1, b >= 1}, {a, b}]
(* {1., {a -> 1., b -> 1.}} *)

This works for this toy example, but it's unlikely that this is going to give good results for realistic problems since it will be very difficult for the solver to figure out where exactly the constraint holds and where not and how to optimize the objective function around this constraint.

Instead, it's almost always better to try and find a way to formulate the problem in such a way that the constraint is guaranteed to hold. For example, any Hermitian, positive definite matrix can be written as a Cholesky decomposition L . Transpose[L] (with L lower triangular). So the general way to write a 2 x 2 positive definite matrix is:

M = With[{L = {{a, 0}, {b, c}}}, L. Transpose[L]]
(* {{a^2, a b}, {a b, b^2 + c^2}} *)

The eigenvalues of this matrix are >= 0:

Minimize[#, {a, b, c}] & /@ Eigenvalues[M]
(*{{0, {a -> -1, b -> -1, c -> 0}}, {0, {a -> 0, b -> 0, c -> 0}}}*)

So this matrix you could use for your minimization option without having to worry about the PositiveSemidefiniteMatrixQ constraint.

| improve this answer | |
$\endgroup$
2
$\begingroup$

For a real symmetric matrix X, we can replace the constraint PositiveDefiniteMatrixQ[X] with Thread[Eigenvalues[X] > 0].

To get around the issue caused by Sign in OP's example A we can apply PiecewiseExpand on Det[A] in the objective function:

min = FindMinimum[{PiecewiseExpand[Det[A], Element[d, Reals]], 
   a^2 + b^2 - 2 c^2 >= 0, Thread[Eigenvalues[B] > 0], a >= 1, 
   b >= 1, -1 < d < 1}, {a, b, c, {d, 0}}]

{1., {a -> 1., b -> 1.98128, c -> 0.641898, d -> 0.}}

Thread[Eigenvalues[B /. min[[2]]] > 0]

{True, True, True, True}

| improve this answer | |
$\endgroup$
1
$\begingroup$

Following on @kglr, but using the definition of positive definiteness as all of the leading principal minors are > 0. Create a function to compute the leading principal minors. Assumes square matrix.

makeLPM[mat_] := Table[Det@mat[[1 ;; i, 1 ;; i]] // MatrixForm, {i, 1, Length@mat}]

lpm = makeLPM[B];
(* {a, a^2, a^2 b - a c^2, a^2 b^2 - 2 a b c^2 + c^4} *)

Replicating @kglr's code, substituting principal minors for eigenvalues

min = FindMinimum[{PiecewiseExpand[Det[A], Element[d, Reals]], 
                  a^2 + b^2 - 2 c^2 >= 0, 
                  Thread[lpm > 0], a >= 1, 
                   b >= 1, -1 < d < 1}, 
                  {a, b, c, {d, 0}}]
 (* {1., {a -> 1., b -> 2.16112, c -> 0.941631, d -> 0.}} *)

This is a different answer from @kglr, but...

Thread[Eigenvalues[B /. min[[2]]] > 0]
 (* {True, True, True, True} *)

 Thread[makeLPM[B /. min[[2]]] > 0]
 (* {True, True, True, True} *)
| 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.