Setting up linear optimization problem

1 visualización (últimos 30 días)
Inna Pelloso
Inna Pelloso el 27 de Mayo de 2022
Comentada: Inna Pelloso el 28 de Mayo de 2022
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
  5 comentarios
Walter Roberson
Walter Roberson el 27 de Mayo de 2022
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
Inna Pelloso el 27 de Mayo de 2022
Correct. I only want to test the values in X.

Iniciar sesión para comentar.

Respuesta aceptada

Matt J
Matt J el 27 de Mayo de 2022
Editada: Matt J el 27 de Mayo de 2022
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
  2 comentarios
Inna Pelloso
Inna Pelloso el 28 de Mayo de 2022
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
Matt J el 28 de Mayo de 2022
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.

Iniciar sesión para comentar.

Más respuestas (1)

Torsten
Torsten el 27 de Mayo de 2022
Editada: Torsten el 27 de Mayo de 2022
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.
  6 comentarios
Walter Roberson
Walter Roberson el 28 de Mayo de 2022
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
Inna Pelloso el 28 de Mayo de 2022
Appreciate the insight!

Iniciar sesión para comentar.

Categorías

Más información sobre Get Started with Optimization Toolbox en Help Center y File Exchange.

Etiquetas

Community Treasure Hunt

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

Start Hunting!

Translated by