Made available in DSpace on 2015-04-22T22:16:10Z (GMT). No. of bitstreams: 1 Dissertacao Jeanne Moreira.pdf: 447774 bytes, checksum: 635ca33ffaf3746929571ab0aabcfd32 (MD5) Previous issue date: 2008-12-29 / FAPEAM - Fundação de Amparo à Pesquisa do Estado do Amazonas / In this work we use the gradient method to minimize, without restrictions, convex and pseudoconvex continuously differentiable functions. An important theme considered is the path length determination. We have that, when minimizing pseudoconvex functions, the linear search is exact. In this case, we present the first algorithm to obtain the path length, where will be included a quadratic regularization term, in the proximal point method sense. When dealing with the minimization of convex functions case, we have that the linear search is not exact. To obtain the path length, two algorithms are presented: the former needs that the gradient of the objective function satisfies a Lipschitz condition with a known constant L > 0. The latter is based on the work of Dennis-Schnabel (see [4]). The three process are based on the quasi-Fejér convergence principle. Although these descent methods need that the objective functions to be minimized have bounded level sets, in order to establish that the limit points are stationary, this approach guarantees the complete convergence of every sequence to a minimizer of the function without the hypothesis of bounded level sets. / Neste trabalho utilizamos o método do gradiente para minimizar, sem restrições, funções continuamente diferenciáveis pseudo-convexas e convexas. Um termo considerado importante é o cálculo do comprimento do passo. Na minimização de funções pseudo-convexas a busca linear é exata. Neste caso, apresentamos o primeiro algoritmo para o cálculo do comprimento do passo, onde é acrescentado um termo de regularização quadrático no sentido do método do ponto proximal. Posteriormente, na minimização de funções convexas, a busca linear é inexata. Para o cálculo do comprimento do passo apresentamos dois algoritmos: um necessita que o gradiente da função objetivo satisfaça uma condição de Lipschitz com constante L > 0 conhecida, e o outro é baseado no trabalho desenvolvido por Dennis-Schnabel (ver [4]). Os três processos baseiam-se na noção da quase-Fejér convergência. Embora os métodos de descida necessitem que a função objetivo a ser minimizada possua conjuntos de níveis limitados a fim de estabelecer que os pontos de acumulação sejam estacionários, nesta abordagem é garantida a convergência completa de toda sequência para um minimizador da função sem a hipótese de limitação do conjunto de nível.

Este trabalho é focado num problema clássico das Ciências e Engenharia, que consiste em cobrir um objeto por esferas de mesmo raio, a ser minimizado. A abordagem prática usual conta com sérias desvantagens. Logo, faz-se necessário trabalhar com isto de forma diferenciada. A técnica proposta aqui envolve a utilização de resultados célebres da geometria algébrica real, que tem como peça central o positivstellensatz de Stengle e, fazendo a devida relação entre esses resultados e otimização com restrições envolvendo representações naturais por somas de quadrados, é possível reduzir o problema original a um de programação semidefinida não linear. Mas, por contar com particularidades que favorecem a aplicação do paradigma de restauração inexata, esta foi a técnica utilizada para resolvê-lo. A versatilidade da técnica e a possibilidade de generalização direta dos objetos envolvidos destacam-se como grandes vantagens desta abordagem, além da visão algébrica inovadora do problema. / This work is focused on a classic problem from Engineering. Basically, it consists of finding the optimal positioning and radius of a set of equal spheres in order to cover a given object. The common approach to this carries some substantial disadvantages, what makes it necessary to nd a dierent way. Here, we explore some renowned results from real algebraic geometry, which has Stengle\'s positivstellensatz as one of its central pieces, and SOS optimization. Once the proper link is made, the original problem can be reduced to a nonlinear semidenite programming one, which has peculiarities that favours the application of an inexact restoration paradigm. We point out the algebraic view and the no use of discretizations as great advantages of this approach, besides the notable versatility and easy generalization in terms of dimension and involved objects.

