The constraint det(A) > 0$\det(A) > 0$ is VERY UNSTABLEvery unstable and ABSOLUTELY HORRIBLEabsolutely horrible. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can make the determinant computed in double precision swing from 1e20 to -1e20? Good luck in trying to have a meaningful determination of whether det(A)$\det(A)$ is > or < 0 at any point. The gradient is the least of your worries. The constraint itself just will not work unless you compute in ultra-high precision, or perhaps you are only dealing with a 2 or 3 dimensional problem. Prof Neumaier was giving you a more numerically stable workaround. But I can say from my experience, imposing a Cholesky factorization type constraint does not seem to work well, and makes the problem non-convex, even if the original problem is convex; you may succeed, but you may wind up adding a bunch of spurious local optima (and even saddlepoints?) to your problem, and that is not a good thing.

Is the matrix A $A$ (constrained to be) symmetric, and do you really wish to impose that det(A) > 0$\det(A) > 0$ and that all leading principal submatrices have det > 0$\det > 0$, i.e., that A$A$ be positive definite? If so, instead of using the constraint det(A) > 0$\det(A) > 0$ (which apart from its terrible numerical properties, is not sufficient to ensure positive definiteness of A$A$, unless it is imposed (as perhaps you do?) on all leading principal submatrices), use a semidefinite constraint, A > 0$A > 0$ in Linear Matrix Inequality (LMI) sense. I.e., a constraint that A is positive definite. However, practical optimization software either does not accept strict inequality constraints, or if it does, treats them as non-strict inequality constraints. If positive semidefinite is o.k., your constraint would be A >= 0 $A \ge 0$ (in LMI sense). If you really need A to be strictly positive definite (det(A) strictly positive), then you need to determine a minimum acceptable eigenvalue, min_eigmin_eig, and then impose the constraint A - min_eig * (Identity matrix of correct size) >= 0A - min_eig * (Identity matrix of correct size) >= 0 (in LMI sense). You do need to make some allowance for solver tolerance used in constraint feasibility assessment (i.e., solver will allow constraint to be violated by a little, for example, by 1e-6 or 1e-8).

Edit in response to edit of Question: As shown in the edited version of your question, A$A$ is constrained to be symmetric nonnegative and have det(A) > 0$\det(A) > 0$, but A$A$ is not constrained to be positive definite. It is in fact possible for an nonnegative symmetric matrix of dimension >= 3 to have positive determinant yet not be positive definite. Do you wish to allow that situation? If so, my answer above the edit above does not apply. If in fact you require A$A$ be positive definite, then my answer above the edit does apply, and you should further edit your question to reflect the constraint that A$A$ be positive definite.

The constraint det(A) > 0 is VERY UNSTABLE and ABSOLUTELY HORRIBLE. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can make the determinant computed in double precision swing from 1e20 to -1e20? Good luck in trying to have a meaningful determination of whether det(A) is > or < 0 at any point. The gradient is the least of your worries. The constraint itself just will not work unless you compute in ultra-high precision, or perhaps you are only dealing with a 2 or 3 dimensional problem. Prof Neumaier was giving you a more numerically stable workaround. But I can say from my experience, imposing a Cholesky factorization type constraint does not seem to work well, and makes the problem non-convex, even if the original problem is convex; you may succeed, but you may wind up adding a bunch of spurious local optima (and even saddlepoints?) to your problem, and that is not a good thing.

Is the matrix A (constrained to be) symmetric, and do you really wish to impose that det(A) > 0 and that all leading principal submatrices have det > 0, i.e., that A be positive definite? If so, instead of using the constraint det(A) > 0 (which apart from its terrible numerical properties, is not sufficient to ensure positive definiteness of A, unless it is imposed (as perhaps you do?) on all leading principal submatrices), use a semidefinite constraint, A > 0 in Linear Matrix Inequality (LMI) sense. I.e., a constraint that A is positive definite. However, practical optimization software either does not accept strict inequality constraints, or if it does, treats them as non-strict inequality constraints. If positive semidefinite is o.k., your constraint would be A >= 0 (in LMI sense). If you really need A to be strictly positive definite (det(A) strictly positive), then you need to determine a minimum acceptable eigenvalue, min_eig, and then impose the constraint A - min_eig * (Identity matrix of correct size) >= 0 (in LMI sense). You do need to make some allowance for solver tolerance used in constraint feasibility assessment (i.e., solver will allow constraint to be violated by a little, for example, by 1e-6 or 1e-8).

