8
$\begingroup$

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$?

$\endgroup$
8
$\begingroup$

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)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.