.. _sec_convexity:

Convexidade
===========


A convexidade desempenha um papel vital no projeto de algoritmos de
otimização. Em grande parte, isso se deve ao fato de que é muito mais
fácil analisar e testar algoritmos em tal contexto. Em outras palavras,
se o algoritmo funcionar mal, mesmo na configuração convexa,
normalmente, não devemos esperar ver grandes resultados de outra forma.
Além disso, embora os problemas de otimização no aprendizado profundo
sejam geralmente não convexos, eles costumam exibir algumas propriedades
dos convexos próximos aos mínimos locais. Isso pode levar a novas
variantes de otimização interessantes, como
:cite:`Izmailov.Podoprikhin.Garipov.ea.2018`.



.. raw:: html

    <div class="mdl-tabs mdl-js-tabs mdl-js-ripple-effect"><div class="mdl-tabs__tab-bar code"><a href="#mxnet-1-0" onclick="tagClick('mxnet'); return false;" class="mdl-tabs__tab is-active">mxnet</a><a href="#pytorch-1-1" onclick="tagClick('pytorch'); return false;" class="mdl-tabs__tab ">pytorch</a><a href="#tensorflow-1-2" onclick="tagClick('tensorflow'); return false;" class="mdl-tabs__tab ">tensorflow</a></div>



.. raw:: html

    <div class="mdl-tabs__panel is-active" id="mxnet-1-0">

.. code:: python

    %matplotlib inline
    from mpl_toolkits import mplot3d
    from mxnet import np, npx
    from d2l import mxnet as d2l
    
    npx.set_np()



.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="pytorch-1-1">

.. code:: python

    %matplotlib inline
    import numpy as np
    import torch
    from mpl_toolkits import mplot3d
    from d2l import torch as d2l



.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="tensorflow-1-2">

.. code:: python

    %matplotlib inline
    import numpy as np
    import tensorflow as tf
    from mpl_toolkits import mplot3d
    from d2l import tensorflow as d2l



.. raw:: html

    </div>



.. raw:: html

    </div>

Definições
----------

Antes da análise convexa, precisamos definir *conjuntos convexos* e
*funções convexas*. Eles levam a ferramentas matemáticas que são
comumente aplicadas ao aprendizado de máquina.

Convex Sets
~~~~~~~~~~~

Os conjuntos são a base da convexidade. Simplificando, um conjunto
:math:`\mathcal{X}` em um espaço vetorial é *convexo* se para qualquer
:math:`a, b \in \mathcal{X}` o segmento de linha conectando :math:`a` e
:math:`b` também estiver em :math:`\mathcal{X}`. Em termos matemáticos,
isso significa que para todos :math:`\lambda \in [0, 1]` temos

.. math:: \lambda  a + (1-\lambda)  b \in \mathcal{X} \text{ whenever } a, b \in \mathcal{X}.

Isso soa um pouco abstrato. Considere :numref:`fig_pacman`. O primeiro
conjunto não é convexo, pois existem segmentos de linha que não estão
contidos nele. Os outros dois conjuntos não sofrem esse problema.

.. _fig_pacman:

.. figure:: ../img/pacman.svg

   O primeiro conjunto é não convexo e os outros dois são convexos.


As definições por si só não são particularmente úteis, a menos que você
possa fazer algo com elas. Neste caso, podemos olhar as interseções como
mostrado em :numref:`fig_convex_intersect`. Suponha que
:math:`\mathcal{X}` e :math:`\mathcal{Y}` são conjuntos convexos. Então
:math:`\mathcal{X} \cap \mathcal{Y}` também é convexo. Para ver isso,
considere qualquer :math:`a, b \in \mathcal{X} \cap \mathcal{Y}`. Como
:math:`\mathcal{X}` e :math:`\mathcal{Y}` são convexos, os segmentos de
linha que conectam :math:`a` e :math:`b` estão contidos em
:math:`\mathcal{X}` e :math:`\mathcal{Y}`. Dado isso, eles também
precisam estar contidos em :math:`\mathcal{X} \cap \mathcal{Y}`,
provando assim nosso teorema.

.. _fig_convex_intersect:

.. figure:: ../img/convex-intersect.svg

   A interseção entre dois conjuntos convexos é convexa.


