Spelling suggestions: "subject:"pontos anteriores"" "subject:"pontos exteriores""
51 |
O método da função Lagrangiana barreira modificada/penalidade / The penalty/modified barrier Lagrangian function methodAguinaldo Aparecido Pereira 27 September 2007 (has links)
Neste trabalho propomos uma abordagem que utiliza o método de barreira modificada/penalidade para a resolução de problemas restritos gerais de otimização. Para isso, foram obtidos dados teóricos, a partir de um levantamento bibliográfico, que explicitaram os métodos primal-dual barreira logarítmica e método de barreira modificada. Nesta abordagem, as restrições de desigualdade canalizadas são tratadas pela função barreira de Frisch modificada, ou por uma extrapolação quadrática e as restrições de igualdade do problema através da função Lagrangiana. A implementação consiste num duplo estágio de aproximação: um ciclo externo, onde o problema restrito é convertido em um problema irrestrito, usando a função Lagrangiana barreira modificada/penalidade; e um ciclo interno, onde o método de Newton é utilizado para a atualização das variáveis primais e duais. É apresentada também uma função barreira clássica extrapolada para a inicialização dos multiplicadores de Lagrange. A eficiência do método foi verificada utilizando um problema teste e em problemas de fluxo de potência ótimo (FPO). / In this paper, we propose an approach that utilizes the penalty/modified barrier method to solve the general constrained problems. On this purpose, theoretical data were obtained, from a bibliographical review, which enlightened the logarithmic barrier primal-dual method and modified barrier method. In this approach, the bound constraints are handled by the modified log-barrier function, or by quadratic extrapolation and the equality constraints of the problem through Lagrangian function. The method, as implemented, consists of a two-stage approach: an outer cycle, where the constrained problem is transformed into unconstrained problem, using penalty/modified barrier Lagrangian function; and an inner cycle, where the Newton\'s method is used for update the primal and dual variables. Also, it is presented a classical barrier extrapolated function for initialization of Lagrange multipliers. The effectiveness of the proposed approach has been examined by solving a test problem and optimal power flow problems (OPF).
|
52 |
Uma apresentação dos métodos de Pontos Interiores na radioterapia e sua comparação com o método Simplex / A Presentation of the Interior Points Methods in Radiotherapy and its Comparison with the Simplex MethodFreitas, Paula Renata de Morais Gomes 15 December 2017 (has links)
Submitted by Paula Freitas (prmoraisg@yahoo.com.br) on 2018-01-15T13:32:04Z
No. of bitstreams: 1
Uma Apresentação dos Métodos de Pontos Interiores na Radioterapia e sua Comparação com o Método Simplex.pdf: 2003833 bytes, checksum: de8a8d33b1cd0e5b57ee871d1e24875c (MD5) / Rejected by Milena Rubi ( ri.bso@ufscar.br), reason: Bom dia!
Além da dissertação, você deve submeter também a carta comprovante devidamente preenchida e assinada pelo orientador.
O modelo da carta encontra-se na página inicial do site do Repositório Institucional.
Att.,
Milena P. Rubi
Bibliotecária
CRB8-6635
Biblioteca Campus Sorocaba
on 2018-01-16T13:23:21Z (GMT) / Submitted by Paula Freitas (prmoraisg@yahoo.com.br) on 2018-01-17T12:08:51Z
No. of bitstreams: 2
Uma Apresentação dos Métodos de Pontos Interiores na Radioterapia e sua Comparação com o Método Simplex.pdf: 2003833 bytes, checksum: de8a8d33b1cd0e5b57ee871d1e24875c (MD5)
modelo-carta-comprovantes.pdf: 221540 bytes, checksum: a0d5d955c3f58ba53124cda70b38db35 (MD5) / Approved for entry into archive by Milena Rubi ( ri.bso@ufscar.br) on 2018-01-17T12:19:27Z (GMT) No. of bitstreams: 2
Uma Apresentação dos Métodos de Pontos Interiores na Radioterapia e sua Comparação com o Método Simplex.pdf: 2003833 bytes, checksum: de8a8d33b1cd0e5b57ee871d1e24875c (MD5)
modelo-carta-comprovantes.pdf: 221540 bytes, checksum: a0d5d955c3f58ba53124cda70b38db35 (MD5) / Approved for entry into archive by Milena Rubi ( ri.bso@ufscar.br) on 2018-01-17T12:19:37Z (GMT) No. of bitstreams: 2
Uma Apresentação dos Métodos de Pontos Interiores na Radioterapia e sua Comparação com o Método Simplex.pdf: 2003833 bytes, checksum: de8a8d33b1cd0e5b57ee871d1e24875c (MD5)
modelo-carta-comprovantes.pdf: 221540 bytes, checksum: a0d5d955c3f58ba53124cda70b38db35 (MD5) / Made available in DSpace on 2018-01-17T12:19:57Z (GMT). No. of bitstreams: 2
Uma Apresentação dos Métodos de Pontos Interiores na Radioterapia e sua Comparação com o Método Simplex.pdf: 2003833 bytes, checksum: de8a8d33b1cd0e5b57ee871d1e24875c (MD5)
modelo-carta-comprovantes.pdf: 221540 bytes, checksum: a0d5d955c3f58ba53124cda70b38db35 (MD5)
Previous issue date: 2017-12-15 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / This work aims to present the Internal Points Methods and to compare the Simplex Method, when applied in the resolution of problems related to the optimal concentration of radiation in the treatment of cancer through radiotherapy. The optimum concentration is related to the higher intensity of radiation associated with less damage to the vital organs. This dissertation was based on works on radiotherapy treatment, aiming to make a comparison between two methods widely used to find an optimal concentration. / Este trabalho visa apresentar os Métodos de Pontos Interiores e fazer uma comparação com o Método Simplex, quando aplicados na resolução de problemas relacionados à concentração ótima de radiação no tratamento de câncer via radioterapia. A concentração ótima está relacionada à maior intensidade de radiação associada ao menor prejuízo aos órgãos vitais. Esta dissertação foi embasada em trabalhos sobre o tratamento por radioterapia, visando realizar uma comparação entre dois métodos muito utilizados para encontrar uma concentração ótima. / CAPES: 5564161
|
53 |
Um novo metodo preditor-corretor para fluxo de potencia otimo / A new predictor-corrector method for optimal power flowProbst, Roy Wilhelm 05 May 2010 (has links)
Orientador: Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-15T18:52:54Z (GMT). No. of bitstreams: 1
Probst_RoyWilhelm_D.pdf: 708668 bytes, checksum: 4823f5bccb159edca170bcf52eb49f4c (MD5)
Previous issue date: 2010 / Resumo: Um método de pontos interiores preditor-eorretor é desenvolvido para o problema de fluxo de potência ótimo ativo-reativo. As tensões são representadas em coordenadas cartesianas ao invés de coordenadas polares, pois estas, sendo quadráticas, permitem correções não lineares nas condições de factibilidade primai e dual e não apenas nas de complementaridade como nos métodos tradicionais de programação não-linear. Outra contribuição fornece uma nova heurística para o tratamento das restrições de magnitude das tensões. Experimentos computacionais com sistemas de teste IEEE e um sistema real brasileiro são apresentados e mostram as vantagens do método proposto / Abstract: A predictor-corrector interior-point method is developed to the AC active and reactive optimal power flow problem. Voltage rectangular coordinates is adopted instead of polar ones, since, being quadratic, it allows nonlinear corrections for the primal and dual feasibility conditions and not only for the complementary constraints as in the traditional nonlinear programming methods. A new heuristic is proposed to handle voltage magnitude constraints. Computational experiments for IEEE test systems and a real Brazilian system are presented showing the advantages of the proposed approach / Doutorado / Pesquisa Operacional / Doutor em Matemática Aplicada
|
54 |
Theoretical and computational issues for improving the performance of linear optimization methods / Aspectos teóricos e computacionais para a melhoria do desempenho de métodos de otimização linearPedro Augusto Munari Junior 31 January 2013 (has links)
Linear optimization tools are used to solve many problems that arise in our day-to-day lives. The linear optimization models and methodologies help to find, for example, the best amount of ingredients in our food, the most suitable routes and timetables for the buses and trains we take, and the right way to invest our savings. We would cite many other situations that involves linear optimization, since a large number of companies around the world base their decisions in solutions which are provided by the linear optimization methodologies. In this thesis, we propose theoretical and computational developments to improve the performance of important linear optimization methods. Namely, we address simplex type methods, interior point methods, the column generation technique and the branch-and-price method. In simplex-type methods, we investigate a variant which exploits special features of problems which are formulated in the general form. We present a novel theoretical description of the method and propose how to efficiently implement this method in practice. Furthermore, we propose how to use the primal-dual interior point method to improve the column generation technique. This results in the primal-dual column generation method, which is more stable in practice and has a better overall performance in relation to other column generation strategies. The primal-dual interior point method also oers advantageous features which can be exploited in the context of the branch-and-price method. We show that these features improves the branching operation and the generation of columns and valid inequalities. For all the strategies which are proposed in this thesis, we present the results of computational experiments which involves publicly available, well-known instances from the literature. The results indicate that these strategies help to improve the performance of the linear optimization methodologies. In particular for a class of problems, namely the vehicle routing problem with time windows, the interior point branch-and-price method proposed in this study was up to 33 times faster than a state-of-the-art implementation available in the literature / Ferramentas de otimização linear são usadas para resolver diversos problemas do nosso dia-a- dia. Os modelos e as metodologias de otimização linear ajudam a obter, por exemplo, a melhor quantidade de ingredientes na nossa alimentação, os horários e as rotas de ônibus e trens que tomamos, e a maneira certa para investir nossas economias. Muitas outras situações que envolvem otimização linear poderiam ser aqui citadas, já que um grande número de empresas em todo o mundo baseia suas decisões em soluções obtidas pelos métodos de otimização linear. Nesta tese, são propostos desenvolvimentos teóricos e computacionais para melhorar o desempenho de métodos de otimização linear. Em particular, serão abordados métodos tipo simplex, métodos de pontos interiores, a técnica de geração de colunas e o método branch-and-price. Em métodos tipo simplex, é investigada uma variante que explora as características especiais de problemas formulados na forma geral. Uma nova descrição teórica do método é apresentada e, também, são propostas técnicas computacionais para a implementação eciente do método. Além disso, propõe-se como utilizar o método primal-dual de pontos interiores para melhorar a técnica de geração de colunas. Isto resulta no método primal-dual de geração de colunas, que é mais estável na prática e tem melhor desempenho geral em relação a outras estratégias de geração de colunas. O método primal-dual de pontos interiores também oferece características vantajosas que podem ser exploradas em conjunto com o método branch-and-price. De acordo com a investigação realizada, estas características melhoram a operação de ramificação e a geração de colunas e de desigualdades válidas. Para todas as estratégias propostas neste trabalho, são apresentados os resultados de experimentos computacionais envolvendo problemas de teste bem conhecidos e disponíveis publicamente. Os resultados indicam que as estratégias propostas ajudam a melhorar o desempenho das metodologias de otimização linear. Em particular para uma classe de problemas, o problema de roteamento de veículos com janelas de tempo, o método branch-and-price de pontos interiores proposto neste estudo foi até 33 vezes mais rápido que uma implementação estado-da-arte disponível na literatura
|
55 |
Uma metodologia para otimização de sistemas elétricos de distribuição A N condutores / A methodology for optimization of N conductors electrical distribution systemsVieira, Felipe de Alcântara 28 August 2013 (has links)
Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-04-06T19:22:41Z
No. of bitstreams: 1
felipedealcantaravieira.pdf: 1984655 bytes, checksum: e8afc46ad440a574f9f1764bed5e412a (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-04-24T03:52:44Z (GMT) No. of bitstreams: 1
felipedealcantaravieira.pdf: 1984655 bytes, checksum: e8afc46ad440a574f9f1764bed5e412a (MD5) / Made available in DSpace on 2016-04-24T03:52:44Z (GMT). No. of bitstreams: 1
felipedealcantaravieira.pdf: 1984655 bytes, checksum: e8afc46ad440a574f9f1764bed5e412a (MD5)
Previous issue date: 2013-08-28 / Este trabalho propõe uma metodologia com foco na resolução de problemas de
otimização de sistemas elétricos de potência, que por ser extremamente genérica e
abrangente, permite a inserção de qualquer tipo de equipamento na modelagem do
sistema sob estudo, bem como a análise de desequilíbrios, da geração distribuída e de
cabos neutros e aterramentos, em sistemas com N condutores. A metodologia
desenvolvida utiliza como base o Método dos Pontos Interiores Primal-Dual aplicado ao
Método de Injeção de Correntes para a análise do sistema elétrico considerando
equações de injeções de correntes em cada nó, escritas por meio de variáveis complexas
em sua forma retangular. A amplitude de utilização do método proposto o faz
interessante inclusive para estudos de smart grids, uma vez que possibilita um grau de
detalhamento bastante elevado nas representações e análises dos sistemas de
distribuição. / This work proposes a methodology focusing on the solution of electrical power
systems problems, which for being extremely generical and embracing, allows the
inclusion of any type of equipment, in the modeling of the system under study, as well
as the analysis of imbalances, distributed generation and of neutral cables and
groundings on N conductors systems. The methodology developed is based on the
Primal-Dual Interior Point Method applied in the Current Injection Method for the
analysis of the electrical system considering the current injections equations at each
node, written using complex variables in rectangular formulation. The proposed method
has a range of use that make it interesting even for smart grids studies, since it allows a
higher degree of details in the representation and analysis of distribution systems.
|
56 |
FDIPA - algoritmo de pontos interiores e direções viáveis para otimização não-linear diferenciável: um estudo de parâmetrosFonseca, Erasmo Tales 06 November 2015 (has links)
Submitted by Renata Lopes (renatasil82@gmail.com) on 2016-04-28T17:57:49Z
No. of bitstreams: 1
erasmotalesfonseca.pdf: 866120 bytes, checksum: 042a0c3210df8046171b1593162cde44 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2016-05-02T01:13:24Z (GMT) No. of bitstreams: 1
erasmotalesfonseca.pdf: 866120 bytes, checksum: 042a0c3210df8046171b1593162cde44 (MD5) / Made available in DSpace on 2016-05-02T01:13:24Z (GMT). No. of bitstreams: 1
erasmotalesfonseca.pdf: 866120 bytes, checksum: 042a0c3210df8046171b1593162cde44 (MD5)
Previous issue date: 2015-11-06 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Neste trabalho apresentamos um estudo da influência dos parâmetros de um algoritmo de
pontos interiores e direções viáveis para solução de problemas de otimização não linear.
Esse algoritmo, denominado FDIPA, tem por objetivo encontrar dentre os pontos de um
conjunto definido por restrições de igualdade e/ou desigualdade, aqueles que minimizam
uma função diferenciável. O FDIPA baseia-se na resolução de dois sistemas de equações
lineares com a mesma matriz de coeficientes, obtidos das condições necessárias de primeira
ordem de Karush-Kuhn-Tucker. A partir de um ponto inicial no interior do conjunto
viável, o FDIPA gera uma sequência de pontos também interiores ao conjunto. Em cada
iteração, uma nova direção de descida é obtida e, em seguida, produz-se uma deflexão da
direção de descida no sentido do interior do conjunto viável, de modo a se obter uma nova
direção que seja de descida e viável. Realiza-se então uma busca linear para obter um novo
ponto interior e garantir a convergência global do método. Uma família de algoritmos
pode ser obtida variando-se as regras de atualização dos parâmetros do FDIPA. O estudo
apresentado neste trabalho foi feito considerando-se um único algoritmo e com restrições
de desigualdade somente. Testes numéricos apontaram para uma escolha de parâmetros
que levou a um número menor de iterações na resolução dos problemas teste. / This work presents a study on the influence of the parameters of an interior point and
feasible directions algorithm for solving non-linear problems. The algorithm, named
FDIPA, aims to find among the points of a set defined by equality and/or inequality
constraints, those which minimize a differentiable function. The FDIPA is based on two
linear systems with the same coefficient matrix, obtained from the Karush-Kuhn-Tucker
first order necessary conditions. From a initial point in the interior of the feasible set,
FDIPA generates a sequence of points which are also interior to the set. At each iteration,
FDIPA produces a descent direction which is deflected towards the interior of the feasible
set in order to create a new descent and feasible direction. Then, a linear search is
performed to get a new interior point and assure the global convergence of the method.
A family of algorithms can be obtained varying the rules used to update the parameters
of the FDIPA. The study presented here has been done considering just one particular
algorithm and inequality constraints only. Numerical tests pointed to a certain choice of
parameters which led to a fewer number of iterations when solving some test problems.
|
57 |
Inclusão de restrições dinâmicas na análise de fluxo de potência ótimo / Inclusion of dynamic restrictions in the analysis of optimal power flowFontoura, Rafael Montes 14 August 2006 (has links)
Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-02-14T10:05:06Z
No. of bitstreams: 1
rafaelmontesfontoura.pdf: 1181632 bytes, checksum: b1fad4f811abb57f040a07696d069ebb (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-02-20T17:52:42Z (GMT) No. of bitstreams: 1
rafaelmontesfontoura.pdf: 1181632 bytes, checksum: b1fad4f811abb57f040a07696d069ebb (MD5) / Made available in DSpace on 2017-02-20T17:52:42Z (GMT). No. of bitstreams: 1
rafaelmontesfontoura.pdf: 1181632 bytes, checksum: b1fad4f811abb57f040a07696d069ebb (MD5)
Previous issue date: 2006-08-14 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Este trabalho propõe a inclusão de restrições dinâmicas na análise de Fluxo de Potência Ótimo (FPO), envolvendo o problema associado ao fechamento de anel elétrico e ao planejamento de fontes de potência reativa. Os algoritmos desenvolvidos utilizam a metodologia primal-dual de pontos interiores (MPI) associada à técnica de decomposição matemática de Benders. A utilização do MPI para cálculo do fluxo de potência é motivada pelo seu bom desempenho, possibilidade de se modelar as não linearidades pertinentes aos sistemas elétricos de potência e conceituada utilização em softwares de uso comercial. A técnica de decomposição matemática de Benders é usada para reduzir a dimensão do sistema e proporcionar informações através dos índices de sensibilidade obtidos nos subproblemas. O objetivo da inclusão de restrições dinâmicas no problema de fluxo de potência ótimo é resguardar a integridade de geradores síncronos diante às perturbações presentes no sistema, sejam elas programadas (Fechamento de Anéis) ou não (Contingências). As análises com restrições dinâmicas podem ser uma ferramenta eficiente para definir ações operacionais preventivas ou investimentos no sistema. Para simulações dinâmicas foi utilizado o programa Anatem, desenvolvido Centro de Pesquisa de Energia Elétrica (CEPEL). A metodologia proposta foi implementada em código MATLAB e testada em sistemas IEEE. / This work proposes the inclusion of dynamic constraints in the Optimal Power Flow (OPF) formulation, involving the problem associated with closing loops and reactive power sources planning. The proposed algorithm uses the primal-dual Interior Point Methodology (IPM) associated with the mathematical Benders decomposition technique. The use of IPM was motivated by its performance, possibility to model the nonlinear issues in power systems and its application in commercial software. The mathematical technique of Benders decomposition was used to reduce system dimension and to provide subproblems sensitivity indexes. Dynamic constraints were included in the problem of optimal power flow in such a way to protect the integrity of synchronous generators when system disturbances occur. These disturbances can either be programmed (closing loops) or not (contingencies). The analysis of dynamic impacts can be an efficient tool to define preventive operational actions or to determine the power system investment planning. The dynamic simulations were carried out using the software ANATEM, from CEPEL. The proposed methodology was implemented in MATLAB and tested in IEEE systems.
|
58 |
Métodos de pontos interiores como alternativa para estimar os parâmetros de uma gramática probabilística livre do contexto / Interior point methods as an alternative for estimating parameters of a stochastic context-free grammarMamián López, Esther Sofía, 1985- 10 July 2013 (has links)
Orientadores: Aurelio Ribeiro Leite de Oliveira, Fredy Angel Amaya Robayo / 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-23T17:46:00Z (GMT). No. of bitstreams: 1
MamianLopez_EstherSofia_M.pdf: 1176541 bytes, checksum: 8f49901f40e77c9511c30e86c0d1bb0d (MD5)
Previous issue date: 2013 / Resumo: Os modelos probabilísticos de uma linguagem (MPL) são modelos matemáticos onde é definida uma função de probabilidade que calcula a probabilidade de ocorrência de uma cadeia em uma linguagem. Os parâmetros de um MPL, que são as probabilidades de uma cadeia, são aprendidos a partir de uma base de dados (amostras de cadeias) pertencentes à linguagem. Uma vez obtidas as probabilidades, ou seja, um modelo da linguagem, existe uma medida para comparar quanto o modelo obtido representa a linguagem em estudo. Esta medida é denominada perplexidade por palavra. O modelo de linguagem probabilístico que propomos estimar, está baseado nas gramáticas probabilísticas livres do contexto. O método clássico para estimar os parâmetros de um MPL (Inside-Outside) demanda uma grande quantidade de tempo, tornando-o inviável para aplicações complexas. A proposta desta dissertação consiste em abordar o problema de estimar os parâmetros de um MPL usando métodos de pontos interiores, obtendo bons resultados em termos de tempo de processamento, número de iterações até obter convergência e perplexidade por palavra / Abstract: In a probabilistic language model (PLM), a probability function is defined to calculate the probability of a particular string ocurring within a language. These probabilities are the PLM parameters and are learned from a corpus (string samples), being part of a language. When the probabilities are calculated, with a language model as a result, a comparison can be realized in order to evaluate the extent to which the model represents the language being studied. This way of evaluation is called perplexity per word. The PLM proposed in this work is based on the probabilistic context-free grammars as an alternative to the classic method inside-outside that can become quite time-consuming, being unviable for complex applications. This proposal is an approach to estimate the PLM parameters using interior point methods with good results being obtained in processing time, iterations number until convergence and perplexity per word / Mestrado / Matematica Aplicada / Mestra em Matemática Aplicada
|
59 |
Estrategias de segunda ordem para problemas de complementaridade / Second order strategies for complementarity problemsShirabayashi, Wesley Vagner Ines 14 August 2018 (has links)
Orientadores: Sandra Augusta Santos, Roberto Andreani / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-14T11:40:11Z (GMT). No. of bitstreams: 1
Shirabayashi_WesleyVagnerInes_D.pdf: 877226 bytes, checksum: a814cd9947431a0aee17517c4cc953f4 (MD5)
Previous issue date: 2009 / Resumo: Neste trabalho reformulamos o problema de complementaridade não linear generalizado (GNCP) em cones poliedrais como um sistema não linear com restrição de não negatividade em algumas variáveis, e trabalhamos na resolução de tal reformulação por meio de estratégias de pontos interiores. Em particular, definimos dois algoritmos e provamos a convergência local de tais algoritmos sob hipóteses usuais. O primeiro algoritmo é baseado no método de Newton, e o segundo, no método tensorial de Chebyshev. O algoritmo baseado no método de Chebyshev pode ser visto como um método do tipo preditor-corretor. Tal algoritmo, quando aplicado a problemas em que as funções envolvidas são afins, e com escolhas adequadas dos parâmetros, torna-se o bem conhecido algoritmo preditor-corretor de Mehrotra. Também apresentamos resultados numéricos que ilustram a competitividade de ambas as propostas. / Abstract: In this work we reformulate the generalized nonlinear complementarity problem (GNCP) in polyhedral cones as a nonlinear system with nonnegativity in some variables and propose the resolution of such reformulation through interior-point methods. In particular we define two algorithms and prove the local convergence of these algorithms under standard assumptions. The first algorithm is based on Newton's method and the second, on the Chebyshev's tensorial method. The algorithm based on Chebyshev's method may be considered a predictor-corrector one. Such algorithm, when applied to problems for which the functions are affine, and the parameters are properly chosen, turns into the well-known Mehrotra's predictor corrector algorithm. We also present numerical results that illustrate the competitiveness of both proposals. / Doutorado / Otimização / Doutor em Matemática Aplicada
|
60 |
Aperfeiçoamento de precondicionadores para solução de sistemas lineares dos métodos de pontos interiores / Improving the preconditioning of linear systems from interior point methodsCasacio, Luciana, 1983- 27 August 2018 (has links)
Orientadores: Christiano Lyra Filho, Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T01:38:37Z (GMT). No. of bitstreams: 1
Casacio_Luciana_D.pdf: 3240577 bytes, checksum: f49bb4444bbbfacf0559d3b88d8feee5 (MD5)
Previous issue date: 2015 / Resumo: A solução de problemas de otimização linear através de métodos de pontos interiores envolve a solução de sistemas lineares. Esses sistemas quase sempre possuem dimensões elevadas e alto grau de esparsidade em aplicações reais. Para solução, tipicamente são realizadas operações algébricas que os reduzem a duas formulações mais simples: uma delas, conhecida por "sistema aumentado", envolve matrizes simétricas indefinidas e geralmente esparsas; a outra, denominada "sistema de equações normais", usa matrizes de menor dimensão, simétricas e definidas positivas. A solução dos sistemas lineares é a fase que requer a maior parte do tempo de processamento dos métodos de pontos interiores. Consequentemente, a escolha dos métodos de solução é de extrema importância para que se tenha uma implementação eficiente. Normalmente, aplicam-se métodos diretos para a solução como, por exemplo, a fatoração de Bunch-Parllett ou a fatoração de Cholesky. No entanto, em problemas de grande porte, o uso de métodos diretos torna-se desaconselhável, por limitações de tempo e memória. Nesses casos, abordagens iterativas se tornam mais atraentes. O sucesso da implementação de métodos iterativos depende do uso de bons precondicionadores, pois a matriz de coeficientes torna-se muito mal condicionada, principalmente próximo da solução ótima. Uma alternativa para tratar o problema de mal condicionamento é o uso de abordagens híbridas com duas fases: a fase I utiliza um precondicionador para o sistema de equações normais construído com informações de fatorações incompletas, denominado fatoração controlada de Cholesky; a fase II, utilizada nas últimas iterações, adota o precondicionador separador desenvolvido especificamente para sistemas mal condicionados. O trabalho propõe um novo critério de ordenamento das colunas para construção do precondicionador separador, que preserva a estrutura esparsa da matriz de coeficientes original. Os resultados teóricos desenvolvidos mostram que a matriz precondicionada tem o número de condição limitado quando o ordenamento proposto é adotado. Experimentos computacionais realizados com todos os problemas da biblioteca NETLIB mostram que a abordagem é competitiva com métodos diretos e que o número de condição da matriz precondicionada é muito menor do que o da matriz original. Foram também realizadas comparações com a abordagem híbrida anterior, baseada em precondicionadores que reduzem a esparsidade do sistema de equações. Esses experimentos confirmaram o bom desempenho da metodologia em relação ao número de iterações dos métodos de pontos interiores, aos tempos computacionais e à qualidade das soluções. Esses benefícios foram obtidos com a preservação da esparsidade dos sistemas de equações, o que destaca a adequação da abordagem proposta para a solução de problemas de grande porte / Abstract: The solution of linear optimization problems through interior point methods involves the solution of linear systems. These systems often have high dimensions and high sparsity degree, specially in real applications. Typically algebraic operations are performed to reduce the systems in two simpler formulations: one of them is known as the augmented system, and the other one, referred as normal equation systems, has a smaller dimension matrix which is symmetric positive definite. The solution of linear systems is the interior point methods step that requires most of the processing time. Consequently, the choice of the solution methods are extremely important in order to have an efficient implementation. Usually, direct methods are applied for solving these systems as, for example, Bunch-Parllett factorization or Cholesky factorization. However, in large scale problems, the use of direct methods becomes discouraging by limitations of time and memory. In such cases, iterative approaches are more attractive. The success of iterative method approaches depends on good preconditioners once the coefficient matrix becomes very ill-conditioned, especially close to an optimal solution. An alternative to treat the problem of ill conditioning is to use hybrid approaches with two phases: phase I uses a preconditioner for the normal equation systems built with incomplete factorizations information, called controlled Cholesky factorization; phase II, used in the final iterations, adopts the splitting preconditioner, which was developed specifically for such ill conditioned systems. This work proposes a new ordering criterion for the columns of the splitting preconditioner that preserves the sparse structure of the original coefficient matrix. Theoretical results show that the preconditioned matrix has a limited condition number when the proposed idea is adopted. Computational experiments performed with all NETLIB problems show that the approach is competitive with direct methods and the condition number of the preconditioned matrix is much smaller than the original matrix. Comparisons are also performed with the previous hybrid approach. These experiments confirm the good performance of the methodology. The final number of iterations, processing time and quality of solutions of interior point methods are suitable. These benefits are obtained preserving the sparse structure of the systems, which highlights the suitability of the proposed approach for large scale problems / Doutorado / Automação / Doutora em Engenharia Elétrica
|
Page generated in 0.1296 seconds