linear programming involving sum of element-wise product of two matrices
3 次查看(过去 30 天)
显示 更早的评论
I was interested in solving the following problem using Matlab
max sum(A.*B)
s.t. Bc < d
where A,B are matrices and c,d are one dimensional arrays of suitable sizes. B is the variable that needs to be optimized, and the remaining are constants. I was wondering whether I could use linprog for this.
1 个评论
Gaurav Ahuja
2017-4-12
This problem seems to be optimizing different objectives(column-wise sum). It would make sense to optimize them separately as for this use-case the column-wise sum would depend only on the respective columns of 'B'(the unknown in this case).
However, if you are interested in maximizing something like
sum(sum(A.*B))
% which is optimizing the sum of column-wise sum of
% element-wise-product. It should be maximum for the
% maximum values of column-wise-sum
Then I have tried to make small working example code for such a situation using 'fmincon' function. You can always use any other similar function for doing so.
A = magic (3)
con = @constraints % we define a function file "constraints.m" that contains the constraints
min = @(B) -(sum(sum(A.*B))) % since all optimisation in Matlab can find minimum so we are trying to minimise the negetive of the objective.
a = [];
b = [];
Aeq = [];
beq = [];
lb = [];
ub = [];
x0 = zeros(3); % starting point for optimization
[sol, fval] = fmincon(min,x0,a,b,Aeq,beq,lb,ub,con) % This would give you 'B' and value of 'sum' (negetively minimised)
% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% the contents of the file "constraints.m" (kept in same folder) are as following:-
function [c,ceq] = constraints(x)
c = x*[1;2;3] - [51;62;37];
ceq = [];
end
% [1;2;3] corresponds to 'c' in the question
% [51;62;37] corresponds to 'd' in the question
% imply Bc <= d (in question its Bc < d (without equalto))
But if you still want to optimize different objectives at once, you can take a look at the following functions like:
fgoalatain
ga
gamultiobj
patternsearch
Kindly note that the results may differ due to implimentation of different algorithms for different functions.
回答(1 个)
Alan Weiss
2017-4-13
Yes, I believe that linprog can address this problem. The linprog problem formulation is to minimize, for a given column vector f and a column vector of unknowns x, the inner product
f'*x
subject to constraints
A*x <= b
Aeq * x == beq
For your problem, if x = B(:) (meaning the column-wise reshaping of the unknown B), then take
f = -A(:)
and I think that the objective function is correct. I take a negative sign because you have a maximization problem.
For the constraints
B*c <= d
you need to reformulate this in terms of the vector x = B(:) as
A*x <= b
with appropriate definitions of A and b. Looking at the transpose:
c'*B' <= d'
You said that c and d are one-dimensional. So take each element of d, look at the corresponding equation in c' and B', and write it in terms of the vector x. OK?
Alan Weiss
MATLAB mathematical toolbox documentation
0 个评论
另请参阅
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!