Edit in response to edit of Question: As shown in the edited version of your question, A is constrained to be symmetric nonnegative and have det(A) > 0, but A is not constrained to be positive definite. It is in fact possible for an nonnegative symmetric matrix of dimension >= 3 to have positive determinant yet not be positive definite. Do you wish to allow that situation? If so, my answer above the edit above does not apply. If in fact you require A be positive definite, then my answer above the edit does apply, and you should further edit your question to reflect the constraint that A be positive definite.

The constraint $\det(A) > 0$ is very unstable and absolutely horrible. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can make the determinant computed in double precision swing from 1e20 to -1e20? Good luck in trying to have a meaningful determination of whether $\det(A)$ is > or < 0 at any point. The gradient is the least of your worries. The constraint itself just will not work unless you compute in ultra-high precision, or perhaps you are only dealing with a 2 or 3 dimensional problem. Prof Neumaier was giving you a more numerically stable workaround. But I can say from my experience, imposing a Cholesky factorization type constraint does not seem to work well, and makes the problem non-convex, even if the original problem is convex; you may succeed, but you may wind up adding a bunch of spurious local optima (and even saddlepoints?) to your problem, and that is not a good thing.

Is the matrix $A$ (constrained to be) symmetric, and do you really wish to impose that $\det(A) > 0$ and that all leading principal submatrices have $\det > 0$, i.e., that $A$ be positive definite? If so, instead of using the constraint $\det(A) > 0$ (which apart from its terrible numerical properties, is not sufficient to ensure positive definiteness of $A$, unless it is imposed (as perhaps you do?) on all leading principal submatrices), use a semidefinite constraint, $A > 0$ in Linear Matrix Inequality (LMI) sense. I.e., a constraint that A is positive definite. However, practical optimization software either does not accept strict inequality constraints, or if it does, treats them as non-strict inequality constraints. If positive semidefinite is o.k., your constraint would be $A \ge 0$ (in LMI sense). If you really need A to be strictly positive definite (det(A) strictly positive), then you need to determine a minimum acceptable eigenvalue, min_eig, and then impose the constraint A - min_eig * (Identity matrix of correct size) >= 0 (in LMI sense). You do need to make some allowance for solver tolerance used in constraint feasibility assessment (i.e., solver will allow constraint to be violated by a little, for example, by 1e-6 or 1e-8).

Edit in response to edit of Question: As shown in the edited version of your question, $A$ is constrained to be symmetric nonnegative and have $\det(A) > 0$, but $A$ is not constrained to be positive definite. It is in fact possible for an nonnegative symmetric matrix of dimension >= 3 to have positive determinant yet not be positive definite. Do you wish to allow that situation? If so, my answer above the edit above does not apply. If in fact you require $A$ be positive definite, then my answer above the edit does apply, and you should further edit your question to reflect the constraint that $A$ be positive definite.

added 622 characters in body
Source Link
Mark L. Stone
  • 1.9k
  • 8
  • 14

The constraint det(A) > 0 is VERY UNSTABLE and ABSOLUTELY HORRIBLE. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can make the determinant computed in double precision swing from 1e20 to -1e20? Good luck in trying to have a meaningful determination of whether det(A) is > or < 0 at any point. The gradient is the least of your worries. The constraint itself just will not work unless you compute in ultra-high precision, or perhaps you are only dealing with a 2 or 3 dimensional problem. Prof Neumaier was giving you a more numerically stable workaround. But I can say from my experience, imposing a Cholesky factorization type constraint does not seem to work well, and makes the problem non-convex, even if the original problem is convex; you may succeed, but you may wind up adding a bunch of spurious local optima (and even saddlepoints?) to your problem, and that is not a good thing.

Is the matrix A (constrained to be) symmetric, and do you really wish to impose that det(A) > 0 and that all leading principal submatrices have det > 0, i.e., that A be positive definite? If so, instead of using the constraint det(A) > 0 (which apart from its terrible numerical properties, is not sufficient to ensure positive definiteness of A, unless it is imposed (as perhaps you do?) on all leading principal submatrices), use a semidefinite constraint, A > 0 in Linear Matrix Inequality (LMI) sense. I.e., a constraint that A is positive definite. However, practical optimization software either does not accept strict inequality constraints, or if it does, treats them as non-strict inequality constraints. If positive semidefinite is o.k., your constraint would be A >= 0 (in LMI sense). If you really need A to be strictly positive definite (det(A) strictly positive), then you need to determine a minimum acceptable eigenvalue, min_eig, and then impose the constraint A - min_eig * (Identity matrix of correct size) >= 0 (in LMI sense). You do need to make some allowance for solver tolerance used in constraint feasibility assessment (i.e., solver will allow constraint to be violated by a little, for example, by 1e-6 or 1e-8).

