Orientador: Prof. Dr. Cláudio Nogueira de Meneses / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2018. / Diversos problemas da area de otimização combinatoria podem ser convertidos, em tempo polinomial, para o problema de Programação Quadratica Binaria Irrestrita (UBQP). Neste problema, desejamos encontrar um vetor solução binario x, de dimensão n, tal que a função objetivo f(x) = x|Qx tenha valor mínimo, onde Q é uma matriz com coeficientes racionais. Em termos de complexidade computacional, o problema UBQP pertence a classe NP-difícil. A importancia deste problema, tanto pratica quanto teorica, tem motivado muitos pesquisadores a dedicarem uma quantidade razoavel de tempo tentando projetar tecnicas de resolução exatas e heuristicas para este problema. Durante o processo de resolução do problema UBQP, estas tecnicas necessitam reavaliar muitas vezes o valor da função objetivo. Dependendo da maneira como esta reavaliação é realizada, pode ser preciso executar um numero relativamente grande de operações elementares (atribuições, adições, subtrações e comparações). Isto pode consumir muito tempo de processamento quando n é grande. Nesta pesquisa, propomos formulas que requerem poucas operações para efetuar a reavaliação. Na literatura do problema UBQP, formulas de reavaliação são aplicadas, normalmente, quando há ate duas alterações nos componentes do vetor solução. As formulas que deduzimos podem ser usadas para efetuar qualquer quantidade de alterações. Analisamos uma das nossas formulas de maneira teorica e deduzimos funções que podem ser adotadas para indicar o melhor momento para aplicar essa formula. Ademais, projetamos algoritmos com estas formulas de reavaliação e verificamos a praticidade destes algoritmos conduzindo experimentos computacionais usando implementações de heurísticas de busca local e Variable Neighborhood Search. Nesses experimentos comparamos o desempenho dessas implementações ao resolver instancias da literatura para o problema UBQP. Os resultados experimentais evidenciaram que as formulas de reavaliação, propostas, podem propiciar reduções relativamente grandes nos tempos de processamento, mesmo quando o numero de diferenças entre soluções é moderadamente grande. / Several combinatorial optimization problems can be reformulated, in polynomial time, to the Unconstrained Binary Quadratic Programming (UBQP) problem. In this problem, we are interested in finding an n-dimensional binary solution vector, x, that minimizes the objective function f(x) = x|Qx, where Q is a matrix with rational coecients. In terms of computational complexity, the UBQP problem belongs to the NP-hard class. The practical and theoretical importance of this problem has motivated many researchers to dedicate a reasonable amount of time developing exact and heuristic solution techniques to solve this problem. During the resolution process of the UBQP problem, these techniques need to evaluate many times the objective function value. Depending on how it is made, it may be necessary to execute a relatively large number of elementary operations, such as assignments, additions, subtractions and comparisons. For n large, this may be time consuming. In this research, we propose formulas to perform the reevaluation requiring lesser operations than the simple evaluation of the objective function. In the literature of the UBQP problem, it is common to use reevaluation formulas only when there are at most two- ip moves that simultaneously change the values of two components. The formulas we have deduced can be used to evaluate any number of ip moves. We analyzed one of our reevaluation formulas and deduced functions that can be used to suggest the best moment to apply this formula. In addition, we designed algorithms with these reevaluation formulas and verified the practicality of these algorithms by conducting computational experiments using implementations of local search and Variable Neighborhood Search heuristics. In these experiments, we compared the performance of these implementations by solving benchmark instances for the UBQP problem. The experimental results showed that the reevaluation formulas we created can provide relatively large reductions in processing times, even when the number of ip moves is moderately large.

