* why the constraints are not met (very often when H is very small, i.e. 10^-3 and lam>10) but the cvx status is 'Solved'?

drwanliwen · March 7, 2016, 11:59am

Hi everyone, this is my first using CVX, after reading users’ guide, I try to use this tool to solve a simple SDP problem.

AND the problem is** why the constraints are not met (very often when H is very small, i.e. 10^-3 and lam>10) but the cvx status is ‘Solved’?

Here is my entire code as follow
**

%%matlab code

**
gama=exp(10log(10)/10);
N0=10^(-176/10)/1000;%-176dBm
num=1e0;
lam =[10];
results = zeros(1, length(lam));
tic
for k=1:length(lam)
for i=1:num
%% channel
H=(randn(2,2)+1jrandn(2,2)); // H is complex
H1=H(1:end,1)*H(1:end,1)’; // H1 is semidefinte
H2=H(1:end,2)*H(1:end,2)’;

    cvx_begin sdp 
        variable W1(2,2) hermitian
        variable W2(2,2) hermitian
        
        P=trace(W1)+trace(W2);
       
        minimize lam(k)*P
        
        subject to
        real(trace(W1*H1))>=real((trace(W2*H1)+N0))*gama;
        real(trace(W2*H2))>=real((trace(W1*H2)+N0))*gama;
        W1>=0; // W1 is semidefinte
        W2>=0;
    cvx_end
    results(k) = results(k) + cvx_optval/num;
end

end
toc
%%
disp(‘results=’)
disp(10log10(results1000))

real(trace(W1H1))>=real((trace(W2H1)+N0))gama %% FALSE very often
real(trace(W2H2))>=real((trace(W1*H2)+N0))*gama%% FALSE very often

**

Matlab results:

**

Calling SDPT3 4.0: 10 variables, 2 equality constraints

num. of constraints = 2
dim. of socp var = 8, num. of socp blk = 2
dim. of linear var = 2

SDPT3: Infeasible path-following algorithms

version predcorr gam expon scale_data
NT 1 0.000 1 0
it pstep dstep pinfeas dinfeas gap prim-obj dual-obj cputime

0|0.000|0.000|9.1e+01|1.5e+00|3.9e+02| 8.000000e+01 0.000000e+00| 0:0:00| chol 1 1
1|0.838|1.000|1.5e+01|6.8e-03|3.9e+01| 1.982089e+01 4.265519e-20| 0:0:00| chol 1 1
2|0.981|1.000|2.8e-01|6.8e-04|7.5e-01| 3.902322e-01 4.662812e-20| 0:0:00| chol 1 1
3|0.988|1.000|3.2e-03|6.8e-05|8.7e-03| 4.529125e-03 4.700639e-20| 0:0:00| chol 1 1
4|0.989|1.000|3.6e-05|6.5e-04|9.7e-05| 5.004081e-05 4.704424e-20| 0:0:00| chol 1 1
5|0.988|1.000|4.1e-07|7.1e-06|1.1e-06| 5.791076e-07 4.744547e-20| 0:0:00| chol 1 1
6|0.515|1.000|2.0e-07|8.3e-08|6.6e-07| 3.158717e-07 6.131414e-20| 0:0:00| chol 1 1
7|0.515|1.000|9.7e-08|4.0e-08|3.9e-07| 1.741536e-07 7.888517e-20| 0:0:00| chol 1 1
8|0.515|1.000|4.7e-08|1.9e-08|2.3e-07| 9.668052e-08 1.002706e-19| 0:0:00| chol 1 1
9|0.517|1.000|2.3e-08|9.4e-09|1.3e-07| 5.401829e-08 1.261651e-19| 0:0:00| chol 1 1
10|0.519|1.000|1.1e-08|4.6e-09|7.8e-08| 3.036949e-08 1.573923e-19| 0:0:00| chol 1 1
11|0.521|1.000|5.3e-09|2.2e-09|4.6e-08| 1.717718e-08 1.949113e-19| 0:0:00| chol 1 1
12|0.524|1.000|2.5e-09|1.1e-09|2.6e-08| 9.772580e-09 2.398138e-19| 0:0:00| chol 1 1
13|0.528|1.000|1.2e-09|5.0e-10|1.5e-08| 5.591564e-09 2.933017e-19| 0:0:00| chol 1 1
14|0.532|1.000|5.5e-10|2.4e-10|8.7e-09| 3.216966e-09 3.566318e-19| 0:0:00|
stop: max(relative gap, infeasibilities) < 1.49e-08

number of iterations = 14
primal objective value = 3.21696630e-09
dual objective value = 3.56631804e-19
gap := trace(XZ) = 8.68e-09
relative gap = 8.68e-09
actual relative gap = 3.22e-09
rel. primal infeas (scaled problem) = 5.52e-10
rel. dual " " " = 2.36e-10
rel. primal infeas (unscaled problem) = 0.00e+00
rel. dual " " " = 0.00e+00
norm(X), norm(y), norm(Z) = 4.4e-10, 1.0e+01, 4.0e+02
norm(A), norm(b), norm© = 6.2e+01, 1.0e+00, 2.9e+01
Total CPU time (secs) = 0.27
CPU time per iteration = 0.02
termination code = 0
DIMACS: 5.5e-10 0.0e+00 3.3e-10 0.0e+00 3.2e-09 8.7e-09

Status: Solved
Optimal value (cvx_optval): +3.21697e-09

Elapsed time is 0.899835 seconds.
results=
-54.9255

ans =

Mark_L_Stone · March 7, 2016, 1:51pm

I just ran the code with SeDuMi, and the constraints “failed” by no more than 1e-14, which is well within allowed numerical tolerance. You are only checking for exact constraint compliance, but not allowing for numerical tolerance. If you re-read the CVX User’s Guide, you should see some discussion about this.

drwanliwen · March 8, 2016, 2:10am

Many thanks for your kindly reply! I read once again the Guide’s section 8.5 Controlling precision and found ‘cvx_precision’ that can be used to adjust the numerical tolerances. SO, I refine the code as following:
…
cvx_solver sedumi
cvx_precision best
%% channel
H=randn(2,2)1e-7%+1jrandn(2,2);
H1=H(1:end,1)*H(1:end,1)’;
H2=H(1:end,2)*H(1:end,2)’;

    cvx_begin sdp 
    .........%% same as before
    cvx_end

BUT, still, I found the constraints not been met but problem was solved. I am confused how should I control the tolerances. And the 'cvx_slvtol ’ seemed to change every time, can you help me to understand this variable? Thank you for your help!

Calling SeDuMi 1.34: 10 variables, 2 equality constraints

SeDuMi 1.34 (beta) by AdvOL, 2005-2008 and Jos F. Sturm, 1998-2003.
Alg = 2: xz-corrector, Adaptive Step-Differentiation, theta = 0.250, beta = 0.500
eqs m = 2, order n = 7, dim = 11, blocks = 3
nnz(A) = 18 + 0, nnz(ADA) = 4, nnz(L) = 3
it : by gap delta rate t/tP t/tD* feas cg cg prec
0 : 1.13E+03 0.000
1 : 2.40E-21 9.65E+01 0.000 0.0857 0.9900 0.9900 1.67 1 1 9.3E+00
2 : 6.07E-21 2.00E+01 0.000 0.2072 0.9000 0.9000 1.06 1 1 2.4E+00
3 : 7.53E-21 7.62E-01 0.000 0.0381 0.9900 0.9900 0.97 1 1 7.5E-01
4 : 7.56E-21 7.49E-05 0.000 0.0001 1.0000 1.0000 1.00 1 1 2.2E-04
5 : 7.56E-21 7.67E-12 0.000 0.0000 1.0000 1.0000 1.00 1 1 2.3E-11

iter seconds digits cx by
5 0.1 8.7 3.2738852695e-14 7.5638892446e-21
|Ax-b| = 3.3e-13, [Ay-c]_+ = 0.0E+00, |x|= 3.7e-13, |y|= 2.6e-01

Detailed timing (sec)
Pre IPM Post
8.600E-02 1.220E-01 2.200E-02
Max-norms: ||b||=2.511886e-20, ||c|| = 2,
Cholesky |add|=0, |skip| = 0, ||L.L|| = 1.

Status: Solved
Optimal value (cvx_optval): +3.27389e-14

Elapsed time is 0.663565 seconds.
results=
-104.8494

ans =

 0 **//second constrain not be met**

Mark_L_Stone · March 8, 2016, 2:30am

I think you just need to understand that your constraints will not necessarily be satisfied exactly. If you need an inequality to be satisfied exactly, you’ll need to instead provide a modified constraint, which even when not satisfied exactly, will ensure your true constraint is satisfied. So, for example,
real(trace(W1*H1)) >= real((trace(W2*H1)+N0))*gama + fudge_factor
where fudge_factor is some small positive number.

drwanliwen · March 8, 2016, 2:35am

OK, thanks for your help! I’ll try that.

* why the **constraints** are not met (very often when H is very small, i.e. 10^-3 and lam>10) but the cvx status is 'Solved'?