Podemos reforçar este resultado com pouco esforço: dados os conjuntos
convexos :math:`\mathcal{X}_i`, sua interseção
:math:`\cap_{i} \mathcal{X}_i` é convexa. Para ver que o inverso não é
verdadeiro, considere dois conjuntos disjuntos
:math:`\mathcal{X} \cap \mathcal{Y} = \emptyset`. Agora escolha
:math:`a \in \mathcal{X}` e :math:`b \in \mathcal{Y}`. O segmento de
linha em :numref:`fig_nonconvex` conectando :math:`a` e :math:`b`
precisa conter alguma parte que não está em :math:`\mathcal{X}` nem em
:math:`\mathcal{Y}`, uma vez que assumimos que
:math:`\mathcal{X} \cap \mathcal{Y} = \emptyset`. Consequentemente, o
segmento de linha também não está em
:math:`\mathcal{X} \cup \mathcal{Y}`, provando assim que, em geral, as
uniões de conjuntos convexos não precisam ser convexas.

.. _fig_nonconvex:

.. figure:: ../img/nonconvex.svg

   A união de dois conjuntos convexos não precisa ser convexa.


Normalmente, os problemas de aprendizado profundo são definidos em
conjuntos convexos. Por exemplo, :math:`\mathbb{R}^d`, o conjunto de
vetores :math:`d`-dimensionais de números reais, é um conjunto convexo
(afinal, a linha entre quaisquer dois pontos em :math:`\mathbb{R}^d`
permanece em :math:`\mathbb{R}^d`). Em alguns casos, trabalhamos com
variáveis de comprimento limitado, como bolas de raio :math:`r` conforme
definido por
:math:`\{\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \text{ e } \|\mathbf{x}\| \leq r\}`.

Função Convexa
~~~~~~~~~~~~~~

Agora que temos conjuntos convexos, podemos introduzir *funções
convexas* :math:`f`. Dado um conjunto convexo :math:`\mathcal{X}`, uma
função :math:`f: \mathcal{X} \to \mathbb{R}` é *convexa* se para todos
:math:`x, x' \in \mathcal{X}` e para todos :math:`\lambda \in [0, 1]`
temos

.. math:: \lambda f(x) + (1-\lambda) f(x') \geq f(\lambda x + (1-\lambda) x').

Para ilustrar isso, vamos representar graficamente algumas funções e
verificar quais satisfazem o requisito. Abaixo definimos algumas
funções, convexas e não convexas.



.. raw:: html

    <div class="mdl-tabs mdl-js-tabs mdl-js-ripple-effect"><div class="mdl-tabs__tab-bar code"><a href="#mxnet-3-0" onclick="tagClick('mxnet'); return false;" class="mdl-tabs__tab is-active">mxnet</a><a href="#pytorch-3-1" onclick="tagClick('pytorch'); return false;" class="mdl-tabs__tab ">pytorch</a><a href="#tensorflow-3-2" onclick="tagClick('tensorflow'); return false;" class="mdl-tabs__tab ">tensorflow</a></div>



.. raw:: html

    <div class="mdl-tabs__panel is-active" id="mxnet-3-0">

.. code:: python

    f = lambda x: 0.5 * x**2  # Convex
    g = lambda x: np.cos(np.pi * x)  # Nonconvex
    h = lambda x: np.exp(0.5 * x)  # Convex
    
    x, segment = np.arange(-2, 2, 0.01), np.array([-1.5, 1])
    d2l.use_svg_display()
    _, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
    for ax, func in zip(axes, [f, g, h]):
        d2l.plot([x, segment], [func(x), func(segment)], axes=ax)



.. figure:: output_convexity_94e148_15_0.svg




.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="pytorch-3-1">

.. code:: python

    f = lambda x: 0.5 * x**2  # Convex
    g = lambda x: torch.cos(np.pi * x)  # Nonconvex
    h = lambda x: torch.exp(0.5 * x)  # Convex
    
    x, segment = torch.arange(-2, 2, 0.01), torch.tensor([-1.5, 1])
    d2l.use_svg_display()
    _, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
    for ax, func in zip(axes, [f, g, h]):
        d2l.plot([x, segment], [func(x), func(segment)], axes=ax)



