Tópicos Especiais em Pesquisa Operacional

Região de Confiança e Modelos

Região de Confiança

É importante dizer que os Métodos de Região de Confiança constituem uma classe de métodos de otimização restrita e irrestrita e nos últimos 20 anos o desenvolvimento desses métodos têm se tornado cada vez maior.

Vale lembrar que esses métodos também são usados no contexto com derivadas, aliás, iremos primeiramente discutir a filosofia dos métodos de região de confi-ança com derivadas para podermos compreender os métodos sem derivada.

Nosso objetivo é tentar entender e discutir quais as vantagens desse método e daremos ênfase no papel do modelo da função objetivo.

2 Trust_Region.nb

Região de Confiança × Busca LinearOs métodos iterativos mais clássicos de minimização irrestrita, alguns deles vistos em Programação Não-Linear, são os métodos de busca linear, onde dado um ponto inicial, calculamos uma direção de descida e um tamanho de passo, como por exemplo o Método de Máxima Descida (Passo de Cauchy), Método de Newton e Métodos Quase-Newton.

CurvasdeNível

Trust_Region.nb 3

Os métodos de região de confiança, por sua vez, vão construir um modelo para a função objetivo e primeiro vão estabelecer o tamanho máximo de passo a ser andado, ou seja, o raio da região de confiança e depois vão calcular a direção, resolvendo o subproblema de minimizar o modelo sujeito a região de confiança.Alguns elementos presentes numa iteração de um método de região de confiança:

4 Trust_Region.nb

ModelosNos método de região de confiança definimos um modelo para função objetivo a partir de um ponto corrente xk e estabelecemos uma bola fechada centrada em xk e com raio Δk. Essa vizinhança em torno de xk é chamada de região de confi-ança, pois nessa região podemos confiar que o modelo gera uma boa aproxi-mação para a função objetivo.

O modelo mais simples possível é o linear, que geometricamente falando é ohiperplano tangente à superfície gráfico da função objetivo no ponto corrente. Porém, esse não é o modelo mais eficiente, uma vez que o hiperplano não con-segue “capturar” a curvatura da função, ou seja, o modelo só consegue represen-tar bem a função numa vizinhança muito próxima do ponto corrente.

Em geral, o modelo quadrático é o mais utilizado, pois é o modelo mais simplescapaz de aproximar a curvatura da função objetivo.

Construindo o modelo

Ainda pensando no contexto com derivadas, a melhor forma de se obter o mod-elo é utilizando o Polinômio de Taylor de ordem 2, que é caracterizado da seguinte maneira:

mkxk = f xk + ▽ f xk

Tx - xk + 1

2 x - xk ▽2 f xk x - xk

Trust_Region.nb 5

ModeloLinear ModeloQuadrático

6 Trust_Region.nb

modelfunctioncontours linearmodelcontours

Trust_Region.nb 7

Verificando a ReduçãoA cada iteração do método podemos atualizar, ou não, o raio Δk da região de confiança. Isso irá depender se o passo dado gera, ou não, uma boa redução no valor da função objetivo. Note que temos que levar em consideração dois fatores para avaliar a redução:

1. se a região de confiança de fato é uma região em que podemos confiar no modelo (até mesmo utilizando o polinômio de Taylor, sabemos que quanto mais longe se está do ponto corrente, maior será o erro de aproximação do modelo), então se for o caso, precisamos diminuir o raio da região de confiança para obter uma aproximação melhor;

2. se o minimizador encontrado é de fato o minimizador do modelo, pois ao resolver o subproblema sujeito à região de confiança, pode acontecer que o minimizador irrestrito do modelo não esteja no interior da região de confiança e então o minimizador restrito do modelo estará na fronteira da região de confiança. Veja que pode ocorrer do minimizador restrito encontrado proporcionar uma boa redução na função objetivo. Nesse caso podemos ser mais ousados e aumentar o raio da região de confiança para a iteração seguinte.

8 Trust_Region.nb

Verificando a ReduçãoPara analisarmos a redução da função objetivo vamos definir ared como sendo a redução real da função objetivo (actual reduction) e a pred como sendo a redução predita pelo modelo (predicted reduction) e a razão entre elas, ρ, da seguinte maneira:

ared= f xk- f (x),

pred=mkxk-mk(x) e

ρ = ared

pred

Trust_Region.nb 9

Algoritmo

10 Trust_Region.nb

Vantagens1. Estamos sempre minimizando um modelo quadrático, gradiente e hessiana são

muito simples de calcular.

2. Esse fato é o que vai fazer toda a diferença quando estudarmos o caso SEM DERIVADAS.

3. Pode ser convertido em um problema escalar (unidimensional)

Desvantagens1. Resolve o subproblema de forma iterativa.

Trust_Region.nb 11

Região de Confiança SEM DerivadasAgora, pensando que não temos mais gradiente e hessiana disponíveis pre-cisamos pensar em uma nova forma de construirmos o modelo para aproximar a função objetivo, e uma boa forma de fazermos isso é via interpolação.

