Made available in DSpace on 2014-07-29T16:02:20Z (GMT). No. of bitstreams: 1 Dissertacao-Jose Henrique Salazar do Amaral.pdf: 346281 bytes, checksum: ed448001994e6dc5edb294a83390961a (MD5) Previous issue date: 2012-06-27 / This paper presents an analysis of convergence of the proximal point method for functions that satisfy the inequality of Lojasiewicz. / Neste trabalho é feita uma análise de convergência do Método do Ponto Proximal para funções não necessariamente convexas que satisfazem a desigualdade de Łojasiewicz.

Este trabalho insere-se no contexto de métodos de multiplicadores para a resolução de problemas de programação convexa semidefinida e a análise de suas propriedades através do método proximal aplicado sobre o problema dual. Nosso foco será uma subclasse de problemas de programação convexa semidefinida com restrições afins, para a qual estudaremos relações de dualidade e condições para a existência de soluções dos problemas primal e dual. Em seguida, analisaremos dois métodos de multiplicadores para resolver essa classe de problemas e que são extensões de métodos conhecidos para programação não-linear. O primeiro, proposto por Doljansky e Teboulle, aborda um método de ponto proximal interior entrópico e sua conexão com um método de multiplicadores exponenciais. O segundo, apresentado por Mosheyev e Zibulevsky, estende para a classe de problemas de nosso interesse um método de lagrangianos aumentados suaves proposto por Ben-Tal e Zibulevsky. Por fim, apresentamos os resultados de testes numéricos feitos com o algoritmo proposto por Mosheyev e Zibulevsky, analisando diferentes escolhas de parâmetros, o aproveitamento do padrão de esparsidade das matrizes do problema e critérios para a resolução aproximada dos subproblemas irrestritos que devem ser resolvidos a cada iteração desse algoritmo de lagrangianos aumentados. / This work deals with multiplier methods to solve semidefinite convex programming problems and the analysis of their proprieties based on the proximal point method applied on the dual problem. We focus on a subclass of semidefinite programming problems with affine constraints, for which we study duality relations an conditions for the existence of solutions of the primal and dual problems. Afterwards, we analyze two multiplier methods to solve this class of problems which are extensions of known methods in nonlinear programming. The first one, introduced by Doljansky e Teboulle, approaches an entropic interior proximal algorithm and their relationship with an exponential multiplier method. The second one, presented by Mosheyev e Zibulevsky, extends a smooth augmented Lagrangian method proposed by Ben-Tal and Zibulevsky for the problems of our interest. Finally, we present the results of numerical experiments for the algorithm proposed by Mosheyev e Zibulevsky, analyzing some choices of parameters, the sparsity patterns of matrices of the problem and criteria to accept approximate solutions of the unconstrained subproblems that must be solved at each iteration of the augmented Lagrangian method.

Problemas reais em áreas como aprendizado de máquina têm chamado atenção pela enorme quantidade de variáveis (> 10^6) e volume de dados. Em problemas dessa escala o custo para se obter e trabalhar com informações de segunda ordem são proibitivos. Tais problemas apresentam características que podem ser aproveitadas por métodos de busca em coordenada. Essa classe de métodos é caracterizada pela alteração de apenas uma ou poucas variáveis a cada iteração. A variante do método comumente descrita na literatura é a minimização cíclica de variáveis. Porém, resultados recentes sugerem que variantes aleatórias do método possuem melhores garantias de convergência. Nessa variante, a cada iteração, a variável a ser alterada é sorteada com uma probabilidade preestabelecida não necessariamente uniforme. Neste trabalho estudamos algumas variações do método de busca em coordenada. São apresentados aspectos teóricos desses métodos, porém focamos nos aspectos práticos de implementação e na comparação experimental entre variações do método de busca em coordenada aplicados a diferentes problemas com aplicações reais. / Real world problemas in areas such as machine learning are known for the huge number of decision variables (> 10^6) and data volume. For such problems working with second order derivatives is prohibitive. These problems have properties that benefits the application of coordinate descent/minimization methods. These kind of methods are defined by the change of a single, or small number of, decision variable at each iteration. In the literature, the commonly found description of this type of method is based on the cyclic change of variables. Recent papers have shown that randomized versions of this method have better convergence properties. This version is based on the change of a single variable chosen randomly at each iteration, based on a fixed, but not necessarily uniform, distribution. In this work we present some theoretical aspects of such methods, but we focus on practical aspects.

