Matrix optimization

I have a operations research problem:

I have a 10x10 matrix and would like to find another matrix satisfying the following condition:

1. sum of square of the difference between elements is minimize. i.e. SUM(SUM((a(i,j) - b(i,j))^2)) is minimized

2. row to the right monotonicity decrease

3. row to the left monotonicity decrease

4. column to the down monotonicity decrease

5. column to the up monotonicity decrease

6. row sum to 1

Thanks much in advance.

[John D'Errico]

Like Walter, I suspect that the only solution that satisfies the constraints is the constant matrix. However, I am not sure what you mean by stating that each row must be both monotone decreasing to the right and to the left. Does this mean that on each side of some unspecified point, a given row must be decreasing? Please be accurate in your specifications, as otherwise we can only conjecture.

Answer 1

[Walter Roberson]

The only way for a row to monotonically decrease to both the left and the right is if the row is constant. The row must sum to 1, so every entry must be 1/10 . This constant matrix, ones(10,10)./10 is the only solution, and is therefore the solution that minimizes the sum of squares difference out of all the possible solutions.

[Kenneth Chen]

Sorry that I didn't specify. To the left and right are relative to the diagonal.

Answer 2

[John D'Errico]

So then you have a linear system of equations in the 100 unknowns, to be satisfied in a least squares sense.

There are linear inequality constraints, such that the elements of each row and column are decreasing away from the main diagonal. You have indicated 180 such linear inequality constraints.

There are also 10 linear equality constraints such that the rows sum to 1.

Put it all together, and this is a lsqlin problem. Unroll the array into a vector. Thus, given a 10x10 matrix b...

A = eye(100,100);

Aeq = toeplitz([1 ;zeros(9,1)],repmat([1,zeros(1,9)],1,10));
rhseq = ones(10,1);

ind = find(tril(ones(10),-1));
m = length(ind);
Aineq = sparse((1:m)',ind,1,m,100) + sparse((1:m)',ind+10,-1,m,100);
Aineq = [Aineq;sparse((1:m)',ind,1,m,100) + sparse((1:m)',ind-1,-1,m,100)];
ind = find(triu(ones(10),1));
Aineq = [Aineq;sparse((1:m)',ind,1,m,100) + sparse((1:m)',ind-10,-1,m,100)];
Aineq = [Aineq;sparse((1:m)',ind,1,m,100) + sparse((1:m)',ind+1,-1,m,100)];
Aineq = full(Aineq);
rhsineq = zeros(4*m,1);

options = optimset('lsqlin');
options.Display = 'none';
options.LargeScale = 'off';
a = lsqlin(A,b(:),Aineq,rhsineq,Aeq,rhseq,[],[],[],options);
a = reshape(a,10,10);