Orientador: Maria Aparecida Diniz Ehrhardt / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica / Made available in DSpace on 2018-08-18T12:52:22Z (GMT). No. of bitstreams: 1 Detsch_DeniseTrevisoli_M.pdf: 1081241 bytes, checksum: c29e7e81ee2ecb8467802991fc75be51 (MD5) Previous issue date: 2011 / Resumo: Este trabalho teve como foco o estudo de problemas SOCP, tanto nos seus aspectos teóricos quanto nos seus aspectos práticos. Problemas SOCP são problemas convexos de otimização nos quais uma função linear 'e minimizada sobre restrições lineares e restrições de cone quadrático. Tivemos dois objetivos principais: estudar o conceito, as aplicações e os métodos de resolução de problemas SOCP, permitindo verificar a viabilidade de trabalhar com tais problemas; e verificar na prática o benefício de se utilizar uma ferramenta específica de SOCP para a resolução de problemas que se enquadram nessa classe. Para a avaliação prática utilizamos um software de otimização genérica (fmincon) e outro específico de SOCP (CVXOPT). A análise ficou concentrada nos requisitos robustez, número de iterações e variação do tempo com o aumento da dimensão dos problemas. Diante dos resultados obtidos com os testes numéricos, pudemos concluir que 'e interessante usar SOCP sempre que possível / Abstract: This dissertation focuses on the study of SOCP problems, both in its theoretical, and in its practical aspects. SOCP problems are convex optimization problems in which a linear function is minimized over linear constraints and second-order cone constraints. We had two main objectives: study the concept, applications and methods for solving the SOCP problem, making it possible to verify the feasibility of working with such problems; and to verify the practical benefits of using a SOCP specific tool for the resolution of problems of this class. The experimental evaluation used a generic optimization software (fmincon) and other SOCP specific software (CVXOPT). The analysis was concentrated on the robustness, number of iterations and time variation with the increasing scale of the problems. From results obtained with the numerical tests, we concluded that SOCP is worth to be used whenever possible / Mestrado / Matematica Aplicada / Mestre em Matemática Aplicada

Orientador: Jose Mario Martinez / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-07-24T02:48:23Z (GMT). No. of bitstreams: 1 Birgin_ErnestoJulianGoldberg_D.pdf: 2665146 bytes, checksum: 6df0c6f9063d1f9674681fe6c064cb8d (MD5) Previous issue date: 1998 / Resumo: Não informado / Abstract: Not informed / Doutorado / Doutor em Matemática Aplicada

No presente trabalho, estudamos e desenvolvemos algoritmos com análise de complexidade de avaliação de pior caso para problemas de programação não linear. Para minimização irrestrita, estabelecemos dois algoritmos semelhantes que exploram modelos de ordem superior com estratégia de regularização. Propusemos uma implementação computacional que preserva as boas propriedades teóricas de complexidade, e fizemos experimentos numéricas com problemas clássicos da literatura, a fim de atestar a implementação e avaliar a aplicabilidade de métodos que empreguem modelos de ordem superior. Para minimização com restrições, estabelecemos um algoritmo de duas fases que converge a pontos que satisfazem condições de otimalidade de primeira ordem não escaladas para o problema de programação não linear. / In the present work, we have studied and developed algorithms with worst-case evaluation complexity analysis for nonlinear programming problems. For the unconstrained optimization case, we have established two similar algorithms that explore high-order regularization models. We have proposed a computational implementation that preserves the good properties of the evaluation complexity theory, and we made numerical experiments with classical problems from the literature, in order to check the implementation and certify the practical applicability of methods that employ high-order models. For the constrained optimization case, we have established a two phases algorithm that converges to points that meet the unscaled first-order optimality condition for the nonlinear programming problem.

