Large problem, a lot of constraints

1

Hi everybody!
I need to solve this task.
Matrix Y is huge(100x200000) and I tried to obtain A from this cvx code:

cvx_begin
variable A(100,100)
minimize ( square_pos( norm( A, 'fro' ) ) ) 
subject to
A*Y>0
1^T*A*Y=1^T
cvx_end

But error “Out of memory. Type HELP MEMORY for your options.” appeared due to large quantity of constraints. Do you have any idea how I can rewrite this problem with less numbers of constraints or in some other ways. I also know, that matrix A*Y should be sparse, maybe it will help.
Thank you!

2

I’m afraid there is no obvious fix here. You’re creating 20 million inequality constraints! That’s a huge problem by CVX standards. As discussed in the first section of the users’ guide, CVX is simply not meant for large-scale problems.

This problem is a quadratic program, however, with relatively simple structure. You might have some luck feeding it directly to Gurobi, MOSEK, or another QP solver.

I do have several side notes, which unfortunately will not overcome the memory issue, but I include anyway for the benefit of the readers.

First: note that strict inequalities are treated as non-strict inequalities in CVX. See this section of the users’ guide for more details. This is going to be true for any quadratic programming solver you might consider as well.

Second: What is 1^T? 1 is just a scalar, so that expression is equivalent to A*Y=1. I also assume you meant to use a double equals == for equality constraints. Perhaps what you are trying to achieve is this: sum(A*Y)==1.

Finally: Adding square_pos to your objective really is unnecessary; and if your problem wasn’t already too large for CVX I’d insist more strongly to remove it. Minimizing the norm term without that square_pos is exactly equivalent. So why introduce extra complexity in the model? That said, if you’re going to pass this problem directly to a QP solver, you will be representing it in this squared form.

3

Most likely you should formulate the dual problem explicit since most optimizers prefer few constraints. I think that might even help cvx too.

4

If solving the dual does not help, then sometimes this type of problems can be solved iteratively using constraint generation as follows.

Step 1: Create an initial problem with a small subset of the constraints.

Step 2: Solve the relaxation.

Step 3: If the solution violate any of the original constraints then add some of the violated constraints. Otherwise you are done.

Step 4: Goto step 2.

5

Of course, CVX would convert this to the dual internally if it estimated it to be more efficient to do so—but it still requires a lot of memory!