Dans cette thèse, une méthode de résolution de problèmes de commande optimale non linéaires sous contraintes d'état et de commande. Cette méthode repose sur l'adaptation des méthodes de points intérieurs, utilisées en optimisation de dimension finie, à la commande optimale. Un choix constructif de fonctions de pénalisation intérieure est fourni dans cette thèse. On montre que ce choix permet d'approcher la solution d'un problème de commande optimale sous contraintes en résolvant une suite de problèmes de commande optimale sans contraintes dont les solutions sont simplement caractérisées par les conditions de stationnarité du calcul des variations.Deux études dans le domaine de la gestion de l'énergie dans les bâtiments sont ensuite conduites. La première consiste à quantifier la durée maximale d'effacement quotidien du chauffage permettant de maintenir la température intérieure dans une certaine bande de confort, et ce pour différents types de bâtiments classés de mal à bien isolés. La seconde étude se concentre sur les bâtiments BBC et consiste à quantifier la capacité de ces bâtiments à réaliser des effacements électriques complets du chauffage de 6h00 à 22h00 tout en maintenant, là encore, la température intérieure dans une bande de confort. Cette étude est réalisée sur l'ensemble de la saison de chauffe. / This thesis exposes a methodology to solve constrained optimal controlof non linear systems by interior penalty methods. A constructivechoice for the penalty functions used to implement the interior methodis exhibited in this thesis. It is shown that itallows us to approach the solution of the non linear optimal controlproblem using a sequence of unconstrained problems, whose solutionsare readily characterized by the simple calculus of variations.Two representatives study of energy management in buildings are conducted using the provided algorithm. The first study consists in quantifying the maximal duration of daily complete load shiftings achievable by several buildings ranging from poorly to well insulated. The second study focuses on low consumption buildings and aim at quantifying the ability of these buildings to perform complete load shiftings of the heating electrical consumption from the day (6 a.m. to 10 p.m.) to the night period over the whole heating season.

