Visão geral dos métodos de gradiente em problemas de otimização matemática

Prefácio

Este artigo focará em métodos para resolver problemas de otimização matemática com base no uso de um gradiente de função. O objetivo principal é coletar no artigo todas as idéias mais importantes que, de alguma forma, estão relacionadas a esse método e suas várias modificações.





UPD Nos comentários, eles escrevem que em alguns navegadores e nas fórmulas de aplicativos para dispositivos móveis não são exibidos. Infelizmente, não sei como lidar com isso. Só posso dizer que usei as macros “inline” e “display” do editor Habrava. Se de repente você souber como consertar isso - escreva nos comentários, por favor.

Nota do autor

Na época em que escrevi, defendi uma dissertação, cuja tarefa exigia que eu tivesse um profundo entendimento de métodos basicamente teóricos de otimização matemática. No entanto, meus olhos (de todos os outros) ainda estão embaçados por fórmulas longas e assustadoras, por isso gastei muito tempo para isolar as ideias-chave que caracterizariam diferentes variações dos métodos de gradiente. Meu objetivo pessoal é escrever um artigo contendo a quantidade mínima de informações necessárias para uma compreensão mais ou menos detalhada do tópico. Mas esteja preparado, não se pode prescindir de fórmulas de qualquer maneira.

Declaração do problema

Antes de descrever o método, você deve primeiro descrever o problema, a saber: “Dado são muitos $$$\ mathcal {K}$ e função $$$f: \ mathcal {K} \ rightarrow \ mathbb {R}$ precisa encontrar um ponto $$$x ^ * \ in \ mathcal {K}$ tal que $$$f (x) \ geq f (x ^ *)$ para todos $$$x \ in \ mathcal {K}$ ", Que geralmente é escrito assim

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathcal {K}}.$$

Em teoria , é geralmente assumido que $$$f$ É uma função diferenciável e convexa e $$$\ mathcal {K}$ - conjunto convexo (e melhor ainda, se for o caso) $$$\ mathcal {K} = \ mathbb {R} ^ n$ ), isso nos dá algumas garantias do sucesso da aplicação da descida de gradiente. Na prática, a descida do gradiente é aplicada com êxito, mesmo quando a tarefa não possui nenhuma das propriedades acima (um exemplo posteriormente neste artigo).

Um pouco de matemática

Suponha que, por enquanto, apenas precisamos encontrar um mínimo de uma função unidimensional

$$

$$f (x) \ rightarrow \ min_ {x \ in \ mathbb {R}}.$$

No século XVII, Pierre Fermat criou um critério que permitia resolver problemas simples de otimização, a saber, se $$$x ^ *$ - ponto mínimo $$$f ^ *$ então

$$

$$f '(x ^ *) = 0$$

onde $$$f '$ - derivado $$$f$ . Este critério é baseado em uma aproximação linear.

$$

$$f (x) \ approx f (x ^ *) + f '(x ^ *) (x-x ^ *).$$

Mais perto $$$x$ para $$$x ^ *$ , mais precisa essa aproximação. No lado direito, há uma expressão que, quando $$$f '(x ^ *) \ neq 0$ talvez goste mais $$$f (x ^ *)$ menos é a essência principal do critério. No caso multidimensional, similarmente à aproximação linear $$$f (x) \ aprox f (x ^ *) + \ nabla f (x ^ *) ^ T (x-x ^ *)$ (a seguir $$$x ^ Ty = \ sum_ {i = 1} ^ nx_iy_i$ - produto escalar padrão, a forma de escrita se deve ao fato de que o produto escalar é o mesmo que o produto da matriz de um vetor de linha por um vetor de coluna), o critério é obtido

$$

$$\ nabla f (x ^ *) = 0.$$

Valor $$$\ nabla f (x ^ *)$ - gradiente de função $$$f$ no ponto $$$x ^ *$ . Além disso, a igualdade do gradiente para zero significa a igualdade de todas as derivadas parciais para zero; portanto, no caso multidimensional, é possível obter esse critério simplesmente aplicando o critério unidimensional para cada variável separadamente.

