I have a problem related to numerical error in convex toolbox. I tried to use convex toolbox to solve a optimization problem:
minimize f(x)
subject to
a'*x+x'*a-a'*a > A
(x,a are vectors, A is a matrix)
However, after getting the result, I substitute the value of x into the constraint LMI, and try to calculate the eigenvalues of matrix a'*x+x'*a-a'*a - A, some of the eigenvalues are not positive, they are around -1e-9. It means the LMI constraint is not satisfied.
So I just wonder if there is any way to solve this issue. I already tried to use some methods suggested by this page “http://cvxr.com/cvx/doc/support.html” but it doesn’t help.
Your “difficulty” probably has to do with solver tolerances, since solvers do not exactly honor constraints they are provided.
Aside from possibly adjusting tolerances, and maybe trying different solvers, you could explicitly build in a buffer for your LMI (which should really use >= not >) being satisfied (or equivalently, a minimum eigenvalue). So pick a value for epsilon, such as 1e-6 (maybe you can get by with 1e-8), and presuming that A is n by n, specify
a'x+x'a-a'a - epsilon*eye(n) >= A
if invoked by cvx_begin sdp, or if not invoked by cvx_begin sdp, then
a'x+x'a-a'a - A - epsilon*eye(n) = semidefinite(n)
Hopefully, the reported solution will strictly satisfy your LMI as originally written, with the solver tolerance slop being less than the buffer you built in.
Thanks a lot for your answer. I tried to increase the precision of the solver in cvx toolbox, I set it to high, but the problem still remains.
I also tried to use your method, but it doesn’t help,too. When I tried to choose epsilon from 1e-3 to 1e-8, the computed eigenvalues are still negative. When I increased epsilon, made it bigger, like 0.1 to 1e-2, solver can’t solve the problem, the result is NaN.
I don’t know if the numerical error is related to the rank of matrix a’x+x’a-a’a, because normally in my case, it’s not full rank.
I suggest you edit your post and show your complete problem specification, including definitions of any relevant matrices, vectors and scalars. Also include the solver output, including intermediate output (don’t use quiet mode) for all the solvers you have installed (at least SeDuMi and sdpt3).
This is simply the nature of inexact numerical solvers. Small errors like this have to be expected, and correcting them as needed is an essential part of your engineering process. Mark’s suggestion is a good one. But the proper answer necessarily depends on the specific application.
I’m going to edit your title to better reflect the nature of this question, which is certainly a good one for this forum! I thank you for bringing it.