Maximise $x^T Ax$ for A symmetric s.t. $x^Tx=1$ and $x$ lies in a finite set of unit vectors

202 Views Asked by At

Given a symmetric matrix $\mathrm A \in \mathbb R^{d \times d}$,

$$\begin{array}{ll} \text{maximize} & \mathrm x^T \mathrm A \mathrm x\\ \text{subject to} & \mathrm x^T \mathrm x = 1\\ & \mathrm x \in S\end{array}$$

where $S$ is a finite set of unit vectors in $\mathbb{R}^d$.


We could try calculating $x^TAx$ for every $x$ in $S$, but suppose that is computationally too slow. So I want to find an alternative method to get to an optimum. I know that if x could be any unit vectors in $\mathbb{R}^d$, we could choose x to be any unit vectors in the eigenspace corresponding to the largest eigenvalue of A. Would choosing the closest point to this eigenspace from our set $S$ give us an optimal for this problem? I would really appreciate some references to some papers/ theorems which explores this idea. Thanks.