Adding spesific constraint for optimization problem in MATLAB usin fmincon function

I'm using the fmincon Function of Matlab to find an optimal solution of power assignments of users in a communication system.

An example scenario includes 3 users and the optimization function tries to find optimal power level assignment. The 'x' variable represents the power level assignments of each users.

Total power is equal to 1 and added as Linear equality constraint for the problem. Aeq*x=beq.

The lower bound and upper bound of each user power level is 0 and 1 consecutively.

The script below solves this optimization problem clearly and gives optimal power levels for all three users.

x0=[0.3,0.2,0.5];

lb=[0 0 0];

ub=[1 1 1];

Aeq = [1,1,1];

beq = [1];

options = optimoptions('fmincon','Algorithm','interior-point','Display','iter');

[x,fval,exitflag,output] = fmincon(@myOpt,x0,[],[],Aeq,beq,lb,ub,[],options);

-----------------------------------------------------------------------------

Here is my question.

I want to add a constraint that maximum two users can be assigned power level at the same time (i.e., x1=[0.1,0.9,0], x2=[0.2,0,0.8] or x2=[0,1,0]).

How can enable this constraint in the fmincon function or other functions in optimization toolbox?

Answer 1

[Matt J]

You cannot handle this through constraints. Just solve the problem 3 times corresponding to the three cases x1=0,x2=0, and x3=0. Then see which of the 3 cases leads to the lowest myOpt value.

[Stephan]

Hi Matt J,

thank you for the feedback - again learned a lesson...

I think the problem has to be solved 6 times, because:

x = [0, 0, 1]
x = [0, 1, 0]
x = [1, 0, 0]

are also solutions which are possible additionally to the cases you told.

What to do when problem size is growing up? Would you change to another algorithm? Which one would you suggest in that case?

Would the constraint:

c = sum(round(x,4)~=0) - 2;

work reliable with ga?

Best regards

Stephan

[Matt J]

I think the problem has to be solved 6 times, because:

No, I don't think so, because for example with

 x = [0, 0, 1]
 x = [0, 1, 0]

Both of these are feasible solutions within the set {x: x(1)=0 }. They should be covered just by making the restriction x(1)=0 in the problem. The other cases you mentioned are similarly covered by one of the original three.

Would the constraint c = sum(round(x,4)~=0) - 2; work reliable with ga?

ga definitely has a better chance of handling it than fmincon, but it is a stochastic algorithm and the problem has an uncertain number of local minima, so you can never be sure how reliable.

In any case, rather than using non-linear discontinuous constraint functions, I would probably recommend expressing it using a combination of integer and inequality constraints. For example, in the 3-variable situation of the OP, you could include three additional binary variables z(i), i=1,2,3 in the problem and impose the linear constraints,

x(i)<=z(i), i=1,2,3
z(1)+z(2)+z(3)<=2

Because the z(i) are binary x(j)>0 would imply z(j)=1 and the sum over z(j) would tell you how many power users are active.

What to do when problem size is growing up?

Note that if the objective function is linear (the OP hasn't told us), then the above could be robustly solved with intlinprog, even in larger dimensional versions of the problem. Otherwise, you would indeed have to resort to ga().

[Stephan]

Thank you!

You teached me a lesson today. My first idea was to introduce 3 binary variables for this - but i did not find a way to combine it with x(1)...x(3) - now i know how to do this.

[omer faruk gemici]

First of all thank you for your valuable comments.

The objective function is nonlinear so i could not employ intlinprog so i continue with ga().

According to your comments I tried two different methods.

1. Adding binary variables z(i), i=1,2,3 to the optimization problem as you mentioned and spesify z(i) as Integer variables by using 'intcon' parameter.

When search space gets larger, GA stuck with local minima and cannot converge to the desired global minima.

Do you have any suggestions to overcome this problem?

2. In the second method, I use GA to determine only the binary variables z(i) to determine enabled users.

In the objective function of GA I employ the fmincon optimization process to determine power levels of enabled users (z(i) = 1). Therefore I calculate optimum power levels for each candidate solution in the ga problem.

Although the second method is more successful than the first one, stucking at the local minima problem still in continues for the most of the experiments.

[Matt J]

What's the objective function (in case 1)?

[omer faruk gemici]

Actually we have multiple subcarriers to share power levels to the users.

At the objective function shannon capacity (R(i,k) = log2(1+p/Noise)) is calculated for each users at each subcarrier where p is the power level to be determined by optimization process. R(i,k) is the throughput of i th user at the k th subcarrier.

And our objective is maximization of geometric mean of each user total throughputs.

when we have 2 subcarriers and 3 users, the variable is 1x6 vector such as [p11 p12 p13 p21 p22 p23];

p11= 1st user power level at the 1st subcarrier

we have a linear equality constraint such as p11 +p21 +p31 = 1; here we need a constraint that maximum 2 users can be assigned power level for each subcarrier.

[Matt J]

But why is my originally posted solution not going to work for this problem? There are only 3 combinations of 2 active users. You can test each combination.

[omer faruk gemici]

The given parameters 2 active users in given 3 three users are just simplified example of the original problem.

In the original problem we have around 50 users (max 2 active users) for each subcarrier and total number of subcarrier is 20.

In this scenario, for each subcarrier we have C(50,1) + C(50,2) = 1275 possible combinations to determine active users. Then totally we have 20^1275 possible solution which very large search space.

[Matt J]

No, I don't think so. Firstly, there are only C(50,2)=1225 combinations per sub-carrier. The C(50,1) combinations are already accounted for, as I explained to Stephan.

Secondly, the optimization as you've described it is separable across sub-carriers. There are no constraints which cause pik, k=1...50, for the i-th carrier to interact with pjk,k=1...50 for the j-th carrier. Therefore, you can solve for each carrier separately, as if it is a 50 variable, 1-carrier problem.

So there are 20*1225=24500 combinations. Doesn't seem too bad.