Online Convex Optimization (OCO) is a field in the intersection of game theory, optimization, and machine learning which has been receiving increasing attention due to its recent applications to a wide range of topics such as complexity theory and graph sparsification. Besides the usually simple description and implementation of OCO algorithms, a lot of this recent success is due to a deepening of our understanding of the OCO setting and their algorithms by using cornerstone ideas from convex analysis and optimization such as the powerful results from convex duality theory. In this text we present a mostly self-contained introduction to the field of online convex optimization. We first describe the online learning and online convex optimization settings, proposing an alternative way to formalize both of them so we can make formal claims in a clear and unambiguous fashion while not cluttering the readers understanding. We then present an overview of the main concepts of convex analysis we use, with a focus on building intuition. With respect to algorithms for OCO, we first present and analyze the Adaptive Follow the Regularized Leader (AdaFTRL) together with an analysis which relies mainly on the duality between strongly convex and strongly smooth functions. We then describe the Adaptive Online Mirror Descent (AdaOMD) and the Adaptive Dual Averaging (AdaDA) algorithms and analyze both by writing them as special cases of the AdaFTRL algorithm. Additionally, we show simple sufficient conditions for Eager and Lazy Online Mirror Descent (the non-adaptive counter-parts of AdaOMD and AdaDA) to be equivalent. We also present the well-known AdaGrad and Online Newton Step algorithms as special cases of the AdaReg algorithm, proposed by Gupta, Koren, and Singer, which is itself a special case of the AdaOMD algorithm. We conclude by taking a bird\'s-eyes view of the connections shown throughout the text, forming a ``genealogy\'\' of OCO algorithms, and discuss some possible path for future research. / Otimização Convexa Online (OCO) é uma área na intersecção de teoria dos jogos, otimização e aprendizado de máquina que tem recebido maior atenção recentemente devido a suas recentes aplicações em uma grande gama de áreas como complexidade computacional e esparsificação de grafos. Além dos algoritmos de OCO usualmente terem descrições diretas e poderem ser implementados de forma relativamente simples, muito do recente sucesso da área foi possível graças a um melhor entendimento do cenário e dos algoritmos de OCO que se deu com uso de conhecidas ideias de análise e otimização convexa como a poderosa teoria de dualidade convexa. Nesse texto nós apresentamos uma introdução (em sua maioria auto-contida) à área de otimização convexa online. Primeiro, descrevemos os cenários de aprendizado online e de otimização convexa online, propondo uma forma alternativa de formalizar ambos os modelos de forma que conseguimos enunciar afirmações claras e formais de forma que não atrapalha o entendimento do leitor. Nós então apresentamos um resumo dos principais conceitos e resultados de análise convexa que usamos no texto com um foco em criar intuição sobre os mesmos. Com relação a algoritmos para OCO, nós começamos apresentando o algoritmo Adaptive Follow the Regularized Leader (AdaFTRL) e analisamos sua eficácia com um resultado sobre a dualidade de funções strongly convex e strongly smooth. Na sequência, descrevemos os algoritmos Adaptive Online Mirror Descent (AdaOMD) e Adaptive Dual Averaging (AdaDA), analisando a eficácia de cada um escrevendo eles como instâncias do algoritmo AdaFTRL. Além disso, nós mostramos condições simples para que as versões Eager e Lazy do Online Mirror Descent (que são as versões não adaptativas do AdaOMD e do AdaDA, respectivamente) sejam equivalentes. Também apresentamos os algoritmos AdaGrad e Online Newton Step, bem conhecidos na literatura sobre OCO, como casos especiais do algoritmo AdaReg, esse último um algoritmo proposto por Gupta, Koren, and Singer, que, por sua vez, é um caso especial do algoritmo AdaOMD. Nós concluímos o texto com uma visão global das conexões entre os algoritmos que mostramos durante o texto, formando uma \"genealogia\" de algoritmos para OCO, além de discutirmos possíveis direções futuras de pesquisa.