Vale ressaltar que essas condições são necessárias, mas não suficientes, o exemplo mais simples é 0 para $$$f (x) = x ^ 2$ e $$$f (x) = x ^ 3$


Este critério é suficiente no caso de uma função convexa, em grande parte por isso foi possível obter tantos resultados para funções convexas.

Funções quadráticas

Funções quadráticas em $$$\ mathbb {R} ^ n$ É uma função do formulário

$$

$$f (x) = f (x_1, x_2, \ ldots, x_n) = \ frac {1} {2} \ sum_ {i, j = 1} ^ na_ {ij} x_ix_j- \ sum_ {i = 1} ^ n b_ix_i + c$$

Para economizar espaço (e se preocupar menos com índices), essa função geralmente é escrita em forma de matriz:

$$

$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c,$$

onde $$$x = (x_1, \ ldots, x_n) ^ T$ , $$$b = (b_1, \ ldots, b_n) ^ T$ , $$$A$ É uma matriz na qual na interseção $$$i$ cordas e $$$j$ coluna é o valor
$$$\ frac {1} {2} (a_ {ij} + a_ {ji})$ ( $$$A$ acaba sendo simétrico - isso é importante). Próximo. ao mencionar uma função quadrática, terei a função acima.

Por que estou falando sobre isso? O fato é que as funções quadráticas são importantes na otimização por dois motivos:

1. Eles também ocorrem na prática, por exemplo, ao construir uma regressão linear com mínimos quadrados
2. O gradiente de uma função quadrática é uma função linear, em particular para a função acima
   

   $$

   $$\ frac {\ parcial} {\ parcial x_i} f (x_1, x_2, \ ldots, x_n) = a_ {ii} x_i + \ sum_ {j \ neq i} \ frac {1} {2} (a_ {ij } + a_ {ji}) x_j -b_i,$$
   
   Ou em forma de matriz
   

   $$

   $$\ nabla f (x) = Ax-b,$$
   
   Assim, o sistema $$$\ nabla f (x) = 0$ - sistema linear. Um sistema que é mais simples que linear não existe. O pensamento que eu estava tentando entender é a otimização de uma função quadrática - a classe mais simples de problemas de otimização . Por outro lado, o fato de que $$$\ nabla f (x ^ *) = 0$ - as condições mínimas necessárias tornam possível resolver sistemas lineares através de problemas de otimização. Um pouco mais tarde, tentarei convencê-lo de que isso faz sentido.
   

Propriedades úteis de gradiente

Bem, parece que descobrimos que se uma função é diferenciável (tem derivadas em relação a todas as variáveis), então no ponto mínimo o gradiente deve ser igual a zero. Mas o gradiente carrega alguma informação útil quando é diferente de zero?

Vamos tentar resolver um problema mais simples: o ponto é dado $$$x$ encontrar ponto $$$\ bar {x}$ tal que $$$f (\ bar {x}) <f (x)$ . Vamos dar um ponto ao lado de $$$x$ novamente usando aproximação linear $$$f (\ bar {x}) \ aprox f (x) + \ nabla f (x) ^ T (\ bar {x} -x)$ . Se você tomar $$$\ bar {x} = x- \ alpha \ nabla f (x)$ , $$$\ alpha> 0$ então nós temos

$$

$$f (\ bar {x}) \ aproximadamente f (x) - \ alpha \ | \ nabla f (x) \ | ^ 2 <f (x).$$

Da mesma forma, se $$$\ alpha <0$ então $$$f (\ bar {x})$ será mais $$$f (x)$ (a seguir $$$|| x || = \ sqrt {x_1 ^ 2 + x_2 ^ 2 + \ ldots + x_n ^ 2} ~$ ) Novamente, como usamos a aproximação, essas considerações serão verdadeiras apenas para pequenos $$$\ alpha$ . Para resumir o acima, se $$$\ nabla f (x) \ neq 0$ , o gradiente indica a direção do maior aumento local na função .

