1
$\begingroup$

I am beginning to study convex optimization and I found the following problem. Let $E\subset \mathbb{R}^n$ be a convex set and $f:E\rightarrow \mathbb{R}$ a convex, non-necessarily differentiable function. We defined the subgradient of $f$ at $x_0$ to be a vector $v\in \mathbb{R}^n$ such that $f(x)\geq f(x_0)+v^t(x-x_0)$, $\forall x\in E$. Later in a proof the professor uses that if $f$ is strictly convex, then the previous inequality is strict, which I am failing to see. Any ideas on how to prove this?

$\endgroup$
1
$\begingroup$

It is proofed in Optimierungsmethoden (Jungnickel, 2.ed., 2008) Theorem 3.1.12 (page 86):

By Definition of the subgradient in the point $x_0\in \mathbb{R}^n$ it holds for all $x\neq x_0$ that $f(x)\geq f(x_0)+v^t(x-x_0)$. We assume that there is a $x\neq x_0$ with $f(x)=f(x_0)+v^t(x-x_0)$ and show a contradiction. Thus $f(x)>f(x_0)+v^t(x-x_0)$ has to hold.

By strict convex we get for all $t\in]0,1[$ $$f(tx_0+(1-t)x)<tf(x_0)+(1-t)f(x)=f(x_0)+(1-t)v^t(x-x_0). $$ For the point $tx_0+(1-t)x\in E$ we get by the subgradient condition in the point $x_0$ $$f(tx_0+(1-t)x)\geq f(x_0)+v^t(tx_0+(1-t)x-x_0)=f(x_0)+(1-t)v^t(x-x_0) .$$ This is a contradiction to the equation before.

$\endgroup$

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.