Universidade do Minho Escola de Ciências Florbela Alexandra Pires Fernandes Programação Não Linear Inteira Mista e Não Convexa Sem Derivadas Tese de Doutoramento em Ciências, especialidade de Matemática Trabalho efetuado sob a orientação de Professora Doutora Maria Fernanda Pires da Costa Professora Doutora Edite Manuela da Graça P. Fernandes Novembro de 2014 Agradecimentos Este percurso que foi tão meu e tão pessoal foi também de outras pessoas que, voluntária ou involuntariamente, o partilharam comigo. São essas pessoas que merecem, agora, a minha atenção. Primeiro, gostaria de agradecer às minhas orientadoras, a Professora Doutora Fernanda Costa e a Professora Doutora Edite Fernandes. Foram, sem dúvida alguma, inexcedíveis em tudo o que é possível imaginar. Além do profundo co￿ nhecimento na área com que me presentearam ao longo destes anos e do qual tentei assimilar o máximo, não posso esquecer o apoio, a força, o incentivo e também o carinho que me deram durante este processo. Sem eles eu não estaria (hoje) a escrever este “Obrigada!”. Aos meus amigos. Os meus amigos foram muito importantes nesta fase. Todos eles, cada um à sua maneira, contribuíram para eu trilhar o meu caminho de forma menos trágica e mais serena. Desde as conversas mais técnicas, que a poucos interessavam... Até às conversas mais banais, às duas horas da manhã, enquanto bebíamos chá... Todos esses momentos foram importantes para manter o meu norte. Ao Instituto Politécnico de Bragança pela atribuição da bolsa PROTEC com referência SFRH/PROTEC/67895/2010 e, em particular, à direção da ESTiG por me proporcionar condições de trabalho adequadas ao bom desenvolvimento dos meus trabalhos de doutoramento. Um agradecimento particular ao colega José Rufino pela sua ajuda relativamente às condições de trabalho “informáticas” v vi que necessitei ao longo dos últimos anos da tese. Por último, à minha família. Ao meu pai e ao Helder. Prevalece ao longo dos tempos o amor, o carinho, as palavras não ditas, a saudade, a imensa saudade que não tem fim... Aos meus pais agradeço a educação que me deram e os valores e princípios que me transmitiram; aos meus irmãos, um enorme obrigada, pois foram incansáveis no apoio incondicional, no carinho e na paciência que tiveram comigo. Assim, mãe, Lila, Rui, Ana, Sofia e Andrey obrigada por me ajudarem a ser feliz. Para a Ana e a Sofia um sorriso especial, pois são as estrelinhas da família! Resumo Programação Não Linear Inteira Mista e Não Convexa Sem Derivadas Vários problemas da área do planeamento de processos de engenharia são mo￿ delados 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 comple￿ xos, 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 paraaresoluçãodeproblemasdePNLIM.Uma, éumatécnicahíbridadepartiçã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, conotadoBBMCSFilter,contacomumalgoritmodeprocurasobreascoordenadas 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 vii viii mistasetratarrestriçõesdedesigualdadeeigualdadepelométododosfiltros. 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 dotempodecomputação, ligeiramentesuperioresquandocomparadascomoutras técnicas disponíveis na literatura. Abstract Nonconvex and Derivative-free Mixed Integer Nonlinear Programming Several problems in engineering process design are modeled as mixed-integer nonlinear programming (MINLP) problems, where the decision variables are con￿ tinuous and integer. In the most complex processes, the involved functions, na￿ mely 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 soluti￿ ons 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) continu￿ ous 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. ix x 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.