Orientador: Alberto Luiz Serpa / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-08-11T04:04:36Z (GMT). No. of bitstreams: 1 Mazoni_AlyssonFernandes_M.pdf: 2883879 bytes, checksum: a514d74c83605535d0c2eaf4a060356f (MD5) Previous issue date: 2008 / Resumo: Esta dissertação aborda técnicas modernas de controle robusto H8 para sistemas dinâmicos lineares. Com isso pretende-se dizer que são usados como ferramentas matemáticas os resultados da teoria de controle de sistemas lineares para o caso com incertezas de vários tipos admitidas sobre o modelo. Os modelos são primariamente estruturas flexíveis e os métodos de projeto são implementados usando exclusivamente a solução de problemas sujeitos a desigualdades matriciais lineares. São abordadas as incertezas paramétrica, dinâmica e politópica com o objetivo de apresentar métodos matemáticos de projeto de controladores para os sistemas incertos. Para o caso de incerteza dinâmica, apresenta-se a técnica de filtros de ponderação. Em contraposição a essa abordagem, os resultados recentes da literatura sobre o lema generalizado de Kalman-Yakubovi?c-Popov e o H8 restrito na freqüência também são usados como métodos de controle independentes de filtros de ponderação. Os métodos são comparados usando modelos de simulação e experimentos no âmbito de estruturas flexíveis. Palavras-chave: Teoria dos sistemas dinâmicos, Programação Convexa, Sistema de controle por realimentação / Abstract: This dissertation deals with modern techniques from the Robust H8 Control of Linear Dynamic Systems. By this it is meant that the results from linear control systems theory are used as mathemathical tools when considering several kinds of uncertainty on the models. These models are mostly of flexible structures and the design methods are implemented using solely the solution of problems subjected to linear matrix inequalities. The types of uncertainty approached are: parametric, dynamic and polytopic; this is done aiming to present mathematical design methods for the uncertain systems considered. When dealing with dynamic uncertainty, the weighting functions are introduced. In contrast with this approach, recent results from literature on the generalised Kalman-Yakubovi?c-Popov lemma and frequency restricted H8 are also used as control design methods whose application is independent of weighting functions. All methods are compared using simple simulation models and experiments with flexible structures . Keywords: Theory of dynamical systems, Convex programming, Feedback control systems / Mestrado / Mecanica dos Sólidos e Projeto Mecanico / Mestre em Engenharia Mecânica

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-26T12:20:46Z No. of bitstreams: 2 Dissertação - Vando Antônio Adona - 2014.pdf: 1128475 bytes, checksum: a2d00afcaef383726904cf6e6fd3527d (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-27T10:48:07Z (GMT) No. of bitstreams: 2 Dissertação - Vando Antônio Adona - 2014.pdf: 1128475 bytes, checksum: a2d00afcaef383726904cf6e6fd3527d (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-03-27T10:48:07Z (GMT). No. of bitstreams: 2 Dissertação - Vando Antônio Adona - 2014.pdf: 1128475 bytes, checksum: a2d00afcaef383726904cf6e6fd3527d (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-12-18 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / We consider an optimization problem for which the objective function is the sum of convex functions, not necessarily differentiable. We study a subgradient method that executes the iterations incrementally selecting each component function sequentially and processing the subgradient iteration individually. We analyze different alternatives for choosing the step length, highlighting the convergence properties for each case. We also analyze the incremental model in other methods, considering proximal iteration and combinations of subgradient and proximal iterations. This incremental approach has been very successful when the number of component functions is large. / Consideramos um problema de otimização cuja função objetivo consiste na soma de funções convexas, não necessariamente diferenciáveis. Estudamos um método subgradiente que executa a iteração de forma incremental, selecionando cada função componente de maneira sequencial e processando a iteração subgradiente individualmente. Analisamos diferentes alternativas para a escolha do comprimento de passo, destacando as propriedades de convergência para cada caso. Abordamos também o modelo incremental em outros métodos, considerando iteração proximal e combinações de iterações subgradiente e proximal. Esta abordagem incremental tem sido muito bem sucedida quando o número de funções componentes é grande.

O foco central desta tese é o desenvolvimento de algoritmos para o problema de recoloração convexa de caminhos. Neste problema, é dado um caminho cujos vértices estão coloridos arbitrariamente, e o objetivo é recolorir o menor número possível de vértices de modo a obter uma coloração convexa. Dizemos que uma coloração de um grafo é convexa se, para cada cor, o subgrafo induzido pelos vértices dessa cor é conexo. Sabe-se que este problema é NP-difícil. Associamos a este problema um poliedro, e estudamos sua estrutura facial, com vistas ao desenvolvimento de um algoritmo. Mostramos várias inequações válidas para este poliedro, e provamos que várias delas definem facetas. Apresentamos um algoritmo de programação dinâmica que resolve em tempo polinomial o problema da separação para uma classe grande de inequações que definem facetas. Implementamos um algoritmo branch-and-cut baseado nesses resultados, e realizamos testes computacionais com instâncias geradas aleatoriamente. Apresentamos adicionalmente uma heurística baseada numa formulação linear que obtivemos. Estudamos também um caso especial deste problema, no qual as instâncias consistem em caminhos coloridos, onde cada cor ocorre no máximo duas vezes. Apresentamos um algoritmo de 3/2-aproximação para este caso, que é também NP-difícil. Para o caso geral, é conhecido na literatura um algoritmo de 2-aproximação. / The focus of this thesis is the design of algorithms for the convex recoloring problem on paths. In this problem, the instance consists of a path whose vertices are arbitrarily colored, and the objective is to recolor the least number of vertices so as to obtain a convex coloring.Acoloring of a graph is convex if, for each color, the subgraph induced by the vertices of this color is connected. This problem is known to be NP-hard. We associate a polyhedron to this problem and investigate its facial structure. We show various classes of valid inequalities for this polyhedron and prove that many of them define facets.We present a polynomial-time dynamic programming algorithm that solves, in polynomial time, the separation problem for a large class of facet-defining inequalities.We report on the computational experiments with a branch-and-cut algorithm that we propose for the problem. Additionally, we present a heuristic that is based on a linear formulation for the problem. We also study a special case of this problem, restricted to instances consisting of colored paths in which each color occurs at most twice. For this case, which is also NP-hard, we present a 3/2-approximation algorithm. For the general case, it is known a 2-approximation algorithm.

Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-07-12T12:23:47Z No. of bitstreams: 1 hernandojoserochafranco.pdf: 1674623 bytes, checksum: f6df7317dd6a8e94e51045dbf75e8241 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-07-17T11:56:13Z (GMT) No. of bitstreams: 1 hernandojoserochafranco.pdf: 1674623 bytes, checksum: f6df7317dd6a8e94e51045dbf75e8241 (MD5) / Made available in DSpace on 2018-07-17T11:56:13Z (GMT). No. of bitstreams: 1 hernandojoserochafranco.pdf: 1674623 bytes, checksum: f6df7317dd6a8e94e51045dbf75e8241 (MD5) Previous issue date: 2018-06-08 / A teoria clássica de otimização presume a existência de certas condições, por exemplo, que as funções envolvidas em um problema desta natureza sejam pelo menos uma vez continuamente diferenciáveis. Entretanto, em muitas aplicações práticas que requerem o emprego de métodos de otimização, essa característica não se encontra presente. Problemas de otimização não diferenciáveis são considerados mais difíceis de lidar. Nesta classe, aqueles que envolvem funções não convexas são ainda mais complexos. O Interior Epigraph Directions (IED) é um método de otimização que se baseia na teoria da Dualidade Lagrangeana e se aplica à resolução de problemas não diferenciáveis, não convexos e com restrições. Neste estudo, apresentamos duas novas versões para o referido método a partir de implementações computacionais de outros algoritmos. A primeira versão, denominada IED+NFDNA, recebeu a incorporação de uma implementação do algoritmo Nonsmooth Feasible Direction Nonconvex Algorithm (NFDNA). Esta versão, ao ser aplicada em experimentos numéricos com problemas teste da literatura, apresentou desempenho satisfatório quando comparada ao IED original e a outros solvers de otimização. Com o objetivo de aperfeiçoar mais o método, reduzindo sua dependência de parâmetros iniciais e também do cálculo de subgradientes, uma segunda versão, IED+GA, foi desenvolvida com a utilização de algoritmos genéticos. Além da resolução de problemas teste, o IED-FGA obteve bons resultados quando aplicado a problemas de engenharia. / The classical theory of optimization assumes the existence of certain conditions, for example, that the functions involved in a problem of this nature are at least once continuously differentiable. However, in many practical applications that require the use of optimization methods, this characteristic is not present. Non-differentiable optimization problems are considered more difficult to deal with. In this class, those involving nonconvex functions are even more complex. Interior Epigraph Directions (IED) is an optimization method that is based on Lagrangean duality theory and applies to the resolution of non-differentiable, non-convex and constrained problems. In this study, we present two new versions for this method from computational implementations of other algorithms. The first version, called IED + NFDNA, received the incorporation of an implementation of the Nonsmooth Feasible Direction Nonconvex Algorithm (NFDNA) algorithm. This version, when applied in numerical experiments with problems in the literature, presented satisfactory performance when compared to the original IED and other optimization solvers. A second version, IED + GA, was developed with the use of genetic algorithms in order to further refine the method, reducing its dependence on initial parameters and also on the calculation of subgradients. In addition to solving test problems, IED + GA achieved good results when applied to engineering problems.

Orientador: Alberto Luiz Serpa / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecanica / Made available in DSpace on 2018-08-04T03:07:46Z (GMT). No. of bitstreams: 1 Lopes_JeanCutrim_M.pdf: 5625354 bytes, checksum: a90581a7277feed28b2e913c2e7ed085 (MD5) Previous issue date: 2005 / Resumo: o objetivo deste trabalho é aplicar o controle H2/H 'Infinito'usando desigualdades matriciais lineares com restrições de alocação de pólos em estruturas flexíveis. O problema de controle H2/H'Infinito' é uma técnica usada para a obtenção de controladores com as propriedades do controle norma H2, que trás desempenho ótimo, e do controle norma H 'Infinito' que proporciona desempenho dinâmico robusto. As desigualdades matriciais lineares permitem que a obtenção do controlador seja formulada como um problema de otimização convexa e com restrições adicionais tais como as referentes à alocação de pólos. O problema de alocação de pólos é importante para ajustar o comportamento dinâmico da planta controlada no que se refere a especificações em termos da velocidade de resposta e do amortecimento, por exemplo. O modelo empregado para o estudo foi uma viga sujeita a distúrbios com o controlador atuando de forma não colocada. As matrizes de estado empregadas ao estudo de controle foram determinadas através das matrizes obtidas pelo método dos elementos finitos, considerando o modelo de viga de Euler-Bemoulli. Os resultados mostraram que o uso da alocação dos pólos melhora o desempenho do controlador H2/H'Infinito'. Para a implementação computacional foi utilizado o aplicativo Matlab / Abstract: The objective ofthis work is to apply the H2/H'Infinity' control technique using linear matrix inequalities and pole placement constraints to the flexible structures control problem. The H2/H'Infinity' control is a technique to design a controller with mixed features of the H2 and H'Infinity' control formulations, such as, optimal dynamical performance and robust performance. The Linear Matrix Inequalities allow to formulate the problem as a convex optimization problem, and additional constraints can be included such as the pole placement. The pole placement requirement comes ftom the necessity of adjusting the transient response of the plant and ensuring specific behavior in terms of speed and damping responses. The mathematical model used for this study is related to a flexible beam, with an applied disturbance and an actuator in different positions. The state-space matrices of the structure were obtained using the finite element method with the Euler-Bernoulli formulation of beams. The results show that the pole placement constraints can improve the performance of the controller H2/H'Infinity',The Matlab was used for the computational implementation / Mestrado / Projeto Mecanico e Mecanica dos Solidos / Mestre em Engenharia Mecânica

O problema de minimização com restrições lineares e importante, não apenas pelo problema em si, que surge em várias áreas, mas também por ser utilizado como subproblema para resolver problemas mais gerais de programação não-linear. GENLIN e um método eficiente para minimização com restrições lineares para problemas de pequeno e médio porte. Para que seja possível a implementação de um método similar para grande porte, é necessário ter um método eficiente, também para grande porte, para projeção de pontos no conjunto de restrições lineares. O problema de projeção em um conjunto de restrições lineares pode ser escrito como um problema de programação quadrática convexa. Neste trabalho, estudamos e implementamos métodos esparsos para resolução de problemas de programação quadrática convexa apenas com restrições de caixa, em particular o clássico método Moré-Toraldo e o \"método\" NQC. O método Moré-Toraldo usa o método dos Gradientes Conjugados para explorar a face da região factível definida pela iteração atual, e o método do Gradiente Projetado para mudar de face. O \"método\" NQC usa o método do Gradiente Espectral Projetado para definir em que face trabalhar, e o método de Newton para calcular o minimizador da quadrática reduzida a esta face. Utilizamos os métodos esparsos Moré-Toraldo e NQC para resolver o problema de projeção de GENLIN e comparamos seus desempenhos / The linearly constrained minimization problem is important, not only for the problem itself, that arises in several areas, but because it is used as a subproblem in order to solve more general nonlinear programming problems. GENLIN is an efficient method for solving small and medium scaled linearly constrained minimization problems. To implement a similar method to solve large scale problems, it is necessary to have an efficient method to solve sparse projection problems onto linear constraints. The problem of projecting a point onto a set of linear constraints can be written as a convex quadratic programming problem. In this work, we study and implement sparse methods to solve box constrained convex quadratic programming problems, in particular the classical Moré-Toraldo method and the NQC \"method\". The Moré-Toraldo method uses the Conjugate Gradient method to explore the face of the feasible region defined by the current iterate, and the Projected Gradient method to move to a different face. The NQC \"method\" uses the Spectral Projected Gradient method to define the face in which it is going to work, and the Newton method to calculate the minimizer of the quadratic function reduced to this face. We used the sparse methods Moré-Toraldo and NQC to solve the projection problem of GENLIN and we compared their performances

Orientador: Alan Rodrigo Panosso / Resumo: O estudo da anisotropia espacial apresenta grande importância na modelagem e mapeamento espacial das variáveis ambientais. Assim, o objetivo do trabalho foi caracterizar a anisotropia espacial da perda de solo e atributos químicos e físicos do solo em diferentes pedoformas com cultivo de cana-de-açúcar, por meio da utilização da dimensão fractal (DF). O estudo foi realizado a partir de um banco de dados legados do Grupo de Pesquisa CSME, referente a uma área de 200 ha, localizada em Tabapuã (SP), Brasil, onde foi estabelecida uma malha de amostragem regular de 50 m, com 623 pontos. Em cada ponto, foi estimada a perda de solo por erosão (A), com a Universal Soil Loss Equation(USLE), bem como os atributos teor de argila (Arg), Areia Total (AT), Capacidade de troca de cátions (CTC), Matéria orgânica (MO) e Fósforo (P). Identificou-se a predominância de condição anisotrópica para todos os atributos na pedoforma convexa nas direções entre 90º e 150º, baseadas nos gráficos de dispersão gerados a partir de diferentes escalas e direções. Porém na pedoforma côncava A, Arg e CTC apresentaram comportamento isotrópico. Obteve-se o melhor ajuste no resultado da validação cruzada de A, na pedoforma côncava no modelo isotrópico e na pedoforma convexa no modelo anisotrópico. Concluiu-se que a pedoforma convexa proporciona maior ocorrência de anisotropia demonstrando que a forma do relevo condiciona padrões diferenciados de anisotropia espacial. / Abstract: The study of spatial anisotropy is of great importance in the modeling and spatial mapping of environmental variables. Thus, the objective of the work was to characterize the spatial anisotropy of soil loss and chemical and physical attributes of the soil in different pedoforms with sugarcane cultivation, using the fractal dimension (DF). The study was carried out from a legacy database of the CSME Research Group, referring to an area of 200 ha, located in Tabapuã (SP), Brazil, where a regular 50 m sampling grid was established, with 623 points . At each point, soil loss by erosion (A) was estimated with the Universal Soil Loss Equation (USLE), as well as the clay content (Arg), Total Sand (AT), Cation exchange capacity (CTC) attributes ), Organic matter (MO) and phosphorus (P). The predominance of anisotropic condition was identified for all attributes in the convex pedoform in the directions between 90º and 150º, based on the scatter plots generated from different scales and directions. However, in the concave pedoform A, Arg and CTC showed isotropic behavior. The best adjustment was obtained in the result of the cross-validation of A, in the concave pedoform in the isotropic model and in the convex pedoform in the anisotropic model. It was concluded that the convex pedoform provides a higher occurrence of anisotropy demonstrating that the shape of the relief conditions different patterns of spatial anisotropy. / Mestre

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.

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.