Orientadores: Christiano Lyra Filho, Aurelio Ribeiro Leite de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-16T02:58:01Z (GMT). No. of bitstreams: 1 Casacio_Luciana_M.pdf: 610633 bytes, checksum: eb421c22c943197133158a0a0de7e858 (MD5) Previous issue date: 2010 / Resumo: Neste trabalho os métodos de pontos interiores primais-duais são utilizados para minimizar as perdas técnicas de energia na geração e transmissão de um sistema de potência hidrotérmico. A estrutura matricial resultante é explorada, objetivando uma implementação eficiente do ponto de vista de tempo de processamento, e robusto, do ponto de vista numérico. Uma vez que a demanda de energia varia ao longo do dia, a geração de energia deve acompanhar a variação da carga. No pré-despacho de sistemas hidrotérmicos, as usinas hidroelétricas devem cumprir uma meta de geração por dia, estabelecida pelo planejamento de longo prazo. O trabalho considera que as usinas e as linhas devem também operar em um estado de "equilíbrio estável", caracterizado a cada período de tempo por restrições de segurança para atender demandas imprevistas ou contingências. A implementação dos métodos de pontos interiores para reduzir as perdas satisfazendo essas restrições foi desenvolvida e comparada com uma implementação para o problema de pré-despacho que não considera as restrições de segurança. A comparação foi realizada em termos de eficiência computacional e qualidade da solução. Os estudos de casos mostram que a inclusão das restrições de segurança permite obter soluções de pré-despacho estáveis, com baixos tempos computacionais e boa estabilidade numérica, abrindo a perspectiva para a utilização da metodologia no pré-despacho dos sistemas brasileiros / Abstract: In this work, the primal-dual interior point methods are used to minimize the technical power generation and transmission losses of a hydrothermal power system. The resulting matrix structure is exploited, aiming an efficient implementation in terms of processing time, and robust, in the numerical point of view. Since the demand for energy varies throughout the day, power generation must follow the load change. In short term hydrothermal scheduling, the hydro generating units must satisfy daily targets, established by long-term scheduling models. This work considers that the hydro generating units and the branch must also operate in a state of "stable equilibrium", characterized in each time interval by security constraints to support some unpredictable demands or contingencies. The implementation of interior point methods to reduce losses satisfying these constraints is developed and compared with an implementation of the predispatch problem without such security constraints. The comparison is performed in terms of computational efficiency and solution quality. Case studies show that the inclusion of security constraints achieves stable predispatch solutions with low computational time and good numerical stability, leading to the prospect of this methodology application in predispatch Brazilian systems / Mestrado / Energia Eletrica / Mestre em Engenharia Elétrica

Orientador: Aurelio Ribeiro Leite de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-16T01:36:50Z (GMT). No. of bitstreams: 1 Silva_DanieleCosta_M.pdf: 1303714 bytes, checksum: 5b7f038f6b0f53fca9601f7784ec02d1 (MD5) Previous issue date: 2010 / Resumo: A presença de linhas redundantes na matriz de restrições não é incomum em problemas reais de grande porte. A existência de tais linhas deve ser levada em consideração na solução destes problemas. Se o método de solução adotado for o método simplex, existem procedimentos eficientes e de fácil implementação que contornam este problema. O mesmo se aplica quando métodos de pontos interiores são adotados e os sistemas lineares resultantes são resolvidos por métodos diretos. No entanto, existem problemas de grande porte cuja única forma possível de solução é resolver os sistemas lineares por métodos iterativos. Nesta situação as linhas redundantes representam uma dificuldade considerável, pois geram uma matriz singular e os métodos iterativos não convergem. A única alternativa viável consiste em detectar tais linhas e eliminá-las antes da aplicação dos métodos de pontos interiores. Este trabalho propõe uma implementação eficiente de um procedimento de detecção de linhas redundantes, que incluímos em uma adaptação própria do PCx que resolve os sistemas lineares por métodos iterativos / Abstract: The presence of dependent rows in the constraint matrix is frequent in real large-scale problems. If the method of solution adopted is the simplex method, there are efficient procedures easy to implement that circumvent this problem. The same applies when interior point methods are adopted and the resulting linear systems are solved for directed methods. However, there are large-scale problems whose only possible solution is to solve linear systems by iterative methods. In this situation, the dependent rows create a singular matrix and the iterative method does not converge. The only viable alternative is to find and remove these rows before applying the method. This dissertation proposes an efficient implementation of a procedure for detection dependent rows, include in a PCx modification that solves linear systems by iterative methods / Mestrado / Programação Linear / Mestre em Matemática Aplicada

