most recent 30 from http://mathoverflow.net 2013-05-26T02:01:26Z http://mathoverflow.net/feeds/question/43627 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/43627/can-subgradient-infer-convexity Shineway 2010-10-26T03:56:13Z 2010-10-26T04:55:46Z

<p>It is known that If $f:U→ R$ is a real-valued convex function defined on a convex open set in the Euclidean space $R^n$, a vector v in that space is called a subgradient at a point $x_0$ in $U$ if for any $x$ in U one has $f(x)-f(x_0)\geq v\cdot(x-x_0)$</p> <p>What if for function $f$, at any $x_0$ I can find $v$, such that $f(x)-f(x_0)\geq v\cdot(x-x_0)$ for any $x$, does this show that $f$ is convex?</p>

http://mathoverflow.net/questions/43627/can-subgradient-infer-convexity/43628#43628 Mike Spivey 2010-10-26T04:19:24Z 2010-10-26T04:55:46Z

<p>Yes. Let $x, y \in U$. Let $z = \lambda x + (1 - \lambda) y$, for $\lambda \in [0,1]$. Let $v_z$ be a subgradient for $z$.</p> <p>Then $$f(x) \geq f(z) + v_z \cdot (x - z) = f(z) + v_z \cdot \left(x - ( \lambda x + (1 - \lambda) y)\right) $$ $$= f(z) + (1 - \lambda) v_z \cdot (x - y).$$ Similarly, $$f(y) \geq f(z) - \lambda v_z \cdot (x - y).$$</p> <p>Multiplying the first inequality by $\lambda$ and the second by $1 - \lambda$ and adding the two, we obtain</p> <p>$$\lambda f(x) + (1 - \lambda)f(y) \geq f(z),$$ proving that $f$ is convex.</p>