A descida do gradiente pode ser aplicada a funções não convexas?

Estou apenas aprendendo sobre otimização e tendo problemas para entender a diferença entre otimização convexa e não convexa. Pelo meu entendimento, uma função convexa é aquela em que "o segmento de linha entre dois pontos no gráfico da função está acima ou no gráfico". Nesse caso, um algoritmo de descida de gradiente pode ser usado, porque existe um único mínimo e os gradientes sempre o levarão a esse mínimo.

No entanto, e a função nesta figura:

Aqui, o segmento de linha azul cruza abaixo da função vermelha. No entanto, a função ainda tem um mínimo único e, portanto, a descida do gradiente ainda o levará a esse mínimo.

Então, minhas perguntas são:

1) A função nesta figura é convexa ou não convexa?

2) Se não for convexo, os métodos de otimização convexa (descida em gradiente) ainda podem ser aplicados?

A função que você representou graficamente não é de fato convexa. No entanto, é quaseiconvex .

A descida de gradiente é um método genérico para otimização contínua, portanto pode ser e é muito comumente aplicado a funções não-convexas. Com uma função suave e um tamanho de etapa razoavelmente selecionado, ele gerará uma sequência de pontos$x_1, x_2, \ldots$ com valores estritamente decrescentes $f(x_1) > f(x_2) > \ldots$.

A descida do gradiente eventualmente convergirá para um ponto estacionário da função, independentemente da convexidade. Se a função for convexa, será um mínimo global, mas, se não, poderá ser um mínimo local ou mesmo um ponto de sela.

Funções quaseiconvexas são um caso interessante. Qualquer mínimo local de uma função quaseiconvexa também é um mínimo global, mas as funções quaseiconvexas também podem ter pontos estacionários que não são mínimos locais (use$f(x) = x^3$por exemplo). Portanto, teoricamente, é possível que a descida do gradiente fique presa em um ponto estacionário e não progrida para um mínimo global. No seu exemplo, se o ombro do lado esquerdo do gráfico se nivelasse perfeitamente, a descida do gradiente poderia ficar presa lá. No entanto, variantes como o método da bola pesada podem ser capazes de "avançar" e atingir o valor mínimo global.

Paulo já mencionou um ponto importante:

• se f é convexo, não há pontos de sela e todos os mínimos locais também são globais. Assim, é garantido que o GD (com um tamanho de etapa adequado) encontre um minimizador global.

O que dificulta a otimização não convexa é a presença de pontos de sela e mínimos locais, onde o gradiente é (0, ..., 0) e que tem um valor objetivo arbitrariamente ruim.

Encontrar o minmizer global em uma configuração desse tipo geralmente é difícil para o NP e, em vez disso, você decide com o objetivo de encontrar um minimizador local.

No entanto, observe que:

• A probabilidade de GD ficar preso em uma sela é realmente 0 ( veja aqui ).
• No entanto, a presença de pontos de sela pode desacelerar gravemente o progresso dos GDs, porque as direções de baixa curvatura são exploradas muito lentamente ( veja aqui )

Dependendo da dimensionalidade do seu problema, pode ser aconselhável seguir uma rotina de otimização de segunda ordem.