Two-dimensional optimization (especially using GLPK)

Suppose I want to perform an optimization where the solution matrix X is a two-dimensional matrix rather than a vector. The constraints and objective functions can therefore operate on various rows/columns of the solution matrix; for example, the sum of the elements in each column of the matrix must be as close as possible to a certain value, but the sum of n consecutive elements in each row must be less than or equal to 1.

Are there any functions or combinations of functions in MATLAB that allow me to do this, and is it also possible to do this using the GLPK package?

Answer 1

[Matt J]

The examples you describe can be handled by any solver just be reshaping X into a vector first. For example the problem you describe is equivalent to

 [m,n]=size(A);
 ec=ones(m,1);
 er=ones(n,1);

 S=kron(speye(n),ec.'); 
 A=kron(er.',speye(m));

 x=X(:);

 min norm(S*x -certainvalue).^2

 s.t.

     A*x<=ec

Also, in MATLAB Optimization Toolbox functions, no constraints or objective functions that are expressed via function handles (instead of matrix data) ever need to process X as a vector. Same with ub,lb data, I think.

[Mike Vukovich]

So, for example, I can use linprog or lsqlin with X as a 2D matrix? If so, then would the objective function and constraints have to be in matrix format as well?

[Matt J]

No, in both linprog and lsqlin, the objective function and constraints are specified using matrices, A,b,Aeq,beq etc... and not using function handles. So, for those, you would need to reformulate the problem in terms of the vector X(:), using techniques in my example above.

But in lsqnonlin, for example, the objective is expressed using a function handle, so you could write that function to accept a 2D matrix argument X as input. The ub,lb data could also be expressed in 2D form.

[Matt J]

In fmincon, meanwhile, you have a hybrid situation. The objective is expressed as a function handle and so can accept a matrix argument X. However, fmincon uses matrices A,Aeq, to specify linear constraints. The fmincon algorithms will internally perform operations like A*X(:) and Aeq*X(:) and so A, Aeq have to be constructed accordingly.

[Matt J]

See also the documentation

http://www.mathworks.com/help/optim/ug/matrix-arguments.html

[Mike Vukovich]

OK thanks!

I noticed that the GLPK package for Matlab (not GLPK itself) has a similar format to linprog and the like (I'm talking about the "glpk" command you can input in MATLAB after installing the package); do you have any experience with it, and can it accept matrices as input?

Also, like in my other question, can you use it to minimize a function of the form "Cx - d" as in this link? http://lists.gnu.org/archive/html/help-glpk/2011-06/msg00023.html

[Matt J]

I have no experience with GLPK/Matlab, I'm afraid. I think if it allowed you to formulate the argument space in matrix form, that would be very obvious in the documentation. I can't see much benefit in having this for linear solvers, though, so I would be surprised if it were supported. Same thing with "Cx-d".