A quadratic programming

[Danilin]

Hi,

I truly appreciate any idea how to solve this non-convex problem:

min. trace(Q'Q)

where Q = A+XYB

variables:

X  (m x 1)

Y  (1 x n)

Initially I thought of constraining column rank of Z=XY by 1 to make it SDP but does not seem to be possible!

Thanks

[Johan Löfberg]

I would not be surprised if this has a simple linear algebra solutions based on SVDs, but I am not confident enough in that area.

What are the dimensions of the problem?

[Danilin]

Thank you for replying,

m=18;

n=3;

B is 3 by 4

[Johan Löfberg]

To begin with, I think a closed solution using SVDs probably not is possible, because this problem looks lot like the type of problems people are trying to solve heuristically using nuclear norm regularizations etc.

18x3, so pretty large then. No simple way to solve it. You could try the global solver to see if it spits out anything reasonably fast, although I doubt it will. You could also try a nuclear norm approach to see if your data is nice enough to allow such a simple approach

m = 18;

n = 3;

A = randn(m,4);

B = randn(n,4);

X = sdpvar(m,1);

Y = sdpvar(1,n);

Z = sdpvar(m,n);

Q = A + Z*B;

objective = trace(Q'*Q);

% Global solver

solvesdp([Z == X*Y, -100 <= [X(:);Y(:)] <= 100], objective,sdpsettings('solver','bmibnb'))

% nuclear norm approach

solvesdp([],objective + norm(Z,'nuclear'))

[Danilin]

Once again thanks,   nuclear norm does not work in my case, guess I have no other choice but a global approach

[Johan Löfberg]

There seem to be a vast literature on rank-constrained weighted Frobenious norm optimization etc, so you should probably take a look at that first. A global approach is most likely not tractable.