.. figure:: output_convexity_94e148_18_0.svg




.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="tensorflow-3-2">

.. code:: python

    f = lambda x: 0.5 * x**2  # Convex
    g = lambda x: tf.cos(np.pi * x)  # Nonconvex
    h = lambda x: tf.exp(0.5 * x)  # Convex
    
    x, segment = tf.range(-2, 2, 0.01), tf.constant([-1.5, 1])
    d2l.use_svg_display()
    _, axes = d2l.plt.subplots(1, 3, figsize=(9, 3))
    for ax, func in zip(axes, [f, g, h]):
        d2l.plot([x, segment], [func(x), func(segment)], axes=ax)



.. figure:: output_convexity_94e148_21_0.svg




.. raw:: html

    </div>



.. raw:: html

    </div>

Como esperado, a função cosseno é *não convexa*, enquanto a parábola e a
função exponencial são. Observe que o requisito de que
:math:`\mathcal{X}` seja um conjunto convexo é necessário para que a
condição faça sentido. Caso contrário, o resultado de
:math:`f(\lambda x + (1-\lambda) x')` pode não ser bem definido.

Desigualdades de Jensen
~~~~~~~~~~~~~~~~~~~~~~~

Dada uma função convexa :math:`f`, uma das ferramentas matemáticas mais
úteis é a *desigualdade de Jensen*. Isso equivale a uma generalização da
definição de convexidade:

.. math:: \sum_i \alpha_i f(x_i)  \geq f\left(\sum_i \alpha_i x_i\right)    \text{ and }    E_X[f(X)]  \geq f\left(E_X[X]\right),

onde :math:`\alpha_i` são números reais não negativos tais que
:math:`\sum_i \alpha_i = 1` e :math:`X` é uma variável aleatória. Em
outras palavras, a expectativa de uma função convexa não é menos do que
a função convexa de uma expectativa, onde a última é geralmente uma
expressão mais simples. Para provar a primeira desigualdade, aplicamos
repetidamente a definição de convexidade a um termo da soma de cada vez.

Uma das aplicações comuns da desigualdade de Jensen é para ligar uma
expressão mais complicada por uma mais simples. Por exemplo, sua
aplicação pode ser no que diz respeito ao log-verossimilhança de
variáveis aleatórias parcialmente observadas. Ou seja, usamos

.. math:: E_{Y \sim P(Y)}[-\log P(X \mid Y)] \geq -\log P(X),

uma vez que :math:`\int P(Y) P(X \mid Y) dY = P(X)`. Isso pode ser usado
em métodos variacionais. Aqui :math:`Y` é normalmente a variável
aleatória não observada, :math:`P(Y)` é a melhor estimativa de como ela
pode ser distribuída e :math:`P(X)` é a distribuição com :math:`Y`
integrada. Por exemplo, no agrupamento :math:`Y` podem ser os rótulos de
cluster e :math:`P(X \mid Y)` é o modelo gerador ao aplicar rótulos de
cluster.

Propriedades
------------

As funções convexas têm algumas propriedades úteis. Nós os descrevemos
abaixo.

Mínimos locais são mínimos globais
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Em primeiro lugar, os mínimos locais das funções convexas também são os
mínimos globais. Podemos provar isso por contradição como segue.

Considere uma função convexa :math:`f` definida em um conjunto convexo
:math:`\mathcal{X}`. Suponha que :math:`x^{\ast} \in \mathcal{X}` seja
um mínimo local: existe um pequeno valor positivo :math:`p` de forma que
para :math:`x \in \mathcal{X}` que satisfaz
:math:`0 < |x - x^{\ast}| \leq p` temos :math:`f(x^{\ast}) < f(x)`.

Suponha que o mínimo local :math:`x^{\ast}` não é o mínimo global de
:math:`f`: existe :math:`x' \in \mathcal{X}` para o qual
:math:`f(x') < f(x^{\ast})`. Também existe :math:`\lambda \in [0, 1)`
como :math:`\lambda = 1 - \frac{p}{|x^{\ast} - x'|}` de modo a
:math:`0 < |\lambda x^{\ast} + (1-\lambda) x' - x^{\ast}| \leq p`.