Neste trabalho, estudamos o problema a recoloração convexa de grafos, denotado por RC. Dizemos que uma coloração dos vértices de um grafo G é convexa se, para cada cor tribuída d, os vértices de G com a cor d induzem um subgrafo conexo. No problema RC, é dado um grafo G e uma coloração de seus vértices, e o objetivo é recolorir o menor número possível de vértices de G tal que a coloração resultante seja convexa. A motivação para o estudo deste problema surgiu em contexto de árvores filogenéticas. Sabe-se que este problema é NP-difícil mesmo quando G é um caminho. Mostramos que o problema RC parametrizado pelo número de mudanças de cor é W[2]-difícil mesmo se a coloração inicial usa apenas duas cores. Além disso, provamos alguns resultados sobre a inaproximabilidade deste problema. Apresentamos uma formulação inteira para a versão com pesos do problema RC em grafos arbitrários, e então a especializamos para o caso de árvores. Estudamos a estrutura facial do politopo definido como a envoltória convexa dos pontos inteiros que satisfazem as restrições da formulação proposta, apresentamos várias classes de desigualdades que definem facetas e descrevemos os correspondentes algoritmos de separação. Implementamos um algoritmo branch-and-cut para o problema RC em árvores e mostramos os resultados computacionais obtidos com uma grande quantidade de instâncias que representam árvores filogenéticas reais. Os experimentos mostram que essa abordagem pode ser usada para resolver instâncias da ordem de 1500 vértices em 40 minutos, um desempenho muito superior ao alcançado por outros algoritmos propostos na literatura. / In this work we study the convex recoloring problem of graphs, denoted by CR. We say that a vertex coloring of a graph G is convex if, for each assigned color d, the vertices of G with color d induce a connected subgraph. In the CR problem, given a graph G and a coloring of its vertices, we want to find a recoloring that is convex and minimizes the number of recolored vertices. The motivation for investigating this problem has its roots in the study of phylogenetic trees. It is known that this problem is NP-hard even when G is a path. We show that the problem CR parameterized by the number of color changes is W[2]-hard even if the initial coloring uses only two colors. Moreover, we prove some inapproximation results for this problem. We also show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and the corresponding separation algorithms. We also present a branch-and-cut algorithm that we have implemented for the special case of trees, and show the computational results obtained with a large number of instances. We considered instances which are real phylogenetic trees. The experiments show that this approach can be used to solve instances up to 1500 vertices in 40 minutes, comparing favorably to other approaches that have been proposed in the literature.

