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$

1 Answer 1

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)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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