Made available in DSpace on 2016-08-17T14:53:12Z (GMT). No. of bitstreams: 1 Marcio Andre Nazareno Ferreira.pdf: 1733085 bytes, checksum: 163ab439fd1be9f3bb9050a8433d34e2 (MD5) Previous issue date: 2010-08-06 / After the restructuring of the electric sector, the distribution utilities must maximize the reliability to avoid violation in the reliability targets at the minimal cost. This agreement between cost and reliability can be satisfied with the application of Predictive Reliability Analysis (PRA) in the planning of distribution networks. The PRA estimates the future performance of distribution networks, with regarding to energy supply interruptions, based on the failure data of the components and network topology. The PRA can delivery estimates for the following statistical reliability indices used in the distribution utilities: System Average Interruption Frequency Index (SAIFI), System Average Interruption Duration Indices (SAIDI), Connection Point Interruption Frequency Index (CPIFI), and Connection Point Interruption Duration Index (CPIDI). However, the PRA is rarely used by engineers during the planning of the distribution utilities. This fact is due to the existence of discrepancies between the indices estimated by the PRA and those measured by distribution utilities. These discrepancies are due to the lack of historical data to estimate the reliability parameters of the components: failure rates and repair times. In spite of the distribution utilities do not have a large amount of historical data associated with failures in their equipment, these utilities store historical data on system reliability indices (SAIDI, SAIFI, CPIFI and CPIDI). This information can be used to adjust the failure data of the components (failure rates and repair times) such that the reliability indices evaluated by the ACP models have nearly the same values as those measured by distribution utilities. This adjustment process of the reliability data in ACP models is named Data Calibration. Usually, the reliability data calibration is carried out through optimization techniques. However, the most of the existing methodologies ignores the nodal reliability indices (CPIFI and CPIDI) in the calibration of failure rates and repair times. Only the CPIFI index has been considered in the data calibration. Furthermore, it is not possible to assure that the SAIFI has the same value as its measured value when the calibration considers the CPIFI index. Nevertheless, the Brazilian Electricity Regulatory Agency (ANEEL) has established penalties for violations in the indices CPIFI and CPIDI. Due to this, the PRA models must accurately estimate the nodal reliability indices CPIFI and CPIDI. The main objective of this dissertation is to develop a calibration methodology of reliability data oriented to nodal reliability indices CPIFI and CPIDI. The proposed methodology uses nonlinear and quadratic programming models to calibrate the failure rates and repair times, respectively, in a decoupled structure. This decoupled structure allows the calibration of failure rates and repair times be carried out separately. Additionally, the utilization of equality constraints in the calibration models assures that the evaluated values of SAIFI and SAIDI indices are identical to their measured values. Furthermore, the proposed calibration model for the failure rates considers the equipment condition information obtained from inspection activities. The calibration models proposed in this dissertation were tested in a feeder of the power distribution utility of Maranhão (CEMAR). The tests results demonstrate that the proposed calibration models can significantly reduce the errors between the measured and evaluated values of the CPIFI and CPIDI indices / Após a reestruturação do setor elétrico, as empresas de distribuição devem maximizar a confiabilidade do fornecimento para evitar violações nas metas de confiabilidade com o menor custo possível. Este compromisso entre custo e confiabilidade pode ser atendido com a aplicação da Análise de Confiabilidade Preditiva (ACP) no processo de planejamento de redes de distribuição. A ACP estima o desempenho futuro da rede de distribuição, com relação a interrupções no fornecimento de energia, com base nos dados de falha dos componentes e na sua topologia. A ACP pode fornecer estimativas para os seguintes indicadores de continuidade estatísticos usados pelas empresas de distribuição: Freqüência Equivalente de Interrupção por Unidade Consumidora (FEC), Duração Equivalente de Interrupção por Unidade Consumidora (DEC), Freqüência de Interrupção individual por Unidade Consumidora ou por Ponto de Conexão (FIC), Duração de Interrupção Individual por Unidade Consumidora ou por Ponto de Conexão (DIC) e Duração Máxima de Interrupção Contínua por Unidade Consumidora ou por Ponto de Conexão (DMIC). Entretanto, a ACP é raramente usada pelos engenheiros de planejamento das empresas de distribuição. Este fato é devido à existência de discrepâncias entre os índices estimados pela ACP e aqueles apurados pelas empresas de distribuição. Estas discrepâncias são causadas pela falta de dados históricos para estimar os parâmetros de confiabilidade dos componentes, isto é: taxas de falha, tempos de reparo e chaveamento. Apesar das empresas de distribuição não possuírem uma grande quantidade de dados históricos associados com as falhas dos seus equipamentos, estas empresas armazenam dados históricos sobre índices de continuidade do sistema (FEC, DEC, DIC e FIC). Esta informação pode ser utilizada para ajustar os dados de falha dos componentes (taxas de falha e os tempos de reparo) tal que os índices calculados pelo modelo de ACP sejam próximos dos índices medidos pelas empresas de distribuição. Este processo de ajuste dos dados de falha dos modelos de ACP é denominado de Calibração de Dados. Geralmente, a calibração de dados de confiabilidade é realizada através de técnicas de otimização. Contudo, a maioria das metodologias existentes desconsidera os índices de confiabilidade nodais (FIC e DIC) na calibração das taxas de falha e tempos de reparo. Apenas o índice nodal FIC tem sido considerado na calibração de dados. Além disso, não é possível garantir que o índice FEC seja igual ao seu valor apurado quando a calibração considera o índice FIC. Contudo, a ANEEL (Agência Nacional de Energia Elétrica) estabeleceu penalidades para violações nos índices FIC e DIC. Devido a isto, os modelos de ACP devem estimar precisamente os índices de confiabilidade nodais FIC e DIC. O principal objetivo desta dissertação é desenvolver uma metodologia de calibração de dados de confiabilidade orientada para os índices nodais FIC e DIC. A metodologia proposta utiliza modelos de programação não-linear e quadrática para calibrar as taxas de falha e os tempos de reparo, respectivamente, em uma estrutura desacoplada. Isto é, a calibração das taxas de falha e dos tempos de reparo é realizada separadamente. Adicionalmente, a utilização de restrições de igualdade nos modelos de calibração assegura que os valores calculados dos índices FEC e DEC sejam idênticos aos seus valores medidos. Além disso, o modelo de calibração proposto para as taxas de falha considera a informação de condição dos equipamentos obtida a partir de atividades de inspeção. Os modelos de calibração propostos nesta dissertação foram testados em um alimentador da Companhia Energética do Maranhão (CEMAR). Os resultados dos testes demonstraram que os modelos de calibração propostos podem reduzir significativamente os erros entre os valores medidos e calculados dos índices FIC e DIC.