Aqui estão dois exemplos para funções bidimensionais. Imagens desse tipo geralmente podem ser vistas em demonstrações de descida de gradiente. Linhas coloridas são as chamadas linhas de nível , este é um conjunto de pontos para os quais a função assume valores fixos; no meu caso, são círculos e elipses. Marquei as linhas azuis do nível com um valor mais baixo, vermelho - com um valor mais alto.



Observe que para uma superfície definida por uma equação da forma $$$f (x) = c$ , $$$\ nabla f (x)$ define o normal (nas pessoas comuns - o perpendicular) a essa superfície. Observe também que, embora o gradiente seja exibido na direção do maior aumento da função, não há garantia de que, na direção oposta ao gradiente, você encontre um mínimo (por exemplo, a figura da esquerda).

Descida de gradiente

Restava apenas um pequeno passo para o método básico de descida por gradiente: aprendemos a partir do ponto $$$x$ ficando ponto $$$\ bar {x}$ com menor valor de função $$$f$ . O que nos impede de repetir isso várias vezes? De fato, esta é a descida do gradiente: construímos a sequência

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k).$$

Valor $$$\ alpha_k$ chamado de tamanho da etapa (no aprendizado de máquina - a velocidade do aprendizado ). Algumas palavras sobre a escolha $$$\ alpha_k$ : se $$$\ alpha_k$ - muito pequena, a sequência muda lentamente, o que torna o algoritmo não muito eficiente; se $$$\ alpha_k$ muito grande, a aproximação linear se torna fraca e talvez até incorreta. Na prática, o tamanho do passo é geralmente selecionado empiricamente; em teoria, geralmente é assumido um gradiente de Lipschitz, a saber, se

$$

$$\ | \ nabla f (x) - \ nabla f (y) \ | \ leq L \ | x-y \ |$$

para todos $$$x, y$ então $$$\ alpha_k <\ frac {2} {L}$ garante diminuição $$$f (x_k)$ .

Análise para funções quadráticas

Se $$$A$ É uma matriz invertível simétrica, $$$Ax ^ * = b$ então para a função quadrática $$$f (x) = \ frac {1} {2} x ^ TAx-b ^ Tx + c$ apontar $$$x ^ *$ é o ponto mínimo ( UPD . desde que esse mínimo exista - $$$f$ não leva nem perto $$$- \ infty$ valores somente se $$$A$ positivo) e, para o método de descida de gradiente, podemos obter os seguintes

$$

$$x_ {k + 1} -x ^ * = x_k- \ alpha_k \ nabla f (x_k) -x ^ * = x_k- \ alpha_k (Ax_k-b) -x ^ * =$$

$$

$$(x_k-x ^ *) - \ alpha_kA (x_k-x ^ *) = (I- \ alpha_k A) (x_k-x ^ *),$$

onde $$$I$ É a matriz de identidade, ou seja, $$$Ix = x$ para todos $$$x$ . Se $$$\ alpha_k \ equiv \ alpha$ vai acabar

$$

$$\ | x_ {k} -x ^ * \ | = \ | (I- \ alpha A) ^ k (x_0-x ^ *) \ | \ leq \ | I- \ alpha A \ | ^ k \ | x_0 -x ^ * \ |.$$

A expressão à esquerda é a distância da aproximação obtida na etapa $$$k$ gradiente descendente até o ponto mínimo, à direita - uma expressão da forma $$$\ lambda ^ k \ beta$ que converge para zero se $$$| \ lambda | <1$ (a condição que escrevi em $$$\ alpha$ no parágrafo anterior, é exatamente isso que garante). Essa estimativa básica garante que a descida do gradiente converja.

Modificações de descida de gradiente

Agora eu gostaria de falar um pouco sobre as modificações comumente usadas na descida do gradiente, principalmente as chamadas

