How to solve an optimization problem with the objective function is a matrix ?
Show older comments
Hello everyone!
I have no idea how to solve optimization problems.
I have an objective function which is a binary matrix, should this matrix be defined (known) or not?
knowing that I looked for examples but I didn't find the relevant one with my problem.
I would be grateful if you could help me!
Answers (1)
Walter Roberson
on 21 Sep 2022
0 votes
Each element of the matrix is effectively a separate objective, so in order to do this you would need to use a multi-objective optimizer.
You can use Problem Based Optimization https://www.mathworks.com/help/optim/problem-based-approach.html . You would probably create optimization variables that are marked as integers with lower bound 0 and upper bound 1. You would set up whatever constraints are appropriate. You would set up a matrix objective . solve() should then notice that gamultiobj() is needed to minimize the problem.
Note that there is a difference between a problem in which the best location is a binary matrix, compared to a problem in which the objective is a binary matrix. If the inputs are all binary and a matrix, but the output were scalar (for example an economic dispatch cost) then there are a number of different minimizers, but there are only a quite small number that can deal with there being multiple objectives (each element of the output matrix being a different objective.)
53 Comments
Majid
on 21 Sep 2022
@Walter Roberson The problem is that I don't know if the objective function should be already defined or not.
for example i have this objective function :
max M = 
in this case u should be known?
Walter Roberson
on 21 Sep 2022
Edited: Walter Roberson
on 21 Sep 2022
That formula is M = sum(u(1:K, 1:L));
It is not clear exactly what is being varied. Is u(i,j) according to some function of some additional variable(s) and the task is to find the combination of inputs so that the sum is greatest? Or is it the K and L are variable, and the task is to find the sub-rectangle that has the highest sum (imagine for example that u(i,j) contain a mix of positive and negative values and you want to know what the highest score is) ?
M appears to be a scalar.
Is u(i,j) binary? If so then M = nnz(u(1:K, 1:L)) and if K and L span all of u then M = nnz(u)
Majid
on 21 Sep 2022
Torsten
on 21 Sep 2022
Yes, if there were no constraints, then u(i,j) = 1 for all i and j would be the obvious solution.
Walter Roberson
on 21 Sep 2022
Your objective function would be along the lines of
function M = objective(x)
calculate u based on x
M = -sum(M, 'all');
end
You want the negative because you are maximizing, and you can maximize by finding the minimum of the negative of the value.
You do not need any constraints on M or u. You might need constraints on x .
Furthermore, the constraints you put on x might involve computing all or most of u first, and testing whether the result has certain properties (for example, diagonal must be 0, or number of entries in the 4th row must be 2). You can avoid re-calculating u by using a function to calculate it, and memoize and call the function from your objective and also from your nonlinear constraint function.
Majid
on 21 Sep 2022
Every system of equations has unknowns that are not defined (not known), but follow some equations.
The equations connecting the unknowns lead to values for the unknowns that make the equations true.
This is the same for the elements of your matrix U.
If the constraints (equations or inequalities) are linear in the unknowns, you have a linear optimization problem, otherwise a nonlinear.
Majid
on 22 Sep 2022
Walter Roberson
on 22 Sep 2022
You would use the trial inputs, x, to create a trial u . You would use that trial u in your nonlinear constraint function to signal whether the trial x lead to a u such that the constraints were satisfied. If you use memoize() like I indicated then it will not be necessary to recalculate u (but if you are using genetic algorithm then calculation of the constraints might be postponed relative to the function evaluation, so you might need to have a cache size a bit larger than your population size.)
Majid
on 22 Sep 2022
Walter Roberson
on 22 Sep 2022
In any problem you have a set of model parameters that need to be determined in order to minimize (or maximize) the objective. You calculate various things from those model parameters. You might then have checks to see if the intermediate values are within range -- constraints on the intermediate values. Then if the constraints pass, you continue to calculate a final "cost" for that set of model parameters. The optimization routine then tries other sets of model parameters, getting an associated "cost", and others yet... and at the end returns the set of model parameters that gives the best overall "cost".
For example suppose you are need to fit an ellipse, and the model includes the locations of the two foci and the length of the major and minor axes -- four parameters for that part. But you have a constraint that (for example) the two foci have to be within a particular distance of a known curved line. So you would use the trial foci locations passed in in order to calculate distances from the curved line, and your constraint function would test whether those distances are acceptable, and your output function would calculate whatever (such as comparing the area of the convex boundary of the input points to the area of the ellipse -- if you were to mazimize that fraction you would be minimizing the area of the ellipse.)
The constraints do not need to be with respect to anything to do with the objective function; they can be totally arbitrary. Items positioned relative to each other by law rather than by calculated safey index for example.
It happens that sometimes the model parameters are binary inputs. For example the model parameters might be your u matrix, and they might be acting as selectors as to which actions to take or not, with there being tradeoffs that make the choices dependent on each other. "Select exactly 3 of these 7" for example. If you have that kind of situation, then create integer constraints on the inputs, minimum 0, maximum 1, and use the linear inequality and linear equality constraints where feasible. Some systems like this are best handled by intlinprog().
Majid
on 22 Sep 2022
Majid
on 22 Sep 2022
Torsten
on 22 Sep 2022
If your matrix u of unknowns is nxm, you would formulate the constraint w-(d(i,j)*u(i,j))>= 0 as
ub = w./D(:)
if all the elements in the matrix D are positive and the objective function as
f = -ones(n*m,1)
Majid
on 22 Sep 2022
% U is a 12x24 matrix
n = 12;
m = 24;
% Your w-value
w = 12;
% Your distance matrix D, randomly created
D = rand(n,m);
% Objective function is max: sum_i sum_j u_ij
f = -ones(n*m,1);
% u_ij >= 0
lb = zeros(n*m,1);
% u_ij <= w/D
ub = w./D(:);
% u_ij integer
intcon = 1:n*m;
sol = intlinprog(f,intcon,[],[],[],[],lb,ub);
sol = reshape(sol,n,m)
%Check whether the solution satisfies the constraints
any(sol > w./D,'All')
any(sol < 0,'All')
Majid
on 22 Sep 2022
Torsten
on 22 Sep 2022
It means that the value of your objective function can be made as large as you want.
This error usually appears if the constraints don't limit the maximum value of the objective function.
Majid
on 22 Sep 2022
Majid
on 22 Sep 2022
Torsten
on 22 Sep 2022
Sorry, but I can't make sense of your description.
Torsten
on 22 Sep 2022
I don't see X appearing anywhere in your problem formulation (your objective function does not depend on X explicitly).
And any special properties of D and E^pi ?
Majid
on 22 Sep 2022
But X (and thus the constraints) are fixed and don't change with U ?
Then your problem doesn't need an optimizer:
U = floor(min(w./D(:),(E_total-E_zi)./E_pi(:),2))
Majid
on 22 Sep 2022
Torsten
on 22 Sep 2022
ok, then
W = min(w./D(:),(E_total-E_zi)./E_pi(:),2);
U = zeros(size(W));
U(W>=1) = 1.0;
Majid
on 22 Sep 2022
Let U be unknown.
The constraints say
U <= w./D(:)
and
U <= (E_total-E_zi)./E_pi(:)
Thus
U <= min(w./D(:),(E_total-E_zi)./E_pi(:),2)
Now we come to solve for U.
You want to maximize sum U where U is binary, thus you must take
U = 0 at the positions where min(w./D(:),(E_total-E_zi)./E_pi(:),2) < 1
and you can take
U = 1 at the positions where min(w./D(:),(E_total-E_zi)./E_pi(:),2) >=1.
And that's the solution for U that takes into account your constraints.
Majid
on 22 Sep 2022
If U is generated at the beginning, what do you want to optimize ?
What is the relationship between U and F ?
I don't understand
i have an initial binary matrix F(m*n) , i will choose some of elements of F and generate new matrix U(m*n)
If F and U are both m*n, then F and U must be identical if the elements of U are chosen from F, don't they ?
But that's exactly what the code does.
U is a copy of the matrix F where the elements that are 1 in F and for which
min(w./D(:),(E_total-E_zi)./E_pi(:),2) < 1
are replaced by 0.
Majid
on 22 Sep 2022
Torsten
on 22 Sep 2022
First state the optimization problem properly. Then in the next step we can look for a suitable optimizer.
It might be the case that I don't understand the problem correctly. But up to now, I don't see the necessity to use an optimizer.
Majid
on 23 Sep 2022
As said, for this problem you don't need optimization.
But if you insist, here is an implementation:
% U is a 12x24 matrix
n = 12;
m = 24;
% Your constant values
w = 12;
E_zi = 4;
E_total = 4.1;
% Your distance matrix D, randomly created
D = rand(n,m);
% Your matrix E_pi, randomly created
E_pi = rand(n,m);
% Objective function is max: sum_i sum_j u_ij
f = -ones(n*m,1);
% u_ij <= min(w/D,E_total-E_zi)/E_pi)
Aineq = eye(n*m);
bineq = min(w./D(:),(E_total-E_zi)./E_pi(:));
% u_ij >= 0
lb = zeros(n*m,1);
% u_ij <= 1
ub = ones(n*m,1);
% u_ij integer
intcon = 1:n*m;
sol = intlinprog(f,intcon,Aineq,bineq,[],[],lb,ub);
sol = reshape(sol,n,m)
any(sol < 0,'All')
any(sol > 1,'All')
any(sol > w./D,'All')
any(sol > (E_total-E_zi)./E_pi,'All')
Majid
on 23 Sep 2022
Now this is exactly the optimization problem you posted.
If something has to be changed, you must change it in the formulation of your problem.
rng('Default')
% U is a 12x24 matrix
n = 12;
m = 24;
% Your constant values
w = 12;
E_zi = 4;
E_total = 4.1;
% Your distance matrix D, randomly created
D = rand(n,m);
% Your matrix E_pi, randomly created
E_pi = rand(n,m);
% Objective function is max: sum_i sum_j u_ij
f = -ones(n*m,1);
% D_ij * u_ij <= w
% E_pi_ij * u_ij <= E_total - E_zi
Aineq = zeros(2*n*m,n*m);
bineq = zeros(2*n*m,1);
icount = 0;
for i = 1:n
for j = 1:m
icount = icount + 1;
Aineq(icount,(i-1)*m+j) = D(i,j);
bineq(icount) = w;
icount = icount + 1;
Aineq(icount,(i-1)*m+j) = E_pi(i,j);
bineq(icount) = E_total - E_zi;
end
end
% u_ij >= 0
lb = zeros(n*m,1);
% u_ij <= 1
ub = ones(n*m,1);
% u_ij integer
intcon = 1:n*m;
sol = intlinprog(f,intcon,Aineq,bineq,[],[],lb,ub);
sol = reshape(sol,m,n).'
any(sol < 0,'All')
any(sol > 1,'All')
any(sol.*D > w,'All')
any(sol.*E_pi > E_total-E_zi,'All')
Torsten
on 23 Sep 2022
ok, then U(i,j) = 1 for 9887 positions and U(i,j) = 0 for 73 positions.
Majid
on 23 Sep 2022
Torsten
on 23 Sep 2022
You can fix U(i,j) as 0 if D(i,j) = 0 and/or E_pi(i,j) = 0. I don't know what makes sense for your task.
Majid
on 23 Sep 2022
U(i,j) = 0 is also a constraint on the U-matrix that can be set for the optimizer.
So you can set it before calling "intlinprog" within the problem formulation.
But all these optimizations are not necessary - I don't understand why you prefer such a difficult solution for such a simple problem.
Majid
on 23 Sep 2022
Torsten
on 23 Sep 2022
You mean U(i,j) should only be constrained by D resp. E_pi if D(i,j) resp.E_pi(i,j) > 0 ?
Majid
on 23 Sep 2022
Then replace
for i = 1:n
for j = 1:m
icount = icount + 1;
Aineq(icount,(i-1)*m+j) = D(i,j);
bineq(icount) = w;
icount = icount + 1;
Aineq(icount,(i-1)*m+j) = E_pi(i,j);
bineq(icount) = E_total - E_zi;
end
end
by
for i = 1:n
for j = 1:m
if D(i,j) > 0
icount = icount + 1;
Aineq(icount,(i-1)*m+j) = D(i,j);
bineq(icount) = w;
end
if E_pi(i,j) > 0
icount = icount + 1;
Aineq(icount,(i-1)*m+j) = E_pi(i,j);
bineq(icount) = E_total - E_zi;
end
end
end
Aineq = Aineq(1:icount,:);
bineq = bineq(1:icount);
Majid
on 23 Sep 2022
Categories
Find more on Linear Programming and Mixed-Integer Linear Programming in Help Center and File Exchange
on 23 Sep 2022
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
