Can this be reformulated better?

1

I need to solve a problem of the form:

$$\min_G \sum_{i\in\Theta_1} \Vert G a_i \Vert_2^2$$
$$\text{s.t.:}\quad\max_{j\in\Theta_2} \Vert G a_j-a_j\Vert_2<\epsilon $$

where G is a complex N\times N matrix, a_{(\cdot)} are complex N\times 1 vectors, total indices i is K and total indices j is M-K. I implemented this as:

%N and epsilon are defined
%A1 is the collection of a_i in Theta_1, of dimensions NxK
%A2 is the collection of a_j in Theta_2, of dimensions Nx(M-K)

%main CVX part
cvx_begin
variable G(N, N) complex;
minimize(max(sum(pow_abs(G*A1, 2), 1)));
subject to
    max(sum(pow_abs(G*A2 - A2, 2), 1)) <= epsilon
cvx_end

For smallish problems (N=10, 20), it works, but MATLAB needs a lot of memory to solve something of the order N=150 (hung after 1 hr). This is not surprising, since the number of variables being solved for increases as N^2. I wonder if there’s an alternate formulation or perhaps specify a certain solver that has lower memory requirements (and solves in good time!)

2

Your cvx objective doesn’t seem to match your problem’s objective. Should be a sum instead of a max, I think.

3

Also, your epsilon in CVX should be epsilon^2 to match problem, right?

4

Ouch, yes, definitely do not use sum(pow_abs. That’s going to be unnecessarily inefficient. It won’t get rid of the N^2 growth problem but it’s probably making your problem 3-4 times larger than necessary. Instead, use norm and norms whenever possible, and sum_square or ``sum_square_abs` when it is not.

But in fact, this can be written entirely in terms of those first two functions. One key is to note that the problem is equivalent even if you minimize the square root of your desired objective. As Bien points out, your LaTeX equation doesn’t match your CVX code. This matches your LaTeX model, except for the new square root:

minimize(norm(G*A1,'Fro'))
subject to
    max(norms(G*A2-A2)) <= epsilon

And this matches your CVX model, again except for the new square root.

minimize(max(norms(G*A1)))
subject to
    max(norms(G*A2-A2)) <= epsilon