Apresentamos dois novos métodos para a solução de problemas de otimização convexa em dois níveis não necessariamente diferenciáveis, i.e., mostramos que as sequências geradas por ambos os métodos convergem para o conjunto ótimo de uma função não suave sujeito a um conjunto que também envolve a minimização de uma função não diferenciável. Ambos os algoritmos dispensam qualquer tipo de resolução de subproblemas ou busca linear durante suas iterações. Ao final, para demonstrar que os métodos são viáveis, resolvemos um problema de reconstrução de imagens tomográficas / We present two new methods for solving bilevel convex optimization problems, where both functions are not necessarily differentiable, i.e., we show that the sequences generated by those methods converge to the optimal set of a nonsmooth function subject to a set that also involves a function minimization. Both algorithms do not require any kind of subproblems resolution or linear search during the iterations. At the end, to prove that our methods are viable, we solve a problem of tomographic image reconstruction

Neste trabalho apresentamos um novo método ótimo para otimização de uma função convexa diferenciável sujeita a restrições convexas. Nosso método é baseado em ideias de Nesterov e Auslender e Teboulle. A proposta dos últimos autores usa uma distância de Bregman coerciva para garantir que os iterados permaneçam no interior do conjunto viável. Nosso método estende esses resultados para permitir o emprego da distância Euclidiana ao quadrado. Mostramos também como estimar a constante de Lipschitz para o gradiente da função objetivo, o que resulta em uma melhora na eficiência numérica do método. Finalmente, apresentamos experimentos numéricos para validar nossa proposta e comparar com o algoritmo de Nesterov. / In this work we introduce a new optimal method for constrained differentiable convex optimization which is based on previous ideas by Nesterov and Auslender and Teboulle. The method proposed by the last authors use a coercive Bregman distance to ensure that the iterates remain in the interior of the feasible set. Our results extend this method to allow the use of the squared Euclidean distance. We also show how to estimate the Lipschitz constant of the gradient of the objective function, improving the numerical behavior of the method. Finally, we present numerical experiments to validate our approach and compare it to Nesterov\'s algorithm.

Este trabalho apresenta uma arquitetura de controle de movimento entre duas posturas distintas para um robô móvel sob rodas com acionamento diferencial em um ambiente estruturado e livre de obstáculos. O conceito clássico de eficiência foi utilizado para a definição das estratégias de controle: um robô se movimenta de forma eficiente quando realiza a tarefa determinada no menor tempo e utilizando menor quantidade energética. A arquitetura proposta é um recorte do modelo de Controle Hierárquico Aninhado (NHC), composto por três níveis de abstração: (i) Planejamento de Caminho, (ii) Planejamento de Trajetória e (iii) Rastreamento de Trajetória. O Planejamento de Caminho proposto suaviza uma geodésica Dubins - o caminho mais eficiente - por uma Spline Grampeada para que este caminho seja definido por uma curva duplamente diferenciável. Uma transformação do espaço de configuração do robô é realizada. O Planejamento de Trajetória é um problema de otimização convexa na forma de Programação Cônica de Segunda Ordem, cujo objetivo é uma função ponderada entre tempo e energia. Como o tempo de percurso e a energia total consumida pelo robô possui uma relação hiperbólica, um algoritmo de sintonia do coeficiente de ponderação entre estas grandezas é proposta. Por fim, um Rastreador de Trajetória de dupla malha baseado em linearização entrada-saída e controle PID é proposto, e obteve resultados satisfatórios no rastreamento do caminho pelo robô. / This work presents a motion control architecture between two different positions for a differential driven wheeled mobile robot in a obstacles free structured environment. The classic concept of efficiency was used to define the control strategies: a robot moves efficiently when it accomplishes the determined task in the shortest time and using less amount of energy. The proposed architecture is a clipping of the Nested Hierarchical Controller (NHC) model, composed of three levels of abstraction: (i) Path Planning, (ii) Trajectory Planning and (iii) Trajectory Tracking. The proposed Path Planning smoothes a geodesic Dubins - the most efficient path - by a Clamped Spline as this path is defined by a twice differentiable curve. A transformation of the robot configuration space is performed. The Trajectory Planning is a convex optimization problem in the form of Second Order Cone Programming, whose objective is a weighted function between time and energy. As the travel time and the total energy consumed by the robot has a hyperbolic relation, a tuning algorithm to the weighting is proposed. Finnaly, a dual-loop Trajectory Tracker based on input-output feedback linearization and PID control is proposed, which obtained satisfactory results in tracking the path by the robot.