[pt] Nesse trabalho, estudamos online packing integer programs, cujas colunas são reveladas uma a uma. Já que algoritmos ótimos foram encontrados para o modelo RANDOMORDER– onde a ordem na qual as colunas são reveladas para o algoritmo é aleatória – o foco da área se voltou para modelo menos otimistas. Um desses modelos é o modelo MIXED, no qual algumas colunas são ordenadas de forma adversária, enquanto outras chegam em ordem aleatória. Pouquíssimos resultados são conhecidos para online packing IPs no modelo MIXED, que é o objeto do nosso estudo. Consideramos problemas de online packing com d dimensões de ocupação (d restrições de empacotamento), cada uma com capacidade B. Assumimos que todas as recompensas e ocupações dos itens estão no intervalo [0, 1]. O objetivo do estudo é projetar um algoritmo no qual a presença de alguns itens adversários tenha um efeito limitado na competitividade do algoritmo relativa às colunas de ordem aleatória. Portanto, usamos como benchmark OPTStoch, que é o valor da solução ótima offline que considera apenas a parte aleatória da instância. Apresentamos um algoritmo que obtém recompensas de pelo menos (1 − 5lambda − Ó de epsilon)OPTStoch com alta probabilidade, onde lambda é a fração de colunas em ordem adversária. Para conseguir tal garantia, projetamos um algoritmo primal-dual onde as decisões são tomadas pelo algoritmo pela avaliação da recompensa e ocupação de cada item, de acordo com as variáveis duais do programa inteiro. Entretanto, diferentemente dos algoritmos primais-duais para o modelo RANDOMORDER, não podemos estimar as variáveis duais pela resolução de um problema reduzido. A causa disso é que, no modelo MIXED, um adversário pode facilmente manipular algumas colunas, para atrapalhar nossa estimação. Para contornar isso, propomos o uso de tecnicas conhecidas de online learning para aprender as variáveis duais do problema de forma online, conforme o problema progride. / [en] We study online packing integer programs, where the columns arrive one by one. Since optimal algorithms were found for the RANDOMORDER model – where columns arrive in random order – much focus of the area has been on less optimistic models. One of those models is the MIXED model, where some columns are adversarially ordered, while others come in random-order. Very few results are known for packing IPs in the MIXED model, which is the object of our study. We consider online IPs with d occupation dimensions (d packing constraints), each one with capacity (or right-hand side) B. We also assume all items rewards and occupations to be less or equal to 1. Our goal is to design an algorithm where the presence of adversarial columns has a limited effect on the algorithm s competitiveness relative to the random-order columns. Thus, we use OPTStoch – the offline optimal solution considering only the random-order part of the input – as a benchmark.We present an algorithm that, relative to OPTStoch, is (1−5 lambda− OBig O of epsilon)-competitive with high probability, where lambda is the fraction of adversarial columns. In order to achieve such a guarantee, we make use of a primal-dual algorithm where the decision variables are set by evaluating each item s reward and occupation according to the dual variables of the IP, like other algorithms for the RANDOMORDER model do. However, we can t hope to estimate those dual variables by solving a scaled version of problem, because they could easily be manipulated by an adversary in the MIXED model. Our solution was to use online learning techniques to learn all aspects of the dual variables in an online fashion, as the problem progresses.

[pt] Motivado por problemas no campo da recuperação de sinais por programação convexa, o objetivo deste trabalho é fornecer uma análise precisa do método das bola pequena e suas conexões com a teoria não assintótica das matrizes aleatórias. Em particular, o estudo dos valores singulares cônicos de matrizes aleatórias desempenhará um papel fundamental na análise de tais problemas. / [en] Motivated by problems in the field of signal recovery by convex programming, the aim of this work is to provide a careful analysis of the celebrated small ball method and its connections with the non-asymptotic theory of random matrices. In particular, the study of the conic singular values of random matrices will play a key role to analyze such problems.