>Magister Scientiae - MSc / In this thesis, we discuss methods for optimising the expected rate of return of a portfolio with minimal risk. As part of the work we look at the Modern Portfolio Theory which tries to maximise the portfolio's expected rate of return for a cer- tain amount of risk. We also use Quadratic Programming to optimise portfolios. Generally it is recognised that portfolios with a high expected return, carry higher risk. The Modern Portfolio Theory assists when choosing portfolios with the lowest possible risk. There is a nite number of assets in a portfolio and we therefore want to allocate them in such a way that we're able to optimise the expected rate of return with minimal risk. We also use the Markowian approach to allocate these assets. The Capital Asset Pricing Model is also used, which will help us to reduce our e cient portfolio to a single portfolio. Furthermore we use the Black-Litterman model to try and optimise our portfolio with a view to understanding the current market conditions, as well as considering how the market will perform in the future. An additional tool we'll use is Value at Risk. This enables us to manage the market risk. To this end, we follow the three basic approaches from Jorion [Value at Risk. USA: McGraw-Hills, 2001]. The Value at Risk tool has become essential in calcu- lating a portfolio's risk over the last decade. It works by monitoring algorithms in order to nd the worst possible scenarios within the portfolio. We perform several numerical experiments in MATLAB and Microsoft Excel and these are presented in the thesis with the relevant descriptions.

