Maximize minimum optimization problem

Hello! I would like to ask for your help concerning the following optimization problem as I am trying to get familiar with such kind of optimization...

Can someone help me about how to write down my objective function and the first inequality constraint (in order to include them in the intlinprog solver)? I mainly don't know how to describe the 'ε' as the obective function... The rest of the constraints can be easily formed in matrices.

Thank you in advance!

Regards,

Chris

[Matt J]

Looks like bintprog would be sufficient, since x is binary. No need for intlinprog.

Answer 1

[Alan Weiss]

It seems to me that your variable $\epsilon$ is unneeded. You simply want to find

 max(sum_t sum_i sum_j rates(i,j) x(t,i,j))

while still satisfying your other constraints. (This maximum, taken over the x(t,i,j), is the value of $\epsilon$.) This is the same as minimizing the negative of that sum. So your objective function vector has components rates(i,j) for the (t,i,j) entry.

Alan Weiss

MATLAB mathematical toolbox documentation

[Chris B]

I think I got your point..

So, my objective function will be again this sum, that is also going to be included to the constraints as well..I will try to project it somehow like this to my code and come back to you!

[Matt J]

No, it will not be included in your constraints. It can be removed from there.

[Chris B]

Thank you for your answer! However, if I had to include something like the same BUT without the first sum_t and to satisfy this inequality for all 't' from 1 to 20, it should be different, right?

I mean only the "sum_i sum_j (rates(i,j)*x(t,i,j))" >= $\epsilon$..

[Matt J]

That would make the problem equivalent to

min max(sum_t sum_i sum_j -rates(i,j) x(t,i,j))

plus your epsilon-independent constraints. If you were to relax the binary constraint on x, the problem could be solved with fminimax. Otherwise, you would probably have to keep both the objective and constraints in the epsilon-modified form.

[Chris B]

Thank you once again! In my case, I shouldn't relax the decision variable as I need it to be hardly 0 or 1... Do you know how this could happen?

[Matt J]

Yes, binary variables happen all the time. That's why you have solvers like intlinprog and bintprog to enforce it.

[Chris B]

But in this case, we don't know how to express the objective f for using it as an input to the intlinprog for example (this epsilon confuses me I could say).. That's my main concern and sorry for asking 'easy- to answer' questions.. I just want to be sure that I understand it properly!

edit : if it is easy for you, can you post just an example of how to write it? Not analytically, in few words if you don't have any problem!

Answer 2

[Matt J]

But in this case, we don't know how to express the objective f for using it as an input to the intlinprog (this epsilon confuses me I could say)

The objective and constraints need to be posed in terms of the concatenated vector of knowns p=[x(:);epsilon] very similar to what we did in your earlier thread,

http://www.mathworks.com/matlabcentral/answers/140614-maximize-d2d-rate-fmincon-problem

So, f(i) would be 0 for all i corresponding to the x(i) while f(end) corresponding to the epsilon would equal -1.

[Chris B]

I see! Thank you very much for your help, I hope it works!!

Chris

[Chris B]

Therefore, p is going to be a single column vector with (M*N +1) elements, where the M*N elements correspond to the x vector and the last one is related to the unknown parameter that we need to maximize. I also understood that

f(end) = -1

because we want to maximize this epsilon and we use the minus sign.

I also created accordingly the A inequality matrix to include it in my constraints and then I have to decide for the corresponding values to the b column vector. It should be valued with '-epsilon' but this is also the asked parameter that we want to maximize...

I am confused a little bit...

Edit : Just to clarify this... The problem is a max-min linear problem that can be solved with intlinprog , right?

All constraints should be formed in matrices as stated in the intlinprog description in MATLAB documentation. So, now, the unknown parameter in our problem is the vector [ x(:) ; epsilon ], but I cannot really understand how to include epsilon in it ...

[Matt J]

and then I have to decide for the corresponding values to the b column vector. It should be valued with '-epsilon' but this is also the asked parameter that we want to maximize...

No, b should be a vector of zeros. Rearrange your constraint inequalities to be of the form

epsilon - sum_i sum_j rates(i,j) x(t,i,j) <=0

This is a system of the form

   A*[x(:);epsilon]<=0

for some appropriately chosen matrix A.

[Chris B]

It worked for me! Thank you so much.

Chris