0
$\begingroup$

Define $J:\Bbb R^n \to \Bbb R$ by

$ J(y) = \frac{1}{2} (Ay).(y) - b.y, \forall y \in \Bbb R^n $

where $A$ is an $n \times n$ real symmetric and positive definite matrix and $b \in \Bbb R^n$. To show that $J$ is strictly convex we need to show

$\tag{1} J(ty_1 + (1-t)y_2) \lt tJ(y_1) + (1-t)J(y_2) $

So we can evaluate the left:

$ J(ty_1 + (1-t)y_2) = \frac{1}{2} A(ty_1 + (1-t)y_2).(ty_1 + (1-t)y_2) - b.(ty_1 + (1-t)y_2) $

expanding we obtain

$ J(ty_1 + (1-t)y_2) = \frac{1}{2}\left(t^2 Ay_1.y_1 + (1-t)^2Ay_2.y_2+t(1-t)(Ay_1.y_2+Ay_2.y_1)\right) - tby_1-(1-t)by_2 $

From here we can come up with some inequalities, for instance $t^2 \le t$ if $t \in [0,1]$ but there is little I can do.

A possible solution is to take the hessian of $J$ which after some arithmetic comes up to be $A$ and simply say that since $J$ is positive definite (symmetry helps in the computation) we have that $J$ is convex. In this question I'd like to see if there is a way of just showing (1).

  • 0
    @PavelM, you mean $\frac{1}{2}A$? $A$ is positive definite. But that doesn't show the inequality in (1).2012-12-18

1 Answers 1

1

We have (note the linear term $y \mapsto \langle b , y \rangle$ is exactly the same on both sides of (1)): \begin{eqnarray} &2& (tJ(y_1) +(1-t) J(y_2) - J(t y_1 +(1-t)y_2)) \\ &= & t \langle y_1, Ay_1 \rangle + (1-t) \langle y_2, Ay_2 \rangle - (t^2 \langle y_1, Ay_1 \rangle + (1-t)^2 \langle y_2, Ay_2 \rangle + t(1-t) \langle y_1, Ay_2 \rangle + t(1-t) \langle y_2, Ay_1 \rangle) \\ &=& t(1-t)\langle y_1, Ay_1 \rangle + t(1-t) \langle y_2, Ay_2 \rangle - t(1-t) \langle y_1, Ay_2 \rangle - t(1-t) \langle y_2, Ay_1 \rangle \\ &=& t(1-t) (\langle y_1, Ay_1 \rangle + \langle y_2, Ay_2 \rangle - \langle y_1, Ay_2 \rangle -\langle y_2, Ay_1 \rangle) \\ &=& t(1-t) \langle y_1-y_2, A(y_1-y_2) \rangle \end{eqnarray}

Since $A>0$, if $t \in (0,1)$ and $y_1 \neq y_2$, this gives $J(y_1) + (1-t) J(y_2) - J(t y_1 +(1-t)y_2) > 0$, which is the required result.

  • 0
    Ooops, you're right. I have fixed it.2012-12-18