Este trabalho é focado num problema clássico das Ciências e Engenharia, que consiste em cobrir um objeto por esferas de mesmo raio, a ser minimizado. A abordagem prática usual conta com sérias desvantagens. Logo, faz-se necessário trabalhar com isto de forma diferenciada. A técnica proposta aqui envolve a utilização de resultados célebres da geometria algébrica real, que tem como peça central o positivstellensatz de Stengle e, fazendo a devida relação entre esses resultados e otimização com restrições envolvendo representações naturais por somas de quadrados, é possível reduzir o problema original a um de programação semidefinida não linear. Mas, por contar com particularidades que favorecem a aplicação do paradigma de restauração inexata, esta foi a técnica utilizada para resolvê-lo. A versatilidade da técnica e a possibilidade de generalização direta dos objetos envolvidos destacam-se como grandes vantagens desta abordagem, além da visão algébrica inovadora do problema. / This work is focused on a classic problem from Engineering. Basically, it consists of finding the optimal positioning and radius of a set of equal spheres in order to cover a given object. The common approach to this carries some substantial disadvantages, what makes it necessary to nd a dierent way. Here, we explore some renowned results from real algebraic geometry, which has Stengle\'s positivstellensatz as one of its central pieces, and SOS optimization. Once the proper link is made, the original problem can be reduced to a nonlinear semidenite programming one, which has peculiarities that favours the application of an inexact restoration paradigm. We point out the algebraic view and the no use of discretizations as great advantages of this approach, besides the notable versatility and easy generalization in terms of dimension and involved objects.

