How to write this optimization problem in CVX form?

Mark_L_Stone · May 9, 2019, 2:53am

I misread where the ptilda 's are. So SINR and sinr and linear-fractional.

I still have to tell you , you have so many different variants of your problem, with incomplete information on all of them, that I’m not sure what any of them are,

So I’m going to bout the burden back on you. Completely define a mathematical optimization problem. prove that it is a convex optimization problem (maximizing a concave function subject to convex constraints). if that can not be accomplished, then try to determine a CVX formulation is fruitless.

susan · May 9, 2019, 3:45pm

Thank you so much for your comment and sorry that I am struggling and failing in defining my problem clearly.

Could you please take a look at the above optimization problem one more time? I don’t think that SINR and sinr are the linear- fractional functions. In the above optimization problem the variable of interest is ptilda. As I have mentioned, the cvx should be used inside nested loops.

So the variable of interest for each cvx inside the nested loops over (k,m,l,i) is ptilda(k,m,l,i) which is a scalar. So, SINR is an affine function of ptilda(k,m,l,i) and sinr is a convex in the CVX variable ptilda(k,m,l,i) . I took the second derivative w.r.t. ptilda(k,m,l,i) and it is >= 0.

So the objective function is convex and by rewriting the constraint as log(convex) = - log(concave function), the constraint is convex and acceptable for cvx. right?

Now, when I run the code I got the error of “Cannot perform the operation: {real affine} ./ {real affine}” in the definition of SINR while it is affine in variable ptilda(k,m,l,i).

I guess the problem comes from defining the cvx variable. I don’t know how to tell cvx that the variable of interest is ptilda(k,m,l,i) while the rest of ptildas are given. in other words, we are going to optimize all of them at the same time. Does it make sense now?

Thanks again for your time

Mark_L_Stone · May 9, 2019, 3:59pm

SINR is linear fractional. I don’t know how you are going to deal with that inside log. So you need to prove that constraint is convex. otherwise, CVX can not be used for this problem.

sinr can be handled with inv_pos.

log(convex) is NOT allowed by CVX

help cvx/log

Disciplined convex programming information:
    log(X) is concave and nondecreasing in X. When used in CVX
    expressions, X must be concave.

Disciplined geometric programming information:
    log(X) is typically not used in geometric programs. Technically it
    possible to do so in certain advanced cases, because monomials and
    posynomials are treated by CVX as log-affine and log-convex
    constructs, respectively. However, such usage is undocumented and
    will not be officially supported.

susan · May 9, 2019, 4:19pm

Thank you so much for your quick reply.

Could you please tell me why SINR is linear fractional? the variable of interest, i., e, ptilda(k,m,l,i) that only shows up in the numerator while the other ptildas in the denominator have nothing to do with the ptilda (k,m,l,i).

My second question is I am using log(convex) = - log(concave function). Is it correct? since as you said, log(convex) is NOT allowed by CVX.

And the last question. how to define the cvx optimization variable? for specific ptilda(k,m,l,i) inside nested loop.

for k = 1 : K
for m = 1: M
for l = 1 : L
for i = 1 : I

            cvx_begin
            cvx_quiet(true);
            variable ptilda(k,m, l, i);
            
            objectvefunction = ...
            maximize(objectvefunction)
            cvx_end
        end
    end
end

end

Thank you very much. Appreciate your help

Mark_L_Stone · May 9, 2019, 4:41pm

I think you want for loops inslide cvx_begin … cvx_end, not outside.

I keep getting confused when you switch between problems.

log(convex) does not necessarily equal - log(concave function). You haven;t shown how the constraint with log having sinr in the argument is convex. i don;t see why it would be.

susan · May 9, 2019, 4:52pm

Thanks again for your quick reply.

Now I got confused too. I didn’t switch between problems( or at least I don’t think I am doing that). sorry for any inconvenience it may have caused.

regarding “log(convex) does not necessarily equal - log(concave function). You haven;t shown how the constraint with log having sinr in the argument is convex. i don;t see why it would be.”

I took the second derivative of the constraint with log having sinr in the argument w.r.t ptilda(k,m,l,i) and it is >= 0. That’s why I believe it is convex. Since log(convex) is not accepted by cvx I am using - log(1/convex). However, I am not sure if it is a right approach to take or not.

And thanks a million for mentioning that I need loops inside cvx. Let me see if it going to work.
Nope! it is not going to work put.
I got still error that SINR is {real affine} ./ {real affine}.

I think it is because cvx consider all ptildas as variable not only one specific one. Any idea how I can deal with this issue? Many thanks in advance

Mark_L_Stone · May 9, 2019, 5:02pm

convex expression <= constant and concave expression >= constant are convex constraints.
convex expression >= constant is not a convex constraint (unless the convex expression is affine, in which case it is also concave)

susan · May 9, 2019, 5:06pm

Is there any easy way that we can convert ( convex expression >= constant) to a convex constraint? Or I need to convexify the constraint as well?

susan · May 9, 2019, 5:23pm

Mark,
Could you please kindly tell me how I can apply cvx to the following optimization problem? assuming it is convex.

the variable of interest is p_{i} and we got K of these variables that we want to optimize.
Is cvx inside the for loop or outside of it?

