8

I'm interested in a type of problem on this form

$$\min_{x} x^{T}Ax+x^{T}b \quad \text{s.t} \quad x^{T}x=1 $$

where $A$ is positive definite. As you can see, if it weren't for the $x^{T}b$ term in the objective, this would be equivalent to finding the eigenvector with the smallest eigenvalue of $A$

This problem becomes trivial when $A=I$, where the solution will be on the form $x=s b$, with some scalar $s$.

  1. Is there a closed-form solution if one knows the eigenvectors/values of $A$? I tried this but I keep going in circles...

  2. Can this type of problem be transformed based on $A$ and $b$ so that the solution $x$ becomes an eigenvector/value of some derived matrix $B$?

Anton Menshov
  • 8,672
  • 7
  • 38
  • 94
Morten Silcowitz
  • 83
  • 3

1 Answers1

8

At least for the second question the answer is yes. See for example Mattheij, Robert MM, and Gustaf Söderlind. "On inhomogeneous eigenvalue problems. I." Linear Algebra and its Applications 88 (1987): 507-531, page 516.

(The optimality conditions of your problem, $$ Ax+b+2\lambda x = 0 \\ x^Tx = 1 $$ constitute an inhomogenous eigenvalue problem)

Aage
  • 188
  • 4