Orientador: Marcia Aparecida Gomes Ruggiero / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-16T01:38:07Z (GMT). No. of bitstreams: 1 Reis_DiegoDerivaldodos_M.pdf: 1640617 bytes, checksum: 7bb1fcda0049b1ac1e6645b7ce8789eb (MD5) Previous issue date: 2010 / Resumo: Uma das estratégias empregadas para resolver vim problema de programação não linear com restrições é usar métodos iterativos que geram uma seqüência de pontos viáveis. A razão é que frequentemente soluções viáveis são úteis em aplicações da engenharia, física ou química, ao contrário das aproximações não viáveis, até mesmo quando estas estão bem próximas do valor ótimo. Porém, quando lidamos com restrições não lineares não suaves, é difícil manter viabilidade e, simultaneamente, melhorar o valor da função objetivo. Uma alternativa é empregar métodos de Restauração Inexata. Em linhas gerais, nestes métodos, a cada iteração dois novos pontos são gerados, um que visa melhorar a viabilidade e outro que diminui o valor da função objetivo. Um terceiro ponto é obtido de modo a atingir um decréscimo mínimo de uma função de mérito composta pelos dois primeiros pontos e que busca o equilíbrio entre viabilidade e otimalidade. Ao processo de encontrar o ponto que melhora a viabilidade, damos o nome de restauração e o objetivo central deste trabalho é analisar esta fase. Analisamos problemas de otimização onde as restrições são não lineares acrescidas por restrições de canalização (limitantes inferior e superior para as variáveis). Para realizar a restauração usamos o método proposto por J. B. Francisco, N. Krejic e J. M. Martinez [11], no qual são considerados sistemas não lineares com restrições de canalização e que faz uso de uma estratégia de região dc confiança com escalamento. O método de Restauração Inexata que usamos é baseado no algoritmo proposto por M. A. Gomes Ruggiero, J. M. Martinez e S. A. Santos [13] que emprega a direção do gradiente espectral projetado [4] para resolver o problema, de hard-spheres. onde a restauração pode ser sempre feita de maneira exata. Neste trabalho resolvemos problemas nos quais a fase de restauração não é necessariamente feita de maneira exata. Os testes computacionais, realizados com problemas acadêmicos, atestam a eficiência do esquema proposto. Usando o algoritmo proposto em [11] para realizar a fase de restauração, implementamos no software MatLab 7.7 o algoritmo do método de Restauração Inexata, encontrado em [13], utilizando o mesmo conjunto de problemas teste usados em [11] além de outros encontrados em [14], obtendo bons resultados / Abstract: One of the strategies employed to solve a nonlinear programming problem with constraints is to use iterative methods that generate a sequence of points feasible. The reason is that viable solutions are often useful in applications engineering, physics or chemistry, unlike the approaches are not viable, even when they are very close to the optimum value. But when dealing with soft constraints nonlinear, it is difficult to maintain viability and, simultaneously, improve the value of the objective function. An alternative is to employ methods of Inexact Restoration. In general, these methods, each iteration two new points are generated, one that aims to improve the viability and another that decreases the value of the objective function. A third point is obtained in order to achieve a decrease of at least a merit function consisting of the first two points and that seeks a balance between feasibility and optimality. The process of finding the point that improves the viability, we give the name of restoration and purpose of this paper is to analyze this phase. We analyze optimization problems where the constraints are nonlinear constraints added by channeling (lower and upper bounds for variables). To accomplish the restoration we use the method proposed by Mr B. Francis, N. Kreji'c and J. M. Martinez [11], which are considered non-linear systems with restricted channel that uses a trust region strategy with scaling. The Inexact restoration method we use is based on the algorithm proposed by M. A. Gomes Ruggiero, J. M. Martinez and S. A. Santos [13] that employs the spectral projected gradient direction [4] to solve the problem of hard-spheres, where the restoration can be done in exactly. Present paper, problems in which phase of restoration is not necessarily done exactly. The computational tests carried out with academic problems, proving the efficiency of the proposed scheme. Using the algorithm proposed in [11] to accomplish the restoration phase, implemented in MatLab 7.7 the algorithm of the method of Inexact Restoration, found in [13], using the same set of test problems used in [11] and other found in [14], obtaining good results / Mestrado / Otimização / Mestre em Matemática Aplicada

Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial. Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema. / Let GI = (VI ,AI) and GM = (VM,AM) be two simple graphs. A mapping from GI to GM is an association set, such that each vertex in VI is associated to a vertex in VM, and each edge in AI is associated to a pair of vertices of VM. A cost is defined to each possible association. The inexact graph correspondence problem (IGCP) consists in finding a mapping from GI to GM, such that the sum of its associations costs is minimized. In this dissertation, we summarize the results found in the literature about the IGCP and some variations. The results included here address the question of how to formulate the IGCP and some variations, using integer linear programming. We prove some computational complexity results which relate IGCP variations with classical problems, like graph isomorphism and partitioning. We give an integer linear programming formulation to the ICEC (IGCP with connectivity and edges cover). We show that the ICEC is NP-hard when the input graphs are complete or trees (we call the second case ICEC for trees). We introduce an integer linear formulation and an algorithm - which has polynomial running time if the vertices of VM have maximum degree bounded by a constant - to the ICEC for trees. We show a especial case in which the ICEC for trees can be solved in polynomial time. Finally, we present some experimental results, also with instances of a real application of the problem.