Distributed parameter systems (DPS) comprise an important class of engineering systems ranging from "traditional" such as tubular reactors, to cutting edge processes such as nano-scale coatings. DPS have been studied extensively and significant advances have been noted, enabling their accurate simulation. To this end a variety of tools have been developed. However, extending these advances for systems design is not a trivial task . Rigorous design and operation policies entail systematic procedures for optimisation and control. These tasks are "upper-level" and utilize existing models and simulators. The higher the accuracy of the underlying models, the more the design procedure benefits. However, employing such models in the context of conventional algorithms may lead to inefficient formulations. The optimisation and control of DPS is a challenging task. These systems are typically discretised over a computational mesh, leading to large-scale problems. Handling the resulting large-scale systems may prove to be an intimidating task and requires special methodologies. Furthermore, it is often the case that the underlying physical phenomena span various temporal and spatial scales, thus complicating the analysis. Stiffness may also potentially be exhibited in the (nonlinear) models of such phenomena. The objective of this work is to design reliable and practical procedures for the optimisation and control of DPS. It has been observed in many systems of engineering interest that although they are described by infinite-dimensional Partial Differential Equations (PDEs) resulting in large discretisation problems, their behaviour has a finite number of significant components , as a result of their dissipative nature. This property has been exploited in various systematic model reduction techniques. Of key importance in this work is the identification of a low-dimensional dominant subspace for the system. This subspace is heuristically found to correspond to part of the eigenspectrum of the system and can therefore be identified efficiently using iterative matrix-free techniques. In this light, only low-dimensional Jacobians and Hessian matrices are involved in the formulation of the proposed algorithms, which are projections of the original matrices onto appropriate low-dimensional subspaces, computed efficiently with directional perturbations.The optimisation algorithm presented employs a 2-step projection scheme, firstly onto the dominant subspace of the system (corresponding to the right-most eigenvalues of the linearised system) and secondly onto the subspace of decision variables. This algorithm is inspired by reduced Hessian Sequential Quadratic Programming methods and therefore locates a local optimum of the nonlinear programming problem given by solving a sequence of reduced quadratic programming (QP) subproblems . This optimisation algorithm is appropriate for systems with a relatively small number of decision variables. Inequality constraints can be accommodated following a penalty-based strategy which aggregates all constraints using an appropriate function , or by employing a partial reduction technique in which only equality constraints are considered for the reduction and the inequalities are linearised and passed on to the QP subproblem . The control algorithm presented is based on the online adaptive construction of low-order linear models used in the context of a linear Model Predictive Control (MPC) algorithm , in which the discrete-time state-space model is recomputed at every sampling time in a receding horizon fashion. Successive linearisation around the current state on the closed-loop trajectory is combined with model reduction, resulting in an efficient procedure for the computation of reduced linearised models, projected onto the dominant subspace of the system. In this case, this subspace corresponds to the eigenvalues of largest magnitude of the discretised dynamical system. Control actions are computed from low-order QP problems solved efficiently online.The optimisation and control algorithms presented may employ input/output simulators (such as commercial packages) extending their use to upper-level tasks. They are also suitable for systems governed by microscopic rules, the equations of which do not exist in closed form. Illustrative case studies are presented, based on tubular reactor models, which exhibit rich parametric behaviour.

In this paper we discuss the identification of parameter functions in material models for elastic large deformations. A model of the the forward problem is given, where the displacement of a deformed material is found as the solution of a n onlinear PDE. Here, the crucial point is the definition of the 2nd Piola-Kirchhoff stress tensor by using several material laws including a number of material parameters. In the main part of the paper we consider the identification of such parameters from measured displacements, where the inverse problem is given as an optimal control problem. We introduce a solution of the identification problem with Lagrange and SQP methods. The presented algorithm is applied to linear elastic material with large deformations.