Contudo, de acordo com a definição de funções convexas, temos

.. math::

   \begin{aligned}
       f(\lambda x^{\ast} + (1-\lambda) x') &\leq \lambda f(x^{\ast}) + (1-\lambda) f(x') \\
       &< \lambda f(x^{\ast}) + (1-\lambda) f(x^{\ast}) \\
       &= f(x^{\ast}),
   \end{aligned}

o que contradiz nossa afirmação de que :math:`x^{\ast}` é um mínimo
local. Portanto, não existe :math:`x' \in \mathcal{X}` para o qual
:math:`f(x') < f(x^{\ast})`. O mínimo local :math:`x^{\ast}` também é o
mínimo global.

Por exemplo, a função convexa :math:`f(x) = (x-1)^2` tem um mínimo local
em :math:`x=1`, que também é o mínimo global.



.. raw:: html

    <div class="mdl-tabs mdl-js-tabs mdl-js-ripple-effect"><div class="mdl-tabs__tab-bar code"><a href="#mxnet-5-0" onclick="tagClick('mxnet'); return false;" class="mdl-tabs__tab is-active">mxnet</a><a href="#pytorch-5-1" onclick="tagClick('pytorch'); return false;" class="mdl-tabs__tab ">pytorch</a><a href="#tensorflow-5-2" onclick="tagClick('tensorflow'); return false;" class="mdl-tabs__tab ">tensorflow</a></div>



.. raw:: html

    <div class="mdl-tabs__panel is-active" id="mxnet-5-0">

.. code:: python

    f = lambda x: (x - 1) ** 2
    d2l.set_figsize()
    d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')



.. figure:: output_convexity_94e148_27_0.svg




.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="pytorch-5-1">

.. code:: python

    f = lambda x: (x - 1) ** 2
    d2l.set_figsize()
    d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')



.. figure:: output_convexity_94e148_30_0.svg




.. raw:: html

    </div>



.. raw:: html

    <div class="mdl-tabs__panel " id="tensorflow-5-2">

.. code:: python

    f = lambda x: (x - 1) ** 2
    d2l.set_figsize()
    d2l.plot([x, segment], [f(x), f(segment)], 'x', 'f(x)')



.. figure:: output_convexity_94e148_33_0.svg




.. raw:: html

    </div>



.. raw:: html

    </div>

O fato de que os mínimos locais para funções convexas também são os
mínimos globais é muito conveniente. Isso significa que, se minimizarmos
as funções, não podemos “ficar presos”. Observe, porém, que isso não
significa que não possa haver mais de um mínimo global ou que possa
mesmo existir um. Por exemplo, a função
:math:`f(x) = \mathrm{max}(|x|-1, 0)` atinge seu valor mínimo no
intervalo :math:`[-1, 1]`. Por outro lado, a função
:math:`f(x) = \exp(x)` não atinge um valor mínimo em :math:`\mathbb{R}`:
para :math:`x \to -\infty` ele assíntotas para :math:`0`, mas não há
:math:`x` para o qual :math:`f(x) = 0`.

Os conjuntos de funções convexas abaixo são convexos
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Nós podemos convenientemente definir conjuntos convexos via *conjuntos
abaixo* de funções convexas. Concretamente, dada uma função convexa
:math:`f` definida em um conjunto convexo :math:`\mathcal{X}`, qualquer
conjunto abaixo

.. math:: \mathcal{S}_b := \{x | x \in \mathcal{X} \text{ and } f(x) \leq b\}

é convexo.

Vamos provar isso rapidamente. Lembre-se de que para qualquer
:math:`x, x' \in \mathcal{S}_b` precisamos mostrar que
:math:`\lambda x + (1-\lambda) x' \in \mathcal{S}_b` enquanto
:math:`\lambda \in [0, 1]`. Como :math:`f(x) \leq b` e
:math:`f(x') \leq b`, pela definição de convexidade, temos

.. math:: f(\lambda x + (1-\lambda) x') \leq \lambda f(x) + (1-\lambda) f(x') \leq b.