Métodos de gradiente inercial ou acelerado

Todos os métodos desta classe são expressos da seguinte maneira

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k) + \ beta_k (x_k-x_ {k-1}).$$

O último termo caracteriza essa mesma "inércia", o algoritmo em cada etapa tenta se mover contra o gradiente, mas ao mesmo tempo se move parcialmente por inércia na mesma direção da iteração anterior. Tais métodos têm duas propriedades importantes:

1. Praticamente não complicam a descida usual do gradiente no plano computacional.
2. Com seleção cuidadosa $$$\ alpha_k, \ beta_k$ esses métodos são uma ordem de magnitude mais rápida que a descida gradual do gradiente, mesmo com uma etapa selecionada de maneira ideal.

Um dos primeiros métodos apareceu em meados do século XX e foi chamado de método da bola pesada , que transmitia a natureza da inércia do método: nesse método $$$\ alpha_k, \ beta_k$ independente de $$$k$ e cuidadosamente selecionado, dependendo da função objetivo. Vale a pena notar que $$$\ alpha_k$ pode ser qualquer coisa, menos $$$\ beta_k$ - geralmente um pouco menos de um .

O método da bola pesada é o método inercial mais simples, mas não o primeiro. Nesse caso, na minha opinião, o primeiro método é muito importante para entender a essência desses métodos.

Método Chebyshev

Sim, sim, o primeiro método deste tipo foi inventado por Chebyshev para resolver sistemas de equações lineares. Em algum momento da análise da descida do gradiente, a seguinte igualdade foi obtida

$$

$$x_ {k + 1} -x ^ * = (I- \ alpha_k A) (x_k-x ^ *) = \ ldots =$$

$$

$$(I- \ alpha_kA) (I- \ alpha_ {k-1} A) \ ldots (I- \ alpha_1A) (x_0-x ^ *) = P_k (A) (x_0-x ^ *),$$

onde $$$P_k$ Algum grau polinomial $$$k$ . Por que não tentar pegar $$$\ alpha_k$ para que $$$P_k (A) (x_0-x ^ *)$ era menor? Um nó de polinômios universais que se desviam menos de zero é o polinômio de Chebyshev. O método de Chebyshev consiste essencialmente na seleção dos parâmetros de descida para que $$$P_k$ era um polinômio de Chebyshev. Há realmente um pequeno problema: para uma descida normal do gradiente, isso simplesmente não é possível. No entanto, para métodos inerciais, isso é possível. Isso se deve principalmente ao fato de os polinômios de Chebyshev satisfazerem a relação de recorrência de segunda ordem

$$

$$T_ {n + 1} (x) = 2xT_n (x) -T_ {n-1} (x),$$

portanto, eles não podem ser criados para a descida do gradiente, que calcula um novo valor a partir de apenas um valor anterior e, por inércia, torna-se possível devido ao fato de os dois valores anteriores serem usados. Acontece que a complexidade do cálculo $$$\ alpha_k, \ beta_k$ não depende de $$$k$ nem o tamanho do espaço $$$n$ .

Método do Gradiente Conjugado

Outro fato muito interessante e importante (uma conseqüência do teorema de Hamilton-Cayley): para qualquer matriz quadrada $$$A$ o tamanho $$$n \ vezes n$ existe um polinômio $$$P$ grau não mais $$$n$ para qual $$$P (A) = 0$ . Por que isso é interessante? É tudo sobre a mesma igualdade

$$

$$x_ {k + 1} -x ^ * = P_k (A) (x_0-x ^ *).$$

Se pudéssemos escolher o tamanho da etapa na descida do gradiente de forma a obter exatamente esse polinômio de zeragem, a descida do gradiente convergiria para um número de iteração fixo não maior que a dimensão $$$A$ . Como já descobrimos, não podemos fazer isso para descida gradiente. Felizmente, para métodos inerciais, podemos. A descrição e justificativa do método é bastante técnica, vou me limitar à essência: a cada iteração, são selecionados parâmetros que fornecem o melhor polinômio, que pode ser construído levando em consideração todas as medições feitas antes da etapa atual da medição do gradiente . Ao mesmo tempo