Orientadores: Christiano Lyra Filho, Aurelio Ribeiro Leite de Oliveira / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-27T01:38:37Z (GMT). No. of bitstreams: 1 Casacio_Luciana_D.pdf: 3240577 bytes, checksum: f49bb4444bbbfacf0559d3b88d8feee5 (MD5) Previous issue date: 2015 / Resumo: A solução de problemas de otimização linear através de métodos de pontos interiores envolve a solução de sistemas lineares. Esses sistemas quase sempre possuem dimensões elevadas e alto grau de esparsidade em aplicações reais. Para solução, tipicamente são realizadas operações algébricas que os reduzem a duas formulações mais simples: uma delas, conhecida por "sistema aumentado", envolve matrizes simétricas indefinidas e geralmente esparsas; a outra, denominada "sistema de equações normais", usa matrizes de menor dimensão, simétricas e definidas positivas. A solução dos sistemas lineares é a fase que requer a maior parte do tempo de processamento dos métodos de pontos interiores. Consequentemente, a escolha dos métodos de solução é de extrema importância para que se tenha uma implementação eficiente. Normalmente, aplicam-se métodos diretos para a solução como, por exemplo, a fatoração de Bunch-Parllett ou a fatoração de Cholesky. No entanto, em problemas de grande porte, o uso de métodos diretos torna-se desaconselhável, por limitações de tempo e memória. Nesses casos, abordagens iterativas se tornam mais atraentes. O sucesso da implementação de métodos iterativos depende do uso de bons precondicionadores, pois a matriz de coeficientes torna-se muito mal condicionada, principalmente próximo da solução ótima. Uma alternativa para tratar o problema de mal condicionamento é o uso de abordagens híbridas com duas fases: a fase I utiliza um precondicionador para o sistema de equações normais construído com informações de fatorações incompletas, denominado fatoração controlada de Cholesky; a fase II, utilizada nas últimas iterações, adota o precondicionador separador desenvolvido especificamente para sistemas mal condicionados. O trabalho propõe um novo critério de ordenamento das colunas para construção do precondicionador separador, que preserva a estrutura esparsa da matriz de coeficientes original. Os resultados teóricos desenvolvidos mostram que a matriz precondicionada tem o número de condição limitado quando o ordenamento proposto é adotado. Experimentos computacionais realizados com todos os problemas da biblioteca NETLIB mostram que a abordagem é competitiva com métodos diretos e que o número de condição da matriz precondicionada é muito menor do que o da matriz original. Foram também realizadas comparações com a abordagem híbrida anterior, baseada em precondicionadores que reduzem a esparsidade do sistema de equações. Esses experimentos confirmaram o bom desempenho da metodologia em relação ao número de iterações dos métodos de pontos interiores, aos tempos computacionais e à qualidade das soluções. Esses benefícios foram obtidos com a preservação da esparsidade dos sistemas de equações, o que destaca a adequação da abordagem proposta para a solução de problemas de grande porte / Abstract: The solution of linear optimization problems through interior point methods involves the solution of linear systems. These systems often have high dimensions and high sparsity degree, specially in real applications. Typically algebraic operations are performed to reduce the systems in two simpler formulations: one of them is known as the augmented system, and the other one, referred as normal equation systems, has a smaller dimension matrix which is symmetric positive definite. The solution of linear systems is the interior point methods step that requires most of the processing time. Consequently, the choice of the solution methods are extremely important in order to have an efficient implementation. Usually, direct methods are applied for solving these systems as, for example, Bunch-Parllett factorization or Cholesky factorization. However, in large scale problems, the use of direct methods becomes discouraging by limitations of time and memory. In such cases, iterative approaches are more attractive. The success of iterative method approaches depends on good preconditioners once the coefficient matrix becomes very ill-conditioned, especially close to an optimal solution. An alternative to treat the problem of ill conditioning is to use hybrid approaches with two phases: phase I uses a preconditioner for the normal equation systems built with incomplete factorizations information, called controlled Cholesky factorization; phase II, used in the final iterations, adopts the splitting preconditioner, which was developed specifically for such ill conditioned systems. This work proposes a new ordering criterion for the columns of the splitting preconditioner that preserves the sparse structure of the original coefficient matrix. Theoretical results show that the preconditioned matrix has a limited condition number when the proposed idea is adopted. Computational experiments performed with all NETLIB problems show that the approach is competitive with direct methods and the condition number of the preconditioned matrix is much smaller than the original matrix. Comparisons are also performed with the previous hybrid approach. These experiments confirm the good performance of the methodology. The final number of iterations, processing time and quality of solutions of interior point methods are suitable. These benefits are obtained preserving the sparse structure of the systems, which highlights the suitability of the proposed approach for large scale problems / Doutorado / Automação / Doutora em Engenharia Elétrica

Neste trabalho, os métodos de pontos interiores primal-dual e preditor corretor são estudados e desenvolvidos para o problema de minimização de custos na geração e perdas na transmissão do pré-despacho DC (fluxo de carga em corrente contínua) de um sistema de potência hidroelétrico, com base no modelo de fluxo em redes e no princípio do mínimo esforço. A estrutura matricial, resultante da simplificação do problema proposto pela inclusão do princípio do mínimo esforço, é estudada visando implementações eficientes. / In this work, the primal-dual and predictor corrector interior points methods are studied and developed for the predispatch DC problem that minimizes generation and transmission losses on hydroelectric power systems, on the basis of the network flow model and the minimum effort principle. The matrix structure, resulting of the simplification of the problem considered by inclusion of the minimum effort principle, is studied aiming efficient implementations. A disturbed primal-dual method is considered on the basis of a heuristic definition that determine the choice of the disturbance parameter. This method showed to be efficient in practice and converged in fewer iterations when compare with an existing implementation of the network flow model.