mkxk = f xk + x - xk

T

g1

g2 +

12x - xk

T.h11 h12

h21 h22.x - xk

g = g1

g2 H =

h11 h12

h21 h22

12 Trust_Region.nb

Relembrando a aula passada...

INTERPOLAÇÃO POLINOMIALE

POSICIONAMENTO DOS PONTOS

Trust_Region.nb 13

Modelo interpoladormodelointerpolado

14 Trust_Region.nb

In[256]:= modelointerpoladocontours

Out[256]=

Trust_Region.nb 15

Contexto HistóricoO primeiro artigo nesta área parece ser o de Levenberg [7], em 1944, que consid-era a adição de um múltiplo da identidade à matriz hessiana como um procedi-mento de estabilização/amortecimento no contexto da solução de problemas não lineares de mínimos quadrados.

Essa ideia foi desenvolvida ainda mais (e aparentemente de forma indepen-dente) por Morrison [10], em 1960, em um artigo raramente mencionado sobre rastreamento de trajetória, em que a convergência do algoritmo de estimativa é aprimorada ao minimizar um modelo quadrático da função objetiva de mínimos quadrados em uma esfera de raio constante.

Morrison provou que a solução de um sistema linear envolvendo a hessiana domodelo aumentado por um múltiplo da matriz de identidade produz a solução do subproblema resultante para uma escolha adequada do parâmetro de amortecimento associado e também que a diminuição do modelo previsto é monótona neste parâmetro.

16 Trust_Region.nb

Contexto HistóricoUma técnica com base na decomposição do autovalor é dado para calcular o mínimo do modelo dentro a esfera escolhida. A mesma ideia fundamental é encontrada no celebrado artigo (que foi considerado o mais citado no ano de 92,

na Science Citation Index 1945-1988) de Marquardt [8] de 1963, que, novamente

de forma independente, apontou o vínculo entre amortecimento da hessiana e reduzindo o comprimento do passo e também provouque a minimização de um modelo amortecido corresponde a minimizar o mod-elo original em uma região restrita.

Os três artigos fazem a observação de que a hessiana pode ser aproximada, o que em seguida, produz um modelo quadrático da função objetivo. Outro con-ceito importante, apresentado em 1961 por Griffith and Stewart [6], e aparente-mente, desconhecendo os trabalhos anteriores, foi a ideia de minimizar sucessi-vamente os modelos da função objetivo (com restrições) em uma região ao redor do iterado atual. No entanto, eles não propõem ajustar o tamanho da região de confiança, mas sim mantê-lo constante ao longo dos cálculos.

Trust_Region.nb 17

Contexto HistóricoUm passo crucial foi feito em 1966 por Goldfeld, Quandt and Trotter [5], que apresentaram um procedimento explícito de atualização para o passo máximo. Se eles viram esse parâmetro como amortecimento da hessiana, o que induz uma restrição do passo, ou como uma restrição para o passo calculada por amortecimento da hessiana não é inteiramente clara no artigo. No entanto, o procedimento de atualização é realmente muito semelhante ao que usamos atualmente.

Em particular, eles introduzem a noção de “achieved versus predicted change”.

Não há dúvida de que a contribuição realmente preparou o cenário para méto-dos de região de confiança na forma que conhecemos hoje. Muito notavelmente, seu artigo não cita nenhuma das contribuições anteriores de Levenberg, Mar-quardt, Morrison ou Griffith and Stewart.

18 Trust_Region.nb

Contexto HistóricoO conceito de região de confiança foi defendido por Powell [14], em 1970, como uma ferramenta para garantir a convergência de um método para otimização sem restrições, onde a fórmula de quase Newton Powell-symmetric-Broyden (PSB) foi usada para construir a hessiana de um modelo quadrático. Powell refere-se a Marquardt como a inspiração para sua proposta. O artigo inédito de Fletcher [3], de 1970, segue as mesmas linhas. Nestas contribuições, o procedi-mento de atualização está claramente focado no raio da região de confiança.

Note-se também a proposta independente de Winfield [18, 19], respectivamente em 1969 e 1973, cuja tese de Harvard de 1965-1969 considerou o uso de uma região de confiança simples, mas claro, mecanismo usando um modelo quadrático no contexto da minimização da função por interpolação em uma tabela de dados.

Trust_Region.nb 19

Contexto HistóricoA partir de 1970, houve uma proliferação de resultados e ideias sobre o assunto. O nome de região de confiança não foi mencionado por Powell [13] em seu artigo, nem por nenhum de seus antecessores. Parece que a primeira aparição oficial dos termos “região de confiança”e “Passo de Cauchy”estava em Dennis

[2] de 1978 e antes disso extraoficialmente em um curso que ele ensinou no US

National Bureau of Economic Research (NBER), pouco depois de ouvir Powell

falar sobre sua técnica para resolver equações não-lineares.

