Search

Submitted by Algacilda Conceição (algacilda@sibi.ufrj.br) on 2018-03-05T20:28:23Z No. of bitstreams: 1 122797.pdf: 3238492 bytes, checksum: 3bca663e6c808e3599e132112d3a01ff (MD5) Made available in DSpace on 2018-03-05T20:28:23Z (GMT). No. of bitstreams: 1 122797.pdf: 3238492 bytes, checksum: 3bca663e6c808e3599e132112d3a01ff (MD5) Previous issue date: 1970-04-22 O princípio do mínimo de Pontryagin fornece condições necessárias para que seja minimizada uma funcional condicionada a um problema de controle. Como resultado, obtém-se, em geral, sistemas de equações diferenciais que as variáveis de controle e parâmetros do problema devem satisfazer. Neste trabalho mostramos que cestos tipos de problemas de controle podem ser aproximados, dentro de certo critério, por problemas de programação matemática, cujas soluções devem satisfazer certas condições. Estas aproximações não são do tipo "discretização no tempo", mas são aproximações nas funções de controle usadas. Estudamos, neste trabalho, condições necessárias e suficientes para os problemas simplificados, assim como alguns métodos numéricos para sua solução.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas, Programa de Pós-Graduação em Matemática Pura e Aplicada, Florianópolis, 2015. Neste trabalho apresentamos uma descrição detalhada do método de máximo declive para problemas quadráticos com busca unidirecional exata (método de Cauchy). Esse método é globalmente convergente, porém é ineficiente, pois é lento e apresenta um comportamento oscilatório, convergindo para uma busca no espaço gerado pelos autovetores associados ao maior e ao menor autovalor da matriz Hessiana do problema quadrático. Analisamos o comportamento oscilatório do gradiente da função objetivo no caso quadrático, bem como da sequência de passos gerados pelo método de Cauchy. Apresentamos o método de Barzilai-Borwein que, experimentalmente, exibe um desempenho melhor do que o método de Cauchy, e, também, algumas variantes do método de Barzilai-Borwein. Analisamos o comportamento do gradiente causado pela escolha de outros tamanhos de passos no método de máximo declive, o que nos permitiu propor uma nova escolha para o tamanho de passo. Com isso, propomos alguns novos algoritmos Cauchy-short, alternated Cauchy-short e outros) que alternam o tamanho de passo entre passos de Cauchy e passos curtos. Adotamos, ainda, uma nova proposta que utiliza passos de tamanhos dados por raízes de um polinômio de Chebyshev de ordem adequada. Experimentalmente, os novos métodos apresentam um bom desempenho, superando inclusive o método de Barzilai-Borwein. Além do bom desempenho, os novos métodos têm a vantagem de gerar sequências monotonicamente decrescentes de valores da função objetivo. Abstract : In this thesis we show a detailed description of the steepest descent method for quadratic problems with exact line searches (Cauchy Method). Although this method is globally convergent, it is inefficient because it is slow and it shows an oscillatory behavior, converging to a search in the space spanned by the eigenvectors associated with the largest and the smallest eigenvalue of the Hessian matrix of the quadratic objective. We analyze the oscillatory behavior of the gradient of the objective function in the quadratic case as well as the sequence of steps generated by the Cauchy method. We describe the Barzilai-Borwein method, which experimentally shows a better performance than the Cauchy method, and also some of its variations. We analyzed the behavior of the gradients due to the choice of different step sizes in the steepest descent method, which allowed us to come up with a new choice for the step size. Thus, we introduce a few new algorithms (Cauchy-short, alternated Cauchy-short and others) which alternate the step sizes between Cauchy steps and short steps. We also describe a new strategy based on step sizes given by the roots of a Chebyshev polynomial with suitable order. Experimentally, the new algorithms show a good enough performance, even better than the Barzilai-Borwein method. Besides the good performance, the new methods have the advantage of generating monotonically decreasing objective function values.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas. Programa de Pós-Graduação em Matemática e Computação Científica. Neste trabalho ser´a apresentado o programa POLIEDRO V1 que tem como objetivo visualizar poliedros limitados (em R2 e R3), para auxiliar na compreens#ao da evoluc¸#ao dos algoritmos Simplex e Branch-and-Bound. Primeiramente, ser#ao estudados alguns conceitos fundamentais de otimizac¸ #ao irrestrita e restrita, as condic¸ #oes de otimalidade e o problema dual em Programac¸ #ao Linear (PL). A segunda fase do texto concentra-se no estudo te´orico de poliedros, formas de representar poliedros e caracterizac¸ #ao de faces. Ap´os, ´e apresentado o programa POLIEDRO V1 em linguagem Matlab, que consiste em visualizar politopos, gerando faces atrav´es da selec¸ #ao e ordenac¸ #ao de v´ertices. A ´ultima fase do trabalho concentra-se no estudo e desenvolvimento dos algoritmos Simplex e Branch-and-Bound. Aplica-se o programa POLIEDRO V1 em Programac¸ #ao Linear visualizando a regi#ao vi´avel como politopo e apresentase a evoluc¸ #ao, passo a passo, do m´etodo Simplex. J´a em Programac¸ #ao Inteira (PI) visualiza-se graficamente o m´etodo Branch-and-Bound, resolvendo o problema de Programac¸ #ao Linear Inteira (PLI) atrav´es de subproblemas gerados por planos de corte. Os subproblemas s#ao resolvidos recursivamente pelo m´etodo Simplex. This work presents the program POLIEDRO V1, whose objective is to visualize bounded polyhedra in R2 and R3, to help the understanding of the evolution of the simplex and branch and bound algorithms. Initially some fundamental concepts in unconstrained and constrained optimization are studied, including the optimality conditions and the dual problem in Linear Programming. The second part of the text is dedicated to the theoretical study of polyhedra, ways of representing polyhedra and the characterization of faces. The program POLIEDRO V1 is then presented in the languageMatlab, consisting in the visualization of polytopes by generating facets through the selection and ordering of vertices. The last phase of the work concentrates on the study and development of the Simplex and Branch-and-Bound algorithms. The program POLIEDRO V1 is applied to visualize the feasible region of a linear programming problem, on which the step by step evolution of the simplex method is drawn. In Integer Programming, the branch-and-bound algorithm is graphically represented by solving recursively the linear programming subproblems generated by adding cutting planes. These subproblems are solved by the simplex method and visualized.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas. Programa de Pós-Graduação em Matemática e Computação Científica.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas. Programa de Pós-Graduação em Matemática e Computação Científica. Neste trabalho nós estudamos alguns métodos de Programação não Linear restrita e irrestrita dando ênfase ao problema que dá título a esta dissertação. No primeiro capítulo são estudados e enunciados métodos como os de Cauchy, Newton, Armijo, Região de Confiança e Dog Leg. No segundo, estudamos Programação Quadrática Seqüencial (PQS) pelo método de Restauração Inexata, que executa em cada iteração um passo de viabilidade e um de otimalidade. Nosso objetivo específico foi tratar do passo de otimalidade, conhecido como passo tangente do PQS, que na nossa proposta consiste em minimizar uma quadrática convexa numa caixa sobre uma variedade afim. Neste sentido, o terceiro capítulo surge para tratar do problema de barreira com o objetivo de definir centro analítico de um poliedro e trajetória central primal. Conceitos de muita importância para resolver, no último capítulo, o problema de minimização de uma quadrática convexa numa caixa sobre uma variedade afim. No tratamanto deste, utilizamos um método de pontos interiores primal-dual de trajetória central, em que nossa escolha de um ponto inicial primal-dual viável é original, representando um novo resultado em Matemática.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Elétrica.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro de Ciências Físicas e Matemáticas. Programa de Pós-Graduação em Matemática e Computação Científica. Neste trabalho apresentamos alguns aspectos computacionais e testes

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção. Neste trabalho apresentamos alguns exemplos de trajetória central mal comportada em otimização convexa. Alguns destes exemplos se parecem com uma antena de TV, contendo uma infinidade de segmentos horizontais de comprimento constante. Outros tem a forma de ziguezague com variação infinita. Mostramos que estes exemplos podem ocorrer mesmo que as funções envolvidas sejam infinitamente diferenciáveis. Apresentamos também, nesta tese, um algoritmo de filtro para programação não linear e provamos sua convergência global para pontos estacionários. Cada iteração é composta em duas fases totalmente independentes, e o único acoplamento entre elas é estabelecido pelo filtro. Sob hipóteses padrões, nós mostramos dois resultados: para o filtro com um tamanho mínimo, o algoritmo gera um ponto de acumulação estacionário; para um filtro levemente maior, todos os pontos de acumulação são estacionários.