Neste trabalho é apresentada uma ferramenta de otimização para análise de problemas de alocação de água em bacias hidrográficas utilizando técnicas de programação linear e linear por partes, integradas a um modelo de amortecimentos de ondas em canais. A otimização é feita de forma global, com uso de softwares de programação linear baseados nos métodos de pontos interiores. A metodologia de uso do sistema consiste em se obter uma solução ?ótima? para situações de disponibilidade de água insuficiente a todos os usos conflitantes na bacia. A ferramenta está sendo acoplada e incorporada ao AcquaNet, um Sistema de Suporte a Decisões (SSD) para análise de sistemas de recursos hídricos, que utiliza um algoritmo de rede de fluxo afim de otimizar a alocação de água. A formulação utilizando programação linear permite a análise global do sistema e por isso, espera-se melhor aproveitamento da água disponível, seja no menor déficit de atendimento às demandas ou maior armazenamento nos reservatórios. A programação linear com utilização de métodos de pontos interiores é atualmente uma técnica bastante conhecida e bem desenvolvida. Existem vários pacotes computacionais gratuitos com implementações eficientes dos métodos de pontos interiores que motivaram sua utilização neste trabalho. / This work presents an optimization tool for analyzing the problems of water allocation in watersheds by utilizing techniques of linear and piecewise linear programming integrated to a pattern of stream flow routing. The optimization is done in a global way with the usage of linear programming packages based upon the Internal Point Methods. The methodology of the usage consists in the acquirement of an optimal solution for situation of insufficient water availability for all conflicting consumptions from the watershed. The tool is being attached and incorporated to AcquaNet, which is a decision support system (DSS) for analysis of water resources systems that utilizes a network flow algorithm, with the purpose of optimizing the water allocation. The formulation that uses the linear programming leads to the analysis of the system as a whole and for this reason it is expected a better usage of the available water with a lower deficit in the supply or a greater storage in the reservoirs. Linear Programming with Internal Point Methods is nowadays a well known and very well developed technique. There are several computational packages with efficient implementations of the Internal Points Methods freely available, and that, has brought great motivation in its usage in the present work.

