Suppose that $g:\mathbb{R}^s \to \mathbb{R}$ is strictly convex function, then I need to show that there exists $\beta\in \mathbb{R}^s$ such that $$g(x)>g(y)+\sum \beta_i (x-y)_i$$ $\forall x\neq y$

I could prove this result when $g$ is differentiable enough, using the Taylor series , but I don't know how to do this for not differentiable $g$.

  • $\begingroup$ What sort of machinery are you allowed to use to prove this? There are a few ways of approaching this. Are you familiar with subgradients? $\endgroup$ – copper.hat Nov 17 '16 at 19:13
  • $\begingroup$ I'm not familiar with that. $\endgroup$ – Goal123 Nov 18 '16 at 4:12
  • $\begingroup$ Are you able to show that the corresponding result for convex functions holds? $\endgroup$ – copper.hat Nov 18 '16 at 5:10
  • $\begingroup$ No,I am getting the same problem in that case too. $\endgroup$ – Goal123 Nov 18 '16 at 6:13
  • $\begingroup$ I added a proof below. $\endgroup$ – copper.hat Nov 18 '16 at 6:13

Here is an approach that relies on the separation theorem.

Let $\operatorname{epi} g$ be the epigraph of $g$, note that it is a convex set. The point $(y, g(y))$ is not in the interior of $\operatorname{epi} g$ so there is a hyperplane separating $(y, g(y))$ and $\operatorname{epi} g$.

In particular, there is some $(h,h_0) \neq 0$ such that $\langle (h,h_0), \gamma -(y, g(y)) \rangle \ge 0$ for all $\gamma \in \operatorname{epi} g$. Since $(y, g(y)+1) \in \operatorname{epi} g$, we see that $h_0 \ge 0$. If $h_0 = 0$, then $\langle (h,0), \gamma -(y, g(y)) \rangle = \langle h, x-y \rangle\ge 0$ for all $x$ hence $h=0$, a contradiction. Hence $h_0 >0$, by dividing through we can assume $h_0 = 1$.

Since $(x,g(x)) \in \operatorname{epi} g$, we have $g(x)-g(y) \ge \langle -h, x-y \rangle$, and letting $\beta = -h$, we have $g(x)-g(y) \ge \langle \beta , x-y \rangle$.

Note that this implies $g(y+t(x-y))-g(y) \ge t \langle \beta , x-y \rangle$ for $t \in [0,1]$.

All that remains is to show strictness. Suppose for some $x\neq y$ we have $g(x)-g(y) = \langle \beta , x-y \rangle$. Then, for $t \in [0,1]$, $t \langle \beta , x-y \rangle \le g(y+t(x-y))-g(y) \le t (g(x)-g(y)) = t \langle \beta , x-y \rangle$, and so $g(y+t(x-y))-g(y) = t \langle \beta , x-y \rangle$, which contradicts the strictness of $g$. Hence $g(x)-g(y) > \langle \beta , x-y \rangle$ when $x \neq y$.


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.