Thanks again

Mark_L_Stone · May 9, 2019, 5:29pm

convex expression >= constant is a non-convex constraint. Any convexification you do will be changing the constraint to something different and non-equivalent.

Every occurrence of cvx_begin … cvx_end is a separate optimization problem. let that guide you.

susan · May 9, 2019, 5:32pm

Got you. Thank you so much for your help. Appreciate that.

susan · May 10, 2019, 5:14pm

Dear Mark,

I am still straggling with applying cvx to the above optimization problem. Could you please tell me cvx should be outside the for loop (over i) or inside the for loop?
If outside, how cvx knows that for each objective function f_{i} the variable of interest is p_{i} and the rest of p_{k}, k \neq i, are given and fixed?
if inside the for loop, how to define the cvx variable in case p_{i} is a scalar or a matrix?

Many thanks in advance

Mark_L_Stone · May 10, 2019, 5:41pm

Which above problem?

Everything from cvx_begin to cvx_end specifies one optimization problem. There should be at most one objective function statement (minimize or maximize) between cvx_beigin and cvx_end.

You can use for loops to build up a CVX expression to use in a minimize or maximize statement. You can specify constraints iinsidie a for loop if you want to.

If you have a separate optimization problem for each value of something parameterized by a for loop index variable, then place the for loop outside cvx_begin to cvx_end/ You can also have for loops outside cvx_begin to cvx_end o specify multiple optimization problems, each of which can have for loops inside cvx_begin to cvx_end.

If there is only a single i entering an optimization problem involving p_i, and there are n different values of : Declare a scalar variable in CVX, and place for i=1:n outside cvx_begin to cvx_end.

If there is only one optimization problem, declare vaaraible p(n)., and perhaps you need a for loop (inside cvx_begin to cvx_end) for the constraints.

susan · May 10, 2019, 6:18pm

Thank you very much for your detailed reply. It helped me a lot.

This is exactly what I wanted to know: “If you have a separate optimization problem for each value of something parameterized by a for loop index variable, then place the for loop outside cvx_begin to cvx_end.”

then as you suggested : “If there is only a single i entering an optimization problem involving p_{i}, and there are n different values of : Declare a scalar variable in CVX, and place for i=1:n outside cvx_begin to cvx_end.”

These are exactly what I am doing and thank for making everything clear.
Here is my issue:
I am trying to solve the following optimization problem without considering any constraints

the variable of interest is ptilda_{k,m,l,i} which is scalar

for k= …
for m = …
for l = …
for i = …
begin_cvx
variable ptilda <=======

        calculating the SINR according the formulation
        
        obj = ... 
        maximize(obj)

end_cvx
end
end
end
end

The cvx gives me an error when want to calculate the first part of the SINR’s denominator.
“Error using cvx/subsref (line 13)
Index in position 1 exceeds array bounds (must not exceed 1)”

The error comes from the fact that I am defining ptilda as a scalar and now it is not able to calculate the function that has nothing to do with this ptilda(k,m,l,i).

Any suggestions for solving this issue would be greatly appreciated.
Thanks

Mark_L_Stone · May 10, 2019, 6:26pm

Don;t use one variable name for two different things. Create separate variables (MATLAB or CVX variables)

I still don;t see how you are going to get the constraint involving sinr accepted. unless \chi / \lambda \le 0.

susan · May 10, 2019, 6:33pm

Thank you very much again for your quick reply. Now I know what I am doing wrongly.

My plan is to keep the concave part of log(1+ sinr) and linearized the rest using Taylor approximation. Then I will get concave expression >= constant which is convex constraint.

Do you think it’s a good/acceptable approach to deal with this non-convex constraint?

Thanks again

Mark_L_Stone · May 10, 2019, 6:45pm

it may or may not converge. If it does converge, it may not necessarily converge to a local maximum, let alone a global maximum. The starting value of the optimization variables at which you do the lineaarization could be critical.

You are essentially building a poor man’s (or woman’s) nonlinear optimization solver, which does not have such important features as safeguarding via line search or trust region. I think you are better off using a non-convex nonlinear optimization solver, which you can not do using CVX. What you are doing might work o.k., but it’s a crap shoot. Even if works for one set of input data, it could fail miserably on another.

susan · May 10, 2019, 6:54pm

Thanks again for your note. You are definitely right.

Could you please introduce me some non-convex nonlinear optimization solver? I am only aware of “Adaptive Random Search” algorithm.

Thanks in advance

Mark_L_Stone · May 10, 2019, 6:57pm

IPOPT, FMINCON, KNITRO, SNOPT, among many other local optimization solvers. f your problem is small enough, you might be able to do semi-rigorous global optimization via BARON, BMIBNB (under YALMIP), COUENNE, or perhaps others.

For further assistance on nonlinear optimization solvers, you can try posting at https://scicomp.stackexchange.com/ or if you can wait hopefully only several more hours or days until it reaches beta and begins, the Operations Research Stack Exchange site https://area51.stackexchange.com/proposals/121892 which I think will be at or.stackexchange.com when it begins.

susan · May 10, 2019, 6:58pm

Thank you so much for all the information you provided me. I Do appreciate your help!