[pt] Diversos problemas em engenharia, aprendizado de máquina e economia podem ser resolvidos através de Programação Semidefinida (SDP). Potenciais aplicações podem ser encontradas em telecomunicações, fluxo de potência e teoria dos jogos. Além disso, como SDP é uma subclasse de otimização convexa, temos uma série de propriedades e garantias que fazem da SDP uma tecnologia muito poderosa. Entretanto, dentre as diferentes subclasses de otimização convexa, SDP ainda permanece como uma das mais desafiadoras. Instancias de larga escala ainda não podem ser resolvidas pelos atuais softwares disponíveis. Nesse sentido, esta tese porpõe um novo algoritmo para resolver problemas de SDP. A principal contribuição deste novo algoritmo é explorar a propriedade de posto baixo presente em diversas instancias. A convergência desta nova metodologia é provada ao mostrar que o algoritmo proposto é um caso particular do Approximate Proximal Point Algorithm. Adicionalmente, as variáveis ótimas duais são disponibilizadas como uma consequência do algoritmo proposto. Além disso, disponibilizamos um software para resolver problemas de SDP, chamado ProxSDP. Três estudos de caso são utilizados para avaliar a performance do algoritmo proposto. / [en] Many problems of interest can be solved by means of Semidefinite Programming (SDP). The potential applications range from telecommunications, electrical power systems, game theory and many more fields. Additionally, the fact that SDP is a subclass of convex optimization brings a set of theoretical guarantees that makes SDP very appealing. However, among all sub-classes of convex optimization, SDP remains one of the most challenging in practice. State-of-the-art semidefinite programming solvers still do not efficiently solve large scale instances. In this regard, this thesis proposes a novel algorithm for solving SDP problems. The main contribution of this novel algorithm is to achieve a substantial speedup by exploiting the low-rank property inherent to several SDP problems. The convergence of the new methodology is proved by showing that the novel algorithm reduces to a particular case of the Approximated Proximal Point Algorithm. Along with the theoretical contributions, an open source numerical solver, called ProxSDP, is made available with this work. The performance of ProxSDP in comparison to state-of-the-art SDP solvers is evaluated on three case studies.

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

No description available.

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.

In this thesis, we present some contributions to the Markov jump linear systems theory in a context of partial information on the Markov chain. We consider that the state of the Markov chain cannot be measured, but instead there is only an observed variable that could model an asynchronous phenomenon between the application and the plant, or a simple fault detection and isolation device. In this formulation, we investigate the problem of designing controllers and filters depending only on the observed variable in the context of H2, H?, and mixed H2/H? control theory. Numerical examples and academic applications are presented for active-fault tolerant control systems and networked control systems. / Nesta tese, apresentamos algumas contribuições para a teoria de sistemas lineares com saltos markovianos em um contexto de observação parcial da cadeia de Markov. Consideramos que o estado da cadeia de Markov não pode ser medido, porém existe uma variável observada que pode modelar um fenômeno assíncrono entre a aplicação e a planta, ou ainda um dispositivo de detecção de falhas simples. Através desse modelo, investigamos o problema da síntese de controladores e filtros que dependem somente da variável observada no contexto das teorias de controle H2, H?, e misto H2/H?. Exemplos numéricos e aplicações acadêmicas são apresentadas no âmbito dos sistemas de controle tolerantes a falhas e dos sistemas de controle através da rede.

Neste trabalho uma nova estratégia de combinação de filtros adaptativos é apresentada e estudada. Inspirada por esquemas incrementais e filtragem adaptativa cooperativa, a combinação convexa usual de filtros em paralelo e independentes é reestruturada como uma configuração série-cooperativa, sem aumento da complexidade computacional. Dois novos algoritmos são projetados utilizando Recursive Least-Squares (RLS) e Least-Mean-Squares (LMS) como subfiltros que compõem a combinação. Para avaliar a performance da estrutura incremental, uma análise de média quadrática é realizada. Esta é feita assumindo que os combinadores têm valores fixos, de forma a permitir o estudo da universalidade da estrutura desacoplada da dinâmica do supervisor. As simulações realizadas mostram uma boa concordância com o modelo teórico obtido. / In this work a new strategy for combination of adaptive filters is introduced and studied. Inspired by incremental schemes and cooperative adaptive filtering, the standard convex combination of parallel-independent filters is rearranged into a series-cooperative configuration, while preserving computational complexity. Two new algorithms are derived employing Recursive Least-Squares (RLS) and Least-Mean-Squares (LMS) algorithms as the component filters. In order to assess the performance of the incremental structure, tracking and steady-state mean-square analysis is derived. The analysis is carried out assuming the combiners are fixed, so that the universality of the new structure may be studied decoupled from the supervisor\'s dynamics. The resulting analytical model shows good agreement with simulation results.

