Problem too big?

1

Let A \in \mathbf{R}^{kD \times D}, Q \in \mathbf{R}^{D \times D}, where A is fixed, Q is unknown, k=2 and D=256. The objective is

\text{minimise} \quad \| \mathbf{1}_{kD} - AQ\mathbf{1}_{D}\|_1\\ \text{s.t.} \quad AQ \geq 0

My direct translation to CVX is

	oneskd = ones(k*D,1);
	onesd = ones(D,1);
	cvx_begin
		variable Q(D,D);
		minimise ( norm(oneskd - A*Q*onesd,1) );
		A*Q >= 0;
	cvx_end

The result is a model with 198144 variables and 131584 equality constraints. Now, in practical applications k is larger than 2, e.g. in the area of 20, or so. However, even with k=2 it already takes more than 8 minutes to solve. Converting the above problem into an equivalent LP did not really help.

Any suggestions how to improve runtime? Whilst A and Q are not sparse, the product AQ should be sparse - not sure if this helps…

2

That’s big all right. No need to convert to an LP; that’s CVX’s job. If Gurobi and MOSEK are slow on this, then there is nothing to be done except build a custom solver.

3

Is 8 mins the raw optimizer time? At MOSEK (support@mosek.com) we are always interested in large problems, so if you are willing to give us some instances we can take at look at it to see if we can suggest something.