<p> This work focuses on solving the general optimal control problems with smart-learning-enabled and theory-supported optimal control (SET-OC) approaches. The proposed SET-OC includes two main directions. Firstly, according to the basic idea of the direct method, the smart-learning-enabled iterative optimization algorithm (SEIOA) is proposed for solving discrete optimal control problems. Via discretization and reformulation, the optimal control problem is converted into a general quadratically constrained quadratic programming (QCQP) problem. Then, the SEIOA is applied to solving QCQPs. To be specific, first, a structure-exploiting decomposition scheme is introduced to reduce the complexity of the original problem. Next, an iterative search, combined with an intersection-cutting plane, is developed to achieve global convergence. Furthermore, considering the implicit relationship between the algorithmic parameters and the convergence rate of the iterative search, deep learning is applied to design the algorithmic parameters from an appropriate amount of training data to improve convergence property. To demonstrate the effectiveness and improved computational performance of the proposed SEIOA, the developed algorithms have been implemented in extensive real-world application problems, including unmanned aerial vehicle path planning problems and general QCQP problems. According to the theoretical analysis of global convergence and the simulation results, the efficiency, robustness, and improved convergence rate of the optimization framework compared to the state-of-the-art optimization methods for solving general QCQP problems are analyzed and verified. Secondly, the onboard learning-based optimal control method (L-OCM) is proposed to solve the optimal control problems. Supported by the optimal control theory, the necessary conditions of optimality for optimal control of the optimal control problem can be derived, which leads to two two-point-boundary-value-problems (TPBVPs). Then, critical parameters are identified to approximate the complete solutions of the TPBVPs. To find the implicit relationship between the initial states and these critical parameters, deep neural networks are constructed to learn the values of these critical parameters in real-time with training data obtained from the offline solutions.  To demonstrate the effectiveness and improved computational performance of the proposed L-OCM approaches, the developed algorithms have been implemented in extensive real-world application problems, including two-dimensional human-Mars entry, powered-descent, landing guidance problems, and fuel-optimal powered descent guidance (PDG) problems. In addition, considering there is no thorough analysis of the properties of the optimal control profile for PDG when considering the state constraints, a rigid theoretical analysis of the fuel-optimal PDG problem with state constraints is further provided. According to the theoretical analysis and simulation results, the optimality, robustness, and real-time performance of the proposed L-OCM are analyzed and verified, which indicates the potential for onboard implementation. </p>

No description available.

In recent years, mobile robots have gained tremendous attention from the entire society: the industry is aiming at selling more intelligent products while the academia is improving their performance from all perspectives. Real world examples include autnomous driving vehicles, multirotors, legged robots, etc. One of the challenging tasks commonly faced by all game players, and all robotics platforms, is to plan motion or locomotion of the robot, calculate an optimal trajectory according to certain criterion and control it accordingly. Difficulty of solving such task usually arises from high-dimensionality and complexity of the system dynamics, fast changing conditions imposed as constraints and necessity for real-time deployment. This work proposes a method over the aforementioned mission by solving an optimal control problem in a receding horizon fashion. Unlike the existing Sequential Linear Quadratic [1] algorithm which is a continuous-time variant of Differential Dynamic Programming [2], we tackle the problem in a discretized multiple shooting fashion. Sequential Quadratic Programming is employed as optimization technique to solve the constrained Nonlinear Programming iteratively. Moreover, we apply trust region method in the sub Quadratic Programming to handle potential indefiniteness of Hessian matrix as well as to improve robustness of the solver. Simulation and benchmark with previous method have been conducted on robotics platforms to show the effectiveness of our solution and superiority under certain circumstances. Experiments have demonstrated that our method is capable of generating trajectories under complicated scenarios where the Hessian matrix contains negative eigenvalues (e.g. obstacle avoidance). / De senaste åren har mobila robotar fått enorm uppmärksamhet från hela samhället: branschen siktar på att sälja mer intelligenta produkter samtidigt som akademin förbättrar sina prestationer ur alla perspektiv. Exempel på verkligheten inkluderar autonoma körande fordon, multirotorer, robotar med ben, etc. En av de utmanande uppgifterna som vanligtvis alla spelare och alla robotplattformar står inför är att planera robotens rörelse eller rörelse, beräkna en optimal bana enligt vissa kriterier och kontrollera det därefter. Svårigheter att lösa en sådan uppgift beror vanligtvis på hög dimensionalitet och komplexitet hos systemdynamiken, snabbt föränderliga villkor som åläggs som begränsningar och nödvändighet för realtidsdistribution. Detta arbete föreslår en metod över det tidigare nämnda uppdraget genom att lösa ett optimalt kontrollproblem på ett vikande horisont. Till skillnad från den befintliga Sequential Linear Quadratic [1] algoritmen som är en kontinuerlig tidsvariant av Differential Dynamic Programming [2], tar vi oss an problemet på ett diskretiserat multipelfotograferingssätt. Sekventiell kvadratisk programmering används som optimeringsteknik för att lösa den begränsade olinjära programmeringen iterativt. Dessutom tillämpar vi trust region-metoden i den sub-kvadratiska programmeringen för att hantera potentiell obestämdhet av hessisk matris samt för att förbättra lösarens robusthet. Simulering och benchmark med tidigare metod har utförts på robotplattformar för att visa effektiviteten hos vår lösning och överlägsenhet under vissa omständigheter. Experiment har visat att vår metod är kapabel att generera banor under komplicerade scenarier där den hessiska matrisen innehåller negativa egenvärden (t.ex. undvikande av hinder).