[pt] Esta dissertação apresenta novos algoritmos aproximados e uma abordagem exata para a resolução de um problema de correspondência inexata de grafos. O problema considerado é o de correspondência entre um grafo representando um modelo genérico e outro representando dados a serem reconhecidos. Assumi-se que o grafo dos dados possui mais vértices que o do modelo. A motivação para o estudo desse problema vem de problemas de reconhecimento de cenas, que consistem na caracterização dos objetos envolvidos em uma determinada cena, assim como das relações existentes entre eles. Uma aplicação para este problema na área de reconhecimento de imagens médicas é a de efetuar-se o reconhecimento de estruturas 3D do cérebro humano, a partir de imagens obtidas por ressonância magnética. Tais imagens são previamente processadas por algum método de segmentação automática e o processo de reconhecimento consiste na busca da correspondência estrutural entre a imagem e um modelo genérico, tipicamente definido como um atlas de imagens médicas. Foram propostos novos algoritmos aproximados, tais como um algoritmo construtivo guloso aleatorizado, um procedimento de reconexão de caminhos e um GRASP que combina estes com uma técnica de busca local. Além disso, foi proposta uma formulação original do problema como um problema de programação linear inteira, que permitiu a resolução de algumas instâncias de forma exata. / [en] This dissertation presents new approximation algorithms and an exact approach to the solution of an inexact graph matching problem. The problem consists in finding the best match between a generic model graph and a graph representing an image, the latter with more nodes than the former. The motivation for studying this problem comes from a scene recognition problem, which consists in characterizing objects involved in a given scene and the relationships between them. An application of this problem appears in the analysis of medical images and consists in recognizing 3-dimensional structures in the human brain using images obtained by magnetic resonance. Such images must be previously processed by an automatic segmentation method and the recognition process consists in the search of an structural matching between the image and a generic model, typically defined as an atlas of medical images. New heuristics are proposed, such as a greedy randomized construction algorithm, a path relinking procedure and a GRASP heuristic that combines them with a local search technique. Furthermore, an original integer formulation of the problem based on integer multicommodity flows is proposed, which makes possible the exact solution of medium- sized instances.

Sejam GI = (VI ,AI) e GM = (VM,AM) dois grafos simples. Um mapeamento de GI para GM é um conjunto de associações, tal que cada vértice de VI está associado a um vértice de VM, e cada aresta de AI está associada a um par de vértices de VM. A cada possível associação é atribuído um custo. O problema de correspondência inexata entre grafos (PCIG) consiste em encontrar um mapeamento de GI para GM, tal que a soma dos custos de suas associações seja mínima. Nesta dissertação, resumimos os resultados encontrados na literatura sobre o PCIG e algumas de suas variações. Os resultados que incluímos aqui tratam sobre a questão de como formular o PCIG e algumas de suas variações, através de programação linear inteira. Provamos alguns resultados de complexidade computacional que relacionam variações do PCIG a problemas clássicos, como isomorfismo e partição de grafos. Fornecemos uma formulação através de programação linear inteira para o PCCA (uma variante do PCIG com conexidade e cobertura de arestas). Mostramos que o PCCA é NP-difícil quando os grafos de entrada são completos ou árvores (chamamos o segundo caso de PCCA para árvores). Apresentamos uma formulação linear inteira e um algoritmo - que é polinomial se o grau máximo dos vértices de VM for limitado por uma constante - para o PCCA para árvores. Mostramos um caso especia em que o PCCA para árvores pode ser resolvido em tempo polinomial. Por último, exibimos alguns resultados experimentais, inclusive com instâncias reais de uma aplicação do problema. / Let GI = (VI ,AI) and GM = (VM,AM) be two simple graphs. A mapping from GI to GM is an association set, such that each vertex in VI is associated to a vertex in VM, and each edge in AI is associated to a pair of vertices of VM. A cost is defined to each possible association. The inexact graph correspondence problem (IGCP) consists in finding a mapping from GI to GM, such that the sum of its associations costs is minimized. In this dissertation, we summarize the results found in the literature about the IGCP and some variations. The results included here address the question of how to formulate the IGCP and some variations, using integer linear programming. We prove some computational complexity results which relate IGCP variations with classical problems, like graph isomorphism and partitioning. We give an integer linear programming formulation to the ICEC (IGCP with connectivity and edges cover). We show that the ICEC is NP-hard when the input graphs are complete or trees (we call the second case ICEC for trees). We introduce an integer linear formulation and an algorithm - which has polynomial running time if the vertices of VM have maximum degree bounded by a constant - to the ICEC for trees. We show a especial case in which the ICEC for trees can be solved in polynomial time. Finally, we present some experimental results, also with instances of a real application of the problem.