Minimization of x^H A x - b^H x - x^H b

[olbes...@gmail.com]

Suppose I have a (complex-valued) unit-norm vector x. Is there a closed-form solution for the minimizer of x^H A x - b^H x - x^H b where A is a positive definite matrix, b a vector and ^H is Hermitian transpose? I guess not. What would be the way to find the solution with manopt?
Thanks

[Nicolas Boumal]

Hello,

There is no closed form, indeed. But this problem can be solved to global optimality (it corresponds to a so-called Trust-Region Subproblem and it is well-known that first- and second-order necessary optimality for it are also sufficient, which means all stable accumulation points of reasonable optimization algorithms are globally optimal.)

In manopt, you would do this as follows:

n = 20;

A = randn(n) + 1i*randn(n);

A = A+A';

b = randn(n, 1) + 1i*randn(n, 1);

problem.M = spherecomplexfactory(n, 1);

problem.cost = @(x) 0.5*x'*A*x + real(b'*x);

problem.egrad = @(x) A*x + b;

problem.ehess = @(x, xdot) A*xdot;

x = trustregions(problem);

You will find that this convergence very fast. It's also ok to use other solvers such as steepestdescent and conjugategradient.

Best,

Nicolas

PS: here is a typical output:

x = trustregions(problem);

                                            f: +3.378021e-01   |grad|: 1.059239e+01

acc TR+   k:     1     num_inner:     1     f: -3.329192e+00   |grad|: 8.972286e+00   exceeded trust region

acc       k:     2     num_inner:     1     f: -7.249164e+00   |grad|: 5.654108e+00   exceeded trust region

acc       k:     3     num_inner:     2     f: -9.088910e+00   |grad|: 5.155246e+00   exceeded trust region

acc       k:     4     num_inner:     2     f: -1.017360e+01   |grad|: 2.697020e+00   exceeded trust region

acc       k:     5     num_inner:     5     f: -1.048018e+01   |grad|: 4.830760e-01   reached target residual-kappa (linear)

acc       k:     6     num_inner:     3     f: -1.048855e+01   |grad|: 4.742407e-02   reached target residual-kappa (linear)

acc       k:     7     num_inner:     7     f: -1.048868e+01   |grad|: 1.734513e-03   reached target residual-theta (superlinear)

acc       k:     8     num_inner:    12     f: -1.048868e+01   |grad|: 2.423308e-06   reached target residual-theta (superlinear)

acc       k:     9     num_inner:    20     f: -1.048868e+01   |grad|: 3.001499e-12   reached target residual-theta (superlinear)

Gradient norm tolerance reached; options.tolgradnorm = 1e-06.

Total time is 0.023974 [s] (excludes statsfun)

[olbes...@gmail.com]

Thank you very much for the answer, I will implement it.