2
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ The proposition from Bertsekas assumes that $\Phi$ only takes on finite values, so it seems like it can't be applied to $\Phi_{\text{ext}}$. $\endgroup$ – littleO Nov 17 '18 at 13:08
  • $\begingroup$ Thank you for pointing it out. I edited the question accordingly. $\endgroup$ – sigmatau Nov 17 '18 at 13:35
  • 1
    $\begingroup$ Your extended function is not necessarily convex. You cannot simply extend a function over the reals to make it convex consider, e.g., $f(x) = 1/x$ near 0. What is $f(x)$ in your question btw? $\endgroup$ – LinAlg Nov 18 '18 at 1:53
2
+50
$\begingroup$

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 .

$\endgroup$
  • 1
    $\begingroup$ @sigmatau If you are satisfied with my answer, could you please submit that 50 point? $\endgroup$ – Red shoes Nov 22 '18 at 6:42

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.