This thesis describes the theory of model predictive control and application of the theory to synchronous drives. It shows explicit and on-line solutions and compares the results with classical vector control structure.

O constante aumento da demanda de energia elétrica sobre as redes e a necessidade de interligação de sistemas através de longas linhas de transmissão, culminaram em problemas relacionados à estabilidade do sistema de potência multimáquinas. Tais problemas envolvem oscilações eletromecânicas de baixa frequência classicadas como modos interáreas. Os modos interáreas são caracterizados por oscilações de frequências de até 1Hz e representam oscilações de um grupo de geradores de uma área contra grupos de geradores de outras áreas. Umavezqueoempregodeestabilizadoresdesistemasdepotência(ESP)possanãosersucienteparagarantirumamortecimentoadequadoaessesmodos,osdispositivosFACTSsurgem como uma alternativa ecaz para o amortecimento de oscilações de baixa frequência. Para este m, o Capacitor Série Controlado por Tiristor (TCSC - Thyristor Controlled Series Capacitor) é um dispositivo FACTS comumente empregado e quando utilizado juntamente com um controlador suplementar para amortecimento de oscilações de potência (POD - Power Oscillation Damping) garante ao sistema de potência estabilidade e amortecimento adequado. Assim, o objetivo deste trabalho de mestrado é realizar o projeto coordenado de controladores ESP e TCSC-POD efetuando um ajuste incremental dos parâmetros dos controladores através da formulação do problema por otimização e programação quadrática. Tal técnica foi utilizada anteriormente somente para o projeto de ESPs. No caso deste trabalho será feita uma adaptação para estender a possibilidade de aplicação da metodologia para casos com dispositivos FACTS presentes. / The increasing demand for electricity over networks and the need for systems interconnection through long transmission lines, resulted in problems related to the multi-machine power systemstability. Theseproblemsinvolvelowfrequencyoscillationsclassiedasinterareasmodes. These modes are characterized by oscillations in frequencies up to 1 Hz, and represent a group of generators from one area oscillating against generator groups from other areas. Once the use of power system stabilyzers (PSS) controllers may not be sucient to ensure adequate damping to these modes, the FACTS devices emerge as an ecient alternative to damping low frequency oscillations. For this purpose, the TCSC (Thyristor Controlled Series Capacitor)isacommonlyusedFACTSdeviceandwhenitisusedtogetherwithasupplementary controller POD (Power Oscillation Damping), ensures stability to power system and adequate damping. These controllers have the same structure as the PSS controllers. Therefore, the objective of this work is to carry out the coordinated design of PSS and TCSC-POD controllers, performing an incremental adjustment of the controllers parameters by formulating the problem as an optimization problem using quadratic programming. This method was previously used only for PSS design. In the case of this work, it is made an adaptation to extend the applicability of the methodology for cases in which there are FACTS devices present.