complex circle manifold optimization

[jifa zhang]

Hello. I have the below optimization. Is the feasible a complex circle manifold? can i use manopt toolbox to deal with this problem? can you help me?

[Nicolas Boumal]

Hello,

I imagine your notation means theta_j is a complex vector in R^M, so that theta_j(i) is its i-th component. And you have N such vectors. if that's correct, than your search space seems to be the set of complex matricex of size M x N whose individual entries have modulus 1.

That is indeed a perfect fit for complexcirclefactory(M, N).

Your problem structure should then look like this:

problem = struct();

problem.M = complexcirclefactory(M, N);  % this is the manifold, with your values of M and N

problem.cost = @(X) ... your cost function here, where X is an MxN matrix with unit-modulus entries ... ;

For quick prototyping, you can then try to call

problem = manoptAD(problem);

to see if automatic differentation can figure out your gradient.

This sometimes fails (and sometimes can be fixed with tinkering, but it takes a bit of trial and error).

In any case, eventually you'll want to implement the gradient of your cost function, by defining the field problem.egrad or problem.grad, and then running checkgradient(problem) to make sure it's correct. You can find more info in the tutorial and in my book (pdf on my webpage).

Best,

Nicolas

[jifa zhang]

thank you very much. I think i can not transform the objective function f(theta_1,\theta_2,\theta_N) into the form of f(X), where X=[ theta_1,\theta_2,\theta_N]. I don not known how to calculate the gradient of  f(theta_1,\theta_2,\theta_N) w.r.t. X. Can i use manopt to deal with this problem?

[Nicolas Boumal]

Do you have an explicit expression (formula) for f ?

[jifa zhang]

yes, this is my objective function.

[Nicolas Boumal]

This should correspond to the following:

% Generate some random data

M = 3; N = 10;
H = randn(M, M, N) + 1i*randn(M, M, N);
H = multiprod(multihconj(H), H);

% Setup a problem structure with manifold and cost function
problem.M = complexcirclefactory(M, N);
problem.cost = @(X) sum(log2(1 + real(sum(conj(X).*squeeze(pagemtimes(H, reshape(X, [M, 1, N]))), 1))));

The code for the cost function should be correct and efficient, though it's perhaps not the easiest to read. Also, pagemtimes was added to recent versions of Matlab.

Automatic differentiation (through manoptAD) unfortunately does not work for that cost function, but it's a good exercise to work it out.

[jifa zhang]

thank you. I realize the term log2(1+theta^H*H*theta) is nonconcave w.r.t theta, so manifold optimization is suitable for this problem?

[Nicolas Boumal]

This has no direct impact on applicability of Manopt. In any case, the manifold itself is nonconvex, so there may be local optima anyway.

Something to pay attention to: Manopt always minimizes, and I see you want to maximize; so you should "minimize -f(X)" instead of "maximize f(X)" (simply add a minus sign to f, grad f etc.)

[jifa zhang]

I got it. So i can use manopt to deal with this problem, although the objective function is nonconcave w.r.t. theta. I just need to formulate the objective function and its gradient, manopt can find a sun-optimal solution?

[Nicolas Boumal]

That's right -- feel free to keep us posted on your results, I'm always curious.