At this point, it would help to know what your objective function and the rest of the constraints are. If the objective function and the rest of the constraints are convex (presuming a minimization problem), you could use CVX or YALMIP (both are free) to solve your problem. You said in a comment (belongs in the question, so you should edit) that the objective is quadratic, but is it convex? If non-convex, you may still be able to use YALMIP, perhaps in conjunction with having YALMIP call the free solver PENLAB. If you use CVX or YALMIP, they take care of any differentiation for you.

Edit in response to edit of Question: As shown in the edited version of your question, A is constrained to be symmetric nonnegative and have det(A) > 0, but A is not constrained to be positive definite. It is in fact possible for an nonnegative symmetric matrix of dimension >= 3 to have positive determinant yet not be positive definite. Do you wish to allow that situation? If so, my answer above the edit above does not apply. If in fact you require A be positive definite, then my answer above the edit does apply, and you should further edit your question to reflect the constraint that A be positive definite.

The constraint det(A) > 0 is VERY UNSTABLE and ABSOLUTELY HORRIBLE. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can make the determinant computed in double precision swing from 1e20 to -1e20? Good luck in trying to have a meaningful determination of whether det(A) is > or < 0 at any point. The gradient is the least of your worries. The constraint itself just will not work unless you compute in ultra-high precision, or perhaps you are only dealing with a 2 or 3 dimensional problem. Prof Neumaier was giving you a more numerically stable workaround. But I can say from my experience, imposing a Cholesky factorization type constraint does not seem to work well, and makes the problem non-convex, even if the original problem is convex; you may succeed, but you may wind up adding a bunch of spurious local optima (and even saddlepoints?) to your problem, and that is not a good thing.

Is the matrix A (constrained to be) symmetric, and do you really wish to impose that det(A) > 0 and that all leading principal submatrices have det > 0, i.e., that A be positive definite? If so, instead of using the constraint det(A) > 0 (which apart from its terrible numerical properties, is not sufficient to ensure positive definiteness of A, unless it is imposed (as perhaps you do?) on all leading principal submatrices), use a semidefinite constraint, A > 0 in Linear Matrix Inequality (LMI) sense. I.e., a constraint that A is positive definite. However, practical optimization software either does not accept strict inequality constraints, or if it does, treats them as non-strict inequality constraints. If positive semidefinite is o.k., your constraint would be A >= 0 (in LMI sense). If you really need A to be strictly positive definite (det(A) strictly positive), then you need to determine a minimum acceptable eigenvalue, min_eig, and then impose the constraint A - min_eig * (Identity matrix of correct size) >= 0 (in LMI sense). You do need to make some allowance for solver tolerance used in constraint feasibility assessment (i.e., solver will allow constraint to be violated by a little, for example, by 1e-6 or 1e-8).

At this point, it would help to know what your objective function and the rest of the constraints are. If the objective function and the rest of the constraints are convex (presuming a minimization problem), you could use CVX or YALMIP (both are free) to solve your problem. You said in a comment (belongs in the question, so you should edit) that the objective is quadratic, but is it convex? If non-convex, you may still be able to use YALMIP, perhaps in conjunction with having YALMIP call the free solver PENLAB. If you use CVX or YALMIP, they take care of any differentiation for you.

The constraint det(A) > 0 is VERY UNSTABLE and ABSOLUTELY HORRIBLE. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can make the determinant computed in double precision swing from 1e20 to -1e20? Good luck in trying to have a meaningful determination of whether det(A) is > or < 0 at any point. The gradient is the least of your worries. The constraint itself just will not work unless you compute in ultra-high precision, or perhaps you are only dealing with a 2 or 3 dimensional problem. Prof Neumaier was giving you a more numerically stable workaround. But I can say from my experience, imposing a Cholesky factorization type constraint does not seem to work well, and makes the problem non-convex, even if the original problem is convex; you may succeed, but you may wind up adding a bunch of spurious local optima (and even saddlepoints?) to your problem, and that is not a good thing.

