Orientador: Aurelio Ribeiro Leite de Oliveira / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica / Made available in DSpace on 2018-08-06T01:00:20Z (GMT). No. of bitstreams: 1 Probst_RoyWilhelm_M.pdf: 553863 bytes, checksum: a1307892a77da1b88d7536dd9027a4c3 (MD5) Previous issue date: 2006 / Resumo: Os métodos de pontos interiores primais-duais de trajetória central e preditor-corretor são desenvolvidos para o problema de minimização das perdas na geração e transmissão do pré-despacho DC de um sistema de potência hidrotêrmico e a estrutura matricial resultante explorada obtendo uma implementação eficiente. No pré-despacho de sistemas hidrotêrmicos, as usinas hidroelétricas têm uma meta a cumprir em um determinado dia, estabelecida pelo planejamento de longo prazo. As usinas termoelétricas, por sua vez, apresentam restrições de rampa, pois necessitam de um determinado tempo tanto para aumentar quanto para reduzir sua produção de energia. A implementação dos métodos de pontos interiores é testada em estudos de casos com sistemas IEEE / Abstract: The central path and the predictor-corrector primal-dual interior points methods are developed for the generation and transmission losses optimization problem for a DC power flow model in a hydrothermal power system and the resulting matrix structure is exploited leading to an efficient implementation. In short term hydrothermal scheduling, the hydro generating units need to satisfy daily targets, established by long-term scheduling models. The thermal generating units have ramp constraints because they need a certain amount of time to change de level of power delivery. Case studies with the developed interior point implementation for IEEE power systems are presented. / Mestrado / Pesquisa Operacional / Mestre em Matemática Aplicada

The focus of this thesis is formulation and development of a mathematical framework for the solution of the contingency constrained optimal power flow (OPF) based on sequential quadratic programming. The contingency constrained optimal power flow minimizes the total cost of a base case operating state as well as the expected cost of recovery from contingencies such as line or generation outages. The sequential quadratic programming (SCP) OPF formulation has been expanded in order to recognize contingency conditions and the problem is solved as a single entity by an efficient interior point method. The new formulation takes into account the system corrective capabilities in response to contingencies introduced through ramp-rate constraints. Contingency constrained OPF is a very challenging problem, because each contingency considered introduces a new problem as large as the base case problem. By proper system reduction and benefits of constraint relaxation (active set) methods, in which transmission constraints are not introduced until they are violated, the size of the system can be reduced significantly Therefore, restricting our attention to the active set constraint set makes this large problem significantly smaller and computationally feasible.

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

A new optimization algorithm, which can efficiently solve large-scale constrained non-linear optimization problems and leverage parallel computing, is designed and studied. The new algorithm, referred to herein as LASO or LArge Scale Optimizer, combines the best features of various algorithms to create a computationally efficient algorithm with strong convergence properties. Numerous algorithms were implemented and tested in its creation. Bound-constrained, step-size, and constrained algorithms have been designed that push the state-of-the-art. Along the way, five novel discoveries have been made: (1) a more efficient and robust method for obtaining second order Lagrange multiplier updates in Augmented Lagrangian algorithms, (2) a method for directly identifying the active constraint set at each iteration, (3) a simplified formulation of the penalty parameter sub-problem, (4) an efficient backtracking line-search procedure, (5) a novel hybrid line-search trust-region step-size calculation method. The broader impact of these contributions is that, for the first time, an Augmented Lagrangian algorithm is made to be competitive with state-of-the-art Sequential Quadratic Programming and Interior Point algorithms. The present work concludes by showing the applicability of the LASO algorithm to simulate one step of digital human walking and to accelerate the optimization process using parallel computing.

