Exercício 13. Quando uma função não é diferenciável, um conceito que pode substituir o de diferenciabilidade é o de subdiferenciabilidade (ou superdiferenciabilidade). Dada uma função convexa f: R^n longrightarrow R e x in R^n, o subdiferencial de f no ponto x é o conjunto partial f(x) dos pontos p in R^n tais que
f(y) >= f(x)+lang<= p, y-xrang<= para todo y in R^n
A desigualdade acima pode ser interpretada geometricamente como: p define um plano que está todo abaixo do gráfico de f e que toca no gráfico de f para y=x.
(i) Mostre que, dados A, B subseteq R^n convexos, fechados e disjuntos, com um deles compacto, existe w in R^n e a>0 tais que
lang<= w, x-yrang<= >= a para todo x in A e todo y in B
Dica: Definir W:=A-B=a-b ; a in A, b in B. Com as nossas hipóteses, mostre que W é fechado, convexo e que 0 notin W. Sendo fechado, minimizar |x|^2 em W, obtendo um minimizante w neq 0 em W. Sendo convexo, (1-t) w+t(x-y) in W.
(ii) Mostre que, se f: R^n longrightarrow R é uma função convexa, então partial f(x0) neq emptyset para todo x0 in R^n.
Dica: Considerar A=(x, y) ; y >= f(x) o epigráfico de f e Bk=(x0, f(x0)-1 / k).
(iii) Mostre que f é diferenciável em x0 se, e somente se, partial f(x0) consiste de um ponto só. Neste último caso, deve ser partial f(x0)=nabla f(x0).

Passo 1

O enunciado trata do conceito de subdiferencial de uma função convexa f:R^ntoR e pede três coisas:
1. (i) Provar um teorema de separação estrita para dois conjuntos convexos, fechados, disjuntos, dos quais um é compacto.
2. (ii) Usar essa separação para mostrar que para qualquer ponto x0 a subdiferencial partial f(x0) não é vazia.
3. (iii) Mostrar que f é diferenciável em x0 se, e somente se, partial f(x0) tem exatamente um ponto, e que esse ponto único é o gradiente nabla f(x0).
Para isso precisaremos de geometria convexa (separação de conjuntos convexos) e das propriedades de funções convexas (epigráfico, derivadas direcionais, caracterização do subdiferencial).

Passo 2

(Prova de (i) – separação estrita)
Defina
W ;=; A - B ;=;,a-b : ain A,;bin BsubsetR^n
1) Como A e B são convexos, W é convexo.
2) Como A e B são fechados e um deles compacto, a soma (diferença) é fechada, logo W é fechado.
3) Acap B=emptyset implica 0notin W.
Agora, sendo W fechado e 0notin W, a função wmapsto|w|^2 atinge seu mínimo em algum win W. Seja
win W, wneq 0,|w|=minzin W|z|
Pelo critério de mínimo em conjunto convexo, para todo zin W e todo tin[0,1] temos (1-t)w+t,zin W. Defina
phi(t)=|(1-t)w+t,z|^2
Como phi tem mínimo em t=0, tem-se phi'(0)>=0, ou seja
lang<= z-w,,wrang<= ;>=;0 Longrightarrow lang<= w,,zrang<= ;>=;|w|^2=:a>0
Como todo elemento de W é da forma x-y com xin A, yin B, segue
lang<= w,,x-yrang<= ;>=;a forall,xin A,;forall,yin B,
como queríamos.

Passo 3

(Prova de (ii) – subdiferencial não vazio)
Dado x0inR^n, considere no espaço R^n+1
A ;=;(x,y)inR^ntimesR : y>= f(x) e B ;=;(x0,;f(x0)-tfrac1k),
onde kinN. Aqui A é o epigráfico de f (convexo e fechado) e B é um ponto (fechado e compacto) estritamente abaixo do epigráfico, logo Acap B=emptyset. Pelos resultados de (i), existe
w=(p,r)inR^ntimesR, a>0
tal que, para todo (x,y)in A e (x0,f(x0)-tfrac1k)in B, vale
lang<= (p,r),,(x,y)-(x0,f(x0)-tfrac1k)rang<=;>=;a
Escolhendo y=f(x) nesse ponto de A, obtemos
lang<= p,,x-x0rang<= ;+;rl(f(x)-f(x0)+tfrac1kr) ;>=;a
Como essa desigualdade vale para todo x, se r>0 podemos reescrever
f(x);>=;f(x0)-tfrac1k;+;a-lang<= p,x-x0rang<=r ;=; f(x0) ;+; l(tfracar-tfrac1kr) ;-; llang<=pr,,x-x0rrang<=
Logo, definindo
p^* ;=;-pr,
temos para todo x
f(x);>=;f(x0);+;lang<= p^*,,x-x0rang<=,
o que mostra que p^*inpartial f(x0). Assim partial f(x0)neqemptyset.

Passo 4

(Prova de (iii) – caracterização da diferenciabilidade)
1) Se f é diferenciável em x0, então
f(x) = f(x0) + lang<=nabla f(x0),,x-x0rang<= + o(|x-x0|)
Da definição de subgradiente segue imediatamente que nabla f(x0)inpartial f(x0). Por convexidade partial f(x0) é convexo e compacto, mas se houvesse outro pneqnabla f(x0) também em partial f(x0), a ordem de pequeno em o(|x-x0|) forçaria p=nabla f(x0). Logo partial f(x0)=nabla f(x0).
2) Reciprocamente, é um fato padrão de convexidade que para toda direção d existe a derivada direcional
f'(x0;d) = suppinpartial f(x0)lang<= p,drang<=
Se partial f(x0) tem exatamente um ponto p, então
f'(x0;d) = lang<= p,drang<= forall,d,
o que mostra que f tem derivada direcional linear em toda direção, i.e.\ é diferenciável e nabla f(x0)=p.

Resposta

(i) Mostramos que definindo W=A-B obtemos um ponto wneq0 e a>0 tais que lang<= w,x-yrang<=>= a para todo xin A, yin B.
(ii) Aplicando (i) ao epigráfico de f e ao ponto abaixo dele, obtemos explicitamente um subgradiente, logo partial f(x0)neqemptyset.
(iii) Demonstramos que f é diferenciável em x0 se, e somente se, partial f(x0) tem exatamente um elemento, e nesse caso esse elemento é nabla f(x0).

Exercícios relacionados