Convexidade e derivados secundários
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Sempre que a segunda derivada de uma função
:math:`f: \mathbb{R}^n \rightarrow \mathbb{R}` existe, é muito fácil
verificar se :math:`f` é convexa. Tudo o que precisamos fazer é
verificar se o hessiano de :math:`f` é semidefinido positivo:
:math:`\nabla^2f \succeq 0`, ou seja, denotando a matriz Hessiana
:math:`\nabla^2f` por :math:`\mathbf{H}`,
:math:`\mathbf{x}^\top \mathbf{H} \mathbf{x} \geq 0` para todo
:math:`\mathbf{x} \in \mathbb{R}^n`. Por exemplo, a função
:math:`f(\mathbf{x}) = \frac{1}{2} \|\mathbf{x}\|^2` é convexa, pois
:math:`\nabla^2 f = \mathbf{1}`, ou seja, seu Hessian é uma matriz de
identidade.

Formalmente, qualquer função unidimensional duas vezes diferenciável
:math:`f: \mathbb{R} \rightarrow \mathbb{R}` é convexa se e somente se
sua segunda derivada :math:`f'' \geq 0`. Para qualquer função
multidimensional duas vezes diferenciável
:math:`f: \mathbb{R}^{n} \rightarrow \mathbb{R}`, é convexo se e somente
se for Hessiano :math:`\nabla^2f \succeq 0`.

Primeiro, precisamos provar o caso unidimensional. Para ver isso
convexidade de :math:`f` implica :math:`f''\geq 0` usamos o fato de que

.. math:: \frac{1}{2} f(x + \epsilon) + \frac{1}{2} f(x - \epsilon) \geq f\left(\frac{x + \epsilon}{2} + \frac{x - \epsilon}{2}\right) = f(x).

Uma vez que a segunda derivada é dada pelo limite sobre diferenças
finitas, segue-se que

.. math:: f''(x) = \lim_{\epsilon \to 0} \frac{f(x+\epsilon) + f(x - \epsilon) - 2f(x)}{\epsilon^2} \geq 0.

Para ver isso :math:`f'' \geq 0` implica que :math:`f` é convexo usamos
o fato de que :math:`f'' \geq 0` implica que :math:`f'` é uma função
monotonicamente não decrescente. Sejam :math:`a < x < b` três pontos em
:math:`\mathbb{R}`, onde :math:`x = (1-\lambda)a + \lambda b` e
:math:`\lambda \in (0, 1)`. De acordo com o teorema do valor médio,
existem :math:`\alpha \in [a, x]` e :math:`\beta \in [x, b]` de tal modo
que

.. math:: f'(\alpha) = \frac{f(x) - f(a)}{x-a} \text{ and } f'(\beta) = \frac{f(b) - f(x)}{b-x}.

Por monotonicidade :math:`f'(\beta) \geq f'(\alpha)`, por isso

.. math:: \frac{x-a}{b-a}f(b) + \frac{b-x}{b-a}f(a) \geq f(x).

De :math:`x = (1-\lambda)a + \lambda b`, temos

.. math:: \lambda f(b) + (1-\lambda)f(a) \geq f((1-\lambda)a + \lambda b),

provando assim convexidade.

Em segundo lugar, precisamos de um lema antes comprovando o caso
multidimensional: :math:`f: \mathbb{R}^n \rightarrow \mathbb{R}` é
convexo se e somente se para todos
:math:`\mathbf{x}, \mathbf{y} \in \mathbb{R}^n`

.. math:: g(z) \stackrel{\mathrm{def}}{=} f(z \mathbf{x} + (1-z)  \mathbf{y}) \text{ where } z \in [0,1]

é convexo.

Para provar que a convexidade de :math:`f` implica que :math:`g` é
convexo, podemos mostrar que para todos :math:`a, b, \lambda \in [0, 1]`
(portanto :math:`0 \leq \lambda a + (1-\lambda) b \leq 1`)

.. math::

   \begin{aligned} &g(\lambda a + (1-\lambda) b)\\
   =&f\left(\left(\lambda a + (1-\lambda) b\right)\mathbf{x} + \left(1-\lambda a - (1-\lambda) b\right)\mathbf{y} \right)\\
   =&f\left(\lambda \left(a \mathbf{x} + (1-a)  \mathbf{y}\right)  + (1-\lambda) \left(b \mathbf{x} + (1-b)  \mathbf{y}\right) \right)\\
   \leq& \lambda f\left(a \mathbf{x} + (1-a)  \mathbf{y}\right)  + (1-\lambda) f\left(b \mathbf{x} + (1-b)  \mathbf{y}\right) \\
   =& \lambda g(a) + (1-\lambda) g(b).
   \end{aligned}