Traditionally, linear programming (LP) has been used to construct convex relaxations in the context of branch and bound for determining global optimal solutions to nonconvex optimization problems. As second-order cone programming (SOCP) and semidefinite programming (SDP) become better understood by optimization researchers, they become alternative choices for obtaining convex relaxations and producing bounds on the optimal values. In this thesis, we study the use of these convex optimization tools in constructing strong relaxations for several nonconvex problems, including 0-1 integer programming, nonconvex box-constrained quadratic programming (BoxQP), and general quadratic programming (QP). We first study a SOCP relaxation for 0-1 integer programs and a sequential relaxation technique based on this SOCP relaxation. We present desirable properties of this SOCP relaxation, for example, this relaxation cuts off all fractional extreme points of the regular LP relaxation. We further prove that the sequential relaxation technique generates the convex hull of 0-1 solutions asymptotically. We next explore nonconvex quadratic programming. We propose a SDP relaxation for BoxQP based on relaxing the first- and second-order KKT conditions, where the difficulty and contribution lie in relaxing the second-order KKT condition. We show that, although the relaxation we obtain this way is equivalent to an existing SDP relaxation at the root node, it is significantly stronger on the children nodes in a branch-and-bound setting. New advance in optimization theory allows one to express QP as optimizing a linear function over the convex cone of completely positive matrices subject to linear constraints, referred to as completely positive programming (CPP). CPP naturally admits strong semidefinite relaxations. We incorporate the first-order KKT conditions of QP into the constraints of QP, and then pose it in the form of CPP to obtain a strong relaxation. We employ the resulting SDP relaxation inside a finite branch-and-bound algorithm to solve the QP. Comparison of our algorithm with commercial global solvers shows potential as well as room for improvement. The remainder is devoted to new techniques for solving a class of large-scale linear programming problems. First order methods, although not as fast as second-order methods, are extremely memory efficient. We develop a first-order method based on Nesterov's smoothing technique and demonstrate the effectiveness of our method on two machine learning problems.

Este trabalho trata do planejamento de trajetórias que minimizam as perdas elétricas no KA\'I yxo, um robô escalador de árvores que tem por finalidade realizar monitoramento ambiental em florestas através da coleta de diferentes tipos de dados. Como essa aplicação requer que o robô permaneça em ambientes remotos, o estudo de técnicas que reduzam as perdas de energia a fim de que se aumente o tempo em operação do robô se mostra relevante, sendo a minimização das perdas elétricas uma contribuição importante nesse sentido. Estruturalmente, o KA\'I yxo consiste em um robô bípede com duas garras e quatro ligamentos interconectados por três juntas rotacionais. Além disso, seu mecanismo de andadura foi biologicamente inspirado na forma de locomoção observada em lagartas mede-palmos, o que permitiu tratar o robô como um manipulador industrial, cuja base é o ligamento associado à garra engastada e cujo efetuador é o ligamento associado à garra livre. Com isso, quando conveniente, o robô foi tratado em dois casos, conforme a garra que se encontra engastada. Inicialmente, realizou-se a modelagem matemática do robô, obtendo-se as equações cinemáticas direta e inversa, e dinâmicas, bem como o modelo das juntas segundo a abordagem do controle independente por junta. Posteriormente, formulou-se um problema de controle ótimo, solucionado através de um método numérico que o transformou em um problema de programação quadrática, que por sua vez foi resolvido iterativamente. Por fim, as trajetórias ótimas planejadas foram implementadas no robô real e, como forma de validação, as novas perdas elétricas foram comparadas com as das trajetórias anteriormente executadas pelo robô, determinando-se a correspondente economia de energia. / This work deals with the minimum-energy trajectory planning, related to the electrical losses, in KA\'I yxo, a tree-climbing robot that aims to perform environmental monitoring in forests through the collection of different types of data. As this application requires that the robot remains in remote environments, the study of techniques that reduce energy losses in order to increase the operation time of the robot is shown to be relevant, and the minimization of the electrical losses is an important contribution in this sense. Structurally, KA\'I yxo consists of a biped robot with two claws and four links interconnected by three revolute joints. In addition, its gait mechanism was biologically inspired in the form of locomotion observed in caterpillars, allowing to treat the robot as an industrial manipulator, which base is the link associated with the fixed claw and which end-effector is the link associated with the free claw. In consequence, when convenient, the robot was treated in two cases, according to the claw that is fixed. Initially, the mathematical model of the robot was developed, being obtained the forward and inverse kinematic and dynamic equations, as well as the model of the joints according to the independent joint control approach. Subsequently, an optimal control problem was formulated, which was solved through a numerical method that turned it into a quadratic programming problem, which in turn was solved iteratively. Finally, the planned optimal trajectories were implemented in the real robot and, as a form of validation, the new electrical losses were compared with those of the trajectories previously executed by the robot, being determined the corresponding energy saving.