Submitted by Fabricia Fialho Reginato (fabriciar) on 2015-07-08T01:19:32Z No. of bitstreams: 1 VladimirGuerreiro.pdf: 5547701 bytes, checksum: b807e1f8091b49a5ee1e0b36e2ae4286 (MD5) / Made available in DSpace on 2015-07-08T01:19:32Z (GMT). No. of bitstreams: 1 VladimirGuerreiro.pdf: 5547701 bytes, checksum: b807e1f8091b49a5ee1e0b36e2ae4286 (MD5) Previous issue date: 2014 / Nenhuma / Em ambientes paralelos, uma das alternativas para tratar o dinamismo, tanto em nível de infraestrutura quanto de aplicação é o uso de migração, principalmente em aplicações que executam em fases utilizando BSP (Bulk Synchronous Parallel). Neste contexto, o modelo de reescalonamento MigBSP foi desenvolvido para tratar da realocação de processos em aplica- ções paralelas. Assim como o modelo BSP, ele considera as três fases de execução de uma superetapa: (i) computação local, (ii) comunicação global e (iii) uma barreira de sincroniza- ção; coletando dados localmente durante a computação para efetuar o cálculo do Potencial de Migração (PM) do processo. Com o PM e parâmetros adicionais fornecidos no inicio da execução da aplicação, o MigBSP tem condições de escolher processos candidatos a migração em uma aplicação paralela executando em um ambiente distribuído. Entretanto, as duas heurísticas possíveis de serem utilizadas hoje, dependem de informações fornecidas pelo usuário e/ou podem não selecionar uma quantidade eficiente de processos no momento do reescalonamento, podendo ser necessário várias chamadas para balancear o ambiente. Desta forma, esta disserta- ção apresenta duas novas heurísticas, MigCube e MigHull. Elas utilizam o MigBSP e efetuam a seleção automática de processos candidatos à migração sem a interferência do programador. As informações fornecidas pelo MigBSP são utilizadas nas heurísticas, a combinação das três métricas mensurados, posicionadas em um plano tridimensional, define cada processo como um ponto no espaço que possui as coordenadas x, y e z, onde cada eixo representa uma mé- trica para tomada de decisão. A heurística MigCube monta um cubo a partir das médias das distâncias entre os pontos, utilizando o processo com o maior PM como centro do cubo. A heurística MigHull segue a definição da Envoltória Convexa, tentando envolver todos os pontos, porém utilizando duas adaptações que se fazem necessárias para a aplicação neste trabalho. O MigBSP foi desenvolvido no simulador SimGrid, e este segue sendo utilizado para a criação das duas heurísticas apresentadas nesta dissertação. Nos testes realizados neste simulador, foi possível verificar um ganho de até 45% no tempo de execução da aplicação utilizando a heurística MigHull, e até 42% utilizando a MigCube, quando comparado a aplicação sem o modelo de migração. Porém, em simulações com um maior número de processos, este ganho tende a cair, já que um dos maiores problemas do BSP e aplicações que executam em grades é o tempo de sincronização de tarefas, ou seja, quanto mais processos, maior a necessidade de sincronização, e mesmo o balanceamento dos processos acaba tendo um resultado prejudicado. / In a parallel environment, one of the alternatives to address the dynamism, both at the infrastructure and application levels, is the use of migration, mostly with applications that execute in steps using BSP (Bulk Synchronous Parallel). In this context, the rescheduling model MigBSP was developed to deal with processes reallocation in parallel applications. As BSP model, MigBSP uses the three steps of a superstep: (i) computation, (ii) communication and (iii) a synchronization barrier; collecting local data during the computation step, to compute the processes’ Potential of Migration (PM). With the PM and additional parameters provided in the beginning of the application’s execution, MigBSP have conditions to choose the processes candidate to migrate in a parallel application running in a distributed system. However, the two heuristics possible to be used today depend of information provided by the user and/or may not select the proper quantity of processes in the rescheduling moment, being necessary many executions to balance the environment. This way, this dissertation present two new heuristics, MigCube and MigHull. They make use of MigBSP, and automatically will choose the processes to migrate without user interference. The information provided by MigBSP are used in the heuristics, the combination of the three measured metrics, positioned in a three-dimensional space, defines each process as a point in space and has the coordinates x, y e z, where each axis represents a metric for decision making. The MigCube heuristic build a cube from the average of the distances between points, using the process with the highest PM as the center of the cube. The MigHull follows the definition of a Convex Hull, trying to involve all points, but using two adaptations that are necessary to implement this work. The MigBSP was developed using SimGrid simulator, and it keeps being used to creation of the two heuristics presented in this dissertation. In the conducted tests in this simulator, was possible to achieve a gain of until 45% on application execution time using MigHull, and until 42% using MigCube, when compared with the application without the migration model. However, simulations with a bigger number of processes, this gain tends to fall, since one of the bigger problems of BSP and applications that run in grid is the time of tasks synchronization, that is, as more processes, more need of synchronization, and even the processes balancing ends up having an impaired outcome.