Para provar o contrário, nós podemos mostrar isso para
todo\ :math:`\lambda \in [0, 1]`

.. math::

   \begin{aligned} &f(\lambda \mathbf{x} + (1-\lambda) \mathbf{y})\\
   =&g(\lambda \cdot 1 + (1-\lambda) \cdot 0)\\
   \leq& \lambda g(1)  + (1-\lambda) g(0) \\
   =& \lambda f(\mathbf{x}) + (1-\lambda) g(\mathbf{y}).
   \end{aligned}

Finalmente, usando o lema acima e o resultado do caso unidimensional, o
caso multi-dimensional pode ser comprovado da seguinte forma. Uma função
multidimensional :math:`f: \mathbb{R}^n \rightarrow \mathbb{R}` é
convexa se e somente se para todos
:math:`\mathbf{x}, \mathbf{y} \in \mathbb{R}^n`
:math:`g(z) \stackrel{\mathrm{def}}{=} f(z \mathbf{x} + (1-z) \mathbf{y})`,
onde :math:`z \in [0,1]`, é convexo. De acordo com o caso
unidimensional, isso vale se e somente se
:math:`g'' = (\mathbf{x} - \mathbf{y})^\top \mathbf{H}(\mathbf{x} - \mathbf{y}) \geq 0`
(:math:`\mathbf{H} \stackrel{\mathrm{def}}{=} \nabla^2f`) para todo
:math:`\mathbf{x}, \mathbf{y} \in \mathbb{R}^n`, que é equivalente a
:math:`\mathbf{H} \succeq 0` de acordo com a definição de matrizes
semidefinidas positivas.

Restrições
----------

Uma das boas propriedades da otimização convexa é que ela nos permite
lidar com as restrições de maneira eficiente. Ou seja, permite-nos
resolver problemas da forma:

.. math::

   \begin{aligned} \mathop{\mathrm{minimize~}}_{\mathbf{x}} & f(\mathbf{x}) \\
       \text{ subject to } & c_i(\mathbf{x}) \leq 0 \text{ for all } i \in \{1, \ldots, N\}.
   \end{aligned}

Aqui :math:`f` é o objetivo e as funções :math:`c_i` são funções de
restrição. Para ver o que isso faz, considere o caso em que
:math:`c_1(\mathbf{x}) = \|\mathbf{x}\|_2 - 1`. Neste caso, os
parâmetros :math:`\mathbf{x}` são restritos à bola unitária. Se uma
segunda restrição é
:math:`c_2(\mathbf{x}) = \mathbf{v}^\top \mathbf{x} + b`, então isso
corresponde a todos :math:`\mathbf{x}` em um meio-espaço. Satisfazer as
duas restrições simultaneamente significa selecionar uma fatia de uma
bola como o conjunto de restrições.

Função de Lagrange
~~~~~~~~~~~~~~~~~~

Em geral, resolver um problema de otimização restrito é difícil. Uma
maneira de lidar com isso vem da física com uma intuição bastante
simples. Imagine uma bola dentro de uma caixa. A bola rolará para o
local mais baixo e as forças da gravidade serão equilibradas com as
forças que os lados da caixa podem impor à bola. Em suma, o gradiente da
função objetivo (ou seja, a gravidade) será compensado pelo gradiente da
função de restrição (necessidade de permanecer dentro da caixa em
virtude das paredes “empurrando para trás”). Observe que qualquer
restrição que não esteja ativa (ou seja, a bola não toca a parede) não
será capaz de exercer qualquer força na bola.

Ignorando a derivação da função de Lagrange :math:`L` (consulte, por
exemplo, o livro de Boyd e Vandenberghe para obter detalhes
:cite:`Boyd.Vandenberghe.2004`), o raciocínio acima pode ser expresso
através do seguinte problema de otimização do ponto de sela:

