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
    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.2011-04-18
  • 0
    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 linear2011-04-18
  • 0
    @Ross Millikan, can you please elaborate on how to express $y$ as a linear sum of the eigenvalues of $Q$?2018-06-26
  • 1
    @WesamF.: you express $y$ as a linear sum of the eigenvectors of $Q$. A symmetric matrix has a complete set of eigenvectors, so they form a basis. Any vector in the space can then be expanded in those eigenvectors.2018-06-26
  • 0
    OK, thank you, You mean we use spectral theorem to decompose $Q$, and express $y$ as linear sum of the eigenvectors, and then manipulate to find the boundary, right?2018-06-26
  • 0
    That would work, though the other answer shows you can just invert $Q$ instead of finding the eigenvectors.2018-06-26