4
$\begingroup$

This is from C. Evans' PDE book, page 130. The convex function $H:\mathbb{R}^n\to\mathbb{R}$ is $C^2$ and satisfies $$ H\big(\frac{p_1+p_2}{2}\big) \leq \frac{1}{2}H(p_1) + \frac{1}{2}H(p_2) - \frac{\theta}{8}|p_1-p_2|^2. $$ The lagrangian $L$ is defined as the Legendre transform of $H$: $$ L(v)=(H^*)(v)=\max_{p\in\mathbb{R}^n}p\cdot v - H (p). $$ It's a fact that the statements $p\cdot v = L(v) + H(p), $ $ p=DL(v), $ $v=DH(p)$ are equivalent.

One must show that from the above estimate it follows that $$ \frac{1}{2}L(v_1)+\frac{1}{2}L(v_2)\leq L\big(\frac{v_1+v_2}{2}\big) + \frac{1}{8\theta}|v_1-v_2|^2.$$ I haven't been able to show this. Below is a screenshot of the book's page.

Thank you.

enter image description here

$\endgroup$
  • $\begingroup$ I would have expected $L(v_i)$ in equation $(37)$ of the book. $\endgroup$ – mvw Jan 1 '16 at 23:11
  • $\begingroup$ @mvw newer editions have $v_1, v_2$ instead of $q_1, q_2.$ $\endgroup$ – Weltschmerz Jan 1 '16 at 23:21
  • 1
    $\begingroup$ If one applies the Legendre transformation to $(36)$, one arrives closer to $(37)$. Alas I have no idea yet how to handle $\lVert p_1 - p_2\rVert^2$. $\endgroup$ – mvw Jan 1 '16 at 23:38
  • $\begingroup$ Isn't it straightforward to show that the hessian $ L_{v_i,v_j} = H_{p_i,p_j}^{-1} $? So the lower bound on the norm of $ H_{p_i,p_j} $ becomes an upper bound on the norm of $ L_{v_i,v_j} $ from which the convexity follows. $\endgroup$ – user226970 Jan 4 '16 at 1:08
  • 1
    $\begingroup$ @epimorphic using $v_1$ and $v_2$ such that $L(v_j)=p_j\cdot v_j - H(p_j), j=1,2.$ $\endgroup$ – Weltschmerz Jan 11 '16 at 0:32
2
+200
$\begingroup$

As your hint says, for every $q_1, q_2 \in \mathbb R^n$ there exist $p_1, p_2 \in \mathbb R^n$ such that $L(q_j) = p_j \cdot q_j - H(p_j)$ for $j \in \{1,2\}$. Combining with the inequality for $H$,

\begin{align} \frac{1}{2} L(q_1) + \frac{1}{2} L(q_2) &= \frac{p_1 \cdot q_1 + p_2 \cdot q_2}{2} - \frac{1}{2} H(p_1) - \frac{1}{2} H(p_2) \\ &\leq \frac{p_1 \cdot q_1 + p_2 \cdot q_2}{2} - H\left(\frac{p_1+p_2}{2}\right) - \frac{\theta}{8} \lvert p_1 - p_2\rvert^2. \end{align}

Note that

\begin{align} \frac{p_1 \cdot q_1 + p_2 \cdot q_2}{2} - H\left(\frac{p_1+p_2}{2}\right) &= \frac{p_1 - p_2}{2} \cdot \frac{q_1 - q_2}{2} + \frac{p_1 + p_2}{2} \cdot \frac{q_1 + q_2}{2} - H\left(\frac{p_1+p_2}{2}\right) \\ &\leq \frac{p_1 - p_2}{2} \cdot \frac{q_1 - q_2}{2} + \max_{p \in \mathbb R^n} \left(p \cdot \frac{q_1 + q_2}{2} - H(p)\right) \\ &= \frac{p_1 - p_2}{2} \cdot \frac{q_1 - q_2}{2} + L\left(\frac{q_1 + q_2}{2}\right), \end{align}

which means

$$ \frac{1}{2} L(q_1) + \frac{1}{2} L(q_2) \leq L\left(\frac{q_1 + q_2}{2}\right) - \frac{\theta \lvert p_1 - p_2\rvert^2 - 2(p_1 - p_2) \cdot (q_1 - q_2)}{8}. $$

The desired inequality for $L$ is now immediate from the fact that

$$ \left\lvert \sqrt\theta (p_1 - p_2) - \frac{q_1 - q_2}{\sqrt\theta}\right\rvert^2 \geq 0. $$

$\endgroup$
  • $\begingroup$ Wonderful, thanks. $\endgroup$ – Weltschmerz Jan 11 '16 at 19:36
  • $\begingroup$ @Weltschmerz Apart from the sign error, that is :P $\endgroup$ – epimorphic Jan 11 '16 at 19:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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