Submitted by marco aurélio santos (marrco.santos@gmail.com) on 2018-07-30T01:42:52Z No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) msc_dissertacao_marcoSantos.pdf: 6142716 bytes, checksum: 17219663e0f7676d5c438178de493d89 (MD5) / Approved for entry into archive by Secretaria PPGI (secretariappgi@icomp.ufam.edu.br) on 2018-07-30T18:34:28Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) msc_dissertacao_marcoSantos.pdf: 6142716 bytes, checksum: 17219663e0f7676d5c438178de493d89 (MD5) / Approved for entry into archive by Divisão de Documentação/BC Biblioteca Central (ddbc@ufam.edu.br) on 2018-07-31T18:29:17Z (GMT) No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) msc_dissertacao_marcoSantos.pdf: 6142716 bytes, checksum: 17219663e0f7676d5c438178de493d89 (MD5) / Made available in DSpace on 2018-07-31T18:29:17Z (GMT). No. of bitstreams: 2 license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) msc_dissertacao_marcoSantos.pdf: 6142716 bytes, checksum: 17219663e0f7676d5c438178de493d89 (MD5) Previous issue date: 2018-04-16 / Internal positioning systems allow the localization of people or certain objects indoors, as well as assist in navigation and orientation. Proposals for indoor location systems based on only one technology have achieved unsatisfactory performance in localization, mainly due to the limitations in relation to the conflicting characteristics present in these environments. This work aims at the development of a hybrid location system, integrating the PDR and Wi-Fi technologies, which aims to provide the location of a user in an internal environment, allowing the user to move around and visualize their current location through a representation on a map. The results were satisfactory, including the direct influence of factors such as: physical characteristics (height, body mass, size of the past), smartphone location, speed of the adopted march and adoption of constant movements. / Os sistemas de posicionamento internos permitem a localização de pessoas ou certos objetos em ambientes internos, assim como ajudam na navegação e orientação. As propostas de sistemas de localização para ambientes internos baseados em somente uma tecnologia tem alcançado desempenho insatisfatório na localização, principalmente, devido às limitações em relação às características conflitantes presentes nesses ambientes. Este trabalho tem como objetivo o desenvolvimento de um sistema híbrido de localização, integrando as tecnologias PDR e Wi-Fi, que visa fornecer a localização de um usuário em um ambiente interno, permitindo ao usuário locomover-se e visualizar a sua localização corrente através de uma representação em um mapa. Os resultados obtidos foram satisfatórios, constando-se a direta influência de fatores como: características físicas (altura, massa corporal, tamanho da passada) do usuário, localização do smartphone, velocidade da marcha adotada e adoção de movimentos constantes.

