Problem related to relaxation of binary variables

Hi, everyone.

I am dealing with a 0-1 programming. In my program, I relax the 0-1 matrix variables X and Y to real values between 0 and 1. Then I introduce penalty terms to force the variables to take binary values. However, due to the precision of Matlab, X and Y may take values like 1e-7 or 0.9999. Although they are very close to 0 and 1, the results are not accurate. I tried to take larger penalty factors and the cvx_optval turns out to be -Inf. The optimal values of X and Y cannot be exactly 0 and 1.

In the CVX code, X and Y are optimization variables. Penalty factors are gamma and eta in line 9 and 10.

Do you have better ways to fix this out?

I have attached my code below.

clear;
clc;

%% Parameters
BW=180000;
K=15;
M=K;
N=K;
gamma=1e6;%penalty factor
eta=1e6;
iter_num=1;

noise_density_dBm=-174;
noise=10^(noise_density_dBm/10)BW;
Pu_max_dBm=23;%dBm
Pu_max=10^(Pu_max_dBm/10);
Pd_max_dBm=43;
Pd_max=10^(Pd_max_dBm/10);
Pu=Pu_max
ones(M,K);
Pd=Pd_max/N*ones(N,K);
% Pd=Pu;

Rd_min=1.5e6/BW;
Ru_min=1.8e4;
%% distance
radius=200;

U_x=random(‘uniform’,-radius,radius,M,1);
U_y=random(‘uniform’,-radius,radius,M,1);
U_d=sqrt(abs(U_x).^2+abs(U_y).^2);

D_x=random(‘uniform’,-radius,radius,N,1);
D_y=random(‘uniform’,-radius,radius,N,1);
D_d=sqrt(abs(D_x).^2+abs(D_y).^2);

d_user=zeros(M,N);
for m=1:M
for n=1:N
d_user(m,n)=sqrt(abs(U_x(m)-D_x(n))^2+abs(U_y(m)-D_y(n))^2);
end
end
%% multiple channel realization
sigma=10;
h_bb_dB=100;

beta_BU_dB=128.1+37.6log10(U_d/1000)+sigmarandn(size(U_d));
beta_BU=10.^(-beta_BU_dB/10);

beta_BD_dB=128.1+37.6log10(D_d/1000)+sigmarandn(size(D_d));
beta_BD=10.^(-beta_BD_dB/10);

beta_user_dB=148+40log10(d_user/1000)+sigmarandn(size(d_user));
beta_user=10.^(-beta_user_dB/10);

h_mk=sqrt(beta_BU).(randn(M,K)+1jrandn(M,K))/sqrt(2);
h_nk=sqrt(beta_BD).(randn(N,K)+1jrandn(N,K))/sqrt(2);
h_bbk=sqrt(10.^(-h_bb_dB/10))(randn(1,K)+1jrandn(1,K))/sqrt(2);

for k=1:K
h_user=sqrt(beta_user).(randn(M,N)+1jrandn(M,N))/sqrt(2);
H(:,:,k)=h_user;
end

%% Initial (Greedy) RB assignments to X and Y.
X_i=eye(M);

Y_i=eye(N);
%% CVX: compute the optimal X and P for FD RBs

f2_i=Msum(log2(noise+sum(Y_i.Pd.(abs(h_bbk).^2),1)))+sum(sum(log2(noise+squeeze(sum(shiftdim(((X_i.Pu)’).ones(K,M,N),1).(abs(H).^2),1)))))- …
gamma
(sum(sum(X_i.^2)))-eta
(sum(sum(Y_i.^2)));
grad_x=squeeze(sum(shiftdim((Pu’).ones(K,M,N),1).(abs(H).^2)./((noise+shiftdim(repmat(squeeze(sum(shiftdim((X_i’).ones(K,M,N),1).shiftdim((Pu’).ones(K,M,N),1).(abs(H).^2),1)),[1,1,M]),2))log(2)),2))- …
2
gamma
X_i;
gradx=reshape(grad_x,1,M
K);
grad_y=MPd.(abs(h_bbk).^2)./((noise+sum(Y_i.Pd.(abs(h_bbk).^2),1))log(2))-2etaY_i;
grady=reshape(grad_y,1,N
K);

cvx_begin
cvx_solver mosek
variables X(M,K) Y(N,K)
minimize(-(sum(sum( log(noise+repmat(sum(Y.Pd.(abs(h_bbk).^2.ones(N,K)),1),M,1)+X.Pu.(abs(h_mk).^2))/log(2) ))+ …
sum(sum( log(noise+ squeeze(sum(shiftdim(repmat((X.Pu)’,[1,1,N]),1).(abs(H).^2),1)) +Y.Pd.(abs(h_nk).^2))/log(2) )) - …
-gamma
sum(sum(X))-etasum(sum(Y))- …
(f2_i+gradx
(reshape(X-X_i,1,MK))’+grady(reshape(Y-Y_i,1,N*K))’)));
subject to
X>=0
X<=1
Y>=0
Y<=1
sum(X,1)<=1
sum(X,2)==1
sum(Y,1)<=1
sum(Y,2)==1
cvx_endPreformatted text

And here is a log under large penalty factors.

Calling Mosek 9.1.9: 2310 variables, 900 equality constraints
For improved efficiency, Mosek is solving the dual problem.

MOSEK Version 9.1.9 (Build date: 2019-11-21 11:34:40)
Copyright © MOSEK ApS, Denmark. WWW: mosek.com
Platform: Windows/64-X86

MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1637) of matrix ‘A’.
MOSEK warning 710: #5 (nearly) zero elements are specified in sparse col ‘’ (1640) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (1643) of matrix ‘A’.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1646) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (1649) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (1652) of matrix ‘A’.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1655) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (1664) of matrix ‘A’.
MOSEK warning 710: #2 (nearly) zero elements are specified in sparse col ‘’ (1667) of matrix ‘A’.
MOSEK warning 710: #1 (nearly) zero elements are specified in sparse col ‘’ (1670) of matrix ‘A’.
Warning number 710 is disabled.
MOSEK warning 52: A numerically large lower bound value 3.5e+08 is specified for constraint ‘’ (198).
MOSEK warning 53: A numerically large upper bound value 3.5e+08 is specified for constraint ‘’ (198).
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 900
Cones : 450
Scalar variables : 2310
Matrix variables : 0
Integer variables : 0

Optimizer started.
Presolve started.
Linear dependency checker started.
Linear dependency checker terminated.
Eliminator started.
Freed constraints in eliminator : 0
Eliminator terminated.
Eliminator - tries : 1 time : 0.00
Lin. dep. - tries : 1 time : 0.02
Lin. dep. - number : 0
Presolve terminated. Time: 0.03
GP based matrix reordering started.
GP based matrix reordering terminated.
Problem
Name :
Objective sense : min
Type : CONIC (conic optimization problem)
Constraints : 900
Cones : 450
Scalar variables : 2310
Matrix variables : 0
Integer variables : 0

Optimizer - threads : 4
Optimizer - solved problem : the primal
Optimizer - Constraints : 450
Optimizer - Cones : 451
Optimizer - Scalar variables : 2311 conic : 1381
Optimizer - Semi-definite variables: 0 scalarized : 0
Factor - setup time : 0.02 dense det. time : 0.00
Factor - ML order time : 0.00 GP order time : 0.02
Factor - nonzeros before factor : 1.06e+04 after factor : 6.92e+04
Factor - dense dim. : 2 flops : 1.38e+07
Factor - GP saved nzs : 263 GP saved flops : 1.40e+05
ITE PFEAS DFEAS GFEAS PRSTATUS POBJ DOBJ MU TIME
0 3.5e+08 1.4e+01 9.0e+02 0.00e+00 3.725272817e+02 -5.226824993e+02 1.0e+00 0.06
1 6.3e+07 2.5e+00 1.6e+02 -1.00e+00 4.205595879e+03 3.837302051e+03 1.8e-01 0.17
2 5.1e+05 2.1e-02 7.9e+01 -1.00e+00 6.259038136e+05 6.245355690e+05 1.5e-03 0.17
3 3.4e+03 1.4e-04 6.4e+00 -1.00e+00 9.487719782e+07 9.497738092e+07 9.8e-06 0.19
Optimizer terminated. Time: 0.25

Interior-point solution summary
Problem status : PRIMAL_INFEASIBLE
Solution status : PRIMAL_INFEASIBLE_CER
Dual. obj: 9.2906447251e+02 nrm: 1e+00 Viol. con: 0e+00 var: 8e-06 cones: 0e+00
Optimizer summary
Optimizer - time: 0.25
Interior-point - iterations : 3 time: 0.19
Basis identification - time: 0.00
Primal - iterations : 0 time: 0.00
Dual - iterations : 0 time: 0.00
Clean primal - iterations : 0 time: 0.00
Clean dual - iterations : 0 time: 0.00
Simplex - time: 0.00
Primal simplex - iterations : 0 time: 0.00
Dual simplex - iterations : 0 time: 0.00
Mixed integer - relaxations: 0 time: 0.00


Status: Unbounded
Optimal value (cvx_optval): -Inf

Your relaxation s very bad numerically. Mosek is warning you. I recommend you declare binary variables as such in CVX, and let Mosek deal with them.

Thank you, Mark. I think it’s a feasible method to solve this problem. But I prefer using relaxation to reduce computing complexity. Is it possible to improve the relaxation?

I gave you my recommendation. Mosek knows how to relax better than you do.

OK, thanks for your suggestions.