Résumé Nous présentons en premier lieu dans ce travail les principales notions de la théorie de l'Analyse Limite (AL) — ou théorie des charges limites — en mécanique. Puis nous proposons une méthode de point intérieur destinée à résoudre des problèmes de programmation convexe posés par la méthode statique de l'AL, en vue d'obtenir des bornes inférieures de la charge limite (ou de ruine) d'un système mécanique. Les principales caractéristiques de cette méthode de point intérieur sont exposées en détail, et particulièrement son itération type. En second lieu, nous exposons l'application de cet algorithme sur un problème concret d'analyse limite, sur une large gamme de tailles numériques, et nous comparons pour validation les résultats obtenus avec ceux déjà existants ainsi qu'avec ceux calculés à partir de versions linéarisées du problème statique. Nous analysons également les résultats obtenus pour des problèmes classiques avec matériaux de Gurson, pour lesquels la linéarisation ou la programmation conique ne s'applique pas. La deuxième partie de cet ouvrage a trait à la méthode cinématique de l'analyse limite, qui, elle, s'occupe de fournir des bornes supérieures des charges limites. En premier lieu, nous traitons de l'équivalence entre la méthode cinématique classique et la méthode cinématique mixe, en partant d'une l'approche variationnelle fournie précédemment par Radenkovic et Nguyen. Ensuite, prenant en compte les exigences particulières aux formulations numériques, nous présentons une méthode mixte originale, parfaitement cinématique, utilisant aussi bien des champs de vitesses linéaires que quadratiques, continus ou discontinus. Son modus operandi pratique est tiré de l'analyse des conditions d'optimalité de Karush, Kuhn et Tucker, fournissant par là un exemple significatif d'interaction fructueuse entre la mécanique et la programmation mathématique. La méthode est testée sur des problèmes classiques avec les critères de plasticité de von Mises/Tresca et Gurson. Ces test démontrent l'efficacité remarquable de cette méthode mixte — qui par ailleurs n'utilise que le critère de plasticité comme information sur le matériau — et sa robustesse, laquelle s'avère même supérieure à celle de codes commerciaux récents de programmation conique. Enfin, nous présentons une approche de décomposition, elle aussi originale, des problèmes de bornes supérieures en analyse limite. Cette approche est basée à la fois sur la méthode cinématique mixte et l'algorithme de point intérieur précédents, et elle est conçue pour utiliser jusqu'à des champs de vitesse quadratiques discontinus. Détaillée dans le cas de la déformation plane, cette approche apparaît très rapidement convergente, ainsi que nous le vérifions sur le problème du barreau comprimé de von Mises/Tresca dans le cas de champs de vitesse linéaires continus. Puis elle est appliquée, dans le cas de champs quadratiques discontinus, au problème classique de la stabilité du talus vertical de Tresca, avec des résultats particulièrement remarquables puisqu'ils améliorent nettement les solutions cinématiques connues jusqu'à présent dans la littérature sur le sujet. Cette caractéristique de forte convergence qualifie particulièrement cette méthode de décomposition comme algorithme de base pour une parallélisation directe— ou récursive — de l'approche par éléments finis de l'analyse limite. Abstract Firstly, the main notions of the theory of Limit analysis (LA) in Mechanics —or collapse load theory – is presented. Then is proposed an Interior Point method to solve convex programming problems raised by the static method of LA, in order to obtain lower bounds to the collapse (or limit) load of a mechanical system. We explain the main features of this Interior Point method, describing in particular its typical iteration. Secondly, we show and analyze the results of its application to a practical Limit Analysis problem, for a wide range of sizes, and we compare them for validation with existing results and with those of linearized versions of the static problem. Classical problems are also analyzed for Gurson materials to which linearization or conic programming does not apply. The second part of this work focuses on the kinematical method of Limit Analysis, aiming this time to provide upper bounds on collapse loads. In a first step, we detail the equivalence between the classical an general mixed approaches, starting from an earlier variational approach of Radenkovic and Nguyen. In a second step, keeping in mind numerical formulation requirements, an original purely kinematical mixed method—using linear or quadratic, continuous or discontinuous velocity fields as virtual variables—is proposed. Its practical modus operandi is deduced from the Karush-Kuhn-Tucker optimality conditions, providing an example of crossfertilization between mechanics and mathematical programming. The method is tested on classical problems for von Mises/tresca and Gurson plasticity criteria. Using only the yield criterion as material data, it appears very efficient and robust, even more reliable than recent conic commercial codes. Furthermore, both static and kinematic present approaches give rise to the first solutions of problem for homogeneous Gurson materials. Finally, an original decomposition approach of the upper bound method of limit analysis is proposed. It is based on both previous kinematical approach and interior point solver, using up to discontinuous quadratic velocity. Detailed in plane strain, this method appears very rapidly convergent, as verified in the von Mises/Tresca compressed bar problem in the linear continuous velocity case. Then the method is applied, using discontinuous quadratic velocity fields, to the classical problem of the stability of a Tresca vertical cut, with very significant results as they notably improved the kinematical solutions of the literature. Moreover its strong convergence qualifies this decomposition scheme as a suitable algorithm for a direct—or recursive—parallelization of the LA finite element approach.

