Constrained quadratic optimization over a closed cone set

Question

Consider a constrained quadratic optimization problem: $$\max_{x \in C} \{ x^\top a - \frac{1}{2} \|x\|^2 \}, $$ where $C$ is a closed cone set. The maximizer of the above problem is denoted by $$x^* := \arg\max_{x \in C} \{ x^\top a - \frac{1}{2} \|x\|^2 \}. $$ Here is my question: Would the following relationship hold true? $$\|x^*\|^2 = a^\top x^* .$$ If yes, how can we prove it? If no, can we find a counter-example?

Answer 1

Yes, the following relation holds true. In fact, finding the maximum in this problem is equivalent to counting convex conjugate to norm squared function $f(x)=\frac{1}{2}||x||^2$. It can be easily shown that $f^{*}(a)=\frac{1}{2}||a||_{*}^2$, where $||a||_{*}$ is dual norm, which defines as follows $$||a||_{*}=\sup\left\{ a^{\top}x| \quad ||x||\le 1\right\}.$$ Indeed, for all $x$ we have the following inequality $$a^{\top}x-\frac{1}{2}||x||^2\le ||a||_{*}||x|| - \frac{1}{2}||x||^2.$$ The maximum of right-hand is $\frac{1}{2}||a||_{*}^2$ and we have that $f^{*}(a)\le \frac{1}{2}||a||_{*}^2$.

On the other hand, let $x$ be any vector with $a^{\top}x=||a||_{*}||x||$. We can scale $x$ so that $||x||=||a||_{*}$. For this $x$ we have $$a^{\top}x-\frac{1}{2}||x||^2=\frac{1}{2}||a||_{*}^2.$$ So, we have the opposite inequality $f^{*}(a)\ge \frac{1}{2}||a||_{*}^2$.

We have proved that $f^{*}(a) = \frac{1}{2}||a||_{*}^2$. It can be seen from the previous that the maximum is reached for those $x$ that satisfy the equality $$a^{\top}x=||a||_{*}||x||=||x||^2.$$