Setting up linear optimization problem

Hi,

I have two 100x1 arrays, X and Y. How do I set this linear problem to run using the optimization toolbox solver?

I want to find the minimum postive value of X, call it M, subject to these constraints:

(1) when the value of X is greater than M, a new variable, Z equals 1

(2) when the value of X is less than -M, the new variable Z equals -1

(3) if -M<X<M, then the new variuable Z equals 0.

I want to find the that maximizes the sum of Y*Z.

Any help would be appreciated!

IP

[Walter Roberson]

When what value is greater than M?

[Inna Pelloso]

When the value of X is greater than M.

[Inna Pelloso]

The problem I am having is in writing the contraints, as they are if statements.

[Walter Roberson]

So only entries already in X are to be considered for M? Making it a discrete problem that you could answer by testing all positive values in X?

[Inna Pelloso]

Correct. I only want to test the values in X.

Answer 1

[Matt J]

X=rand(100,1);
Y=rand(100,1);

timeit(@()doOptimization(X,Y))

ans = 0.0015

function doOptimization(X,Y)

    fun=@(M)objective(M,X,Y);
    
    Xs=sort(X(:).'); 
    n=numel(X);
    Msamps=abs( interp1( Xs, linspace(1,n,2*n-1) ) ); %optimal M must be one of these
    Fsamps=arrayfun(fun,Msamps);
    
    Foptimal=max(Fsamps); %optimal objective
    
    Moptimal=min( Msamps(Fsamps==Foptimal) );   %optimal M
end


function fval=objective(M,X,Y)

   Z=(abs(X)>=M);
   Z(X<-M)=-1;
   
   fval = Y(:).'*Z(:);

end

[Inna Pelloso]

I really appreciate your help. It's not perfect, but you methodology definitely is. I guess the optimizer can only take simple contraints. Thank you!

[Matt J]

I guess the optimizer can only take simple contraints.

It has nothing to do with the ability to implement constraints. Because your objective is piecewise constant, the above is what an optimizer would have to do anyway.

Answer 2

[Torsten]

Since your vectors X and Y are of moderate size, don't use an optimization tool.

I think it's best to proceed as follows:

1. Extract all positive entries of the X-vector.

2. For each of these x-values, calculate the Z vector and evaluate sum(Z*Y).

3. From the sums obtained, choose the maximum sum. If the maximum sum is only attained once, the

corresponding x-value is the solution. If there are several x-values with the maximum sum, choose the

smallest.

[Inna Pelloso]

Is there any way to write the constraints incorporating an 'if statement', and then using the solver in the optimization toolbox?

What you mention is akin to a brute force method, and not practical as I'm dealign with very large datasets. The problem as stated, is a generalization.

[Torsten]

What you mention is akin to a brute force method, and not practical as I'm dealign with very large datasets.

I don't think an optimizer will be faster for a problem of this type, also with larger datasets, because what else can be done apart from testing all possible choices for M in X.

The problem as stated, is a generalization.

?

[Matt J]

Your objective is a piecewise constant 1D function of M. There is no way to reliably find the global minimum but to evaluate all the pieces by brute force. Not, at least, without further assumptions on X and Y.

[Inna Pelloso]

Unfortunately, that is correct.

[Walter Roberson]

I have a vectorized method mentally outlined that (if I have not overlooked something) would take time and memory proportional to numel(X) * numel(unique(abs(X)). It is not clear to me that any algorithm could improve the big-O() time but non-vectorized could probably improve the memory usage.

If there is a more time-efficient method it would probably require dynamic programming. There just might possibly be an approach that is numel(X) * log(numel(unique(abs(X)))

[Inna Pelloso]

Appreciate the insight!