In this thesis, we present some contributions to the Markov jump linear systems theory in a context of partial information on the Markov chain. We consider that the state of the Markov chain cannot be measured, but instead there is only an observed variable that could model an asynchronous phenomenon between the application and the plant, or a simple fault detection and isolation device. In this formulation, we investigate the problem of designing controllers and filters depending only on the observed variable in the context of H2, H?, and mixed H2/H? control theory. Numerical examples and academic applications are presented for active-fault tolerant control systems and networked control systems. / Nesta tese, apresentamos algumas contribuições para a teoria de sistemas lineares com saltos markovianos em um contexto de observação parcial da cadeia de Markov. Consideramos que o estado da cadeia de Markov não pode ser medido, porém existe uma variável observada que pode modelar um fenômeno assíncrono entre a aplicação e a planta, ou ainda um dispositivo de detecção de falhas simples. Através desse modelo, investigamos o problema da síntese de controladores e filtros que dependem somente da variável observada no contexto das teorias de controle H2, H?, e misto H2/H?. Exemplos numéricos e aplicações acadêmicas são apresentadas no âmbito dos sistemas de controle tolerantes a falhas e dos sistemas de controle através da rede.

Neste trabalho uma nova estratégia de combinação de filtros adaptativos é apresentada e estudada. Inspirada por esquemas incrementais e filtragem adaptativa cooperativa, a combinação convexa usual de filtros em paralelo e independentes é reestruturada como uma configuração série-cooperativa, sem aumento da complexidade computacional. Dois novos algoritmos são projetados utilizando Recursive Least-Squares (RLS) e Least-Mean-Squares (LMS) como subfiltros que compõem a combinação. Para avaliar a performance da estrutura incremental, uma análise de média quadrática é realizada. Esta é feita assumindo que os combinadores têm valores fixos, de forma a permitir o estudo da universalidade da estrutura desacoplada da dinâmica do supervisor. As simulações realizadas mostram uma boa concordância com o modelo teórico obtido. / In this work a new strategy for combination of adaptive filters is introduced and studied. Inspired by incremental schemes and cooperative adaptive filtering, the standard convex combination of parallel-independent filters is rearranged into a series-cooperative configuration, while preserving computational complexity. Two new algorithms are derived employing Recursive Least-Squares (RLS) and Least-Mean-Squares (LMS) algorithms as the component filters. In order to assess the performance of the incremental structure, tracking and steady-state mean-square analysis is derived. The analysis is carried out assuming the combiners are fixed, so that the universality of the new structure may be studied decoupled from the supervisor\'s dynamics. The resulting analytical model shows good agreement with simulation results.

