import matplotlib.pyplot as pp
import numpy as np

n = 100
x = np.tile( np.linspace( -1.0, 1.0, n ), ( n, 1 ) )
y = x.T

pp.contour( np.abs( x ) + np.abs( y ) )
# pp.contour( np.sqrt( x ** 2.0 + ( y / 1.5 ) ** 2.0 ) )
pp.axis( 'square' )
pp.colorbar()
pt = [ -0.5, -0.5 ]
pp.show()

Exercício

Prove que se $f : \mathbb R^n \to \mathbb R$ é diferenciável em $\def\vect{\boldsymbol}\vect x$, então o gradiente $\nabla f( \vect x )$ é ortogonal à superfície de nível $$\large \Gamma := \bigl\{ \bigl( \vect y, f( \vect y ) \bigr) \in \mathbb R \times \mathbb R^n : f( \vect y ) = f( \vect x ) \bigr\} $$ no ponto $\bigl( \vect x, f( \vect x ) \bigr)$.

Dica: note que se parametrizarmos a superfície de nível por $$\large \Gamma = \{ \vect\gamma( \vect t ) : \gamma \in \mathbb R^{n - 1} \} $$ onde $\vect \gamma : \mathbb R^{n - 1} \to \mathbb R\times \mathbb R^n$ temos $$\large f( \vect \gamma( \vect t ) ) = c. $$

Subdiferencial e subgradientes

Seja $f : \mathbb R^n \to \mathbb R$ convexa. Definimos o subdiferencial de $f$ em $\vect x \in \mathbb R^n$ como $$\large \partial f( \vect x ) := \{ \vect v \in \mathbb R^n : f( \vect y ) \ge f( \vect x ) + \vect v^T( \vect y - \vect x ) \quad\forall \vect y \in \mathbb R^n \}. $$

Se $\vect v \in \partial f( \vect x )$, dizemos que $\vect v$ é um subgradiente de $f$ em $\vect x$.

Propriedade: Seja $f : \mathbb R^n \to \mathbb R$ convexa, então, para todo $\vect x \in \mathbb R^n$, $\partial f( \vect x ) \neq \emptyset$. Além disso, se $f$ é diferenciável em $\vect x$, então $\partial f( \vect x ) = \{ \nabla f( \vect x ) \}$.

Nós aqui iremos comparar o valor de $$\large \| \vect x - \vect y \|_2^2 $$ com o valor de $$\large \| \vect x - \lambda \vect v - \vect y \|_2^2 $$ onde $\lambda \ge 0$ e $\vect v \in \partial f( \vect x )$.

$$\large \begin{split} \| \vect x - \lambda v - \vect y \|_2^2 &{} = \| ( \vect x - \vect y ) - \lambda v \|_2^2 = \| \vect x - \vect y \|_2^2 - 2 \lambda\vect v^T( \vect x - \vect y ) + \lambda^2\| \vect v \|_2^2\\ &{} = \| \vect x - \vect y \|_2^2 + 2 \lambda\vect v^T( \vect y - \vect x ) + \lambda^2\| \vect v \|_2^2\\ &{} \le \| \vect x - \vect y \|_2^2 + 2 \lambda\bigl( f( \vect y ) - f( \vect x ) \bigr) + \lambda^2\| \vect v \|_2^2 \end{split} $$

Método do subgradiente

1. $k \leftarrow 0$

2. Para $k \in \{ 0, 1, 2, \dots \}$

   1.$$\large

    \vect x^{( k + 1 )} = \vect x^{( k )} - \lambda_k\vect v_k
   

   $$ onde $\vect v_k \in \partial f( \vect x_k )$

   1. $k \leftarrow k + 1$

Métodos de bundle são alternativas mais sofisticadas e que podem rodar bem em problemas médios/pequenos.

O algoritmo converge se os subgradientes forem limitados e $$\large \sum_{k = 0}^\infty \lambda_k = \infty, \quad \lambda_k \to 0^+. $$

Exercício

Qual o subdiferencial de $| x |$ em todos os pontos do domínio? Prove que é $$\large \partial | x | = \begin{cases} \{ -1 \} & \text{se } x < 0\\ [ -1, 1 ] & \text{se } x = 0\\ \{ 1 \} & \text{se } x > 0 \end{cases} $$

Exercício

Prove que o máximo dentre funções convexas é uma função convexa.

Exercício

Qual é o subdiferencial do máximo entre duas funções convexas?

$$\large \| A\vect x - \vect b \|_1 $$