Optimization is a scientific discipline that lies at the boundary between pure and applied mathematics. Indeed, while on the one hand some of its developments involve rather theoretical concepts, its most successful algorithms are on the other hand heavily used by numerous companies to solve scheduling and design problems on a daily basis. Our research started with the study of the conic formulation for convex optimization problems. This approach was already studied in the seventies but has recently gained a lot of interest due to development of a new class of algorithms called interior-point methods. This setting is able to exploit the two most important characteristics of convexity: - a very rich duality theory (existence of a dual problem that is strongly related to the primal problem, with a very symmetric formulation), - the ability to solve these problems efficiently, both from the theoretical (polynomial algorithmic complexity) and practical (implementations allowing the resolution of large-scale problems) point of views. Most of the research in this area involved so-called self-dual cones, where the dual problem has exactly the same structure as the primal: the most famous classes of convex optimization problems (linear optimization, convex quadratic optimization and semidefinite optimization) belong to this category. We brought some contributions in this field: - a survey of interior-point methods for linear optimization, with an emphasis on the fundamental principles that lie behind the design of these algorithms, - a computational study of a method of linear approximation of convex quadratic optimization (more precisely, the second-order cone that can be used in the formulation of quadratic problems is replaced by a polyhedral approximation whose accuracy that can be guaranteed a priori), - an application of semidefinite optimization to classification, whose principle consists in separating different classes of patterns using ellipsoids defined in the feature space (this approach was successfully applied to the prediction of student grades). However, our research focussed on a much less studied category of convex problems which does not rely on self-dual cones, i.e. structured problems whose dual is formulated very differently from the primal. We studied in particular - geometric optimization, developed in the late sixties, which possesses numerous application in the field of engineering (entropy optimization, used in information theory, also belongs to this class of problems) - l_p-norm optimization, a generalization of linear and convex quadratic optimization, which allows the formulation of constraints built around expressions of the form |ax+b|^p (where p is a fixed exponent strictly greater than 1). For each of these classes of problems, we introduced a new type of convex cone that made their formulation as standard conic problems possible. This allowed us to derive very simplified proofs of the classical duality results pertaining to these problems, notably weak duality (a mere consequence of convexity) and the absence of a duality gap (strong duality property without any constraint qualification, which does not hold in the general convex case). We also uncovered a very surprising result that stipulates that geometric optimization can be viewed as a limit case of l_p-norm optimization. Encouraged by the similarities we observed, we developed a general framework that encompasses these two classes of problems and unifies all the previously obtained conic formulations. We also brought our attention to the design of interior-point methods to solve these problems. The theory of polynomial algorithms for convex optimization developed by Nesterov and Nemirovsky asserts that the main ingredient for these methods is a computable self-concordant barrier function for the corresponding cones. We were able to define such a barrier function in the case of l_p-norm optimization (whose parameter, which is the main determining factor in the algorithmic complexity of the method, is proportional to the number of variables in the formulation and independent from p) as well as in the case of the general framework mentioned above. Finally, we contributed a survey of the self-concordancy property, improving some useful results about the value of the complexity parameter for certain categories of barrier functions and providing some insight on the reason why the most commonly adopted definition for self-concordant functions is the best possible.

Neste trabalho é apresentada uma ferramenta de otimização para análise de problemas de alocação de água em bacias hidrográficas utilizando técnicas de programação linear e linear por partes, integradas a um modelo de amortecimentos de ondas em canais. A otimização é feita de forma global, com uso de softwares de programação linear baseados nos métodos de pontos interiores. A metodologia de uso do sistema consiste em se obter uma solução ?ótima? para situações de disponibilidade de água insuficiente a todos os usos conflitantes na bacia. A ferramenta está sendo acoplada e incorporada ao AcquaNet, um Sistema de Suporte a Decisões (SSD) para análise de sistemas de recursos hídricos, que utiliza um algoritmo de rede de fluxo afim de otimizar a alocação de água. A formulação utilizando programação linear permite a análise global do sistema e por isso, espera-se melhor aproveitamento da água disponível, seja no menor déficit de atendimento às demandas ou maior armazenamento nos reservatórios. A programação linear com utilização de métodos de pontos interiores é atualmente uma técnica bastante conhecida e bem desenvolvida. Existem vários pacotes computacionais gratuitos com implementações eficientes dos métodos de pontos interiores que motivaram sua utilização neste trabalho. / This work presents an optimization tool for analyzing the problems of water allocation in watersheds by utilizing techniques of linear and piecewise linear programming integrated to a pattern of stream flow routing. The optimization is done in a global way with the usage of linear programming packages based upon the Internal Point Methods. The methodology of the usage consists in the acquirement of an optimal solution for situation of insufficient water availability for all conflicting consumptions from the watershed. The tool is being attached and incorporated to AcquaNet, which is a decision support system (DSS) for analysis of water resources systems that utilizes a network flow algorithm, with the purpose of optimizing the water allocation. The formulation that uses the linear programming leads to the analysis of the system as a whole and for this reason it is expected a better usage of the available water with a lower deficit in the supply or a greater storage in the reservoirs. Linear Programming with Internal Point Methods is nowadays a well known and very well developed technique. There are several computational packages with efficient implementations of the Internal Points Methods freely available, and that, has brought great motivation in its usage in the present work.