Orientador: José Roberto Sanches Mantovani / Resumo: Neste trabalho, o modelo matemático do problema de fluxo de potência ótimo básico não linear é analisado e manipulado algebricamente para obter um modelo de programação convexa, do tipo cônico de segunda ordem. O conceito de envelopes convexos é apresentado para tratar a não linearidade e não convexidade da restrição trigonométrica inversa que surge ao escrever o modelo de FPO como um modelo cônico. Aplicando duas proposições apresentadas neste trabalho a restrição trigonométrica é resolvida em um pré-processamento por um solver de otimalidade local, neste caso o KNITRO, que enumera todas as possibilidades dos pontos de KKT para obter os envelopes convexos e tornar o modelo de FPO totalmente convexo. O modelo é implementado no AMPL e é resolvido com solvers de otimalidade global com sistemas testes da literatura, nesta tese usam-se os sistemas testes IEEE 14, 30, 57 e 118 barras. Os resultados obtidos são validados comparando-os com resultados fornecidos pelo Matpower, que é um simulador para FPO. Como contribuição desta tese, o modelo convexo de FPO obtido é utilizado como exemplo de aplicações no problema de despacho ótimo de potência ativa e reativa, considerando competições via programação binível. São apresentados dois modelos biníveis e dois modelos uníveis. O modelo iterativo convexo utiliza-se do modelo proposto de FPO convexo e as não linearidades são convexificadas fazendo uso dos envelopes de McCormick. O conceito de dualidade forte é empregado afim de obter um mod... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: In this work, the basic nonlinear mathematical model for the optimal power flow (OPF) problem is analyzed and manipulated algebraically in order to obtain a second-order conic convex programming model. The concept of convex envelopes is presented to deal with the nonlinearity and nonconvexity of the inverse trigonometric constraint that arises when transforming the nonconvex OPF model into an equivalent conic model. By applying two propositions presented in this work, the trigonometric constraint is solved in a pre-processing stage by a local optimization solver, in this case, the KNITRO solver, which considers all the possibilities of the KKT points to obtain the convex envelopes and find a completely convex OPF model, is used. The model is implemented in AMPL and is solved via global optimization solvers while to show the effectiveness of the model several IEEE systems such as the IEEE 14-, 30-, 57-, and 118-bus systems are used. The obtained results are validated by comparing them with the results provided by Matpower, which is an OPF solver. As a contribution of this thesis, the obtained convex OPF model is used as an application in the active and reactive optimal power dispatch problem, considering competition via bilevel programming. Two bilevel models and two single-level models are presented. The convex iterative model uses the proposed convex OPF model, and the nonlinearities are convexified using McCormick envelopes. The concept of strong duality is employed to obta... (Complete abstract click electronic access below) / Doutor

Orientador: Alberto Luiz Serpa / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Mecânica / Made available in DSpace on 2018-08-16T17:57:08Z (GMT). No. of bitstreams: 1 Santos_MarcelMerlindos_M.pdf: 5016793 bytes, checksum: f37e8e9c24d066f039f997af537b3b4f (MD5) Previous issue date: 2010 / Resumo: Nesse estudo foram aplicadas as técnicas de controle H1 em modelos de suspensões ativas veiculares. O interesse de controlar o sistema baseado nessa técnica está também no fato de que sua obtenção pode ser feita através da solução de problemas de otimização, sendo estes baseados no uso de Desigualdades Matriciais Lineares (LMI, do inglês Linear Matrix Inequalities), que proporciona flexibilidade na formulação de problemas de otimização e possui algoritmos eficientes para a solução. Esse estudo foi baseado em três modelos de suspensão diferentes, com dois, quatro e sete graus de liberdade. Uma suspensão deve proporcionar conforto e segurança aos passageiros. Baseado nisso, adotou-se como desempenho o deslocamento simultâneo das rodas relativo ao chão (segurança) e a aceleração vertical do veículo (conforto dos passageiros). Como sinal de medição, utilizou-se a aceleração vertical do veículo. O controlador foi obtido considerando incertezas do modelo (neste estudo consideradas como incertezas paramétricas). Todos os modelos de suspensão veicular com controle simulados apresentaram melhores resultados, reduzindo não só a resposta temporal do sistema como também a resposta em freqüência, melhorando o conforto e a segurança dos passageiros. Conclui-se assim que é possível controlar o sistema mesmo quando sujeito a incertezas de modelagem. Para a solução numérica do problema foi utilizado o software MATLAB 7.4 com dois pacotes livres de otimização: Yalmip e Sedumi / Abstract: In this study the techniques of control H1 were applied in active suspension models. The interest in controling the system using this technique is based on the fact that the solution can be obtained by solving optimization problems, which are based on the use of Linear Matrix Inequalities, providing flexibility during the problem formulation and with efficient algorithms to solve the problem. This study was based on three different suspension models with two, four and seven degrees of freedom. A suspension should provide comfort and security to the passengers. Based on this, the displacement of wheels on the ground (security) and the vertical acceleration of the vehicle (passengers comfort) were adopted as system performance. The vertical acceleration of the vehicle was the measured signal. The active suspension controller was designed considering uncertainties (in this study as parametric uncertainties). All active suspensions controled models simulated improved their results, reducing not only system's time response but also system's frequency response. This means an improvement of the passengers' safety and comfort. It was concluded that controlling the system even when it has uncertainties was possible. To solve the numerical problem the software MATLAB 7.4 was used with two free optimization packages: Yalmip and Sedumi / Mestrado / Mecanica dos Sólidos e Projeto Mecanico / Mestre em Engenharia Mecânica