Orientador: Marcos Julio Rider Flores / Banca: Ruben Augusto Romero Lazaro / Banca: José Roberto Sanches Mantovani / Banca: Antonio César Baleeiro Alves / Banca: Geraldo Roberto Martins da Costa / Resumo: Neste trabalho foi desenvolvida uma estratégia de resolução de problemas de otimização em sistemas de distribuição de energia elétrica que são modelados como problemas de programação não linear inteira mista (PNLIM), através da teoria de programação cônica de segunda ordem (PCSO) com variáveis inteiras e contínuas (PCSOIM). Apesar dos modelos de PNLIM e de PCSOIM, não serem problemas de otimização equivalentes, foi provado que é possível garantir, mediante algumas condições, que a solução encontrada pelo modelo de PCSOIM é a solução ótima para o problema de PNLIM. A estratégia traçada nesta tese permite a substituição de alguns problemas de PNLIM, com região de busca não convexa, de difícil resolução, de grande porte, e sem garantia de ótimo global; por problemas de PCSOIM que possuem formulação convexa, com solução ótima garantida pelo solver comercial robusto. Os modelos foram implementados em linguagem AMPL e foram utilizados os solvers CPLEX e KNITRO para a resolução. A metodologia proposta foi avaliada para os seguintes problemas de otimização em sistemas de distribuição de energia elétrica: reconfiguração de sistemas de distribuição, análise de sistemas de distribuição com geração distribuída, operação ótima e alocação ótima de banco de capacitores e reguladores de tensão e operação ótima de dispositivos de armazenamento de energia em sistemas com fontes renováveis. Os sistemas testados foram os de 3, 11, 33, 42, 70, 136, 202 e de 400 nós / Abstract: In this work it is presented a strategy for solving optimization problems in power distribution systems that are modeled as mixed integer nonlinear programming (MINLP) problems, through the theory of second-order cone programming (SOCP) with integer and continuous variables (MISOCP). Despite MINLP models and MISOCP optimization problems are not equivalent, it was proven that it is possible to guarantee, through some conditions, that the solution found by the MISOCP model is the optimal solution to the MINLP problem. The strategy outlined in this thesis, allows the replacement of some MINLP problems, with a non- convex region of search, difficult to solve, large, and with no guarantee of global optimal convergence, by MISOCP problems that have convex formulation, for which optimal solution convergence can be ensured by robust commercial solvers. The models were implemented in AMPL language and solved by CPLEX and KNITRO. The proposed methodology was evaluated for the following distribution problems: reconfiguration of distribution systems, analysis of distribution systems with distributed generation, optimal operation and optimal allocation of capacitor banks and voltage regulators and optimal operation of energy storage devices in networks with renewable energy sources. The 3, 11, 33, 42, 70, 136, 202 and 400 bus systems were tested / Doutor

Problemas com múltiplos objetivos são muito frequentes nas áreas de Otimização, Economia, Finanças, Transportes, Engenharia e várias outras. Como os objetivos são, geralmente, conflitantes, faz-se necessário o uso de técnicas apropriadas para obter boas soluções. A área que trata de problemas deste tipo é chamada de Otimização Multiobjetivo. Neste trabalho, estudamos os problemas dessa área e alguns dos métodos existentes para resolvê-los. Primeiramente, alguns conceitos relacionados ao conjunto de soluções são definidos, como o de eficiência, no intuito de entender o que seria a melhor solução para este tipo de problema. Em seguida, apresentamos algumas condições de otimalidade de primeira ordem, incluindo as do tipo Fritz John para problemas de Otimização Multiobjetivo. Discutimos ainda sobre algumas condições de regularidade e total regularidade, as quais desempenham o mesmo papel das condições de qualificação em Programação Não-Linear, propiciando a estrita positividade dos multiplicadores de Lagrange associados às funções objetivo. Posteriormente, alguns dos métodos existentes para resolver problemas de Otimização Multiobjetivo são descritos e comparados entre si. Ao final, aplicamos a teoria e métodos de Otimização Multiobjetivo nas áreas de Compressed Sensing e Otimização de Portfolio. Exibimos então testes computacionais realizados com alguns dos métodos discutidos envolvendo problemas de Otimização de Portfolio e fazemos uma análise dos resultados. / Problems with multiple objectives are very frequent in areas such as Optimization, Economy, Finance, Transportation, Engineering and many others. Since the objectives are usually conflicting, there is a need for appropriate techniques to obtain good solutions. The area that deals with problems of this type is called Multiobjective Optimization. The aim of this work is to study the problems of such area and some of the methods available to solve them. Firstly, some basic concepts related to the feasible set are defined, for instance, efficiency, in order to comprehend which solution could be the best for this kind of problem. Secondly, we present some first-order optimality conditions, including the Fritz John ones for Multiobjective Optimization. We also discuss about regularity and total regularity conditions, which play the same role in Nonlinear Multiobjective Optimization as the constraint qualifications in Nonlinear Programming, providing the strict positivity of the Lagrange multipliers associated to the objective functions. Afterwards, some of the existing methods to solve Multiobjective Optimization problems are described and compared with each other. At last, the theory and methods of Multiobjective Optimization are applied into the fields of Compressed Sensing and Portfolio Optimization. We, then, show computational tests performed with some of the methods discussed involving Portfolio Optimization problems and we present an analysis of the results.