Made available in DSpace on 2016-12-23T14:33:35Z (GMT). No. of bitstreams: 1 dissertacao.pdf: 2646193 bytes, checksum: 043989a54d6611e19c06eb6bcd7bba69 (MD5) Previous issue date: 2006-06-23 / Neste trabalho é proposta uma estratégia de solução para a construção otimizada de distritos postais. Distrito Postal consiste num conjunto de segmento de eixo de logradouros conectados. Dada uma localidade formada por inúmeros segmentos de logradouros, esse trabalho propõe o arranjamento de subgrupos conexos de segmentos de eixos de logradouros de modo a compor um distrito postal. A estratégia é transformar o sistema de logradouros de uma localidade em um grafo. A partir desse grafo, extrair seus respectivos subgrafos cíclicos que são entendidos como entidades atômicas. Essas entidades atômicas passam por um processo de montagem até comporem um conjunto de distritos postais. A metodologia aqui apresentada divide o trabalho em duas fases distintas: a primeira compreende o processo de obtenção dos subgrafos cíclicos; e a segunda compreende o processo de montagem de distrito postal. O processo de obtenção de subgrafos cíclicos consiste na obtenção da envoltória convexa do grafo e posterior extração dos subgrafos cíclicos tangentes às arestas dessa. Isso de forma sequencial, ou seja, determina-se a primeira envoltória convexa do grafo e extraemse seus respectivos subgrafos tangentes; determina-se a segunda envoltória convexa e extraem-se seus subgrafos, e assim sucessivamente. O trabalho de determinação da envoltória convexa e de extração dos subgrafos cíclicos é feito através de operações da geometria computacional. O processo de construção dos distritos postais se dá através da clusterização dos subgrafos cíclicos, usando como ferramenta a meta-heurística Simulated Annealing. O problema do Carteiro Chinês e Carteiro Chinês Capacitado são formulações suporte para o presente trabalho. O objetivo principal do trabalho é obter, de forma rápida e eficiente o distrito postal otimizado, com menor percurso improdutivo possível, oferecendo agilidade no processo de distribuição domiciliária de objetos postais. / This study proposes a strategia solution for the optimized construction of postal districts. Postal District is a set of segments of publics areas connecteds. Given a locality composed of uncounted segments of publics areas, this study proposes an arrangement of connects subgroups of publics areas with the goal of composing a postal district. The strategy is to transform the system of public areas of a place in a graph and from this graph, to extract their respective cyclical subgraphs that are understood as atomics entities. Those atomics entities are submited by an assembly process until compose a group of postal districts. The methodology here presented divides the study in two different phases: the first one understands the process of obtaining of the cyclical subgraphs; and the second one is understood as the assembly process of postal district The process of obtaining of cyclical subgraph consists in the obtaining of the hull convex of the graph and subsequent extracting up the cyclical subgraphs tangent to edge of that. That is, in a sequential way, in other words, it is determined the first convex hull of the graph and extract up their respective tangent subgraphs; it is determined the second convex hull and extract up their subgraphs and so forth. The study of determination of the convex hull and extracting of the cyclical subgraphs is done through operations of the computational geometry. The process of construction of the postal districts is given through the clustering of the cyclicals subgraphs, using as a tool the meta- heuristic Simulated Annealing. The Chinese Postman's Problem and Capacited Chinese Postman's Problem are formulations support for the present study. The main objective of the study is to obtain, in a fast and efficient way the optimized postal district, with smaller unproductive course possible, offering agility for the process of domiciliary distribution of postal objects.

[pt] Esta tese investiga e desenvolve algoritmos baseados em relaxação Lagrangiana e técnica de desagregação multiparamétrica normalizada para resolver problemas não convexos de programação inteira-mista quadrática com restrições quadráticas. Primeiro, é realizada uma revisão de técnias de relaxação para este tipo de problema e subclasses do mesmo. Num segundo momento, a técnica de desagregação multiparamétrica normalizada é aprimorada para sua versão reformulada onde o tamanho dos subproblemas a serem resolvidos tem seu tamanho reduzido, em particular no número de variáveis binárias geradas. Ademais, dificuldas em aplicar a relaxação Lagrangiana a problemas não convexos são discutidos e como podem ser solucionados caso o subproblema dual seja substituído por uma relaxação não convexa do mesmo. Este método Lagrangiano modificado é comparado com resolvedores globais comerciais e resolvedores de código livre. O método proposto convergiu em 35 das 36 instâncias testadas, enquanto o Baron, um dos resolvedores que obteve os melhores resultados, conseguiu convergir apenas para 4 das 36 instâncias. Adicionalmente, mesmo para a única instância que nosso método não conseguiu resolver, ele obteve um gap relativo de menos de 1 por cento, enquanto o Baron atingiu um gap entre 10 por cento e 30 por cento para a maioria das instâncias que o mesmo não convergiu. / [en] This thesis investigates and develops algorithms based on Lagrangian relaxation and normalized multiparametric disaggregation technique to solve nonconvex mixed-integer quadratically constrained quadratic programming. First, relaxations for quadratic programming and related problem classes are reviewed. Then, the normalized multiparametric disaggregation technique is improved to a reformulated version, in which the size of the generated subproblems are reduced in the number of binary variables. Furthermore, issues related to the use of the Lagrangian relaxation to solve nonconvex problems are addressed by replacing the dual subproblems with convex relaxations. This method is compared to commercial and open source off-the-shelf global solvers using randomly generated instances. The proposed method converged in 35 of 36 instances, while Baron, the benchmark solver that obtained the best results only converged in 4 of 36. Additionally, even for the one instance the methods did not converge, it achieved relative gaps below 1 percent in all instances, while Baron achieved relative gaps between 10 percent and 30 percent in most of them.

