Right Solver for SCA using Exponential Sets

[mardank (Markus Krantzik)]

Hey!
I’m currently working on solving the following problem. Here I use successive convex aproximation of the function 1/mu in constraint (1c).

Until now, the problem in CVX only converges if I use Mosek at default (not best) precision. Is there a reason why solvers like sedumi or sdpt3 are not converging?

Convert problem to cvx

Unfortunately, you started with a tricky problem on which to start using CVX. As I wrote above, z needs to be declared a (CVX) variable. Given that you really need z to be a length n,vector, and still need bw to be a CVX variable, you can use variables bw(n) z(n) I’m not sure I understand the relation between your code and the problem in your first post, so I will present code as if the simplified 1-D indexing in your code covers your situation, and guess on variable names. Otherwise, you wi…

I tried to simulate the problem from this post which also uses exponential sets, and it worked with all solvers.

Thanks in advance,
Markus K

clear;
close all;

% === Simulation constant parameter ===
K = 2; % Number of ground user

delta = 40*1e-3; % Time slot duration [s]
V_max = 70; % Maximum velocity [m/s]
A_0 = db2pow(-30); % [dB]
sigma_n = sqrt(db2pow(-90) * 1e-3); % [dB]
kappa_m = 1e6;
B = 1e06 ; % Bandwidth [Hz]
E_min = db2pow(0); % Minimum energy level fronthaul channel [dB]
P_kmax = ones(1, K) * db2pow(23) * 1e-3; % Maximum power for each user [dB]
D = 0.5 * 1e06; % Amount of data [bit]
Q_max = (K + 1) * 100 * D; % Maximum buffer capacity [bit]

sigma = 1; 
theta_channel = rand(K, 1) * 2*pi;
h_k = sqrt(kappa_m /(kappa_m + 1)) * sigma .* exp(1i * theta_channel) ...
		+ sqrt(1/(kappa_m + 1)) * randn(1, 1, "like", 1i) .* sigma;

% === Simulation location parameter ===
height_uav = 100;
GU_pos = randn(2,K);
GU_pos = [25, 25; 15, 5; 0, 0];

beta_k = [1; 1];

% === Local parameter for simulation ===
iter_max = 30;
mu_k_sca_last = ones(2, 1);

for iter_sca = 1: iter_max
	% === CVX - Problem ===
	cvx_begin
		cvx_solver sedumi;
		% cvx_solver sdpt3;
		% cvx_solver mosek;
		
		cvx_precision low

		% Optimization variables
		variable u_pos(2, 1) nonnegative % 
		variable r_k(K, 1) nonnegative % Channel capacity (fronthaul channel)
		variable b_k(K, 1) nonnegative % Bandwidth of the channel (fronthaul channel)
		variable mu_k(K, 1) nonnegative % Slack variables
		variable z_k(K, 1) nonnegative

		variable x nonnegative;
		
		maximize(x)

		% == Constraints ==
		subject to
		
		% C3a - 
		z_k <= mu_k+ b_k;

		for k = 1:K
			% => Version with exponential set {(x, y, z) | y > 0, y*exp(x/y) <= z }
			%	 b_k .* exp((r_k .* log(2))./b_k) <= z_k
			{r_k(k) * log(2), b_k(k), z_k(k)} == exponential(1);

			% => Version with relative entropy {rel_entr(x, y) = x*log(x/y)}
			% r_k(k) * log(2) + rel_entr(b_k(k), z_k(k)) <= 0;

			% C3b - 
			GU_num = 2;
			C_k = sigma_n^2/(A_0 * abs(h_k(k))^2);
			C_k * pow_pos(norm([u_pos; height_uav] - GU_pos(:, k)), 2) - P_kmax(k)*(2/mu_k_sca_last(k) - mu_k(k)/mu_k_sca_last(k)^2) <= 0;
		end

		% C4 - total bandwidth for all channels
		sum(b_k(:)) <= B;

		% C5 - mimumum SNR ???
		r_k >= b_k * E_min;
		
		% C8 - data volume
		r_k .* delta >= beta_k .* x;
	cvx_end

	% === update SCA ===
	mu_k_sca_last = mu_k;

end

[Erling (Erling D.Andersen)]

Some reasons:

• Only Mosek handles the exponential cone natively.
• Only Mosek has an extensive presolve procedure which removes a lot of nasty stuff.
• Only Mosek is under active development. (The author of SeDuMi sadly died years ago.)
• The number of man hours put into Mosek is way bigger than say SeDuMi.

[Mark_L_Stone]

Further expanding on @Erling 's post, which was being written at the same time as mine:

Mosek is the best solver to use for this problem. CVX 2.2 uses Mosek’s native exponential cone capability. The other solvers cause CVX’s much more unreliable Successive Approximation method to be used. That said, unsafeguarded (no line search or trust region) SCA is a very unreliable algorithm.

Always stick with the default precision, regardless of which solver is called.

[mardank (Markus Krantzik)]

Thanks to both of you!
I’m just a bit confused, since in another project they had to use the sdpt3 solver and could not use Mosek to solve the more complex optimization problem.

In general, would it be better to use an exponential set or reformulate the constraints and use something like the relative entropy function? As described in the following post.

Solve optimization problems of exp function

Yes, it can be done, but it’s a bit complicated. Suppose you have a single term y*exp(x/y) that you wish to handle. Then what you do is replace that term with a new variable z, and now you need to add a constraint equivalent to y*exp(x/y) <= z There are two ways to do this. One is to use the exponential cone: { x, y, z } == exponential( 1 ) The other is to use rel_entr: x + rel_entr(y,z) <= 0 You’ll have to do some algebra to confirm that this inequality is equivalent to the first. If you …

[Mark_L_Stone]

If you are using Mosek as solver with CVX 2.2., it might not matter whether you explicitly use CVX’s exponential sets or rel_entr, provided the formulations are mathematically equivalent. if you are using CVXQIUAD’s exponential.m replacement, only certain formulations cause that to be used (CVXQUAD: How to use CVXQUAD's Pade Approximant instead of CVX's unreliable Successive Approximation for GP mode, log, exp, entr, rel_entr, kl_div, log_det, det_rootn, exponential cone. CVXQUAD's Quantum (Matrix) Entropy & Matrix Log related functions ).

Once CVX 2.2 became available (with Mosek 9.x or 10.x)), use of Mosek became the preferred way of solving problems involving exponential cone functions (log, exp, entr, rel_entr, exponential sets, and some others)… You are looking at some very old posts which predate all options other than CVX’s unreliable Successive Approximation method.