I am reading Boyd's Convex Optimization textbook and I am looking at example 3.22, line 2.
It says $y^T x – \frac12 x^T Q x$ is bounded from above for all possible values of $y$. Also, it is important to note $Q$ is a symmetric positive definite. So for all values of $x$, $x^T Q x$ is a positive number. Why is $y^T x – \frac12 x^T Q x$ bounded above? I am not sure how to compare the quantity $y^T x$ with the quantity $\frac12 x^T Q x$. For $y=0$, I can see why.. then there are two cases, $y>0$ and $y<0$.
Thanks
Best Answer
Hint: For given $y$ write $x:=Q^{-1}y + v$ with a new independent vector variable $v$. The resulting quadratic function of $v$ will have no linear term.
I'm expanding the hint: We are given the function $\phi(x):=y^T x -{1\over2} x^T Q x$ where $y$ is an a priori given constant vector. Writing $x:= Q^{-1} y+v$ we get the pullback (i.e., $\phi$ written as a function of the new variable $v$) $$\eqalign{\tilde\phi(v)&=y^T(Q^{-1}y +v) -{1\over 2}(y^T Q^{-1} + v^T)\ Q\ (Q^{-1}y + v)\cr &= y^T Q^{-1}y + y^T v -{1\over2}(y^TQ^{-1} + v^T)( y+ Qv)\cr &={1\over2} y^TQ^{-1} y -{1\over 2} v^T Q v\cr}$$ (note that $y^T v=v^T y$). Here the right side is a constant minus something positive definite, so it is bounded above by this constant.