.. math:: L(\mathbf{x},\alpha) = f(\mathbf{x}) + \sum_i \alpha_i c_i(\mathbf{x}) \text{ where } \alpha_i \geq 0.

Aqui, as variáveis :math:`\alpha_i` são os chamados *Multiplicadores de
Lagrange* que garantem que uma restrição seja devidamente aplicada. Eles
são escolhidos apenas grandes o suficiente para garantir que
:math:`c_i(\mathbf{x}) \leq 0` para todos os :math:`i`. Por exemplo,
para qualquer :math:`\mathbf{x}` para o qual :math:`c_i(\mathbf{x}) < 0`
naturalmente, acabaríamos escolhendo :math:`\alpha_i = 0`. Além disso,
este é um problema de otimização *ponto de sela* em que se deseja
*maximizar* :math:`L` em relação a :math:`\alpha` e simultaneamente
*minimizá-lo* em relação a :math:`\mathbf{x}`. Existe uma vasta
literatura explicando como chegar à função
:math:`L(\mathbf{x}, \alpha)`. Para nossos propósitos, é suficiente
saber que o ponto de sela de :math:`L` é onde o problema de otimização
restrito original é resolvido de forma otimizada.

Penalidades
~~~~~~~~~~~

Uma maneira de satisfazer problemas de otimização restrita pelo menos
aproximadamente é adaptar a função de Lagrange :math:`L`. Em vez de
satisfazer :math:`c_i(\mathbf{x}) \leq 0`, simplesmente adicionamos
:math:`\alpha_i c_i(\mathbf{x})` à função objetivo :math:`f(x)`. Isso
garante que as restrições não sejam violadas demais.

Na verdade, temos usado esse truque o tempo todo. Considere a diminuição
do peso em :numref:`sec_weight_decay`. Nele adicionamos
:math:`\frac{\lambda}{2} \|\mathbf{w}\|^2` à função objetivo para
garantir que :math:`\mathbf{w}` não cresça muito. Usando o ponto de
vista da otimização restrita, podemos ver que isso garantirá que
:math:`\|\mathbf{w}\|^2 - r^2 \leq 0` para algum raio :math:`r`. Ajustar
o valor de :math:`\lambda` nos permite variar o tamanho de
:math:`\mathbf{w}`.

Em geral, adicionar penalidades é uma boa maneira de garantir a
satisfação aproximada da restrição. Na prática, isso acaba sendo muito
mais robusto do que a satisfação exata. Além disso, para problemas não
convexos, muitas das propriedades que tornam a abordagem exata tão
atraente no caso convexo (por exemplo, otimização) não são mais válidas.

Projeções
~~~~~~~~~

Uma estratégia alternativa para satisfazer as restrições são as
projeções. Novamente, nós os encontramos antes, por exemplo, ao lidar
com recorte de gradiente em :numref:`sec_rnn_scratch`. Lá, garantimos
que um gradiente tem comprimento limitado por :math:`c` via

.. math:: \mathbf{g} \leftarrow \mathbf{g} \cdot \mathrm{min}(1, c/\|\mathbf{g}\|).

Isso acaba sendo uma *projeção* de :math:`g` na bola de raio :math:`c`.
Mais geralmente, uma projeção em um conjunto (convexo)
:math:`\mathcal{X}` é definida como