The vertex coloring problem is a classic problem in graph theory that asks for a partition of the vertex set into a minimum number of stable sets. This thesis presents our studies on three vertex (re)coloring problems on graphs and on a problem related to a long-standing conjecture on subdivision of digraphs. Firstly, we address the convex recoloring problem in which an arbitrarily colored graph G is given and one wishes to find a minimum weight recoloring such that each color class induces a connected subgraph of G. We show inapproximability results, introduce an integer linear programming (ILP) formulation that models the problem and present some computational experiments using a column generation approach. The k-fold coloring problem is a generalization of the classic vertex coloring problem and consists in covering the vertex set of a graph by a minimum number of stable sets in such a way that every vertex is covered by at least k (possibly identical) stable sets. We present an ILP formulation for this problem and show a detailed polyhedral study of the polytope associated with this formulation. The last coloring problem studied in this thesis is the proper orientation problem. It consists in orienting the edge set of a given graph so that adjacent vertices have different in-degrees and the maximum in-degree is minimized. Clearly, the in-degrees induce a partition of the vertex set into stable sets, that is, a coloring (in the conventional sense) of the vertices. Our contributions in this problem are on hardness and upper bounds for bipartite graphs. Finally, we study a problem related to a conjecture of Mader from the eighties on subdivision of digraphs. This conjecture states that, for every acyclic digraph H, there exists an integer f(H) such that every digraph with minimum out-degree at least f(H) contains a subdivision of H as a subdigraph. We show evidences for this conjecture by proving that it holds for some particular classes of acyclic digraphs. / O problema de coloração de grafos é um problema clássico em teoria dos grafos cujo objetivo é particionar o conjunto de vértices em um número mínimo de conjuntos estáveis. Nesta tese apresentamos nossas contribuições sobre três problemas de coloração de grafos e um problema relacionado a uma antiga conjectura sobre subdivisão de digrafos. Primeiramente, abordamos o problema de recoloração convexa no qual é dado um grafo arbitrariamente colorido G e deseja-se encontrar uma recoloração de peso mínimo tal que cada classe de cor induza um subgrafo conexo de G. Mostramos resultados sobre inaproximabilidade, introduzimos uma formulação linear inteira que modela esse problema, e apresentamos alguns resultados computacionais usando uma abordagem de geração de colunas. O problema de k-upla coloração é uma generalização do problema clássico de coloração de vértices e consiste em cobrir o conjunto de vértices de um grafo com uma quantidade mínima de conjuntos estáveis de tal forma que cada vértice seja coberto por pelo menos k conjuntos estáveis (possivelmente idênticos). Apresentamos uma formulação linear inteira para esse problema e fazemos um estudo detalhado do politopo associado a essa formulação. O último problema de coloração estudado nesta tese é o problema de orientação própria. Ele consiste em orientar o conjunto de arestas de um dado grafo de tal forma que vértices adjacentes possuam graus de entrada distintos e o maior grau de entrada seja minimizado. Claramente, os graus de entrada induzem uma partição do conjunto de vértices em conjuntos estáveis, ou seja, induzem uma coloração (no sentido convencional) dos vértices. Nossas contribuições nesse problema são em complexidade computacional e limitantes superiores para grafos bipartidos. Finalmente, estudamos um problema relacionado a uma conjectura de Mader, dos anos oitenta, sobre subdivisão de digrafos. Esta conjectura afirma que, para cada digrafo acíclico H, existe um inteiro f(H) tal que todo digrafo com grau mínimo de saída pelo menos f(H) contém uma subdivisão de H como subdigrafo. Damos evidências para essa conjectura mostrando que ela é válida para classes particulares de digrafos acíclicos.