Is the matrix A (constrained to be) symmetric, and do you really wish to impose that det(A) > 0 and that all leading principal submatrices have det > 0, i.e., that A be positive definite? If so, instead of using the constraint det(A) > 0 (which apart from its terrible numerical properties, is not sufficient to ensure positive definiteness of A, unless it is imposed (as perhaps you do?) on all leading principal submatrices), use a semidefinite constraint, A > 0 in Linear Matrix Inequality (LMI) sense. I.e., a constraint that A is positive definite. However, practical optimization software either does not accept strict inequality constraints, or if it does, treats them as non-strict inequality constraints. If positive semidefinite is o.k., your constraint would be A >= 0 (in LMI sense). If you really need A to be strictly positive definite (det(A) strictly positive), then you need to determine a minimum acceptable eigenvalue, min_eig, and then impose the constraint A - min_eig * (Identity matrix of correct size) >= 0 (in LMI sense). You do need to make some allowance for solver tolerance used in constraint feasibility assessment (i.e., solver will allow constraint to be violated by a little, for example, by 1e-6 or 1e-8).

At this point, it would help to know what your objective function and the rest of the constraints are. If the objective function and the rest of the constraints are convex (presuming a minimization problem), you could use CVX or YALMIP (both are free) to solve your problem. You said in a comment (belongs in the question, so you should edit) that the objective is quadratic, but is it convex? If non-convex, you may still be able to use YALMIP, perhaps in conjunction with having YALMIP call the free solver PENLAB. If you use CVX or YALMIP, they take care of any differentiation for you.

Edit in response to edit of Question: As shown in the edited version of your question, A is constrained to be symmetric nonnegative and have det(A) > 0, but A is not constrained to be positive definite. It is in fact possible for an nonnegative symmetric matrix of dimension >= 3 to have positive determinant yet not be positive definite. Do you wish to allow that situation? If so, my answer above the edit above does not apply. If in fact you require A be positive definite, then my answer above the edit does apply, and you should further edit your question to reflect the constraint that A be positive definite.

added 59 characters in body
Source Link
Mark L. Stone
  • 1.9k
  • 8
  • 14

The constraint det(A) > 0 is VERY UNSTABLE and ABSOLUTELY HORRIBLE. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can make the determinant computed in double precision swing from 1e20 to -1e20? Good luck in trying to have a meaningful determination of whether det(A) is > or < 0 at any point. The gradient is the least of your worries. The constraint itself just will not work unless you compute in ultra-high precision, or perhaps you are only dealing with a 2 or 3 dimensional problem. Prof Neumaier was giving you a more numerically stable workaround. But I can say from my experience, imposing a Cholesky factorization type constraint does not seem to work well, and makes the problem non-convex, even if the original problem is convex; you may succeed, but you may wind up adding a bunch of spurious local optima (and even saddlepoints?) to your problem, and that is not a good thing.

Is the matrix A (constrained to be) symmetric, and do you really wish to impose that det(A) > 0 and that all leading principal submatrices have det > 0, i.e., that A be positive definite? If so, instead of using the constraint det(A) > 0 (which apart from its terrible numerical properties, is not sufficient to ensure positive definiteness of A, unless it is imposed (as perhaps you do?) on all leading principal submatrices), use a semidefinite constraint, A > 0 in Linear Matrix Inequality (LMI) sense. I.e., a constraint that A is positive definite. However, practical optimization software either does not accept strict inequality constraints, or if it does, treats them as non-strict inequality constraints. If positive semidefinite is o.k., your constraint would be A >= 0 (in LMI sense). If you really need A to be strictly positive definite (det(A) strictly positive), then you need to determine a minimum acceptable eigenvalue, min_eig, and then impose the constraint A - min_eig * (Identity matrix of correct size) >= 0 (in LMI sense). You do need to make some allowance for solver tolerance used in constraint feasibility assessment (i.e., solver will allow constraint to be violated by a little, for example, by 1e-6 or 1e-8).

At this point, it would help to know what your objective function and the rest of the constraints are. If the objective function and the rest of the constraints are convex (presuming a minimization problem), you could use CVX or YALMIP (both are free) to solve your problem. You said in a comment (belongs in the question, so you should edit) that the objective is quadratic, but is it convex? If non-convex, you may still be able to use YALMIP, perhaps in conjunction with having YALMIP call the free solver PENLAB. If you use CVX or YALMIP, they take care of any differentiation for you.