1. Uma iteração de descida de gradiente (sem levar em consideração os cálculos de parâmetros) contém uma multiplicação de matriz por um vetor e 2-3 adições de vetor
2. O cálculo dos parâmetros também requer multiplicação de matriz 1-2 por vetor, multiplicação de vetor escalar 2-3 por vetor e várias adições de vetores.

A coisa mais difícil no plano computacional é a multiplicação da matriz por um vetor, isso geralmente é feito no tempo $$$\ mathcal {O} (n ^ 2)$ No entanto, para uma implementação especial, isso pode ser feito em $$$\ mathcal {O} (m)$ onde $$$m$ - o número de elementos diferentes de zero em $$$A$ . Dada a convergência do método do gradiente conjugado, não mais que $$$n$ iterações obtêm a complexidade geral do algoritmo $$$\ mathcal {O} (nm)$ , que em todos os casos não é pior $$$\ mathcal {O} (n ^ 3)$ para o método de Gauss ou Cholesky, mas muito melhor se $$$m << n ^ 2$ isso não é tão raro.

O método do gradiente conjugado também funciona bem se $$$f$ não é uma função quadrática, mas não converge em um número finito de etapas e geralmente requer pequenas modificações adicionais

Método Nesterov

Para as comunidades de otimização matemática e aprendizado de máquina, o nome "Nesterov" tem sido um nome familiar. Nos anos 80 do século passado, Yu.E. Nesterov apresentou uma versão interessante do método inercial, que tem a forma

$$

$$x_ {k + 1} = x_k- \ alpha_k \ nabla f (x_k + \ beta_k (x_k-x_ {k-1})) + \ beta_k (x_k-x_ {k-1}),$$

não implica nenhum cálculo complicado $$$\ alpha_k, \ beta_k$ como no método do gradiente conjugado, em geral, o comportamento do método é semelhante ao método da bola pesada, mas sua convergência é geralmente muito mais confiável, tanto na teoria quanto na prática.

Descida do gradiente estocástico

A única diferença formal em relação à descida do gradiente usual é o uso de uma função em vez de um gradiente $$$g (x, \ theta)$ tal que $$$E_ \ theta g (x, \ theta) = \ nabla f (x)$ ( $$$E_ \ theta$ - expectativa aleatória $$$\ theta$ ), então a descida do gradiente estocástico tem a forma

$$

$$x_ {k + 1} = x_k- \ alpha_kg (x_k, \ theta_k).$$

$$$\ theta_k$ - Este é um parâmetro aleatório que não afetamos, mas ao mesmo tempo, em média, vamos contra o gradiente. Como exemplo, considere as funções

$$

$$f (x) = \ frac {1} {2m} \ sum_ {j = 1} ^ m \ | x-y_j \ | ^ 2, ~~ \ nabla f (x) = \ frac {1} {m} \ sum_ {j = 1} ^ m (x-y_j)$$

e

$$

$$g (x, i) = x-y_i.$$

Se $$$i$ leva valores $$$1, \ ldots, m$ igualmente provável apenas média $$$g$ É um gradiente $$$f$ . Este exemplo também é indicativo do seguinte: a complexidade do cálculo do gradiente em $$$m$ vezes mais que a complexidade computacional $$$g$ . Isso permite que a descida do gradiente estocástico seja feita ao mesmo tempo em $$$m$ vezes mais iterações. Apesar do declínio estocástico do gradiente geralmente convergir mais lentamente que o normal, devido a um aumento tão grande no número de iterações, é possível melhorar a taxa de convergência por unidade de tempo. Até onde eu sei, no momento, a descida gradiente estocástica é o método básico de treinamento da maioria das redes neurais, implementado em todas as principais bibliotecas ML: fluxo tensor, tocha, caffe, CNTK, etc.