Problemas de otimização em caixas são de grande importância, não só por surgirem naturalmente na formulação de problemas da vida prática, mas também por aparecerem como subproblemas de métodos de penalização ou do tipo Lagrangiano Aumentado para resolução de problemas de programação não-linear. O objetivo do trabalho é estudar um algoritmo de restrições ativas para problemas de otimização em caixas recentemente apresentado chamado ASA e compará-lo à versão mais recente de GENCAN, que é também um método de restrições ativas. Para tanto, foi elaborada uma metodologia de testes robusta e minuciosa, que se propõe a remediar vários dos aspectos comumente criticados em trabalhos anteriores. Com isso, puderam ser extraídas conclusões que levaram à melhoria de GENCAN, conforme ficou posteriormente comprovado por meio da metodologia aqui introduzida. / Box-constrained optimization problems are of great importance not only for naturally arising in several real-life problems formulation, but also for their occurrence as sub-problems in both penalty and Augmented Lagrangian methods for solving nonlinear programming problems. This work aimed at studying a recently introduced active-set method for box-constrained optimization called ASA and comparing it to the latest version of GENCAN, which is also an active-set method. For that purpose, we designed a robust and thorough testing methodology intended to remedy many of the widely criticized aspects of prior works. Thereby, we could draw conclusions leading to GENCAN\'s further development, as it later became evident by means of the same methodology herein proposed.

Neste trabalho será apresentado um algoritmo de pontos interiores para a solução do problema de fluxo de carga ótimo (FCO). A abordagem proposta é o método primai dual barreira logarítmica. As restrições de desigualdade do problema de FCO são transformadas em igualdades pelo uso de variáveis de folga, e estas são incorporadas na função objetivo através da função barreira logarítmica. A esparsidade da matriz Lagrangeana é explorada e o processo de fatoração é feito por elementos e não por submatrizes. Resultados numéricos de testes realizados em sistemas de 3, 14, 30 e 118 barras serão apresentados com o objetivo de mostrar a eficiência do método. / In this thesis an interior point algorithm is presented for the solution of the optimal power flow problem (OPF). The approach proposed here is the logarithmic barrier primal-dual method. The inequality constraints of the optimal power flow problem are transformed into equalities by slack variables that are incorporated into the objective function through the logarithmic barrier function. The sparsity of the Lagrangian matrix is explored and the factorization process is carried out by elements rather than submatrices. Numerical tests results obtained with systems of 3, 14, 30 and 118 buses are presented to show the efficiency of the method.

