1
$\begingroup$

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

2 Answers 2

3

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.

  • 0
    $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$2011-06-17
0

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.

  • 0
    That would work, though the other answer shows you can just invert $Q$ instead of finding the eigenvectors.2018-06-26