Efficient stochastic optimization through variance reduction techniques and thorough assessment of high-dimensional spaces
Carregando...
Arquivos
Data
Autor(es)
Título da Revista
ISSN da Revista
Título de Volume
Editor
Universidade Federal de Minas Gerais
Descrição
Tipo
Tese de doutorado
Título alternativo
Otimização estocástica eficiente por meio de técnicas de redução de variância e avaliação completa de espaços de alta dimensão
Primeiro orientador
Membros da banca
Reinaldo Castro Souza
Alexandre Salles da Cunha
Maurício Cardoso de Souza
Alexandre Salles da Cunha
Maurício Cardoso de Souza
Resumo
Stochastic optimization is a fertile and exciting area of research. These methods aim at
finding optimal or near optimal solutions of problems for which uncertainty cannot be
neglected. Stochastic optimization can be used to model a vast range of problems, such as
power system, maintenance, chemical industry, decision support, geosciences, health care,
supply chain, risk management and queuing system. In spite of its wide applicability,
current literature indicates a clear demand for efficient techniques that can handle largescale and more complex problems. We address (i) the issue of model dependence at
practitioners choice on input parameters which can lead to poor models; (ii) we explore
potentials of variance reduction techniques to increase efficiency of Monte Carlo simulation
embedded in algorithms; (iii) and we investigate high-dimensional optimization problems.
To position this research on the current literature, we offer a comprehensive survey on
stochastic optimization methods. In particular, we introduce the main features of each
method, their most commonly used techniques, their benefits and limitations, explore
current research trends, and discuss some gaps yet to be investigated. Then we offer
three interrelated contributions. First, a novel Metamodeling framework based on vontrol
variates is presented. The main contribution is to propose a metamodel formulation which
is, at the same time, computationally efficient and flexible enough so that it can be applied
to large class of problems, characterized by different shapes of objective function and
uncertainty behavior (variance). We remark the proposed formulation is less dependent
on practitioners choice on input parameters than the current available metamodels. Our
second contribution is to propose a procedure via control variates to improve the efficiency
of a random search method in finding optimal values. The novelty of our hybrid procedure
is to use the output of already sampled points to guide a reduction of variance of the new
sampled points. We remark that the proposed procedure is generic in the sense that it can
be applied to a larger set of stochastic optimization methods. Finally, we take a deep dive
into optimization in high-dimensional space. We derive properties of high-dimensional
space to guide the design of more sophisticated stochastic optimization methods that can
efficiently handle the dimensionality increase that characterize real applications.
Abstract
Otimização estocástica é uma área de pesquisa fértil e entusiástica. Seus métodos buscam
soluções ótimas ou quase ótimas de problemas em que a incerteza não pode ser negligenciada. A otimização estocástica pode ser utilizada para modelar uma vasta gama de
problemas, como sistemas de energia, manutenção, indústria química, suporte a tomada
de decisão, geociências, saúde, cadeias de suprimentos, gestão de risco e gestão de filas.
A despeito de sua abrangente aplicabilidade, a literatura atual indica uma demanda clara
por t´ecnicas mais eficientes que possam lidar com problemas mais complexos e de larga
escala. N´os abordamos (i) a questão da dependência dos modelos em escolhas de usuários
sobre parâmetros de entrada, que podem levar a modelagens ruins; (ii) exploramos o potencial de técnicas de redução de variância para aumentar a eficiência da simulação de
Monte Carlo embutida nos algoritmos; (iii) e investigamos problemas de otimização em
grandes dimensões. Para posicionar esta pesquisa na literatura atual, oferecemos uma
revisão abrangente sobre métodos de otimização estocástica. Em particular, introduzimos
as principais características de cada método, suas técnicas mais utilizadas, seus benefícios
e limitações, as tendências atuais de pesquisa, e discutimos algumas lacunas ainda a serem
investigadas. Em seguida, oferecemos três contribuições inter-relacionadas. Primeiro, um
novo modelo de Metamodeling baseado em control variates é apresentado. A principal
contribuição ´e propor uma formulação de metamodelo que ´e, ao mesmo tempo, computacionalmente eficiente e flexível o suficiente para possibilitar aplicação a uma ampla classe
de problemas, com diferentes formatos da função objetivo e de comportamentos de incerteza (variância). A formulação proposta ´e menos dependente de parâmetros de entrada
que os atuais metamodelos disponíveis. Nossa segunda contribuição ´e propor um procedimento via control variates para melhorar a eficiência de um método de busca aleatória. A
novidade deste nosso procedimento híbrido ´e usar as saídas de pontos já amostrados para
guiar a redução de variância em pontos a serem amostrados. O procedimento proposto ´e
genérico no sentido de que pode ser aplicado a um conjunto mais amplo de métodos de
otimização estocástica. Finalmente, mergulhamos em espaços de grandes dimensões para
possibilitar o desenvolvimento de métodos de otimização estocástica mais sofisticados que
possam lidar eficientemente com o aumento dimensional que caracteriza aplicações reais.
Assunto
Engenharia de produção, Método de Monte Carlo
Palavras-chave
Otimização estocástica, Manutenção, Indústria química