A convexidade e por que importa

Um vale, uma resposta

Uma função é convexa se o segmento entre dois pontos quaisquer do seu gráfico fica sobre o gráfico ou acima dele: $f(\theta\mathbf x+(1-\theta)\mathbf y)\le\theta f(\mathbf x)+(1-\theta)f(\mathbf y)$ para todo $\theta\in[0,1]$ . Para uma função duas vezes diferenciável há um teste prático: $f$ é convexa exatamente quando sua hessiana é semidefinida positiva em toda parte, isto é, todos os autovalores são $\ge0$ . Somas de funções convexas, seus múltiplos positivos e o máximo de funções convexas são convexos, e é assim que grandes objetivos convexos são montados com peças pequenas.

H(\mathbf w)\succeq0\ \ \forall\,\mathbf w\ \Longrightarrow\ \nabla f(\mathbf w^{*})=0\ \Rightarrow\ f(\mathbf w^{*})=\min_{\mathbf w}f(\mathbf w)

(1)

A convexidade é o que torna a otimização confiável. Todo mínimo local é um mínimo global, um gradiente zero basta para parar, e a resposta não depende de onde o solver começa. Se a função é estritamente convexa o minimizador também é único, e se é fortemente convexa, com curvatura de pelo menos $\mu>0$ em cada direção, a descida do gradiente converge na taxa geométrica vista antes. Sem convexidade nada disso é garantido: o solver pode parar num vale que não é o mais profundo.

Um teste e um contraexemploPara

f(x)=x^2

tome os pontos

0

4

com

\theta=\tfrac12

. O valor no ponto médio é

f(2)=4

, enquanto a média dos valores das extremidades é

(0+16)/2=8

; a diferença de

4

é positiva, como a convexidade exige. Agora tome

f(x,y)=x^2+4xy+y^2

. Sua hessiana

\begin{pmatrix}2&4\\4&2\end{pmatrix}

tem autovalores

6

-2

. Um é negativo, então

f

não é convexa: a origem é um ponto de sela.

Em finanças, os objetivos convexos incluem a variância da carteira $\mathbf w^{T}\Sigma\mathbf w$ (uma matriz de covariância é semidefinida positiva), perdas de mínimos quadrados, a norma $\ell_1$ $\lVert\mathbf w\rVert_1$ e o expected shortfall (CVaR) em função dos pesos. O valor em risco, um teto para o número de pesos não nulos e o índice de Sharpe como está não são convexos. Uma matriz de covariância amostral estimada com menos observações que ativos é semidefinida positiva mas singular, então a variância é convexa sem ser estritamente convexa e muitos vetores de pesos empatam no mínimo.

Teste da hessiana: autovalores todos $\ge0$ em toda parte, convexa; um autovalor negativo, não convexa.
Vantagem: todo mínimo local é global, então o ponto de partida não importa.
Blocos: somas, múltiplos positivos e máximos de funções convexas continuam convexos.

Relaxe o que não é convexoQuando uma exigência não é convexa, como no máximo

k

pesos não nulos, é comum trocá-la por uma prima convexa, aqui a penalidade

\ell_1

. O problema relaxado é resolvido com confiança e em geral dá uma boa resposta, mas é outro problema: confira o resultado contra a exigência original antes de usá-lo.

Lab: o que é avaliado

Uma folga de convexidade15 pts
O autovalor que quebra a convexidade15 pts
Qual hessiana é convexa15 pts
Objetivos convexos em finanças15 pts
Um gradiente zero10 pts
Vocabulário da convexidade15 pts
Por que solvers gostam de problemas convexos15 pts

Um vale, uma resposta

H(\mathbf w)\succeq0\ \ \forall\,\mathbf w\ \Longrightarrow\ \nabla f(\mathbf w^{*})=0\ \Rightarrow\ f(\mathbf w^{*})=\min_{\mathbf w}f(\mathbf w)

(1)

Um teste e um contraexemploPara

f(x)=x^2

tome os pontos

0

4

com

\theta=\tfrac12

. O valor no ponto médio é

f(2)=4

, enquanto a média dos valores das extremidades é

(0+16)/2=8

; a diferença de

4

é positiva, como a convexidade exige. Agora tome

f(x,y)=x^2+4xy+y^2

. Sua hessiana

\begin{pmatrix}2&4\\4&2\end{pmatrix}

tem autovalores

6

-2

. Um é negativo, então

f

não é convexa: a origem é um ponto de sela.

Teste da hessiana: autovalores todos $\ge0$ em toda parte, convexa; um autovalor negativo, não convexa.
Vantagem: todo mínimo local é global, então o ponto de partida não importa.
Blocos: somas, múltiplos positivos e máximos de funções convexas continuam convexos.

Relaxe o que não é convexoQuando uma exigência não é convexa, como no máximo

k

pesos não nulos, é comum trocá-la por uma prima convexa, aqui a penalidade

\ell_1

. O problema relaxado é resolvido com confiança e em geral dá uma boa resposta, mas é outro problema: confira o resultado contra a exigência original antes de usá-lo.

Lab: o que é avaliado

Uma folga de convexidade15 pts
O autovalor que quebra a convexidade15 pts
Qual hessiana é convexa15 pts
Objetivos convexos em finanças15 pts
Um gradiente zero10 pts
Vocabulário da convexidade15 pts
Por que solvers gostam de problemas convexos15 pts

Um vale, uma resposta

Lab: o que é avaliado

Entre para executar o seu código.

A convexidade e por que importa

Um vale, uma resposta

Lab: o que é avaliado

Entre para executar o seu código.