Please use this identifier to cite or link to this item:
https://hdl.handle.net/1822/36413
Title: | Programação não linear inteira mista e não convexa sem derivadas |
Other titles: | Nonconvex and derivative-free mixed integer nonlinear programming |
Author(s): | Fernandes, Florbela Alexandra Pires |
Advisor(s): | Costa, Maria Fernanda Pires da Fernandes, Edite Manuela da G. P. |
Issue date: | 19-Feb-2015 |
Abstract(s): | Vários problemas da área do planeamento de processos de engenharia são modelados como problemas de programação não linear inteira mista (PNLIM), em
que as variáveis de decisão são contínuas e inteiras. Nos processos mais complexos, as funções envolvidas no problema, nomeadamente a função objetivo e as
funções de restrição, são não convexas e eventualmente não suaves. Este tipo de
problemas de otimização são difíceis de resolver e são o foco principal desta tese.
Assim, o objetivo principal deste estudo é desenvolver algoritmos eficazes que
não exijam o cálculo de derivadas e sejam capazes de convergir para as soluções
de problemas de PNLIM não convexos. Duas abordagens diferentes são propostas
para a resolução de problemas de PNLIM. Uma, é uma técnica híbrida de partição
e avaliação (BB) uma vez que combina o paradigma BB com uma estratégia
estocástica de otimização do tipo de iniciação múltipla, de tal forma que seja
garantida com probabilidade um a convergência para uma solução global de um
problema de relaxação contínua de programação não linear (PNL). O método,
conotado BBMCSFilter, conta com um algoritmo de procura sobre as coordenadas
baseado no método dos filtros para convergir para minimizantes, a partir de um
qualquer ponto retirado do espaço de procura. A segunda abordagem, designada
por MS+m-HJ-f, faz uma extensão da estratégia de iniciação múltipla para poder
tratar simultaneamente as variáveis contínuas e inteiras. O método de procura
direta Hooke-and-Jeeves é modificado por forma a manusear variáveis inteiras
mistas e tratar restrições de desigualdade e igualdade pelo método dos filtros. Este
método também foi desenvolvido com o objetivo de calcular múltiplas soluções
de problemas de PNLIM.
As experiências numéricas realizadas com as novas abordagens mostram que
os algoritmos propostos são eficazes. Foram obtidas soluções de qualidade mais
elevada com velocidades de convergência, em termos de avaliações das funções e
do tempo de computação, ligeiramente superiores quando comparadas com outras
técnicas disponíveis na literatura. Several problems in engineering process design are modeled as mixed-integer nonlinear programming (MINLP) problems, where the decision variables are continuous and integer. In the most complex processes, the involved functions, namely the objective and the constraint functions, are non-convex and eventually non-smooth. This type of optimization problems are difficult to solve and are the main focus of this thesis. Thus, the main goal of this study is to develop effective algorithms that do not require derivative information and are capable of converging to the solutions of non-convex MINLP problems. Two different approaches are proposed for MINLP. One is a hybrid branch and bound (BB) technique in the sense that combines the BB paradigm with a stochastic optimization multistart strategy, so that convergence to a global solution of a nonlinear programming (NLP) continuous relaxation problem is guaranteed with probability one. The method, coined BBMCSFilter, relies on a coordinate search filter-based algorithm to converge to minimizers, from any sampled point in the search space. The second approach, denoted by MS+m-HJ-f, extends the multistart strategy to be able to handle continuous and integer variables simultaneously. The direct search Hooke-and-Jeeves method is modified in order to address mixed integer variables and to handle inequality and equality constraints by the filter method. This method has also been designed to determine multiple solutions to MINLP problems. Numerical experiments carried out with these new approaches show that the proposed algorithms are effective. Higher quality solutions with convergence speed, in terms of function evaluations and computation time, slightly superior are obtained when compared with other techniques available in the literature. |
Type: | Doctoral thesis |
Description: | Tese de Doutoramento em Ciências (área de especialização em Matemática). |
URI: | https://hdl.handle.net/1822/36413 |
Access: | Open access |
Appears in Collections: | DMA - Teses de doutoramento |