Os problemas de empacotamento de itens irregulares são problemas de corte e empacotamento, nos quais peças irregulares de menor tamanho (que chamamos de itens) devem ser empacotados inteiramente em uma peça grande (que chamamos de placa), obedecendo a restrições de nãosobreposição e minimizando as dimensões da placa. Para garantir a não-sobreposição, fazemos uso de retas separadoras, quer dizer, retas que separam um item de outro. Apresentamos modelos de programação não-linear para problemas de empacotamentos de itens regulares e irregulares que rotacionam livremente. Os itens podem ser círculos, polígonos convexos e não-convexos. A principal vantagem dos modelos é a simplicidade, já que estes utilizam somente conceitos básicos de geometria. Usamos o algoritmo de programação não-linear IPOPT (um algoritmo de tipo de pontos interiores), que faz parte da COIN-OR, para a resolução dos problemas. Testes computacionais foram executados usando instâncias conhecidas da literatura e os resultados foram comparados com resultados apresentados na literatura, obtidos com outras metodologias que também usam rotações livre, mostrando que nossos modelos são competitivos. Propomos também o uso de parábolas separadoras para a verificação de não-sobreposição na modelagem do problema, o que pode trazer ganhos computacionais e melhor qualidade de soluções. / The irregular packing problems are cutting and packing problems, in which smaller irregular pieces (which we call items) should be packaged entirely in one large piece (which we call a plate), obeying non-overlapping constraints and minimizing the dimensions of the plate. To ensure non-overlapping, we make use of separation lines, that is, lines that separate one item from another. We present nonlinear programming models for problems of packing regular and irregular items that rotate freely. The items can be circles, convex and nonconvex polygons. The main advantage of the models is their simplicity, because they use only basic geometry concepts. We use the nonlinear programming algorithm IPOPT (an algorithm of interior points type), which is part of COIN-OR, to solve the problems. Computational tests were performed using known instances of the literature and the results were compared with results presented in the literature, obtained with other methodologies that also use free rotations, showing that our models are competitive. We also propose the use of separating parabola to avoid items overlaping in the models, which could provide greater computational eficiency as well as solutions with better quality.

Neste trabalho a família de métodos de pontos interiores barreira logarítmica é desenvolvida para o problema de regressão pela norma Lp e a estrutura matricial resultante é explorada objetivando uma implementação eficiente. Apresentamos alguns conceitos sobre métodos de pontos interiores necessários para o desenvolvimento do método e descrevemos um método de convergência quadrática previamente conhecido. Uma implementação em Matlab dos métodos de pontos interiores desenvolvidos é comparada com uma implementação do método quadrático existente, obtendo desempenho computacional superior. / In this work the family of logarithmic barrier interior point methods is developed for the norm Lp fitting problem and the resultant matrix structure is exploited in order to have an efficient implementation. We introduce some concepts about interior point methods necessary for the development of the method and describe a previously known quadratic convergent problem. An implementation in Matlab of the interior point methods developed is compared with an implementation of the known quadratic method obtaining better computational performance.

Neste trabalho propomos uma abordagem para a resolução do problema de fluxo de potência ótimo. Para isso, foram obtidos dados teóricos, a partir de um levantamento bibliográfico, que explicitaram os métodos de penalidade, de barreira, de Newton-Lagrangiano, da função Lagrangiana aumentada e dual-Lagrangiano. Nesta abordagem, as restrições de igualdade são tratadas pelo método de Newton, as restrições canalizadas, de tensão e tap, pelo método da função barreira logarítmica, e as restrições de desigualdade e demais restrições canalizadas, pelo método da função Lagrangiana aumentada. A motivação para este estudo foi a necessidade de manter as variáveis - tensão e tap - dentro de seus limites. Os resultados numéricos apresentados evidenciam o potencial desta metodologia para a resolução de problemas de programação não-linear e, em particular, do problema de fluxo de potência ótimo. / A new approach to solving the optimal power flow problem is proposed in this study. The first step in developing this method was to obtain theoretical material from bibliographic survey, which described in detail the penalty method, the barrier method, Newton\'s method, the augmented Lagrangian method end the dual-Lagrangian method. In the new approach, equality constraints are handled by Newton\'s method, the voltage end tap box inequality constraints by the logarithmic barrier method and the inequality constraints and the other box inequality constraints by the augmented Lagrangian method. The motivation for this research was the necessity to keep the voltage and tap variables within their limits. The numerical results demonstrate the potential of this methodology for the solution of nonlinear problems and, in particular, of the optimal power flow problem.