# Proving quadratic function is bounded (vector input)

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

-

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.
$y^T x - \frac12 x^T Q x = y^T(Q^{-1} y + v) - \frac12 (Q^{-1} y + v)^T Q (Q^{-1} y + v) = y^T Q^{-1} y + y^T v - \frac12 (y^T Q^{-1}^T + v^T) Q (Q^{-1} y+ v)$ $= y^T Q^{-1} y + y^T v - \frac12 (y^T Q^{-1} + v^T)(y + Qv) = y^T Q^{-1} y + y^T v - \frac12 (y^T Q^{-1} y + y^T v + v^T y + v^T Q v) = \frac12 y^T Q^{-1} y - \frac12 v^T Q v$ – jrand Jun 17 '11 at 20:18
Hint: Presumably $x$ is a vector and $y$ is a vector of the same length as $x$. As $Q$ is symmetric positive definite, it has a complete set of eigenvectors, so you can express $y$ as a linear sum of them. Then note the order of quantifiers-$y$ is chosen, then the function is bounded above.
Is this the same as showing $\frac12 x^T Q x$ "dominates" $y^T x$ ? I was thinking about holding $y$ constant positive or negative, and seeing what happens when I change x. – jrand Apr 18 '11 at 3:32
That is the right approach, and the point of the "order of quantifiers" phrase. As $x$ grows (in a particular direction), the first is quadratic, while the second is linear – Ross Millikan Apr 18 '11 at 3:38