linear programming involving sum of element-wise product of two matrices

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.

[Gaurav Ahuja]

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.

Answer 1

[Alan Weiss]

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