24 views (last 30 days)

Hi,

I am trying to optimise a set of 11 variables where x(1:10) are integer variables which have a lower bound of 1 and an upper bound of 3, and x(11) is continuous and can have a value between -inf and inf. The objective function f is linear however there is a second order cone constraint which is required to minimise another objective function. The SOC constraint works with continuous variables using coneprog, however this doesnt seem to allow me to specify integer variables. Is there any way I can solve this problem using the optimisation toolbox?

Many thanks

Ben

Ameer Hamza
on 20 Oct 2020

Ameer Hamza
on 23 Oct 2020

John D'Errico
on 23 Oct 2020

You have a nonlinear constraint. intLINprog (caps inserted to make it clear) is a purely linear programmling tool, that solves integer variable problems.

In MATLAB, this is solved using mainly GA for the general case.

Matt J
on 23 Oct 2020

Edited: Matt J
on 23 Oct 2020

My approach would be to reduce this to a 1-variable minimization over x(11) and solve that with fminsearch,

[Combinations{1:10}]=ndgrid(1:3);

Combinations=reshape(cat(11,Combinations{:}),[],10).';

x11=fminsearch(@(x11)innerProblem(x11,Combinations,f,SOCVariables),x11_guess)

function [fmin,xmin]=innerProblem(x11,Combinations,f,SOCvariables)

....

end

The objective function, which I call innerProblem here, simply does a combinatoric search for the minimum of the conic program over the integer variables subject to a fixed known input value for the eleventh variable x11. Because your integer variables only range from 1 to 3, there aren't that many combinations to search through. All the combinations can be easily pre-computed as columns of the 10x59049 matrix Combinations. Also, the operations needed to evaluate all the combinations are highly vectorizable - no for-loops involved.

John D'Errico
on 23 Oct 2020

This MAY be the correct solution, in that there are only 3^10 combinations of variables. That makes an exhaustive solution in the linear set a viable problem to solve.

3^10

ans =

59049

That is not a large set at all. Essentially, conditional on the value of x(11), you find the optimal set for the other 10 unknowns. When you find the best value for x(11), you should be done, MAYBE.

The problem I see here is that the solution chosen from the integer set of variables may vary considerably. And that may essentially create an objective function that is discontinuous. In turn, that can easily blow fminsearch out of the water, causing it to converge to a poor solution.

So while Matt's idea may work out, I would look at the results very carefully. For example, if you start from a different point for x(11), how much will the solution vary?

In turn, that suggests a possible extension of Matt's idea: to use a multi-start method. Thus, start fminsearch at various points in the domain of x(11). Save the solution you find from each start point in the set, as well as the function value arrived at there. Then take the best solution arrived at from the various start points. The size of the starting set you try will improve your chances at finding the globally optimal solution.

John D'Errico
on 23 Oct 2020

Opportunities for recent engineering grads.

Apply TodayFind the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
## 0 Comments

Sign in to comment.