Vale ressaltar que as idéias dos métodos inerciais são usadas para a descida do gradiente estocástico e, na prática, frequentemente aumentam, em teoria, geralmente se supõe que a taxa de convergência assintótica não mude devido ao fato de que o principal erro na descida do gradiente estocástico é devido à dispersão $$$g$ .

Descida do sub-gradiente

Essa variação permite que você trabalhe com funções não diferenciáveis, descreverei em mais detalhes. Novamente teremos que recordar a aproximação linear - o fato é que existe uma característica simples de convexidade através de um gradiente, uma função diferenciável $$$f$ convexo se e somente se $$$f (y) \ geq f (x) + \ nabla f (x) ^ T (y-x)$ para todos $$$x, y$ . Acontece que uma função convexa não precisa ser diferenciável, mas em qualquer ponto $$$x$ certamente existe esse vetor $$$g$ que $$$f (y) \ geq f (x) + g ^ T (y-x)$ para todos $$$y$ . Tal vetor $$$g$ comumente chamado subgradiente $$$f$ no ponto $$$x$ , o conjunto de todos os subgradientes para pontos $$$x$ chamado subdiferencial $$$x$ e denotar $$$\ f parcial (x)$ (apesar da designação - não tem nada a ver com derivadas parciais). No caso unidimensional $$$g$ É um número e a propriedade acima significa simplesmente que o gráfico $$$f$ fica acima da linha que passa $$$(x, f (x))$ e ter uma inclinação $$$g$ (veja as fotos abaixo). Noto que pode haver vários subgradientes para um ponto, até um número infinito.



Geralmente, não é muito difícil calcular pelo menos um subgradiente para um ponto; uma descida do subgradiente usa essencialmente um subgradiente em vez de um gradiente. Acontece que isso é suficiente; em teoria, a taxa de convergência diminui, no entanto, por exemplo, nas redes neurais uma função indiferenciada $$$ReLU (x) = \ máx (0, x)$ eles gostam de usá-lo apenas porque o treinamento é mais rápido (a propósito, este é um exemplo de uma função não convexa e não diferenciável na qual a descida do (sub) gradiente é aplicada com êxito. $$$Relu$ rede neural convexa, mas com várias camadas, contendo $$$Relu$ , não convexo e não diferenciável). Como exemplo, para uma função $$$f (x) = | x |$ subdiferencial é calculado de maneira muito simples

$$

$$\ parcial f (x) = \ begin {cases} 1, & x> 0, \\ -1, & x <0, \\ [-1, 1], & x = 0. \ end {cases}$$

Talvez a última coisa importante a saber é que a descida do sub-gradiente não converge em um tamanho de passo constante . É mais fácil ver a função acima. $$$f (x) = | x |$ . Até a ausência de uma derivada em um ponto quebra a convergência:

1. Digamos que começamos do ponto $$$x_0$ .
2. Etapa de descida do sub-gradiente:
   

   $$

   $$x_ {k + 1} = \ begin {cases} x_ {k} -1, & x> 0, \\ x_k + 1, & x <0, \\ ??? & x = 0. \ end {cases}$$
3. Se $$$x_0> 0$ nos primeiros passos subtrairemos um, se $$$x_0 <0$ depois adicione. De uma forma ou de outra, em algum momento nos encontraremos no intervalo $$$[0, 1)$ a partir do qual chegamos $$$[- 1, 0)$ , e então saltaremos entre dois pontos desses intervalos.

Em teoria, para descidas por sub-gradientes, é recomendável executar uma sequência de etapas

$$

$$\ alpha_k = \ frac {1} {(k + 1) ^ c}.$$

Onde $$$c$ geralmente $$$1$ ou $$$\ frac {1} {2}$ . Na prática, muitas vezes vi etapas bem-sucedidas $$$\ alpha_k = e ^ {- ck}$ , embora, para essas etapas de um modo geral, não haja convergência.