No entanto, esta terminologia não se difundiu a comunidade de pesquisa por vários anos. Por exemplo, em 1973 Winfield [19] fala sobre uma região de vali-dade para um modelo quadrático, em 1980 Fletcher [4] usa o termo método do passo restrito para indicar que a etapa é restrita a uma determinada região cen-trada no iterado atual, e em 1981 Toint [17] se refere a uma região confiável. A excelente pesquisa de Moré [11], de 1973, influenciou na padronização da termi-nologia. O artigo de Powell [14], em 1970, provou convergência global para seu algoritmo de região de confiança.

Mais informações em sobre os métodos sem derivadas podem ser encontrados em [15], [16] e [12] e para mais informações sobre o método de região de confi-ança ver [9].

20 Trust_Region.nb

Referências Bibliográficas[1] A. R. Conn, N. I. M. Gould, and P. L. Toint. Trust region methods. SIAM, Philadelphia, 2000. URL https://doi.org/10.1137/1.9780898719857.

[2] J. E. Dennis, Jr. A brief introduction to quasi-Newton methods. Numerical

analysis, 22:19–52, 1978. URL http://hdl.handle.net/1813/7448.

[3] R. Fletcher. An efficient, globally convergent, algorithm for unconstrained and linearly constrained optimization problems. Technical Repor 431, AERE Harwell Laboratory, Harwell, Oxfordshire, England, 1970.

[4] R. Fletcher. Practical Methods of Optimization, Volume 1: Unconstrained

Optimization. John Wiley & Sons, Chichester, England, 1980.

[5] S. M. Goldfeld, R. E. Quandt, and H. F. Trotter. Maximization by quadratic hill-climbing. Econometrica: Journal of the Econometric Society, 34(3):541–551, 1966.

Trust_Region.nb 21

Referências Bibliográficas[6] R. E. Griffith and R. A. Stewart. A Nonlinear Programming Technique for the Optimization of Continuous Processing Systems. Management Science, 7(4):379–392, 1961. doi: https://doi.org/10.1287/mnsc.7.4.379.

[7] K. Levenberg. A method for the solution of certain non-linear problems in least squares. Quarterly Journal on Applied Mathematics, 2(2):164–168, 1944. URL http://www.jstor.org/stable/43633451.

[8] D. W. Marquardt. An algorithm for least-squares estimation of nonlinear parameters. Journal of the society for Industrial and Apple Mathematics, 11(2):431–441, 1963. doi: https://doi.org/10.1137/0111030.

[9] J. C. A. Medeiros and S. A. Santos. Estudo de um método baseado em autoval-ores generalizados para o subproblema de região de confiança. 2018. URL: http-s://www.ime.unicamp.br/~ra149233/IC/Parcial.pdf.

22 Trust_Region.nb

Referências Bibliográficas[10] D. D. Morrison. Methods for nonlinear least squares problems and conver-gence proofs. Technical Report 19690071284, Space Technology Labs., Inc., Los Angeles, CA, United States, 1960. URL https://ntrs.nasa.gov-/search.jsp?R=19690071284.

[11] J. J. Moré. Recent developments in algorithms and software for trust region methods. In Mathematical programming The state of the art, pages 258–287. Springer, Berlin, 1983.

[12] I. X. M. d. Nascimento e S. A. Santos. Otimização sem derivadas : sobre a construção e a qualidade de modelos quadráticos na solução de problemas irrestritos. Dissertação de Mestrado em Matemática Aplicada, Universidade Estadual de Campinas (UNICAMP), Campinas, 2014. URL http://repositorio.u-nicamp.br/jspui/handle/REPOSIP/306528.

[13] M. J. D. Powell. A Fortran subroutine for solving systems of nonlinear alge-braic equations. Numerical methods for nonlinear algebraic equations, pages 115–161, 1970.

[14] M. J. D. Powell. A new algorithm for unconstrained optimization. In Nonlin-

ear programming, pages 31–65. Academic Press, London, 1970.

[15] M. J. D. Powell. On trust region methods for unconstrained minimization without derivatives. Mathematical programming, 97(3):605–623, 2003. URL https://link.springer.com/article/10.1007/s10107-003-0430-6.

Trust_Region.nb 23

Referências Bibliográficas[16] M. J. D. Powell. On the use of quadratic models in unconstrained minimiza-tion without derivatives. Technical Report DAMTP 2003/NA03, University of Minnesota Digital Conservancy, Cambridge, 2003. URL http://www.damtp.-cam.ac.uk/user/na/NA_papers/.

[17] P. L. Toint. Towards an efficient sparsity exploiting Newton method for minimization. In Sparse Matrices and Their Uses, pages 57–88. Academic Press, 1981. Publication editors : I.S. Duff.

[18] D. Winfield. Function and functional optimization by interpolation in data

tables. Ph.D. thesis, Harvard University, Cambridge, MA, USA, 1969. URL http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.839.5049&rep=rep1&type=pdf.

[19] D. Winfield. Function minimization by interpolation in a data table. Jour-

nal of the Institute of Mathematics and Its Applications, 12(3):339–347, 1973. doi: https://doi.org/10.1093/imamat/12.3.339.

24 Trust_Region.nb