Apresentamos dois novos métodos para a solução de problemas de otimização convexa em dois níveis não necessariamente diferenciáveis, i.e., mostramos que as sequências geradas por ambos os métodos convergem para o conjunto ótimo de uma função não suave sujeito a um conjunto que também envolve a minimização de uma função não diferenciável. Ambos os algoritmos dispensam qualquer tipo de resolução de subproblemas ou busca linear durante suas iterações. Ao final, para demonstrar que os métodos são viáveis, resolvemos um problema de reconstrução de imagens tomográficas / We present two new methods for solving bilevel convex optimization problems, where both functions are not necessarily differentiable, i.e., we show that the sequences generated by those methods converge to the optimal set of a nonsmooth function subject to a set that also involves a function minimization. Both algorithms do not require any kind of subproblems resolution or linear search during the iterations. At the end, to prove that our methods are viable, we solve a problem of tomographic image reconstruction

Neste trabalho apresentamos um novo método ótimo para otimização de uma função convexa diferenciável sujeita a restrições convexas. Nosso método é baseado em ideias de Nesterov e Auslender e Teboulle. A proposta dos últimos autores usa uma distância de Bregman coerciva para garantir que os iterados permaneçam no interior do conjunto viável. Nosso método estende esses resultados para permitir o emprego da distância Euclidiana ao quadrado. Mostramos também como estimar a constante de Lipschitz para o gradiente da função objetivo, o que resulta em uma melhora na eficiência numérica do método. Finalmente, apresentamos experimentos numéricos para validar nossa proposta e comparar com o algoritmo de Nesterov. / In this work we introduce a new optimal method for constrained differentiable convex optimization which is based on previous ideas by Nesterov and Auslender and Teboulle. The method proposed by the last authors use a coercive Bregman distance to ensure that the iterates remain in the interior of the feasible set. Our results extend this method to allow the use of the squared Euclidean distance. We also show how to estimate the Lipschitz constant of the gradient of the objective function, improving the numerical behavior of the method. Finally, we present numerical experiments to validate our approach and compare it to Nesterov\'s algorithm.

Este trabalho apresenta uma arquitetura de controle de movimento entre duas posturas distintas para um robô móvel sob rodas com acionamento diferencial em um ambiente estruturado e livre de obstáculos. O conceito clássico de eficiência foi utilizado para a definição das estratégias de controle: um robô se movimenta de forma eficiente quando realiza a tarefa determinada no menor tempo e utilizando menor quantidade energética. A arquitetura proposta é um recorte do modelo de Controle Hierárquico Aninhado (NHC), composto por três níveis de abstração: (i) Planejamento de Caminho, (ii) Planejamento de Trajetória e (iii) Rastreamento de Trajetória. O Planejamento de Caminho proposto suaviza uma geodésica Dubins - o caminho mais eficiente - por uma Spline Grampeada para que este caminho seja definido por uma curva duplamente diferenciável. Uma transformação do espaço de configuração do robô é realizada. O Planejamento de Trajetória é um problema de otimização convexa na forma de Programação Cônica de Segunda Ordem, cujo objetivo é uma função ponderada entre tempo e energia. Como o tempo de percurso e a energia total consumida pelo robô possui uma relação hiperbólica, um algoritmo de sintonia do coeficiente de ponderação entre estas grandezas é proposta. Por fim, um Rastreador de Trajetória de dupla malha baseado em linearização entrada-saída e controle PID é proposto, e obteve resultados satisfatórios no rastreamento do caminho pelo robô. / This work presents a motion control architecture between two different positions for a differential driven wheeled mobile robot in a obstacles free structured environment. The classic concept of efficiency was used to define the control strategies: a robot moves efficiently when it accomplishes the determined task in the shortest time and using less amount of energy. The proposed architecture is a clipping of the Nested Hierarchical Controller (NHC) model, composed of three levels of abstraction: (i) Path Planning, (ii) Trajectory Planning and (iii) Trajectory Tracking. The proposed Path Planning smoothes a geodesic Dubins - the most efficient path - by a Clamped Spline as this path is defined by a twice differentiable curve. A transformation of the robot configuration space is performed. The Trajectory Planning is a convex optimization problem in the form of Second Order Cone Programming, whose objective is a weighted function between time and energy. As the travel time and the total energy consumed by the robot has a hyperbolic relation, a tuning algorithm to the weighting is proposed. Finnaly, a dual-loop Trajectory Tracker based on input-output feedback linearization and PID control is proposed, which obtained satisfactory results in tracking the path by the robot.

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.

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.

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.