The constraint det(A) > 0 is VERY UNSTABLE and ABSOLUTELY HORRIBLE. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can make the determinant computed in double precision swing from 1e20 to -1e20? Good luck in trying to have a meaningful determination of whether det(A) is > or < 0 at any point. The gradient is the least of your worries. The constraint itself just will not work unless you compute in ultra-high precision, or perhaps you are only dealing with a 2 or 3 dimensional problem. Prof Neumaier was giving you a more numerically stable workaround.

Is the matrix A (constrained to be) symmetric, and do you really wish to impose that det(A) > 0 and that all leading principal submatrices have det > 0, i.e., that A be positive definite? If so, instead of using the constraint det(A) > 0 (which apart from its terrible numerical properties, is not sufficient to ensure positive definiteness of A, unless it is imposed (as perhaps you do?) on all leading principal submatrices), use a semidefinite constraint, A > 0 in Linear Matrix Inequality (LMI) sense. I.e., a constraint that A is positive definite. However, practical optimization software either does not accept strict inequality constraints, or if it does, treats them as non-strict inequality constraints. If positive semidefinite is o.k., your constraint would be A >= 0 (in LMI sense). If you really need A to be strictly positive definite (det(A) strictly positive), then you need to determine a minimum acceptable eigenvalue, min_eig, and then impose the constraint A - min_eig * (Identity matrix of correct size) >= 0 (in LMI sense). You do need to make some allowance for solver tolerance used in constraint feasibility assessment (i.e., solver will allow constraint to be violated by a little, for example, by 1e-6 or 1e-8).

At this point, it would help to know what your objective function and the rest of the constraints are. If the objective function and the rest of the constraints are convex (presuming a minimization problem), you could use CVX or YALMIP (both are free) to solve your problem. You said that the objective is quadratic, but is it convex? If non-convex, you may still be able to use YALMIP, perhaps in conjunction with having YALMIP call the free solver PENLAB. If you use CVX or YALMIP, they take care of any differentiation for you.

The constraint det(A) > 0 is VERY UNSTABLE and ABSOLUTELY HORRIBLE. Would you believe that on practical, non-contrived 6 by 6 symmetric matrices, changing one element of the matrix by 1e-15 can make the determinant computed in double precision swing from 1e20 to -1e20? Good luck in trying to have a meaningful determination of whether det(A) is > or < 0 at any point. The gradient is the least of your worries. The constraint itself just will not work unless you compute in ultra-high precision, or perhaps you are only dealing with a 2 or 3 dimensional problem. Prof Neumaier was giving you a more numerically stable workaround. But I can say from my experience, imposing a Cholesky factorization type constraint does not seem to work well, and makes the problem non-convex, even if the original problem is convex; you may succeed, but you may wind up adding a bunch of spurious local optima (and even saddlepoints?) to your problem, and that is not a good thing.

Is the matrix A (constrained to be) symmetric, and do you really wish to impose that det(A) > 0 and that all leading principal submatrices have det > 0, i.e., that A be positive definite? If so, instead of using the constraint det(A) > 0 (which apart from its terrible numerical properties, is not sufficient to ensure positive definiteness of A, unless it is imposed (as perhaps you do?) on all leading principal submatrices), use a semidefinite constraint, A > 0 in Linear Matrix Inequality (LMI) sense. I.e., a constraint that A is positive definite. However, practical optimization software either does not accept strict inequality constraints, or if it does, treats them as non-strict inequality constraints. If positive semidefinite is o.k., your constraint would be A >= 0 (in LMI sense). If you really need A to be strictly positive definite (det(A) strictly positive), then you need to determine a minimum acceptable eigenvalue, min_eig, and then impose the constraint A - min_eig * (Identity matrix of correct size) >= 0 (in LMI sense). You do need to make some allowance for solver tolerance used in constraint feasibility assessment (i.e., solver will allow constraint to be violated by a little, for example, by 1e-6 or 1e-8).

At this point, it would help to know what your objective function and the rest of the constraints are. If the objective function and the rest of the constraints are convex (presuming a minimization problem), you could use CVX or YALMIP (both are free) to solve your problem. You said in a comment (belongs in the question, so you should edit) that the objective is quadratic, but is it convex? If non-convex, you may still be able to use YALMIP, perhaps in conjunction with having YALMIP call the free solver PENLAB. If you use CVX or YALMIP, they take care of any differentiation for you.

Source Link
Mark L. Stone
  • 1.9k
  • 8
  • 14
Loading