[Definition] $f$ is concave (convex upward) when $$\forall x,y\in G,\forall 0<\lambda<1, \,f(\lambda x+(1-\lambda)y)\geq \lambda f(x)+(1-\lambda)f(y) $$

Prove that $f:G\to\mathbb{R} \, (G\subset\mathbb{R^n} \text{ is a domain})$ is concave (convex upward) $$\iff \forall x,\exists \text{ a vector } \boldsymbol v(x)\in \mathbb{ R}^n \, \mathrm{s.t.} \, \forall z ,\ f(z)-f(x)\leq (z-x)\cdot \boldsymbol{v}(x)$$

  • $(1)$ for $f\in C^1$, it's easy to prove the theorem above and $ \boldsymbol v(x)=\nabla f(x)$,and for $f\in C^{2}$ Hessian is positive definite;

  • $(2)$ $1$-dimension is easy, because $$\forall x\leq y\leq z, \bigg[\frac{f(y)-f(x)}{y-x}\geq \frac{f(z)-f(x)}{z-x}\Longrightarrow \hspace{5cm}$$ $$ \hspace{3cm} \exists f'_+(x),f'_-(x), \; f(z)-f(x)\leq\min\{f'_+(x),f'_-(x)\}(z-x) \bigg]$$

  • $(3)$ But for any $f$, I can only prove that in any direction $ \hat{\boldsymbol r} , f(x+\hat{ \boldsymbol r} t)-f(x)\leq C( \hat{\boldsymbol r})||\hat{\boldsymbol r}t||$ (same as $1$-dimension case), but how should I find $\boldsymbol{v}(x)$?

  • $\begingroup$ Hint: Consider the 2nd order or higher Taylor expansion of some function. How is the expression of concave related to derivatives? $\endgroup$
    – mavavilj
    Jun 28 at 18:04
  • $\begingroup$ but f is not always smooth, maby we just know $f\in C^0$, so we cannot differentiate it. $\endgroup$
    – LEY
    Jun 28 at 18:14
  • $\begingroup$ I guess I know how toprove this. just let$ v(x)=(C(e_i))$,where $e_i$ is a set of basis. $\endgroup$
    – LEY
    Jun 28 at 23:40
  • $\begingroup$ Consider subgradient. $\endgroup$
    – mavavilj
    Jun 29 at 4:24

Your Answer

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

Browse other questions tagged or ask your own question.