This dissertation focuses on constrained control of two applications: helicopter and ocean current turbines (OCT). A major contribution in the helicopter application is a novel model predictive control (MPC) framework for helicopter shipboard operations in high demanding sea-based conditions. A complex helicopter-ship dynamics interface has been developed as a system of implicit nonlinear ordinary differential equations to capture essential characteristics of the nonlinear helicopter dynamics, the ship dynamics, and the ship airwake interactions. Various airwake models such as Control Equivalent Turbulence Inputs (CETI) model and Computation Fluid Dynamics (CFD) data of the airwake are incorporated in the interface to describe a realistic model of the shipborne helicopter. The feasibility of the MPC design is investigated using two case studies: automatic deck landing during the ship quiescent period in sea state 5, and lateral reposition toward the ship in different wind-over-deck conditions. To improve the overall MPC performance, an updating scheme for the internal model of the MPC is proposed using linearization around operating points. A mixed-integer MPC algorithm is also developed for helicopter precision landing on moving decks. The performance of this control structure is evaluated via numerical simulations of the automatic deck landing in adverse conditions such as landing on up-stroke, and down-stroke moving decks with high energy indices. Kino-dynamic motion planning for coordinated maneuvers to satisfy the helicopter-ship rendezvous conditions is implemented via mixed integer quadratic programming. In the OCT application, the major contribution is that a new idea is leveraged from helicopter blade control by introducing cyclic blade pitch control in OCT. A minimum energy, constrained control method, namely Output Variance Constrained (OVC) control is studied for OCT flight control in the presence of external disturbances. The minimum achievable output variance bounds are also computed and a parametric study of design parameters is conducted to evaluate their influence on the OVC performance. The performance of the OVC control method is evaluated both on the linear and nonlinear OCT models. Furthermore, control design for the OCT with sensor failures is also examined. Lastly, the MPC strategy is also investigated to improve the OCT flight control performance in simultaneous satisfaction of multiple constraints and to avoid blade stall. / Ph. D.

Includes bibliography. / Successful multivariable control system design demands knowledge, skill and creativity of the designer. The goal of the research described in this dissertation was to investigate, implement, and evaluate methods by which artificial intelligence techniques, in a broad sense, may be used in a design system to assist the user. An intelligent, interactive, control system design tool has been developed to fulfil this aim. The design tool comprises two main components; an expert system on the upper level, and a powerful CACSD package on the lower level. The expert system has been constructed to assist and guide the designer in using the facilities provided by the underlying CACSD package. Unlike other expert systems, the user is also aided in formulating and refining a comprehensive and achievable design specification, and in dealing with conflicts which may arise within this specification. The assistance is aimed at both novice and experienced designers. The CACSD package includes a synthesis program which attempts to find a controller that satisfies the design specification. The synthesis program is based upon a recent factorization theory approach, where the linear multivariable control system design problem is translated into, and techniques efficiency solved as, a quadratic programming problem, which significantly improve the time and space of this method have been developed, making it practical to solve substantial multivariable design problems using only a microcomputer. The design system has been used by students at the University of Cape Town. Designs produced using the expert system tool are compared against those produced using classical design methods.

With the rise of online retailer giants like Amazon, and enhancements in internet and mobile technologies, online shopping is becoming increasingly popular. This has lead to new opportunities in online price optimization. The overarching motivation and theme of this thesis is to review these opportunities and provide methods and models in the context of retailers' online pricing decisions. In Chapter 2 a multi-period revenue maximization and pricing optimization problem in the presence of reference prices is formulated as a mixed integer nonlinear program. Two algorithms are developed to solve the optimization problem: a generalized Benders' decomposition algorithm and a myopic heuristic. This is followed by numerical computations to illustrate the effciency of the solution approaches as well as some managerial pricing insights. In Chapter 3 a data-driven quadratic programming optimization model for online pricing in the presence of customer ratings is proposed. A new demand function is developed for a multi-product, nite horizon, online retail environment. To solve the optimization problem, a myopic pricing heuristic as well as exact solution approaches are introduced. Using customer reviews ratings data from Amazon.com, a new customer rating forecasting model is validated. This is followed by several analytical and numerical insights. In Chapter 4 a multinomial choice model is used for customer purchase decision to find optimal personalized price discounts for an online retailer that incorporates customer locations and feedback from their reviews. Closed form solutions are derived for two special cases of this problem. To gain some analytical insights extensive numerical experiments are carried followed by several analytical and numerical insights. / Thesis / Doctor of Philosophy (PhD) / The increase in online retail and the improvements in mobile technologies has lead to advantages and opportunities for both customers and retailers. One of these advantages is the ability to keep and efficiently access records of historical orders for both customers and retailers. In addition, online retailing has dramatically decreased the cost of price adjustments and discounts compared to the brick and mortar environment. At the same time, with the increase in online retailing we are witnessing proliferations of online reviews in e-commerce platforms. Given this availability of data and the new capabilities in an online retail environment, there is a need to develop pricing optimization models that integrate all these new features. The overarching motivation and theme of this thesis is to review these opportunities and provide methods and models in the context of retailers' online pricing decisions.

No description available.