A pesquisa objetiva estudar o design de móveis e os interiores concebidos por Lina Bo Bardi entre 1947 e 1968, período em que a arquiteta desenvolve projetos que são produto de sua experiência na Itália e no Brasil. Sob esta perspectiva, a investigação de um período anterior a seu traslado para o Brasil é fundamental para resgatar fatos históricos, políticos e sócio-culturais, como também os postulados modernos, a predisposição dos arquitetos de estender suas funções ao design de mobiliário e o advento do neo-realismo italiano que fazem parte da formação de Lina Bo. Imbuída deste contexto e no desejo de configurar uma identidade brasileira, Lina Bo Bardi realiza uma observação antropológica um atento olhar na busca de temas locais que concilia aos conceitos modernos internacionalizados. Ela considera materiais, técnicas, tradições, costumes, natureza, arte, artesanato ou pré-artesanato, cultura e sociedade do país que adota. Esta conduta traduz, para sua arquitetura, interiores e mobiliário, vários tipos de integração edificação e entorno, interior e exterior, móvel e ambiente, vernáculo e móvel, arte e povo , muitas vezes constituindo uma inequívoca mimética, não só entre a arquitetura e seu habitat, como, também, entre o design de móveis e os de elementos da terra. É relevante destacar o desenvolvimento desta postura que confere ao móvel e, conseqüentemente, ao ambiente, uma feição peculiarmente moderna com um caráter de brasilidade, oferecendo uma importante contribuição à nossa cultura material. / The objective of the research is to study the design of the furniture and interiors that were conceived by Lina Bo Bardi between 1947 and 1968, a period during which the architect developed projects that were the result of her experiences in Italy and Brazil. From this perspective the investigation into a period prior to her arrival in Brazil is fundamental when it comes to recovering the historical, political, social and cultural facts, as well as the modern postulates, the predisposition of architects to extend their functions to designing furniture and the rise of Italian neo-realism, all of which form part of the background of Lina Bo. Heavily influenced by this context and with her desire to shape a Brazilian identity Lina Bo Bardi observes in an anthropological way takes a close look in her search for local themes which reconciles the modern internationalized concepts. She considers the materials, techniques, traditions, customs, nature, art, handicrafts or pre-handicrafts, culture and society of the country she adopted. This transfers various types of integration buildings and their surroundings, interiors and exteriors, furniture and the environment, the vernacular and furniture, art and the people -, into her architecture, her interiors and her furniture, which often constitute an unequivocal mimicry, not only between the architecture and its habitat, but also between the design of furniture and the elements from the land. It is important to highlight the development of this posture that provides the piece of furniture and consequently the environment with features that are particularly modern and with a sense of Brazilianity, thus making an important contribution to our material culture.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-19T17:29:36Z No. of bitstreams: 1 rafaelsantosrocha.pdf: 980623 bytes, checksum: 82b73ddc57b57ae5da6c345e14f34a15 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-20T12:28:44Z (GMT) No. of bitstreams: 1 rafaelsantosrocha.pdf: 980623 bytes, checksum: 82b73ddc57b57ae5da6c345e14f34a15 (MD5) / Made available in DSpace on 2017-04-20T12:28:44Z (GMT). No. of bitstreams: 1 rafaelsantosrocha.pdf: 980623 bytes, checksum: 82b73ddc57b57ae5da6c345e14f34a15 (MD5) Previous issue date: 2008-08-15 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O planejamento do setor energético é fundamental para assegurar o suprimento de energia ao menor custo, com o menor risco e com os menores impactos sócio-econômicos e ambientais para a sociedade. Estes fatores assim como a complexidade dos aspectos envolvidos no funcionamento da indústria de produção de energia elétrica explicam a importância do planejamento do setor energético. Atualmente, o sistema elétrico brasileiro é operado de maneira centralizada por agentes reguladores que atuam com grande poder institucional sobre as variáveis do sistema através de decisões que trazem impactos e influenciam fortemente o futuro dos sistemas. O fato de o sistema brasileiro ser predominantemente hidrelétrico faz com que essas decisões, na maioria das vezes, sejam tomadas num ambiente de incertezas e assim necessitam de processos sistemáticos de apoio à decisão, em especial sobre as perspectivas do futuro com relação aos riscos de suprimento de energia. Neste contexto, a energia firme, definida como a máxima capacidade de produção contínua de energia, sem a ocorrência de déficits energéticos, influencia diretamente na remuneração das usinas hidrelétricas e na realização dos contratos de venda de energia elétrica pois é utilizada no cálculo da energia assegurada, que representa o lastro de geração de energia destas usinas no Brasil. Hoje, o cálculo da energia firme de cada usina hidrelétrica do sistema elétrico brasileiro é feito através de modelos de simulação, em particular, os modelos Modelo de Simulação de Usinas Individualizadas (MSUI) desenvolvido pela Eletrobrás e o Modelo de Simulação a Usinas Individualizadas para Subsistemas Hidrotérmicos Interligados (SUISHI-O) desenvolvido pelo Centro de Pesquisas em Energia Elétrica (CEPEL). A topologia das usinas é respeitada e, através de regras heurísticas, é simulada a operação das mesmas, considerando-se a série histórica de vazões desde janeiro de 1931. Este trabalho tem como objetivo o desenvolvimento de uma ferramenta computacional destinada ao cálculo da energia firme das usinas hidrelétricas. Para isto, é proposta uma solução, através de um único problema de programação não linear, com a representação das não linearidades inerentes à produtividade das usinas hidrelétricas e a representação individualizada dos reservatórios juntamente com a série histórica de vazões desde o mês de janeiro de 1931. A solução do problema de otimização não linear é obtida através do Método Primal-Dual de Pontos Interiores (MPI). A metodologia proposta foi implementada em linguagem C++, permitindo aplicar o cálculo de energia firme ao Sistema Interligado Nacional Brasileiro (SIN). Será apresentado um estudo de caso abrangendo o Sistema Interligado Nacional (SIN), resultando em um problema com mais de 400 mil variáveis, onde poderá ser observada a importância de se resolver o problema considerando-se as não linearidades em um problema de otimização. Estes resultados foram comparados com os obtidos através do modelo linear do cálculo da energia firme. Resultados adicionais com a entrada de novas usinas no sistema (Estreito Tocantins e Peixe Angical) são avaliados para validar a aplicação da metodologia a sistemas reais. Os resultados obtidos mostram que a metodologia proposta é promissora. Adicionalmente, o sistema computacional desenvolvido é uma ferramenta capaz de receber aperfeiçoamentos e modificações para incorporação de diversas outras funcionalidades relacionadas ao planejamento e operação de sistemas elétricos de potência. / The energy sector planning is fundamental to assure the energy supply at the smallest costs and risks and with the smallest socioeconomic and environmental impacts for the society. These factors as well as the aspects complexity involved in the industry operation of the electrical energy production explain the importance of the energy sector planning. Nowadays, the Brazilian electrical system is operated centralized by regulators agents that acts with great institutional power on the system’s variables through decisions that brings impacts and strongly influence the future of the systems. The fact of the Brazilian system predominantly being hydroelectric does those decisions, in most of the time, to be taken in an uncertain environment and then requires systematic processes of decision support, especially above the future perspectives regarding the energy supply risks. In this context, the firm energy, defined as the maximum continuous capacity of energy production, without the occurrence of energy deficits, influence directly the remuneration of the hydroelectric power stations and the electric power sales contracts because it is used in the evaluation of the assured energy, that represents the energy generation ballast of these plants in Brazil. Today, the firm energy evaluation of each hydroelectric power station of the Brazilian electrical system is accomplished through simulation models, in particular, the MSUI model, developed by Eletrobr´as and the SUISHI-O model, developed by CEPEL. The power stations topology is respected and, through heuristic rules, is simulated its operation, considering the historical flow series since January of 1931. This work has as objective the development of a computacional tool destined to the firm energy evaluation of the hydroelectric power stations. For this, a solution is proposed, through a single nonlinear programming problem, with the representation of the nonlinearities inherent to the hydroelectric power stations productivity and the individualized reservoirs representation together with the historical flow series since January of 1931. The solution of the nonlinear optimization problem is obtained through Primal-Dual Interior Point Method. The proposed methodology was implemented in computational language C++, allowing to apply the firm energy evaluation to the Brazilian Interconnected National System. A study case will be presented extending the Brazilian Interconnected National System, resulting in a problem with more than 400 thousand variables, in wich it will be observed the importance to solve the problem considering the nonlinearities in a unique optimization problem. These results were compared to the obtained ones with the linear model of the firm energy evaluation. Additional results with the entrance of new power stations in the system (Estreito Tocantins and Peixe Angical) are evaluated to validate the methodology appliance to real systems. The obtained results shows that the proposed methodology is promising. Additionally, the developed software is a tool capable to receive improvements and modifications for incorporation of several other functionalities related to the planning and operation of electrical power systems.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-20T14:19:59Z No. of bitstreams: 1 marcelosilvaneves.pdf: 962677 bytes, checksum: 134310c582f4e3179b04920d81ae9630 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-20T15:04:55Z (GMT) No. of bitstreams: 1 marcelosilvaneves.pdf: 962677 bytes, checksum: 134310c582f4e3179b04920d81ae9630 (MD5) / Made available in DSpace on 2017-04-20T15:04:55Z (GMT). No. of bitstreams: 1 marcelosilvaneves.pdf: 962677 bytes, checksum: 134310c582f4e3179b04920d81ae9630 (MD5) Previous issue date: 2008-08-22 / CNPq - Conselho Nacional de Desenvolvimento Científico e Tecnológico / Neste trabalho é proposta uma nova metodologia para a modelagem estática de carga em Sistemas Elétricos de Potência. A ferramenta proposta visa à estimação dos parâmetros dos modelos exponencial e polinomial (ZIP) relativos às potências ativa e reativa da carga com as variações estáticas de tensão. Estes parâmetros são determinados a partir da análise de um conjunto de medições de potências realizadas sob variações forçadas e sustentadas de tensão, em um determinado ponto de interesse do sistema. A estimação dos parâmetros que compõem a carga é realizada utilizando-se o método dos mínimos quadrados ponderados de estimação estática de estados onde os pesos das medidas são considerados unitários. Adicionalmente a metodologia primal-dual de pontos interiores é utilizada para a inclusão das restrições de canalização impostas pelos modelos da carga. Para verificar a eficácia da metodologia, são realizados estudos a partir de dados de medição obtidos de uma subestação de propriedade da CEMIG, obtendo-se os parâmetros dos modelos polinomial e exponencial. / In this work a new methodology for static load modeling in electric power systems is proposed. The proposed tool aims to make the estimation of the exponential and polynomial (ZIP) load parameters related to active and reactive power as a function of static voltage variations. Those parameters are determined from the analysis of a set of active and reactive power measurements under forced variations of voltages at a given interest point of the electric power system. The load composition parameters are determined using the minimum weighted least square static state estimation technique having unit values for the measurement weights. Additionally, the primal-dual interior point technique was used to solve the problem in order to consider the inclusion of equality and inequality constraints imposed by the load model parameters. In order to very the effectiveness of the proposed methodology, various sets of data measurements were obtained from a substation of the property of CEMIG and the load composition parameters were estimated for both the polynomial and exponential models.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-09-20T19:52:57Z No. of bitstreams: 1 patriciademouraesilvatoledo.pdf: 5745939 bytes, checksum: 0b875746feb2068b1161798ac3cbc66e (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-09-22T15:20:34Z (GMT) No. of bitstreams: 1 patriciademouraesilvatoledo.pdf: 5745939 bytes, checksum: 0b875746feb2068b1161798ac3cbc66e (MD5) / Made available in DSpace on 2017-09-22T15:20:34Z (GMT). No. of bitstreams: 1 patriciademouraesilvatoledo.pdf: 5745939 bytes, checksum: 0b875746feb2068b1161798ac3cbc66e (MD5) Previous issue date: 2017-04-24 / Esta dissertação discorre a respeito da manifestação da individualidade no espaço do quarto compartilhado de hostel, a partir dos conceitos e fundamentos do design de interiores aplicados. A pesquisa foi motivada pelo questionamento: “como se manifesta a individualidade nos quartos compartilhados de hostel e quais os elementos do design de interiores são responsáveis por potencializarem esta manifestação? ” Portanto, teve-se como principal objetivo, compreender como se dá a individualidade no espaço do quarto compartilhado de hostels. Tratou-se de uma pesquisa de natureza básica, exploratória e de caráter qualitativo quanto à abordagem do problema. A coleta de dados se deu tanto a partir de um levantamento bibliográfico quanto de uma pesquisa de campo. Ao final da pesquisa, constatou-se que a utilização do design de interiores, através de categorias como, mobiliário, leiaute e equipamentos, contribui diretamente na delimitação e identificação da manifestação da individualidade nos quartos compartilhados de hostels. Sobretudo, identificamos o habitáculo da cama como o elemento de maior representatividade da manifestação da individualidade. Além de se apresentar como um importante instrumento para compreensão da dinâmica entre indivíduo e espaço. / This dissertation discusses shared rooms individuality space, that is revealed in a hostel, from concepts and fundamentals of interior design. The research was promoted by the request: “how individuality is shown in hostel shared rooms and which elements of interior design are able to stimulate this demonstration?” To understand how the individuality in hostel shared rooms is shown, is the principal aim of this research. It is a basic and quality feature task, related with the approaching. The data collection took place from a bibliographic survey as well a field research. At the end, we come to a conclusion that the delimitation and identification showing individuality, is stimulated directly, by the usage of the interior design concepts and theories through elements as furniture, layout and equipment in hostel shared rooms besides revealing an important appliance to have individual dynamic comprehension.

Orientadores: Aurelio Ribeiro Leite de Oliveira, Fernando da Rocha Villas-Bôas, Clóvis Perin Filho / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T03:16:18Z (GMT). No. of bitstreams: 1 Santos_LuizRafaeldos_D.pdf: 1892418 bytes, checksum: f636057b6014ba9f4fdbc0c69c99bdeb (MD5) Previous issue date: 2014 / Resumo: Neste trabalho, propomos um método de pontos interiores do tipo preditor-corretor para programação linear em um contexto primal-dual, em que o próximo iterado será escolhido através de um subproblema de minimização de uma função de mérito polinomial a três variáveis: a primeira variável é o tamanho de passo, a segunda define a trajetória central e a última modela o peso que uma direção corretora deve ter. A minimização da função de mérito é feita sujeitando-a à restrições definidas por uma vizinhança da trajetória central que permite passos largos. Dessa maneira, combinamos diferentes direções, tais como preditora, corretora e de centralização com o objetivo de obter uma direção melhor. O método proposto generaliza grande parte dos métodos de pontos interiores preditores-corretores, a depender da escolha do valor das variáveis acima descritas. É feita, então uma análise de convergência do método proposto, considerando um ponto inicial que tem bom desempenho na prática, e que resulta em convergência linear dos iterados em complexidade polinomial. São feitos experimentos numéricos, utilizando o conjunto de testes Netlib, que mostram que essa abordagem é competitiva, quando comparada a implementações de pontos interiores bem estabelecidas como o PCx / Abstract: In this work we propose a predictor-corrector interior point method for linear programming in a primal-dual context, where the next iterate is chosen by the minimization of a polynomial merit function of three variables: the first one is the step length, the second one defines the central path and the last one models the weight that a corrector direction must have. The merit function minimization is performed by restricting it to constraints defined by a neighborhood of the central path that allows wide steps. In this framework, we combine different directions, such as the predictor, the corrector and the centering directions, with the aim of producing a better direction. The proposed method generalizes most of predictor-corrector interior point methods, depending on the choice of the variables described above. Convergence analysis of the method is carried out, considering an initial point that has a good practical performance, which results in Q-linear convergence of the iterates with polynomial complexity. Numerical experiments are made, using the Netlib test set, which show that this approach is competitive when compared to well established solvers, such as PCx / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientador: Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica / Made available in DSpace on 2018-08-25T19:56:24Z (GMT). No. of bitstreams: 1 Silva_LinoMarcosda_D.pdf: 2297954 bytes, checksum: 2213b987c2753edec9152998b30b7c74 (MD5) Previous issue date: 2014 / Resumo: O método de pontos interiores para programação linear resolve em poucas iterações problemas de grande porte. No entanto, requer a cada iteração a resolução de dois sistemas lineares, os quais possuem a mesma matriz de coeficientes. Essa etapa se constitui no passo mais caro do método por aumentar consideravelmente o tempo de processamento e a necessidade de armazenamento de dados. Reduzir o tempo de solução dos sistemas lineares é, portanto, uma forma de melhorar o desempenho do método. De um modo geral, problemas de programação linear de grande porte possuem matrizes esparsas. Uma vez que os sistemas lineares a serem resolvidos são simétricos positivos definidos, métodos iterativos como o método dos gradientes conjugados precondicionado podem ser utilizados na resolução dos mesmos. Além disso, fatores de Cholesky incompletos podem ser utilizados como precondicionadores para o problema. Por outro lado, fatorações incompletas podem sofrer falhas na diagonal durante o processo de fatoração, e quando tais falhas ocorrem uma correção é efetuada somando-se um valor positivo aos elementos da diagonal da matriz do sistema linear e a fatoração da nova matriz é reiniciada, aumentando dessa forma o tempo de precondicionamento, quer seja devido a reconstrução do precondicionador, quer seja devido a perda de qualidade do mesmo. O precondicionador fatoração controlada de Cholesky tem um bom desempenho nas iterações iniciais do método de pontos interiores e tem sido importante nas implementações de abordagens de precondicionamento híbrido. No entanto, sendo uma fatoração incompleta, o mesmo não está livre da ocorrência de falhas no cálculo do pivô. Neste estudo propomos duas modificações à fatoração controlada de Cholesky a fim de evitar ou diminuir o número de reinícios da fatoração das matrizes diagonalmente modificadas. Resultados computacionais mostram que a técnica pode reduzir significativamente o tempo de resolução de certas classes de problemas de programação linear via método de pontos interiores / Abstract: The interior point method solves large linear programming problems in few iterations. However, each iteration requires computing the solution of one or more linear systems. This constitutes the most expensive step of the method by greatly increasing the processing time and the need for data storage. According to it, reducing the time to solve the linear system is a way of improving the method performance. In general, large linear programming problems have sparse matrices. Since the linear systems to be solved are symmetric positive definite, iterative methods such as the preconditioned conjugate gradient method can be used to solve them. Furthermore, incomplete Cholesky factor can be used as a preconditioner to the problem. On the other hand, breakdown may occur during incomplete factorizations. When such failure occur, a correction is made by adding a positive number to diagonal elements of the linear system matrix and the factorization of the new matrix is restarted, thus increasing the time of preconditioning, either due to computing the preconditioner, or due to loss of its quality. The controlled Cholesky factorization preconditioner performs well in early iterations of interior point methods and has been important on implementations of hybrid preconditioning approaches. However, being an incomplete factorization, it is not free from faulty pivots. In this study we propose two modifications to the controlled Cholesky factorization in order to avoid or decrease the refactoring diagonally modified matrices number. Computational results show that the proposed techniques can significantly reduces the time for solving linear programming problems by interior point method / Doutorado / Matematica Aplicada / Doutor em Matemática Aplicada

Orientadores: Daniela Renata Cantane, Aurelio Ribeiro Leite de Oliveira / 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-23T12:26:43Z (GMT). No. of bitstreams: 1 Kikuchi_PaulaAparecida_M.pdf: 1402695 bytes, checksum: 8339a3eaa502e0d7b3a9ebfe61097f83 (MD5) Previous issue date: 2013 / Resumo: Vários são os métodos propostos para reconstrução de sinal. Nosso enfoque é o método Basis Pursuit. Trabalhando com dicionários overcomplete, são inúmeras as combinações possíveis para a representação do sinal. Basis Pursuit encontra a mais esparsa, porque minimiza a soma dos módulos dos coeficientes da combinação, ou seja, minimiza os coeficientes na norma 1. Veremos que podemos reescrever o problema em questão como um problema de programação linear. Apresentaremos um método já existente para a resolução deste problema, o Método Primal-Dual Barreira Logarítmica. Em um primeiro momento, vamos aplicar o Método Barreira Logarítmica, e buscando maior eficiência, iremos incluir a direção afim-escala, a direção de centragem e a direção de correção no mesmo método, obtendo o Método Primal-Dual Barreira Logarítmica Preditor- Corretor, além de implementar uma variação deste. Resultados computacionais com problemas reais comprovam a eficiência do método proposto / Abstract: There are many proposed methods for signal reconstruction. However, our focus is on the Basis Pursuit method. When working with overcomplete dictionaries, there exist countless possible combinations to represent the signal. Basis Pursuit finds the sparsest, because it minimizes the sum of the combination coefficients absolute values, i.e., it minimizes the coefficients on norm 1. We will see that the problem in question can be rewritten as a linear programming problem. An existing method is shown for the solution of this problem, the Primal-Dual Logarithmic Barrier Method. Initially, we will apply the Logarithmic Barrier Method, and seeking higher efficiency, we will include the affine scaling direction, the centering direction and the nonlinear correction direction in the same method, obtaining the Predictor-Corrector Primal-Dual Logarithmic Barrier Method, of which a variation is also implemented. Computational results with real life problems show the efficiency of the proposed method / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada