What if the iteration graph does not converge?

[xulele (xu)]

clc;
clear;
close all;
M = 2;
K = 2;
L = 2;
T = 1;
PC_k = 0.00001;
eta = 0.8;
Rmin_k = 0.4;
sigma = 10^(-6);
E_hm = 0.387930eye(2);
E_k = 1.29857eye(6);
P_max = 1;
delta_k = 0.4;
upsilon_k = 0.4;
g_k = 1.6397900000000000 - 0.0001410100000000000i;
G_k = [0.81000000000000 - 0.0390100000000000i;0.0151000000000000 - 0.07500000000000i];
f_k = [0.2725900000000 - 0.015500000000000i,1.190000000000000 - 0.16300000000000i];
h_k = [-0.11680000000000 + 0.126200000000000i;-0.012775000000000000000 + 0.11400000000000i];
A = diag(conj(G_k).‘)(conj(f_k).')(conj(h_k).’);
B = g_k*(conj(h_k).‘);
H1 = horzcat(A, B’);
H_k = (conj(H1).‘);
I = [];
R_sum = [];
for i=1:1:10
%
theta1 = 2pirand;
theta2 = 2pirand;
V_1k = exp(1).^(1jtheta1);
V_2k = exp(1).^(1jtheta2);
theta_1k = [V_1k,V_2k];
theta_k = horzcat(theta_1k,1);
psi_k = [0.1,0.1];
alpha_1k = [0.5;0.5];
W_1k = eye(2);
cvx_begin sdp
cvx_solver mosek
variable Theta_k(3,3) complex hermitian
variable t_k(K)
variables b3k(K) b4k(K) d3k(K) d4k(K) mu_k(K)
expressions A3 a3 c3 A4 a4 c4 D2 I_2k chi_2k Z_k e_k
for k=1:1:K
chi_2k(k) = (alpha_1k(k)*real(theta_k)*real(H_k)*real(W_1k)*real((conj(H_k).’))*real((conj(theta_k.‘))))./(sigma^2);
Z_k(k) = t_k(k).chi_2k(k);
I_2k(k) = 2^(Rmin_k.(inv_pos(t_k(k))))-1;
A3 = real(sqrt(E_k))*real(kron(W_1k,Theta_k))*real(sqrt(E_k));
a3 = real(kron(W_1k,Theta_k))*real(sqrt(E_k))*real(vec(H_k));
c3 = real((conj(vec(H_k)).’))*real(kron(W_1k,Theta_k))real(vec(H_k))-(sigma^2I_2k(k))./alpha_1k(k);
A4 = real(sqrt(E_hm))*real(((T-t_k(k).*alpha_1k(k))etaW_1k))*real(sqrt(E_hm));
a4 = real(sqrt(E_hm))*real(((T-t_k(k).*alpha_1k(k))etaW_1k))*real(h_k);
c4 = real((conj(h_k).‘))*real(((T-t_k(k).*alpha_1k(k))etaW_1k))real(h_k)-t_k(k).PC_k;
e_k(k) = 1+Z_k(k)-t_k(k);
end
max sum(psi_k.(-rel_entr(t_k,t_k+Z_k))/log(2))
subject to
for k=1:1:K
-(real(trace(A3))-sqrt(-2log(delta_k))*b3k(k)+log(delta_k)*b4k(k)+c3 ) <= 0;
norm([vec(A3);sqrt(2)*a3]) <= b3k(k);
b4k(k)eye(6)+A3 == hermitian_semidefinite(6);
b4k(k) >= 0;
end
for k=1:1:K
real(trace(A4))-sqrt(-2log(delta_k))*d3k(k)+log(delta_k)*d4k(k)+c4 >= 0;
norm([vec(A4);sqrt(2)*a4]) <= d3k(k);
d4k(k)*eye(K)+A4 == hermitian_semidefinite(K);
d4k(k) >= 0;
end
for k=1:1:K
sum(t_k(k)) <= T;
t_k(k) >= 0;
end
for k=1:1:K
mu_k(k) >= 0;
end
for k=1:1:K
D2 = [mu_k(k)*eye(6)-real(sqrt(E_k))*real(kron(W_1k,Theta_k))*real(sqrt(E_k)), -real(kron(W_1k,Theta_k))*real(sqrt(E_k))*real(vec(H_k));
-real((conj(vec(H_k)).’))*real(sqrt(E_k))*real(kron(W_1k,Theta_k)), -mu_k(k)-real((conj(vec(H_k))'))*real(kron(W_1k,Theta_k))*real(vec(H_k))+(e_k(k)./alpha_1k(k))*sigma^2];
end
Theta_k == hermitian_semidefinite(3);
D2 == hermitian_semidefinite(7);
cvx_end

cvx_begin sdp
cvx_solver mosek
variable W_k(K,K) complex hermitian
variables b1k(K) b2k(K) d1k(K) d2k(K) mu_k(K)
expressions A1 a1 c1 A2 a2 c2 D1 chi_1k I_1k
for k=1:1:K
chi_1k(k) = (alpha_1k(k)*real(theta_k)*real(H_k)*real(W_k)*real((conj(H_k).‘))*real((conj(theta_k.’))))./(sigma^2);
I_1k(k) = 2.^(Rmin_k./t_k(k))-1;
A1 = real(sqrt(E_k))*real(kron(W_k,Theta_k))*real(sqrt(E_k));
a1 = kron(W_k,Theta_k)*real(sqrt(E_k))*real(vec(H_k));
c1 = real((conj(vec(H_k)).‘))*kron(W_k,Theta_k)real(vec(H_k))-(sigma^2I_1k(k))./alpha_1k(k);
A2 = real(sqrt(E_hm))*real(((T-t_k(k).*alpha_1k(k))etaW_k))*real(sqrt(E_hm));
a2 = real(sqrt(E_hm))*real(((T-t_k(k).*alpha_1k(k))etaW_k))*real(h_k);
c2 = real((conj(h_k).’))*real(((T-t_k(k).*alpha_1k(k))etaW_k))*real(h_k)-t_k(k)PC_k;
end
max sum(psi_k.t_k.(log(1+chi_1k)/log(2)))
subject to
for k=1:1:K
real(trace(W_k)) <= P_max;
end
for k=1:1:K
real(real(trace(A1))-sqrt(-2log(delta_k))*b1k(k)+log(delta_k)*b2k(k)+c1) >= 0;
norm([vec(A1);sqrt(2)*a1]) <= b1k(k);
b2k(k)eye(6)+A1 == hermitian_semidefinite(6);
b2k(k) >= 0;
end
for k=1:1:K
real(real(trace(A2))-sqrt(-2log(upsilon_k))*d1k(k)+log(upsilon_k)*d2k(k)+c2) >= 0;
norm([vec(A2);sqrt(2)*a2]) <= d1k(k);
d2k(k)*eye(K)+A2 == hermitian_semidefinite(K);
d2k(k) >= 0;
end
for k=1:1:K
mu_k(k) >= 0;
end
for k=1:1:K
D1 = [mu_k(k)*eye(6)-real(sqrt(E_k))*real(kron(W_k,Theta_k))*real(sqrt(E_k)), -real(kron(W_k,Theta_k))*real(sqrt(E_k))*real(vec(H_k));…
-real((conj(vec(H_k)).‘))*real(sqrt(E_k))*real(kron(W_k,Theta_k)), -mu_k(k)-real((conj(vec(H_k))’))*real(kron(W_k,Theta_k))*real(vec(H_k))+(chi_1k(k)./alpha_1k(k))*sigma^2];
end
D1 == hermitian_semidefinite(7);
W_k == hermitian_semidefinite(K);

cvx_end
cvx_begin
cvx_solver mosek
variable alpha_k(K)
variables b5k(K) b6k(K) d5k(K) d6k(K) mu_k(K)
expressions A5 a5 c5 A6 a6 c6 D3 chi_3k F_k I_3k
for k=1:1:K
chi_3k(k) = (alpha_k(k)*real(theta_k)*real(H_k)*real(W_k)*real((conj(H_k).‘))*real((conj(theta_k.’))))./(sigma.^2);
I_3k(k) = 2.^(Rmin_k./t_k(k))-1;
F_k(k) = 1+chi_3k(k)-alpha_k(k);
A5 = real(sqrt(E_k))*real(kron(W_k,Theta_k))*real(sqrt(E_k));
a5 = real(kron(W_k,Theta_k))*real(sqrt(E_k))*real(vec(H_k));
c5 = real((conj(vec(H_k)).‘))*real(kron(W_k,Theta_k))real(vec(H_k))-sigma^2I_3k(k).*inv_pos(alpha_k(k));
A6 = real(sqrt(E_hm))*real(((T-t_k(k).*alpha_k(k))etaW_k))*real(sqrt(E_hm));
a6 = real(sqrt(E_hm))*real(((T-t_k(k).*alpha_k(k))etaW_k))*real(h_k);
c6 = real((conj(h_k).’))*real(((T-t_k(k).alpha_k(k))etaW_k))real(h_k)-t_k(k)PC_k;
end
max sum(psi_kt_k(log(1+chi_3k)/log(2)))
subject to
for k=1:1:K
-(real(trace(A5))-sqrt(-2log(delta_k))*b5k(k)+log(delta_k)*b6k(k)+c5 ) <= 0;
norm([vec(A5);sqrt(2)*a5]) <= b5k(k);
b6k(k)eye(6)+A5 == hermitian_semidefinite(6);
b6k(k) >= 0;
end
for k=1:1:K
real(trace(A6))-sqrt(-2log(upsilon_k))*d5k(k)+log(upsilon_k)*d6k(k)+c6 >= 0;
norm([vec(A6);sqrt(2)*a6]) <= d5k(k);
d6k(k)*eye(K)+A6 == hermitian_semidefinite(K);
d6k(k) >= 0;
end
for k=1:1:K
0 <= alpha_k(k) <= 1;
end
for k=1:K
mu_k(k) >= 0;
end
for k=1:1:K
D3 = [mu_k(k)*eye(6)-real(sqrt(E_k))*real(kron(W_k,Theta_k))*real(sqrt(E_k)), -real(kron(W_k,Theta_k))*real(sqrt(E_k))*real(vec(H_k));
-real((conj(vec(H_k)).‘))*real(sqrt(E_k))*real(kron(W_k,Theta_k)), -mu_k(k)-real((conj(vec(H_k))’))*real(kron(W_k,Theta_k))*real(vec(H_k))+F_k(k)*sigma^2];
end

D3 == hermitian_semidefinite(7);
cvx_end
a1 = sum(psi_k.t_k.(log(1+(alpha_k*real(theta_k)*real(H_k)*real(W_k)*real((conj(H_k).‘))*real((conj(theta_k.’))))./(sigma^2))/log(2)));
a = a1(1);
I = [I i];
R_sum = [R_sum a];
end

figure;
plot(I,R_sum(:),‘k-*’);
xlabel(‘Iteration’);
ylabel(‘throughout(Mbps)’);
Dear Mark, I ultimately want to obtain a convergent iteration diagram, but after repeated debugging, I still cannot make the final iteration diagram converge because I used alternating optimization method to achieve it, and there are random functions in the subproblems, which leads to different results in each run. Do you have any good suggestions for me to achieve convergence of the iteration diagram? Looking forward to your reply. The above is my complete MATLAB code.

[Mark_L_Stone]

Why should the alternating optimization necessarily converge to anything? Do you have a proof that it does?

In general, posters can’t expect to get much, if any, help on this forum as to how to make alternating optimization or Successive Convex Approximation work well, or at all. Just because a paper or book shows an example where such a scheme appears to work, doesn’t mean that all, or even many, examples are likely to work.

[Liuyep]

hello, I use the Taylor approximation to tranform a nonconvex problem into a convex problem, and I use CVX to solve it. However, the iteration graph is not convergent. How do you sovle it or do you know what make the curve up and down? Thanks

[Mark_L_Stone]

See my preceding post.

Also see

The result obtained using the SeDuMi solver is inaccurate. The optimal solution is not as good as before the optimization.

Unsafeguarded (no line search or trust region)Successive Convex Approximation (SCA) or generally, alternating variables optimization are unreliable. It might not descend (for minimization problem), i.e., iterates could get worse. It might not converge to anything; and if it does converge, it might not be to a local optimum of the original problem, let alone a global optimum. The solution of successive iterations, and therefore subproblem inputs, can become wilder and wilder, until at some point …