Métodos proximais

Infelizmente, não conheço uma boa tradução para "proximal" no contexto da otimização, por isso chamarei esse método. Os métodos proximais apareceram como uma generalização dos métodos de gradiente projetivo. A ideia é muito simples: se houver uma função $$$f$ representado como uma soma $$$f (x) = \ varphi (x) + h (x)$ onde $$$\ varphi$ É uma função convexa diferenciável e $$$h (x)$ - convexo, para o qual existe um operador proximal especial $$$prox_h (x)$ (neste artigo vou me limitar apenas a exemplos, não descreverei em termos gerais), as propriedades de convergência da descida do gradiente para $$$\ varphi$ permanecer e para descida gradiente para $$$f$ se após cada iteração aplicar esse operador proximal ao ponto atual $$$x_k$ , em outras palavras, a forma geral do método proximal é assim:

$$

$$x_ {k + 1} = prox _ {\ alpha_kh} (x_k- \ alpha_k \ nabla \ varphi (x_k))$$

Eu acho que até agora é completamente incompreensível por que isso pode ser necessário, especialmente considerando que eu não expliquei o que é um operador proximal. Aqui estão dois exemplos:

1. $$$h (x)$ - função indicadora de um conjunto convexo $$$\ mathcal {K}$ isso é
   

   $$

   $$h (x) = \ begin {cases} 0, & x \ in \ mathcal {K}, \\ + \ infty, & x \ notin \ mathcal {K}. \\ \ end {cases}$$
   
   Neste caso $$$prox _ {\ alpha_kh} (x)$ É uma projeção no aparelho $$$\ mathcal {K}$ , ou seja, "o mais próximo $$$x$ ponto de ajuste $$$\ mathcal {K}$ " Assim, restringimos a descida do gradiente apenas ao conjunto $$$\ mathcal {K}$ , o que nos permite resolver problemas com restrições. Infelizmente, o cálculo da projeção no caso geral pode ser ainda mais difícil, portanto esse método é geralmente usado se as restrições forem simples, por exemplo, as chamadas restrições de caixa: para cada coordenada
   

   $$

   $$l_i \ leq x_i \ leq r_i$$
   
   
2. $$$h (x) = \ lambda \ | x \ | _1 = \ lambda \ sum_ {i = 1} ^ n | x_i |$ - $$$\ ell_1$ -regularização. Eles gostam de adicionar esse termo a problemas de otimização no aprendizado de máquina para evitar a reciclagem. A regularização desse tipo também tende a anular os componentes menos significativos. Para essa função, o operador proximal tem a forma (uma expressão para uma única coordenada é descrita abaixo):
   

   $$

   $$[prox _ {\ alpha h} (x)] _ i = \ begin {cases} x_i- \ alpha, & x_i> \ alpha, \\ x_i + \ alpha, e x_i <- \ alpha, \\ 0 e x_i \ em [- \ alpha, \ alpha], \ end {cases}$$
   
   o que é bem fácil de calcular.

Conclusão

Isso encerra as principais variações do método gradiente conhecidas por mim. Talvez, no final, notei que todas essas modificações (exceto talvez o método do gradiente conjugado) podem interagir facilmente entre si. Eu deliberadamente não incluí o método de Newton e os métodos quase-Newton (BFGS e outros) nesta lista: embora eles usem um gradiente, são métodos mais complexos e exigem cálculos adicionais específicos, que geralmente são mais caros do que calcular um gradiente. No entanto, se este texto estiver em demanda, terei prazer em fazer uma revisão semelhante sobre eles.

Literatura usada / recomendada

Boyd. S, Vandenberghe L. Otimização convexa
Shewchuk JR Uma Introdução ao Método do Gradiente Conjugado Sem Dor Agonizante
Teoria de otimização convexa da Bertsekas DP

Nesterov Yu. E. Métodos de otimização convexos
Gasnikov A.V. Descida de gradiente universal