Compreendendo as condições de Wolfe para uma pesquisa de linha inexata

12

De acordo com a Otimização Numérica do Livro de Nocedal & Wright (2006), as condições de Wolfe para uma busca inexata de linhas são, para uma direção de descida ,p

Diminuição suficiente: Condição de curvatura: paraf ( x + α p ) T p c 2f ( x ) T p 0 < c 1 < c 2 < 1f(x+αp)f(x)+c1αkf(x)Tp
f(x+αp)Tpc2f(x)Tp
0<c1<c2<1

Eu posso ver como a condição de diminuição suficiente afirma que o valor da função no novo ponto deve estar abaixo da tangente em . Mas não tenho certeza do que a condição da curvatura está me dizendo geometricamente. Além disso, por que a relação ser imposta? O que isso faz, geometricamente?x c 1 < c 2x+αpxc1<c2

Paulo
fonte

Respostas:

12

A condição de curvatura diz essencialmente o seguinte: Sabemos que (porque é uma direção de descida). Então, na direção , ela vai ladeira abaixo. Agora, estamos procurando um mínimo, ou seja, um ponto em que . Isso significa que não queremos aceitar comprimentos de passo onde o gradiente na direção , ou seja, ainda é tão negativo quanto em x. Em vez disso, queremos parar em um local em que o gradiente seja menos negativo ou até positivo.f(x)p<0ppf=0x+αppf(x+αp)p

Como o lado direito da condição de curvatura é negativo, uma variante comum da condição é exigirque eu costumo achar mais fácil de entender.

|f(x+αp)p|c2|f(x)p|

Compreender isso permitirá que você construa facilmente casos em que você não pode satisfazer ambas as condições, a menos que .c1<c2

Wolfgang Bangerth
fonte
Então, não importa o que lisa função I escolher, estabelecendo irá resultar em uma diminuição suficiente ou condição curvatura não estar satisfeito? fc2<c1
Paul
1
Não, o contrário. Se você escolher , existem funções que uma das duas condições não é satisfeita, mesmo que você tenha uma direção de descida. Nesse caso, a pesquisa de linhas não encontraria um comprimento de etapa. f ( x )c2<c1f(x)
Wolfgang Bangerth