How to optimize a vector, where only two values are allowed?

Hello,

as you see in the Pseudocode I have an optimization problem with two inputvectors, which I combine as a matrix. This works well so far.

Now I have the problem that the vector v2 can only have two values: 0 and 1. But I don't know how the two values are best distributed over the vector.

So I would like that during running the optimization the best distribution of zeros and ones over the vector v2 is calculated. How can I make this restriction for v2?

Thanks for your help

    mExample=[v1,v2];
    opts = optimoptions(@fmincon,'MaxIterations',500,'MaxFunctionEvaluations',500);
    optFunction = @(mExample)OptimProb(vstativ,mExample);
    optProblem  = createOptimProblem('fminunc', 'x0', mExample, 'objective', optFunction,'options',opts);
    [mExampleSolution, OptimizationCriterion, ~, Output] = run(MultiStart, optProblem, NMultistart);
    
    function OptimizationCriterion = OptimProb(vstatic,mExample)
    %calculateOptimizationCriterion from vstatic and mExample
end

Answer 1

[Jon]

If your objective function is linear (I can't tell from what you have included) e.g. minimize over x, f'x where f is row vector, and the constraints are also linear and you have the optimization toolbox, you could use the intlinprog function. https://www.mathworks.com/help/optim/ug/intlinprog.html

From the documentation, for intlinprog you can see that you can restrict certain elements of x to be integers. You can also further set upper and lower bounds on these elements, so by defining a lower bound of zero and an upper bound of 1 you would have what you want.

I can't quite understand the details of what you are doing from you code snippet, but I have the idea that you somehow have two vectors that you are trying to optimize. To fit into the standard framework, used by intlin, you could concatenate those into one long vector, and just set the integer constraints on the elements that have to be integers. After you have solved the problem, you could once again break the long vector down into two individual vectors.

[amship]

Thanks for your answer.

Unfortunately it is not a linear problem.

It's a non-konvex optimization problem, which I try to break down by inserting 'MaxIterations'. And I hope that the problem will get konvex by just allowing v2 to accept values of 0 and 1.

[Jon]

I don't know if this would help in your situation but one trick you might be able to try would be to consider the elements of v2 to be the bits in a binary string (0 or 1) of the same length as v2.

So for example if v2 were a length 3, as a binary value it could have possible values of 0 = bin2dec('000'), 1 = dec2bin('001') , 2 = dec2bin('010') ...7 = dec2bin('111'). You could then include in your optimization a single scalar, inlets call it k2, in place of the vector v2, with lower bound 0, and upper bound 2^n - 1, where n is the number of elements in your original vector v2. Internally, in your cost function you can convert k2 back to a vector with elements of zero and one using v2 = bitget(k2,1:n).

You would still have the problem of restricting k2 to being an integer, but perhaps somehow you round to a nearest integer.

Alternatively, I also see that MATLAB's genetic optimization algorithm, https://www.mathworks.com/help/gads/mixed-integer-optimization.html

allows you to restrict values of specific elements to being integers. So maybe you can either use this in combination with the above idea, in which the bits are encoded in a single integer with bounds 0, 2^n-1, or directly as vector whose elements are restricted to be integers with bounds 0, 1

[Brendan Hamm]

I would agree that for a non-convex problem with integer constraints that genetic algorithms would be the way to solve it. As you are using MultiStart, you opviously have the Global optimization toolbox and you can solve this. There is an input IntCon which should contain the indices of all of the binary values in the input vector, and you would also need to declare the lower bound and upper bound on these values to be 0 and 1 respectivelly.

There is no need to do a bit encoding on the values, this would be extremelly inefficient.

You should not use a rounding of a continuous variable to represent an integer value.