Generalization of properties of the subgradient of a convex function $f$

convex optimizationconvex-analysis

In Bertsekas, Convex Optimization Algorithms The following Proposition is proved.

Let $\Phi: \mathbb{R}^{n} \to \mathbb{R}$ be a convex function. For every $x \in \mathbb{R}^{n}$, we have

(a) The subgradient $\partial \Phi(x)$ is a nonempty, convex and compact set, and we have
\begin{equation}
\label{eq-quotient}
\Phi'(x;d):= \lim \limits_{\alpha \to 0} \dfrac{\Phi(x+\alpha d)-\Phi(x)}{\alpha} =\max_{g \in \partial f(x)} g^{\intercal} d \quad \forall \ d \in \mathbb{R^{n}}
\end{equation}

(b) If $\Phi$ is differentiable at $x$ with gradient $\nabla \Phi(x)$, then $\nabla \Phi(x)$ is its unique subgradient at $x$, and we have $\Phi'(x;d)= \nabla \Phi(x)^{\intercal}$

What I want to show: I want to generalize the nonemptyness, closedness and compactness of the subgradient to convex functions, defined on arbitrary open convex subsets of $\mathbb{R}^{n}$. My Proof goes as follows: Let $\Phi : X \to \mathbb{R}^{n}$ be a convex function with $X \subseteq \mathbb{R}^{n}$ a convex open set.

We can (I think) extend $\Phi$ to a convex function $\Phi _{\text{ext}}: \mathbb{R}^{n} \to \mathbb{R}$ by defining

\begin{equation}
\Phi_{\text{ext}}(x)=\Phi(x) \text{ if } x \in X \text{ and } \Phi_{\text{ext}}(x)= \infty \text{ if } x \notin X
\end{equation}

. By the proposition stated above, we know that for $p \in X$, $\partial \Phi_{\text{ext}}(p)$ is non-empty, closed and compact. We also know that $\partial \Phi_{\text{ext}}(p)= \partial \Phi(p)$ holds, since
\begin{gather}
\partial \Phi_{\text{ext}}(p)=\{ y \in \mathbb{R}^{n} \ | \ \langle y, q-p \rangle \leq \Phi_{\text{ext}}(q) – \Phi_{\text{ext}}(p) \ \forall q \in \mathbb{R}^{n} \} \\
= \{ y \in \mathbb{R}^{n} \ | \ \langle y, q-p \rangle \leq \Phi_{\text{ext}}(q) – \Phi(p) \ \forall q \in X \} \cap \{ y \in \mathbb{R^{n}} \ | \ \langle y, \rangle \leq \Phi_{\text{ext}}(q) – \Phi(p) \ \forall q \in \mathbb{R}^{n} \setminus X \} \\
=\{ y \in \mathbb{R}^{n} \ | \ \langle y, q-p \rangle \leq \Phi_{\text{ext}}(q) – \Phi(p) \ \forall q \in X \} \cap \mathbb{R}^{n} \\
=\{ y \in \mathbb{R}^{n} \ | \ \langle y, q-p \rangle \leq \Phi(q) – \Phi(p) \ \forall q \in X \} \\
= \partial \Phi(p)
\end{gather}

In particular, the fact that $\partial \Phi(p)$ is non empty, closed and compact follows from the fact that $\partial \Phi_{\text{ext}}(p)$ fulfills the property.

Question: Is my proof correct?

Edit: As pointed out by littleO, the proof in bertsekas assumes that the convex function has finite values. Hence my modified question is then: Given that $\Phi$ is finite, is my proof correct if we would replace the definition of $\Phi_{\text{ext}}$ with

\begin{equation}
\Phi_{\text{ext}}(x)=\Phi(x) \text{ if } x \in X \text{ and } \Phi_{\text{ext}}(x)= \sup_{s \in X} \Phi(s) \text{ if } x \notin X
\end{equation}

Best Answer

Your proof is incorrect because $\Phi$ might not be extendable to a convex function on entire $\Bbb{R^n}$. For example take $\Phi$ the function whose graph is the lower half of the unit circle.

Now how to proof what you claimed: Subdifferentials and directional derivatives is a local feature of function. So first prove that $ y \in \partial \Phi (p) $ if and only if there exist an open neighborhood of $p$, say $X$ such that

$$\ \langle y, q-p \rangle \leq \Phi(q) - \Phi(p) \quad \ \forall q \in X $$

Hint: For right to left define the function $ f(x)= \Phi(x) - \Phi(p) - \langle y, x-p \rangle$ observe that $f$ is convex on the whole $\Bbb{R^n}$ and take a local minimum at $x =p$, so it has to be global minimum too.

Now mimic the Bertsekas' proof, for the local version of subdifferential .

Related Question