Multiple constraint feasibility

Uncategorized
May 2, 2014
A

Hello dear friends,

I’m trying to solve the following feasibility problem in CVX as:

cvx_begin SDP quiet

cvx_precision high
variable X( N , N ) hermitian

maximize 0

subject to

X           >= 0 ;
trace(X*A) == 1;
trace(X*B) == x_min*trace(X*C); 

cvx_end

where \bf{A}, \bf{B} and \bf{C} are Hermitian matrices containing constant values. The problem is solved by exhaustive or bisection search over the parameter x_{min}.

When I run it, it returns infeasible for the “cvx_status” string. On the other hand, a random Gaussian complex vector as \bf{x} can be generated and normalized to satisfies the constraint “trace(X*A) == 1”. Furthermore, the corresponding parameter x_{min} can be found. Then, if we solve the above problem using the found x_{min}, it becomes infeasible. This happens while we just found a feasible solution for the problem by the same x_{min}.

If we omit the constraint “trace(X*A) == 1” from the problem, it becomes solved. But according to above paragraph, it seems that there is a problem with CVX.

Best regards,
Ashkan

A

It seems that the source of the problem are low order matrices containing elements from the order 10^{-15}. If you multiply the matrices by 10^{15} and scale them up, the problems are not infeasible anymore and get solved.

It seems that either MATLAB or CVX has difficulty handling very small numbers.

M

Oh, this is most definitely the case. At some point, the solvers must decide whether a number is “close to zero” or “truly zero”.

A

Dear Michael, thanks for the insight.