.. math:: \mathrm{Proj}_\mathcal{X}(\mathbf{x}) = \mathop{\mathrm{argmin}}_{\mathbf{x}' \in \mathcal{X}} \|\mathbf{x} - \mathbf{x}'\|_2.

Portanto, é o ponto mais próximo em :math:`\mathcal{X}` para
:math:`\mathbf{x}`. Isso soa um pouco abstrato.
:numref:`fig_projections` explica um pouco mais claramente. Nele temos
dois conjuntos convexos, um círculo e um diamante. Os pontos dentro do
conjunto (amarelo) permanecem inalterados. Pontos fora do conjunto
(preto) são mapeados para o ponto mais próximo dentro do conjunto
(vermelho). Enquanto para bolas de :math:`L_2` isso não altera a
direção, este não precisa ser o caso em geral, como pode ser visto no
caso do diamante.

.. _fig_projections:

.. figure:: ../img/projections.svg

   Projeções convexas.


Um dos usos para projeções convexas é calcular vetores de peso esparsos.
Neste caso, projetamos :math:`\mathbf{w}` em uma bola :math:`L_1` (a
última é uma versão generalizada do diamante na imagem acima).

Sumário
-------

No contexto de aprendizagem profunda, o principal objetivo das funções
convexas é motivar algoritmos de otimização e nos ajudar a entendê-los
em detalhes. A seguir, veremos como a descida gradiente e a descida
gradiente estocástica podem ser derivadas de acordo.

-  As interseções de conjuntos convexos são convexas. Os sindicatos não.
-  A expectativa de uma função convexa é maior do que a função convexa
   de uma expectativa (desigualdade de Jensen).
-  Uma função duas vezes diferenciável é convexa se, e somente se, sua
   segunda derivada tem apenas autovalores não negativos em toda a
   extensão.
-  Restrições convexas podem ser adicionadas por meio da função
   Lagrange. Na prática, basta adicioná-los com uma penalidade à função
   objetivo.
-  As projeções são mapeadas para pontos no conjunto (convexo) mais
   próximo do ponto original.

Exercícios
----------

1. Suponha que queremos verificar a convexidade de um conjunto
   desenhando todas as linhas entre os pontos dentro do conjunto e
   verificando se as linhas estão contidas.

   1. Prove que é suficiente verificar apenas os pontos no limite.
   2. Prove que é suficiente verificar apenas os vértices do conjunto.

2. Denote por
   :math:`\mathcal{B}_p[r] := \{\mathbf{x} | \mathbf{x} \in \mathbb{R}^d \text{ and } \|\mathbf{x}\|_p \leq r\}`
   a bola de raio :math:`r` usando a norma :math:`p`. Prove que
   :math:`\mathcal{B}_p[r]` é convexo para todos :math:`p\geq 1`.
3. Dadas as funções convexas :math:`f` e :math:`g` mostram que
   :math:`\mathrm{max} (f, g)` também é convexo. Prove que
   :math:`\mathrm{min} (f, g)` não é convexo.
4. Prove que a normalização da função softmax é convexa. Mais
   especificamente, provar a convexidade de
   :math:`f(x) = \log \sum_i \exp(x_i)`.
5. Prove que os subespaços lineares são conjuntos convexos, ou seja,
   :math:`\mathcal{X} = \{\mathbf{x} | \mathbf{W} \mathbf{x} = \mathbf{b}\}`.
6. Prove que no caso de subespaços lineares com :math:`\mathbf{b} = 0` a
   projeção :math:`\mathrm{Proj}_\mathcal{X}` pode ser escrita como
   :math:`\mathbf{M} \mathbf{x}` para algumas matrizes
   :math:`\mathbf{M}`.
7. Mostre que para funções convexas duas vezes diferenciáveis
   ​​\ :math:`f` podemos escrever
   :math:`f(x + \epsilon) = f(x) + \epsilon f'(x) + \frac{1}{2} \epsilon^2 f''(x + \xi)`
   para algum :math:`\xi \in [0, \epsilon]`.
8. Dado um vetor :math:`\mathbf{w} \in \mathbb{R}^d` com
   :math:`\|\mathbf{w}\|_1 > 1`, calcule a projeção na bola unitária
   :math:`\ell_1`.

   1. Como etapa intermediária, escreva o objetivo penalizado
      :math:`\|\mathbf{w} - \mathbf{w}'\|_2^2 + \lambda \|\mathbf{w}'\|_1`
      e calcule a solução para um dado :math:`\lambda > 0`.
   2. Você consegue encontrar o valor ‘certo’ de :math:`\lambda` sem
      muitas tentativas e erros?

9. Dado um conjunto convexo :math:`\mathcal{X}` e dois vetores
   :math:`\mathbf{x}` e :math:`\mathbf{y}` provam que as projeções nunca
   aumentam as distâncias, ou seja,
   :math:`\|\mathbf{x} - \mathbf{y}\| \geq \|\mathrm{Proj}_\mathcal{X}(\mathbf{x}) - \mathrm{Proj}_\mathcal{X}(\mathbf{y})\|`.

`Discussions <https://discuss.d2l.ai/t/350>`__