How to make square(sqrt(x)) feasible?


(Jamie Song) #1

Hello

cvx_begin
    variable ap_power(ap_num,user_num)
    minimize(sum(sqrt(ap_power(:,k)).*channel_est_var(:,k),1)^2);
    subject to
        for m = 1:ap_num
            ap_power(m,:)*channel_est_var(m,:)' == 1
        end        
cvx_end

where ap_num,user_num,channel_est_var,k is known. CVX returns “Disciplined convex programming error: Illegal operation: square( {concave} ).”. The objective function is a concave function of ap_power. Could I do something to make it feasible?


(Mark L. Stone) #2

Have you proven this problem is convex? Please read Why isn't CVX accepting my model? READ THIS FIRST! .

Given that you are minimizing, the objective function must be convex in order for the problem to be convex.

if you declared a variable sqrt_ap_power instead of ap_power, then you could avoid the sqrt in the objective function. But that would turn the affine (linear) constraints into non-convex quadratic equality constraitns involving sqrt_ap_power^2.

I will mark this as non-convex unless and until you show it is a convex problem.


(Mark L. Stone) #3

EDIT: This post is incorrect. I am keeping it only so that the following posts make sense. Please go by my previous post, which was my original, but deleted, and now undeleted post.

Given that you are minimizing, the objective function must be convex in order for the problem to be convex.

if you declared a nonnegative variable sqrt_ap_power instead of ap_power, then you could avoid the sqrt in the objective function. But that would turn the affine (linear) constraints into non-convex quadratic equality constraints involving sqrt_ap_power^2.

Ischannel_est_var channel estimated variance, and therefore nonnegative? Given your taking the square root of ap_power and given the constraints, I presume and will assume channel_est_var is nonnegative. Therefore, both sides of the equality constraints can be squared, resulting in
sqrt_ap_power(m,:)*sqrt(channel_est_var(m,:)') == 1

The objective function using sqrt_ap_power in place of ap_power, cab be squared as you have it, but the optimal value of sqrt_ap_power will be the same if it is not squared, and then you would have a Linear Programing problem.

So

cvx_begin
    variable sqrt_ap_power(ap_num,user_num) nonnegative
    minimize(sum(sqrt_ap_power(:,k).*channel_est_var(:,k),1));
    subject to
        for m = 1:ap_num
            sqrt_ap_power(m,:)*sqrt(channel_est_var(m,:)') == 1
        end        
cvx_end

I will let you check to make sure I didn’t mess up any parentheses.


(Jamie Song) #4

Thank you for your replay. channel_est_var is indeed nonnegative. I’m sorry I didn’t make it clear. However, I don’t think
sqrt_ap_power(m,:)*sqrt(channel_est_var(m,:)’) == 1
and
sqrt(ap_power(m,:)*channel_est_var(m,:)’) == 1
are equivalent. The order of operations lead to different results.


(Mark L. Stone) #5

You are correct. I have just undeleted my original post, which I deleted (and unmarked the thread as non-convex at the time) in a moment of mixed-up thought when I came up with the solution which you rightfully pointed pout is incorrect. So my original post is the one to go by. Non-convex problem as far as i can tell.


(Jamie Song) #6

This is a proof of the convexity of this problem.


(Mark L. Stone) #7

Presuming that is correct, that shows the objective function is concave, as you stated in your first post. But Minimizing a non-affine concave function is not convex.

You ca change variables, as I suggested in my first post, and get a convex (affine) if the squaring is removed) objective, but that pushes the non-convexity into the constraints. You could relax the transformed constraint, now with a convex quadratic left-hand side, into a convex <= inequality which CVX would accept, but that would have optimal value of ap_power = 0, which is obviously worthless as a solution to your original problem.


(Jamie Song) #8

Thank you for your help. I’ll see what else I can do to solve this problem.