Spelling suggestions: "subject:"nonlinear aptimization"" "subject:"nonlinear foptimization""
11 |
A Nonlinear Optimization Approach to H2-Optimal Modeling and ControlPetersson, Daniel January 2013 (has links)
Mathematical models of physical systems are pervasive in engineering. These models can be used to analyze properties of the system, to simulate the system, or synthesize controllers. However, many of these models are too complex or too large for standard analysis and synthesis methods to be applicable. Hence, there is a need to reduce the complexity of models. In this thesis, techniques for reducing complexity of large linear time-invariant (lti) state-space models and linear parameter-varying (lpv) models are presented. Additionally, a method for synthesizing controllers is also presented. The methods in this thesis all revolve around a system theoretical measure called the H2-norm, and the minimization of this norm using nonlinear optimization. Since the optimization problems rapidly grow large, significant effort is spent on understanding and exploiting the inherent structures available in the problems to reduce the computational complexity when performing the optimization. The first part of the thesis addresses the classical model-reduction problem of lti state-space models. Various H2 problems are formulated and solved using the proposed structure-exploiting nonlinear optimization technique. The standard problem formulation is extended to incorporate also frequency-weighted problems and norms defined on finite frequency intervals, both for continuous and discrete-time models. Additionally, a regularization-based method to account for uncertainty in data is explored. Several examples reveal that the method is highly competitive with alternative approaches. Techniques for finding lpv models from data, and reducing the complexity of lpv models are presented. The basic ideas introduced in the first part of the thesis are extended to the lpv case, once again covering a range of different setups. lpv models are commonly used for analysis and synthesis of controllers, but the efficiency of these methods depends highly on a particular algebraic structure in the lpv models. A method to account for and derive models suitable for controller synthesis is proposed. Many of the methods are thoroughly tested on a realistic modeling problem arising in the design and flight clearance of an Airbus aircraft model. Finally, output-feedback H2 controller synthesis for lpv models is addressed by generalizing the ideas and methods used for modeling. One of the ideas here is to skip the lpv modeling phase before creating the controller, and instead synthesize the controller directly from the data, which classically would have been used to generate a model to be used in the controller synthesis problem. The method specializes to standard output-feedback H2 controller synthesis in the lti case, and favorable comparisons with alternative state-of-the-art implementations are presented.
|
12 |
Solution of Large-scale Structured Optimization Problems with Schur-complement and Augmented Lagrangian Decomposition MethodsJose S Rodriguez (6760907) 02 August 2019 (has links)
<pre>In this dissertation we develop numerical algorithms and software tools to facilitate parallel solutions of nonlinear programming (NLP) problems. In particular, we address large-scale, block-structured problems with an intrinsic decomposable configuration. These problems arise in a great number of engineering applications, including parameter estimation, optimal control, network optimization, and stochastic programming. The structure of these problems can be leveraged by optimization solvers to accelerate solutions and overcome memory limitations, and we propose variants to two classes of optimization algorithms: augmented Lagrangian (AL) schemes and Schur-complement interior-point methods. </pre>
<pre><br></pre>
<pre>The convergence properties of augmented Lagrangian decomposition schemes like the alternating direction method of multipliers (ADMM) and progressive hedging (PH) are well established for convex optimization but convergence guarantees in non-convex settings are still poorly understood. In practice, however, ADMM and PH often perform satisfactorily in complex non-convex NLPs. In this work, we study connections between the method of multipliers (MM), ADMM, and PH to derive benchmarking metrics that explain why PH and ADMM work in practice. We illustrate the concepts using challenging dynamic optimization problems. Our exposition seeks to establish more formalism in benchmarking ADMM, PH, and AL schemes and to motivate algorithmic improvements.</pre>
<pre><br></pre>
<pre>The effectiveness of nonlinear interior-point solvers for solving large-scale problems relies quite heavily on the solution of the underlying linear algebra systems. The schur-complement decomposition is very effective for parallelizing the solution of linear systems with modest coupling. However, for systems with large number of coupling variables the schur-complement method does not scale favorably. We implement an approach that uses a Krylov solver (GMRES) preconditioned with ADMM to solve block-structured linear systems that arise in the interior-point method. We show that this ADMM-GMRES approach overcomes the well-known scalability issues of Schur decomposition.</pre>
<pre><br></pre>
<pre>One important drawback of using decomposition approaches like ADMM and PH is their convergence rate. Unlike Schur-complement interior-point algorithms that have super-linear convergence, augmented Lagrangian approaches typically exhibit linear and sublinear rates. We exploit connections between ADMM and the Schur-complement decomposition to derive an accelerated version of ADMM. Specifically, we study the effectiveness of performing a Newton-Raphson algorithm to compute multiplier estimates for augmented Lagrangian methods. We demonstrate using two-stage stochastic programming problems that our multiplier update achieves convergence in fewer iterations for MM on general nonlinear problems. In the case of ADMM, the newton update significantly reduces the number of subproblem solves for convex quadratic programs (QPs). Moreover, we show that using newton multiplier updates makes the method robust to the selection of the penalty parameter.</pre>
<pre><br></pre>
<pre>Traditionally, state-of-the-art optimization solvers are implemented in low-level programming languages. In our experience, the development of decomposition algorithms in these frameworks is challenging. They present a steep learning curve and can slow the development and testing of new numerical algorithms. To mitigate these challenges, we developed PyNumero, a new open source framework implemented in Python and C++. The package seeks to facilitate development of optimization algorithms for large-scale optimization within a high-level programming environment while at the same time minimizing the computational burden of using Python. The efficiency of PyNumero is illustrated by implementing algorithms for problems arising in stochastic programming and optimal control. Timing results are presented for both serial and parallel implementations. Our computational studies demonstrate that with the appropriate balance between compiled code and Python, efficient implementations of optimization algorithms are achievable in these high-level languages.</pre>
|
13 |
Génération de Posture Multi-Contact Viable pour Robot Humanoïde par Optimisation non-linéaire sur Variétés / Viable Multi-Contact Posture Computation for Humanoid Robots using Nonlinear Optimization on ManifoldsBrossette, Stanislas 10 October 2016 (has links)
Un robot humanoïde est un système polyarticulé complexe dont la cinématique et la dynamique sont gouvernées par des équations non linéaires. Trouver des postures viables qui minimisent une tâche objectif tout en satisfaisant un ensemble de contraintes (intrinsèques ou extrinsèques) est un problème central pour la planification de mouvement robotique et est une fonctionnalité importante de tout logiciel de robotique. Le générateur de posture (PG) a pour rôle de trouver une posture viable en formulant puis résolvant un problème d’optimisation non linéaire. Nous étendons l’état de l’art en proposant de nouvelles formulations et méthodes de résolution de problèmes de génération de postures. Nous enrichissons la formulation de contraintes de contact par ajout de variables au problème d’optimisation, ce qui permet au solveur de décider automatiquement de la zone d’intersection entre deux polygones en contact ou encore de décider du lieu de contact sur une surface non plane. Nous présentons une reformulation du PG qui gère nativement les variétés non Euclidiennes et nous permet de formuler des problèmes mathématiques plus élégants et efficaces. Pour résoudre de tels problèmes, nous avons développé un solveur non linéaire par SQP qui supporte nativement les variables sur variétés. Ainsi, nous avons une meilleure maîtrise de notre solveur et pouvons le spécialiser pour la résolution de problèmes de robotique. / Humanoid robots are complex poly-articulated structures whose kinematics and dynamics are governed by nonlinear equations. Finding viable postures to realize set-point task objectives under a set of constraints (intrinsic and extrinsic limitations) is a key issue in the planning of robot motion and an important feature of any robotics framework. It is handled by the so called posture generator (PG) that consists in formalizing the viable posture as the solution to a nonlinear optimization problem. We present several extensions to the state-of-the-art by exploring new formulations and resolution methods for the posture generation problems. We reformulate the notion of contact constraints by adding variables to enrich our optimization problem and allow the solver to decide on the shape of the intersection of contact polygons or of the location of a contact point on a non-flat surface. We present a reformulation of the PG problem that encompasses non-Euclidean manifolds natively for a more elegant and efficient mathematical formulation of the problems. To solve such problems, we decided to implement a new SQP solver that is most suited to non-Euclidean manifolds structural objects. By doing so, we have a better mastering in the way to tune and specialize our solver for robotics problems.
|
14 |
Uma arquitetura neuro-genética para otimização não-linear restrita / Neuro-genetic architecture for constrained nonlinear optimizationBertoni, Fabiana Cristina 15 October 2007 (has links)
Os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar problemas relacionados à otimização de sistemas. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. As redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de otimização não-linear restrita utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para o problema de otimização não-linear restrita. / Systems based on artificial neural networks and genetic algorithms are an alternative method for solving systems optimization problems. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. Artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving constrained nonlinear optimization problems using a neuro-genetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the constraint nonlinear optimization problem.
|
15 |
Kvazi Njutnovi postupci za probleme stohastičkog programiranja / Quasi Newton Methods for Stochastic Programming ProblemsOvcin Zoran 19 July 2016 (has links)
<p>Posmatra se problem minimizacije bez ograničenja. U determinističkom slučaju ti problemi se uspešno rešavaju iterativnim Kvazi Njutnovim postupcima. Ovde se istražuje stohastički slučaj, kada su poznate vrednosti funkcije cilja i njenog gradijenta na koje je uticao šum. Koristi se novi način određivanja dužina koraka, koji kombinuje metod linijskog pretraživanja i metod stohastičke aproksimacije tako da zadrži dobre osobine oba pristupa i obezbedi veću efikasnost postupka. Metod je testiran u kombinaciji sa više načina izbora pravca u iterativnom postupku. Dokazana je konvergencija novog postupka i testiranjem na velikom broju standardnih test problema pokazana njegova efikasnost. Takođe se za rešavanje problema ekvilibriuma u Neoklasičnoj ekonomiji predlaže i dokazuje konvergencija jednog Fiksnog Njutnovog postupka. U zadatku nalaženja rešenja za niz problema kojima se preciznije modelira slučajni sistem, ovaj Fiksni Njutnov postupak ostvaruje veliku uštedu CPU vremena u odnosu na Njutnov metod. U prvom delu teze je dat opšti teoretski uvod. U drugom delu je dat pregled relevantnih rezultata iz posmatranih oblasti zajedno sa dva originalna rezultata. U trećem delu su dati rezultati numeričkih testova.</p> / <p>The problem under consideration is unconstrained minimization pro-blem. The problem in deterministic case is often solved with Quasi Newton met-hods. In noisy environment, which is considered, new approach for step length along descent direction is used. The new approach combines line search and stoc-hastic approximation method using good characteristics of both enabling better efficiency. The convergence is proved. New step length is tested with three de-scent directions. Many standard test problems show the efficiency of the met-hod. Also, a new, affordable procedure based on application of the fixed Newton method for a sequence of equilibrium problems generated by simulation is intro-duced. The convergence conditions of the method are derived. The numerical results show a clear difference in the quality of information obtained by solving a sequence of problems if compared with the single equilibrium problem. In the first part general theoretical introduction is given. In the second part a survey of results from scientific community is given together with original results. The third part contains many numerical tests of new methods that show its efficiency.</p>
|
16 |
Uma arquitetura neuro-genética para otimização não-linear restrita / Neuro-genetic architecture for constrained nonlinear optimizationFabiana Cristina Bertoni 15 October 2007 (has links)
Os sistemas baseados em redes neurais artificiais e algoritmos genéticos oferecem um método alternativo para solucionar problemas relacionados à otimização de sistemas. Os algoritmos genéticos devem a sua popularidade à possibilidade de percorrer espaços de busca não-lineares e extensos. As redes neurais artificiais possuem altas taxas de processamento por utilizarem um número elevado de elementos processadores simples com alta conectividade entre si. Redes neurais com conexões realimentadas fornecem um modelo computacional capaz de resolver vários tipos de problemas de otimização, os quais consistem, geralmente, da otimização de uma função objetivo que pode estar sujeita ou não a um conjunto de restrições. Esta tese apresenta uma abordagem inovadora para resolver problemas de otimização não-linear restrita utilizando uma arquitetura neuro-genética. Mais especificamente, uma rede neural de Hopfield modificada é associada a um algoritmo genético visando garantir a convergência da rede em direção aos pontos de equilíbrio factíveis que representam as soluções para o problema de otimização não-linear restrita. / Systems based on artificial neural networks and genetic algorithms are an alternative method for solving systems optimization problems. The genetic algorithms must its popularity to make possible cover nonlinear and extensive search spaces. Artificial neural networks have high processing rates due to the use of a massive number of simple processing elements and the high degree of connectivity between these elements. Neural networks with feedback connections provide a computing model capable of solving a large class of optimization problems, which refer to optimization of an objective function that can be subject to constraints. This thesis presents a novel approach for solving constrained nonlinear optimization problems using a neuro-genetic approach. More specifically, a modified Hopfield neural network is associated with a genetic algorithm in order to guarantee the convergence of the network to the equilibrium points, which represent feasible solutions for the constraint nonlinear optimization problem.
|
17 |
Optimal Slewing of a Constrained Telescope Using Seventh Order Polynomial Input TorquesBush, Julia K 01 September 2012 (has links)
Two-axis gimbals are frequently used to point cameras and telescopes at various points of interest for surveillance, science, and art. The rotation of a two-axis gimbal system is governed by nonlinear angular momentum equations of motion. This paper presents a method for slewing a telescope in space with a gimbaled sensor attached to a nominally non-rotating spacecraft using two seventh order polynomial input functions to characterize torques. To accomplish this task, picking the optimal coefficients of the seventh order polynomial was necessary. It was also desired to use constraint equations to limit the excursion, angular velocity, angular acceleration, and jerk of the gimbal. A Matlab code was developed for this purpose. Matlab’s fmincon was used to do the optimization, and a comparison to a previously validated one-degree-of-freedom (DOF) model was presented for validation of the nonlinear, two-degree-of-freedom model. Results for a fully constrained 2 DOF slew maneuver were also shown. This thesis demonstrates that seventh order polynomial torques can be used to accurately slew a telescope in space using nonlinear equations of motion.
|
18 |
Mathematical programming techniques for solving stochastic optimization problems with certainty equivalent measures of riskVinel, Alexander 01 May 2015 (has links)
The problem of risk-averse decision making under uncertainties is studied from both modeling and computational perspectives. First, we consider a framework for constructing coherent and convex measures of risk which is inspired by infimal convolution operator, and prove that the proposed approach constitutes a new general representation of these classes. We then discuss how this scheme may be effectively employed to obtain a class of certainty equivalent measures of risk that can directly
incorporate decision maker's preferences as expressed by utility functions. This approach is consequently utilized to introduce a new family of measures, the log-exponential convex measures of risk. Conducted numerical experiments show that this family can be a useful tool when modeling risk-averse decision preferences under heavy-tailed distributions of uncertainties. Next, numerical methods for solving the rising optimization problems are developed. A special attention is devoted to the class p-order cone programming problems and mixed-integer models. Solution approaches proposed include approximation schemes for $p$-order cone and more general nonlinear programming problems, lifted conic and nonlinear valid inequalities, mixed-integer rounding conic cuts and new linear disjunctive cuts.
|
19 |
Real-Time Optimal Parametric Design of a Simple Infiltration-Evaporation Model Using the Assess-Predict-Optimize (APO) StrategyAli, S., Damodaran, Murali, Patera, Anthony T. 01 1900 (has links)
Optimal parametric design of a system must be able to respond quickly to short term needs as well as long term conditions. To this end, we present an Assess-Predict-Optimize (APO) strategy which allows for easy modification of a system’s characteristics and constraints, enabling quick design adaptation. There are three components to the APO strategy: Assess - extract necessary information from given data; Predict - predict future behavior of system; and Optimize – obtain optimal system configuration based on information from the other components. The APO strategy utilizes three key mathematical ingredients to yield real-time results which would certainly conform to given constraints: dimension reduction of the model, a posteriori error estimation, and optimization methods. The resulting formulation resembles a bilevel optimization problem with an inherent nonconvexity in the inner level. Using a simple infiltration-evaporation model to simulate an irrigation system, we demonstrate the APO strategy’s ability to yield real-time optimal results. The linearized model, described by a coercive elliptic partial differential equation, is discretized by the reduced-basis output bounds method. A primal-dual interior point method is then chosen to solve the resulting APO problem. / Singapore-MIT Alliance (SMA)
|
20 |
Simultaneous activity and attenuation reconstruction in emission tomographyDicken, Volker January 1998 (has links)
In single photon emission computed tomography (SPECT) one is interested in reconstructing the activity distribution f of some radiopharmaceutical. The data gathered suffer from attenuation due to the tissue density µ. Each imaged slice incorporates noisy sample values of the nonlinear attenuated Radon transform
(formular at this place in the original abstract)
Traditional theory for SPECT reconstruction treats µ as a known parameter. In practical applications, however, µ is not known, but either crudely estimated, determined in costly additional measurements or plainly neglected. We demonstrate that an approximation of both f and µ from SPECT data alone is feasible, leading to quantitatively more accurate SPECT images. The result is based on nonlinear Tikhonov regularization techniques for parameter estimation problems in differential equations combined with Gauss-Newton-CG minimization.
|
Page generated in 0.1265 seconds