maximizing inner product of vectors in an ellipsoid and a given vector

Question

I have been wrestling with this for quite a long time but couldn't convince myself that the following is true:

What I do understand: $\theta_a$ denotes the set of points that are within the ellipsoid. Also, $A_{t, a}$ is a matrix that "describes" the shape of the ellipsoid. $\hat{\theta}_{t,a}$ is the red point that is the center of the ellipsoid, and $c_t$ is the "radius" of the ellipsoid.

I cannot show to myself that $\displaystyle\max_{\theta_{a}} x_{t,a}^{T} \theta_{a}$ can be derived into the LHS form: $x_{t,a}^{T} \hat{\theta}_{t,a} + c_t \sqrt{x_{t,a}^{T} A_{t,a}^{-1} x_{t,a}}$

Can anyone show me how this is true?

Thanks!

For more context, you can view it here: http://www.yisongyue.com/courses/cs159/lectures/LinUCB.pdf

Answer 1

There must be something wrong if you look at the dimensions. Actually the constraint should be $$(\theta_a-\hat{\theta}_{t,a})^TA_{t,a}(\theta_a-\hat{\theta}_{t,a})\leq c_t^2.$$

The inner product takes its maximum on the boundary of the ellipsoid so we can make the constraint a equation. The gradient of Lagrange function has to be zero at the maximum: $$\left\{\begin{array}{rcl} x+2\lambda A(\theta-\hat{\theta}) &=&\vec{0} \\ (\theta-\hat{\theta})^TA(\theta-\hat{\theta})-c^2&=&0 \end{array}\right.$$

So $$x^T(\theta-\hat{\theta})=2\lambda(\theta-\hat{\theta})^TA(\theta-\hat{\theta})=2\lambda c^2,$$ $$x^TA^{-1}x=4\lambda^2(\theta-\hat{\theta})^TAA^{-1}A(\theta-\hat{\theta})=4\lambda^2c^2,$$ which implies $x^T\theta=x^T\hat{\theta}\pm c\sqrt{x^TA^{-1}x}$. Since it's the maximum we take the positive sign here, so we have the LHS you wanted.