Tese (doutorado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Produção Propomos uma nova metodologia para construção de funções de penalização para algoritmos de lagrangeano aumentado aplicados a problemas de programação convexa e com restrições. Métodos de lagrangeano aumentado partem normalmente de funções de penalização estritamente convexas e crescentes, que são combinadas com multiplicadores de lagrange m para compor termos de penalização com formato

Dissertação (Mestrado) - UNiversidade Federal de Santa Catarina, Centro de Ciencias Fisicas e Matematicas Apresentase uma prova geral do Teorema de Equivalencia que relaciona o Método de Ponto Proximal e o Método Lagrangeano Aumentado a qual inclui quase todos os casos existentes na literatura. Também mostramos novos resultados de unicidade a respeito da sequencia de multiplicadores (seqüência dual) gerada pelo algoritmo Lagrangeano Aumentado. Abstract : We present here a general proof of the well known Equivalence Theorem which relates the Proximal Point and the Augmented Lagrangian methods. This p.roof includes almost all the cases existent in the literature. Following a logical path we first do a detailed study of the Proximal Point method and its evolution since its introduction in 1970 until now when applied to the specific problem of minimizing a closed proper convex function. This subjet is very dispersed and so we have attempted to put order and simplicity in it by giving sufficient conditions for the Proximal Point algorithm to be well defined. Next we have described the Generalized Augmented Lagrangian method and we have proved the well-definiteness of the corresponding algorithm. Without making use of the relationship between the Proximal Point and the Augmented Lagrangian methods we have obtained new uniqueness results on the sequence of multipliers (dual sequence) generated by the Augmented Lagrangian algorithm. In order to prove the Theorem of Equivalence we defined the kernel to be used in the Proximal Point method as the summation of the conjugares of the penalties of the Augmented Lagrangian method and then we proved the well-definiteness of the associated Proximal Point algorithm when applied to the dual problem. Finally we proved that the sequences {µk} generated by each of the methods are indeed the same.

Dissertação (mestrado) - Universidade Federal de Santa Catarina. Centro de Ciências Físicas e Matemáticas. Neste trabalho analisamos, em particular, um algoritmo que segue a trajetória central associada a um problema de complementariedade linear monótona, gerando pontos em vizinhanças grandes da trajetória. Esse algoritmo baseia-se em passos que procuram uma aproximação rápida da face ótima do problema, e, quando houver necessidade, em passos corretores, que provocam uma aproximação à trajetória central. A trajetória central termina no ponto conhecido como ótimo central, que é o centro analítico da face ótima. Neste trabalho mostramos como este algoritmo gera seqüências que convergem para o ótimo central, e como o algoritmo de centralização é acelerado pela aproximação desse ponto.

Tese (doutorado) - Universidade Federal do Rio de Janeiro, Coordenação dos Programas de Pos-Graduação em Engenharia

Submitted by Algacilda Conceição (algacilda@sibi.ufrj.br) on 2018-04-05T15:57:04Z No. of bitstreams: 1 134158.pdf: 5683196 bytes, checksum: c1409c0d3a6d663d355d750044c37d71 (MD5) Made available in DSpace on 2018-04-05T15:57:04Z (GMT). No. of bitstreams: 1 134158.pdf: 5683196 bytes, checksum: c1409c0d3a6d663d355d750044c37d71 (MD5) Previous issue date: 1973-12 COPPETEC Universidade Federal de Ouro Preto Este trabalho resulta da implementação, em computador, de uma série de algoritmos destinados a resolver problemas vinculados e desvinculados da área de Programação Linear. Os métodos são apresentados de forma resumida e, em seguida, são expostos os algoritmos correspondentes. O trabalho é de cunho essencialmente prático e não houve, por este motivo, intenção de estabelecer desenvolvimentos teóricos inéditos, a menos de uma pequena ênfase sobre manipulação de precisões utilizadas pelos algoritmos. O sistema foi organizado de modo a oferecer facilidades de operação aos usuários que dele fizerem uso. This work is the result of the computer implementation of a set of nonlinear programming algorithms destined to solve constrained or unconstrained problems. The methods are concisely discussed after which the corresponding algorithms are presented. As the algorithms are approached from an essentially practical point of view, no original theoretical developments are pursued with the possible exception of some emphasis on the precision manipulations made by the algorithms. The system has been organized in order to provide to the user a good easiness in operation.

Submitted by Algacilda Conceição (algacilda@sibi.ufrj.br) on 2018-03-08T18:57:59Z No. of bitstreams: 1 124547.pdf: 3739764 bytes, checksum: 5f9f8259c7403fae27fe054a6a7208e5 (MD5) Made available in DSpace on 2018-03-08T18:57:59Z (GMT). No. of bitstreams: 1 124547.pdf: 3739764 bytes, checksum: 5f9f8259c7403fae27fe054a6a7208e5 (MD5) Previous issue date: 1971-04 Definimos problemas dinâmicos de transporte como problemas de transporte em redes com fluxo dinâmico. O modelo de redes com fluxo dinâmico formulado neste trabalho trata de redes que admitem em cada ramo, um fluxo entrante e um fluxo saliente não necessariamente iguais. Uma equação diferencial relaciona a diferença entre os fluxos entrante e saliente de um ramo, a um "acúmulo de material" no ramo. Com este tratamento, podemos estudar as redes como sistemas dinâmicos cujos controles são dados pelos fluxos. Resultados de dualidade permitem-nos encontrar soluções para os problemas de controle ótimo resultantes com descentralização dos controles. Dynamic transportation problems are defined as transportation problems in graphs with dynamic flow. The dynamic flow graph model presented in this work represents networks such that each branch admits as incoming flow and an outgoing flow, these flows not being necessarily equal. A differencial equation relates the difference between incoming and outgoing flows to an "accumulation of material" in the branch. This approach allows the study of graphs as dynamic systems the controls of which are given by the flows. Duality results lead to descentralized control solution for the optimal control problems formulated by the treatment above.

Submitted by Algacilda Conceição (algacilda@sibi.ufrj.br) on 2018-03-20T18:27:04Z No. of bitstreams: 1 129795.pdf: 4359286 bytes, checksum: 44fd9ca02fdbe523a1ac344491febbf1 (MD5) Made available in DSpace on 2018-03-20T18:27:04Z (GMT). No. of bitstreams: 1 129795.pdf: 4359286 bytes, checksum: 44fd9ca02fdbe523a1ac344491febbf1 (MD5) Previous issue date: 1972-08 Este trabalho trata da otimização de sistemas decomponíveis. Um problema decomponível de programação matemática é proposto e sua solução obtida por coordenação dual. Dois conceitos básicos que aparecem em programação matemática de sistemas de grande porte são usados: linearização externa e relaxação. Um algoritmo tipo plano cortante que permite o abandono de vínculos plenamente satisfeitos é obtido com base em resultados de teoria de dualidade. Sua aplicação ao problema linearizado externamente resulta em um método convergente para solução do problema original. Um programa de computador foi desenvolvido com este propósito. This work deals with the optimization of decomposable systems. A decomposable mathematical programming problem is proposed ans its solution is achieved by means of dual coordination. Two basic concepts arising in large scale mathematical programming are used: outer linearization and relaxation. A cutting plane algorithm without nested constraint sets is sinthetized based on results from duality theory. Its appication to the outer linearized problem results in a convergent method for the solution of the original problem. A computer program has been developed.

Submitted by Algacilda Conceição (algacilda@sibi.ufrj.br) on 2018-03-16T19:13:47Z No. of bitstreams: 1 130278.pdf: 5399051 bytes, checksum: 04fe5ab53ca6f5bf3abd35c033cdbc7d (MD5) Made available in DSpace on 2018-03-16T19:13:47Z (GMT). No. of bitstreams: 1 130278.pdf: 5399051 bytes, checksum: 04fe5ab53ca6f5bf3abd35c033cdbc7d (MD5) Previous issue date: 1972-09 Visando otimizar-se um sistema decomponível não-linear, estuda-se um algoritmo primal de direções viáveis. No decurso desse estudo formalizam-se e demonstram-se alguns resultados conhecidos e desenvolvem-se interpretações econômicas. Um critério para testar a diferenciabilidade das funções pertubação envolvidas no algoritmo é desenvolvido, podendo tal propriedade ser utilizada com vantagens computacionais. Rapidamente se discute o conceito de Ɛ-atividade de vínculos ligado à convergência do algoritmo. Finalmente, apresenta-se uma sub-rotina em FORTRAN IV que obtém, em cada iteração do algoritmo, uma direção viável. A primal feasible directions algorithm is studied to optimize non-linear decomposable systems. In the course of these studies some known results are formalized and proved, and economical interpretations are developed. A criterion is derived to detect the different hability of the pertubation functions involved in the algorithm, and this property is used with some computational advantages. The concept of Ɛ-activity of constraints is discussed, and related to the convergente of the algorithm. Finally, a FORTRAN IV subroutine is presented capable of finding a feasible direction in each iteration of the algorithm.