Unbounded output due to mutual infeasibility in cvx

I am trying to maximize this capacity function with respect to the matrix F:

maximize( log_det( eye( 6, 6 ) + ( sigma^-2.eye( 6,6 ))HF*H’ )) subject to the constrains:

(1) trace( F ) <= Pt should be a positive value

(2) trace( GFG’ ) <= Ith should be a positive value

such that:

(’): is the complex conjugate of a matrix

F : 12x12 is a variable complex hermitian positive definite matrix

I : is a 6x6 identity matrix

H : 6x12 is a constant matrix

G : 3x12 is a constant matrix

Pt: is a scalar constant

Ith: is a scalar constant

sigma: is a scalar constant

H & G were just randn complex matrices

the code is

Nr = 6;
Nt = 10;
Np = 3;

H = randn(Nr,Nt)+irandn(Nr,Nt);
G = randn(Np,Nt)+i
randn(Np,Nt);
I = eye(Nr,Nr);
Pt = 10;
Ith = 1;
sigma = 5;

cvx_begin sdp

variable F(Nt,Nt) complex hermitian semidefinite

minimize( - det_rootn( I + ( sigma ^-2.I ) H * F * H’ ) )

subject to

trace(GFG’) >=0;

trace(F) >=0;

trace(F) <= Pt;

trace(GFG’) <= Ith;

cvx_end

result:

Status: Unbounded
Optimal value (cvx_optval): -Inf

Do you mean your minimize line to be
minimize( - det_rootn( I + ( sigma ^-2.*I )* H * F * H' ) )
which is also the same as

minimize( - det_rootn( I + ( sigma ^-2)* H * F * H’ ) )

I successfully solved a couple of random instances of this problem with both SeDuMi and SDPT3, getting the same answers with both solvers. However, I did receive warnings of coefficient matrix not being full rank, or nearly dependent constraints. I haven’t looked at your problem carefully enough to know whether it could be infeasible for any random instances of G and H.

That is absolutely right. You can also take the identity matrix out as it yields the same equation. Anyway, i didn’t understand the point when you said that you have successfully solved random instances of this problem. Do you mean that the status of the problem was “Solved” and you have received a bounded result of the argument? because i have never got any bounded solution with both of those solvers. I believe that it is possible that i have a bug in the software package as i am running it on linux - XFC. I believe that the problem is feasible

THIS IS MY CURRENT OUTPUT

Calling SDPT3 4.0: 533 variables, 58 equality constraints

num. of constraints = 58
dim. of sdp var = 44, num. of sdp blk = 2
dim. of socp var = 18, num. of socp blk = 6
dim. of linear var = 4
dim. of free var = 1
6 linear variables from unrestricted variable.

*** convert ublk to linear blk
*** convert ublk to linear blk


SDPT3: homogeneous self-dual path-following algorithms


version predcorr gam expon
HKM 1 0.000 1
it pstep dstep pinfeas dinfeas gap mean(obj) cputime kap tau theta

0|0.000|0.000|3.9e+00|4.4e+00|7.3e+01|-5.000000e-01| 0:0:00|7.3e+01|1.0e+00|1.0e+00| chol 1 1
1|1.000|1.000|1.8e+00|2.0e+00|6.1e+01|-5.494814e-01| 0:0:00|2.4e+01|7.0e-01|3.2e-01| chol 1 1
2|0.784|0.784|8.3e-01|9.4e-01|3.7e+01|-8.587416e-01| 0:0:00|9.9e+00|5.8e-01|1.2e-01| chol 1 1
3|1.000|1.000|1.4e+00|1.6e+00|3.0e+02|-7.418333e+00| 0:0:00|7.7e+00|1.6e-01|5.7e-02| chol 1 1
4|0.884|0.884|4.0e-01|4.6e-01|1.3e+02|-1.721727e+01| 0:0:00|4.9e+00|8.8e-02|9.1e-03| chol 1 1
5|1.000|1.000|7.0e-01|8.0e-01|2.1e+03|-1.788767e+02| 0:0:00|4.6e+00|1.1e-02|1.9e-03| chol 1 1
6|0.960|0.960|3.7e-01|4.2e-01|8.0e+03|-1.726287e+03| 0:0:01|4.6e+00|1.2e-03|1.2e-04| chol 1 1
7|0.971|0.971|3.1e-01|3.5e-01|9.9e+04|-3.157875e+04| 0:0:01|4.6e+00|7.2e-05|5.8e-06| chol 1 1
8|0.966|0.966|2.9e-01|3.3e-01|1.6e+06|-6.166149e+05| 0:0:01|4.7e+00|3.9e-06|2.8e-07|
Stop: dual problem is suspected of being infeasible

number of iterations = 8
residual of dual infeasibility
certificate X = 2.32e-07
reldist to infeas. <= 3.22e-09
Total CPU time (secs) = 0.56
CPU time per iteration = 0.07
termination code = 2
DIMACS: 2.9e-01 0.0e+00 3.3e-01 0.0e+00 -1.0e+00 1.3e+00


Status: Unbounded
Optimal value (cvx_optval): -Inf

Here is what I got for one of the random instances of H and G.
With SeDuMi:

Calling SeDuMi 1.34: 267 variables, 144 equality constraints
------------------------------------------------------------
Warning: Rank deficient, rank = 124, tol =  1.031070e-10. 
> In sedumi at 268
  In cvx_run_solver at 50
  In cvx_sedumi>solve at 245
  In cvxprob.solve at 428
  In cvx_end at 87 
The coefficient matrix is not full row rank, numerical problems may occur.
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 = 144, order n = 40, dim = 512, blocks = 9
nnz(A) = 5901 + 0, nnz(ADA) = 18310, nnz(L) = 9242
 it :     b*y       gap    delta  rate   t/tP*  t/tD*   feas cg cg  prec
  0 :            1.55E+01 0.000
  1 :  -6.38E+00 5.50E+00 0.000 0.3556 0.9000 0.9000   2.33  1  1  1.9E+01
  2 :  -2.41E+00 1.69E+00 0.000 0.3070 0.9000 0.9000   2.34  1  1  3.5E+00
  3 :  -1.75E+00 4.22E-01 0.000 0.2501 0.9000 0.9000   1.33  1  1  7.8E-01
  4 :  -1.87E+00 8.56E-02 0.000 0.2027 0.9000 0.9000   0.94  1  1  1.6E-01
  5 :  -1.91E+00 8.14E-03 0.000 0.0950 0.9900 0.9900   0.99  1  1  1.6E-02
  6 :  -1.91E+00 6.69E-04 0.000 0.0822 0.9000 0.0000   1.00  1  1  3.9E-03
  7 :  -1.92E+00 1.30E-05 0.000 0.0194 0.9907 0.9900   1.00  1  1  1.6E-04
  8 :  -1.92E+00 4.13E-07 0.000 0.0319 0.9902 0.9900   1.00  1  1  5.9E-06
  9 :  -1.92E+00 8.69E-08 0.000 0.2103 0.9000 0.8687   1.00  1  1  1.2E-06
 10 :  -1.92E+00 3.06E-08 0.000 0.3514 0.9000 0.7677   1.00  1  1  4.0E-07
 11 :  -1.92E+00 1.32E-08 0.000 0.4319 0.9000 0.6788   1.00  1  1  1.6E-07
 12 :  -1.92E+00 5.34E-09 0.000 0.4043 0.9000 0.7424   1.00  1  1  6.1E-08
 13 :  -1.92E+00 1.87E-09 0.000 0.3504 0.9000 0.7085   1.00  1  1  2.1E-08
 14 :  -1.92E+00 5.46E-10 0.000 0.2920 0.9000 0.7487   1.00  1  2  6.1E-09

iter seconds digits       c*x               b*y
 14      1.6   Inf -1.9199876240e+00 -1.9199876184e+00
|Ax-b| =   3.3e-08, [Ay-c]_+ =   8.4E-10, |x|=  1.8e+01, |y|=  2.1e+00

Detailed timing (sec)
   Pre          IPM          Post
1.400E-02    1.940E-01    2.002E-03    
Max-norms: ||b||=10, ||c|| = 1.000000e+00,
Cholesky |add|=0, |skip| = 20, ||L.L|| = 535.641.
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -1.91999

Same H and G as above, but with SDPT3:

 Calling SDPT3 4.0: 267 variables, 144 equality constraints
------------------------------------------------------------

 num. of constraints = 144
 dim. of sdp    var  = 56,   num. of sdp  blk  =  8
 dim. of linear var  =  5
 number of nearly dependent constraints = 20
 To remove these constraints, re-run sqlp.m with OPTIONS.rmdepconstr = 1.
*******************************************************************
   SDPT3: Infeasible path-following algorithms
*******************************************************************
 version  predcorr  gam  expon  scale_data
   HKM      1      0.000   1        0    
it pstep dstep pinfeas dinfeas  gap      prim-obj      dual-obj    cputime
-------------------------------------------------------------------
 0||0.000||0.000||4.1e+02||4.6e+01||9.4e+04||-9.701626e+00  0.000000e+00|| 0:0:00|| chol  1  1 
 1||0.238||0.724||3.1e+02||1.3e+01||9.0e+04|| 9.532086e+00 -1.424646e+03|| 0:0:01|| chol  1  1 
 2||0.947||1.000||1.7e+01||9.0e-02||5.7e+03|| 2.190449e+01 -1.112847e+03|| 0:0:01|| chol  1  1 
 3||0.959||0.987||6.9e-01||1.0e-02||6.3e+02|| 1.098220e+00 -4.846120e+02|| 0:0:01|| chol  1  1 
 4||1.000||0.918||1.5e-07||1.6e-03||7.0e+01||-1.602152e-01 -7.002483e+01|| 0:0:01|| chol  1  1 
 5||1.000||0.886||5.0e-08||2.7e-04||8.4e+00||-4.244311e-01 -8.835594e+00|| 0:0:01|| chol  1  1 
 6||0.885||1.000||8.6e-09||9.0e-06||4.6e+00||-1.219593e+00 -5.843789e+00|| 0:0:01|| chol  1  1 
 7||0.995||0.905||4.2e-09||1.7e-06||4.7e-01||-1.624154e+00 -2.095788e+00|| 0:0:01|| chol  1  1 
 8||0.923||1.000||1.3e-09||9.1e-08||1.7e-01||-1.852451e+00 -2.024653e+00|| 0:0:01|| chol  1  1 
 9||0.980||0.882||5.8e-10||1.9e-08||1.8e-02||-1.915192e+00 -1.933270e+00|| 0:0:01|| chol  1  1 
10||0.985||0.973||1.8e-10||1.5e-09||7.1e-04||-1.919765e+00 -1.920477e+00|| 0:0:01||# chol  1  2 
11||0.966||0.976||6.1e-11||1.6e-10||2.0e-05||-1.919980e+00 -1.920000e+00|| 0:0:01||# chol  2  2 
12||1.000||1.000||8.1e-11||1.2e-11||1.8e-06||-1.919987e+00 -1.919988e+00|| 0:0:01||# chol  2  2 
13||1.000||1.000||4.2e-11||1.6e-11||7.5e-08||-1.919988e+00 -1.919988e+00|| 0:0:01||# chol  2  2 
14||1.000||1.000||2.1e-11||8.4e-12||4.2e-09||-1.919988e+00 -1.919988e+00|| 0:0:01||
  stop: max(relative gap, infeasibilities) < 1.49e-08
-------------------------------------------------------------------
 number of iterations   = 14
 primal objective value = -1.91998765e+00
 dual   objective value = -1.91998765e+00
 gap := trace(XZ)       = 4.19e-09
 relative gap           = 8.66e-10
 actual relative gap    = 6.28e-10
 rel. primal infeas     = 2.10e-11
 rel. dual   infeas     = 8.36e-12
 norm(X), norm(y), norm(Z) = 2.4e+01, 1.2e+08, 2.2e+00
 norm(A), norm(b), norm(C) = 3.0e+01, 1.1e+01, 2.4e+00
 Total CPU time (secs)  = 0.85  
 CPU time per iteration = 0.06  
 termination code       =  0
 DIMACS: 2.2e-11  0.0e+00  1.0e-11  0.0e+00  6.3e-10  8.7e-10
-------------------------------------------------------------------
------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -1.91999
1 Like

That is a great result. But i still don’t know why my software package doesn’t give that answer. I will try it on windows and see if things change with it. Please keep tracking this question of course if you are interested to know what happens at last and i thank you very much for your help.