Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer
    
$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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.