# Why function $f$ is concave (convex upward) $\iff\forall x,\exists\text{ vector } \boldsymbol v(x) s.t. \forall z, f(z)-f(x)\leq (z-x)\cdot v(x)$

[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)$$?

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