Control systems and optimization

Summary

In many practical situations, the number and existence of objects that are supposed to be tracked are a priori unknown. This information is an important part of the tracking output. In this chapter we include the object existence in the track state. As in previous chapters, the track state pdf propagates between scans as a Markov process, and is updated using the Bayes formula.

Object existence is particularly important in the cluttered environment, when the origin of each measurement is a priori unknown. This chapter reveals the close relationship (generalization/specialization) of a number of object-existence-based target tracking filters, which have a common derivation and common update cycle.

Some of the algorithms mentioned here also appear in other chapters of this book. These include probabilistic data association (PDA) (Section 4.3), integrated PDA (IPDA) (Sections 5.4.4 and 6.4.4) and joint IPDA (JIPDA) (Section 6.4.5). The derivations of this chapter follow a different track, and the results are more general as they also cater for non-homogeneous clutter.

Introduction

Object tracking aims to estimate the states of a (usually moving) unknown number of objects, using measurements received from sensors, and based on assumptions and models of the objects and measurements.

The object tracking algorithms presented in this chapter are based on the following assumptions, unless stated otherwise:

Object:
– There are zero or more objects in the surveillance area. The number and the position of the objects are a priori unknown.
[…]

This is a textbook and reference for readers interested in quasilinear control (QLC). QLC is a set of methods for performance analysis and design of linear plant or nonlinear instrumentation (LPNI) systems. The approach of QLC is based on the method of stochastic linearization, which reduces the nonlinearities of actuators and sensors to quasilinear gains. Unlike the usual - Jacobian linearization - stochastic linearization is global. Using this approximation, QLC extends most of the linear control theory techniques to LPNI systems. A bisection algorithm for solving these equations is provided. In addition, QLC includes new problems, specific for the LPNI scenario. Examples include Instrumented LQR/LQG, in which the controller is designed simultaneously with the actuator and sensor, and partial and complete performance recovery, in which the degradation of linear performance is either contained by selecting the right instrumentation or completely eliminated by the controller boosting.

In this complete introduction to the theory of finding derivatives of scalar-, vector- and matrix-valued functions with respect to complex matrix variables, Hjørungnes describes an essential set of mathematical tools for solving research problems where unknown parameters are contained in complex-valued matrices. The first book examining complex-valued matrix derivatives from an engineering perspective, it uses numerous practical examples from signal processing and communications to demonstrate how these tools can be used to analyze and optimize the performance of engineering systems. Covering un-patterned and certain patterned matrices, this self-contained and easy-to-follow reference deals with applications in a range of areas including wireless communications, control theory, adaptive filtering, resource management and digital signal processing. Over 80 end-of-chapter exercises are provided, with a complete solutions manual available online.

Summary

Introduction

Multivariable minimization can be approached using gradient and Hessian information, or using the function evaluations only. We have discussed the gradient- or derivative-based methods in earlier chapters. We present here several algorithms that do not involve derivatives. We refer to these methods as direct methods. These methods are referred to in the literature as zero order methods or minimization methods without derivatives. Direct methods are generally robust. A degree of randomness can be introduced in order to achieve global optimization. Direct methods lend themselves valuable when gradient information is not readily available or when the evaluation of the gradient is cumbersome and prone to errors. We present here the algorithms of cyclic coordinates, method of Hooke and Jeeves [1961], method of Rosenbrock [1960], simplex method of Nelder and Mead [1965], Powell's [1964] method of conjugate directions. The concepts of simulated annealing, genetic, and differential evolution algorithms are also discussed. Box's complex method for constrained problems is also included. All these algorithms are implemented in complete computer programs.

Cyclic Coordinate Search

In this method, the search is conducted along each of the coordinate directions for finding the minimum. If ei is the unit vector along the coordinate direction i, we determine the value αi minimizing f(α) = f(x + αei), where αi is a real number. A move is made to the new point x + αiei at the end of the search along the direction i.

Summary

Introduction

Linear programming (LP) is the term used for defining a wide range of optimization problems, in which the objective function to be minimized or maximized is linear in the unknown variables and the constraints are a combination of linear equalities and inequalities. LP problems occur in many real-life economic situations where profits are to be maximized or costs minimized with constraint limits on resources. While the simplex method introduced in the following can be used for hand solution of LP problems, computer use becomes necessary even for a small number of variables. Problems involving diet decisions, transportation, production and manufacturing, product mix, engineering limit analysis in design, airline scheduling, and so on, are solved using computers. Linear programming also has applications in nonlinear programming (NLP). Successive linearization of a nonlinear problem leads to a sequence of LP problems that can be solved efficiently.

Practical understanding and geometric concepts of LP problems including computer solutions with EXCEL SOLVER and MATLAB, and output interpretation are presented in Sections 4.1–4.5. Thus, even if the focus is on nonlinear programming, the student is urged to understand these sections. Subsequently, algorithms based on Simplex (Tableau-, Revised-, Dual-) and Interior methods, and Sensitivity Analysis, are presented.

Summary

Introduction

Transportation, assignment, and network problems are of great significance in engineering industry, agriculture, global economy, and commerce. These problems can be solved by the conventional simplex method of linear programming. However, because of their simpler structures, they are more efficiently solved by special methods. In most cases, the calculations involved are simple additions and subtractions and the methods are effective and robust. Many problems in totally different situations may be closely related to these models and the methods may be used for their solution. We consider the transportation, assignment, and network flow problems with a view to develop the formulation of the problems, the solution algorithms, and their implementation in simple computer codes.

Transportation Problem

There are m supply points where quantities s1, s2,…, sm, respectively, are produced or stocked. There are n delivery points or destinations where respective quantities of d1, d2,…, dn, are in demand. Cost is incurred on an item shipped from origination point i to the destination j. The problem is to determine the amounts (≥ 0) originating at i and delivered at j so that the supply and demand constraints are satisfied and the total cost is a minimum.

Summary

Introduction

Dynamic programming evolved out of the extensive work of Richard Bellman in the 1950s. The method is generally applicable to problems that break up into stages and exhibit the Markovian property. A process exhibits the Markovian property if the decisions for optimal return at a stage in the process depend only on the current state of the system and the subsequent decisions. A variety of problems in engineering, economics, agriculture and science exhibit this property. Dynamic programming is the method of choice in many computer science problems, such as the Longest Common Subsequence problem that is used frequently by biologists to determine the longest common subsequence in a pair of DNA sequences; it is also the method of choice to determine the difference between two files.

When applicable, advantages of dynamic programming over other methods lie in being able to handle discrete variables, constraints, and uncertainty at each subproblem level as opposed to considering all aspects simultaneously in an entire decision model, and in sensitivity analysis. However, computer implementation via dynamic programming does require some problem-dedicated code writing.

Dynamic programming relies on the principle of optimality enunciated by Bellman. The principle defines an optimal policy.

Summary

Introduction

The majority of engineering problems involve constrained minimization – that is, the task is to minimize a function subject to constraints. A very common instance of a constrained optimization problem arises in finding the minimum weight design of a structure subject to constraints on stress and deflection. Important concepts pertaining to linear constrained problems were discussed in Sections 4.1–4.5 in Chapter 4 including active or binding constraints, Lagrange multipliers, computer solutions, and geometric concepts. These concepts are also relevant to nonlinear problems. The numerical techniques presented here directly tackle the nonlinear constraints, most of which call an LP solver within the iterative loop. In contrast, penalty function techniques transform the constrained problem into a sequence of unconstrained problems as discussed in Chapter 6. In this chapter, we first present graphical solution for two variable problems and solution using EXCEL SOLVER and MATLAB. Subsequently, formulating problems in “standard NLP” form is discussed followed by optimality conditions, geometric concepts, and convexity. Four gradient-based numerical methods applicable to problems with differentiable functions are presented in detail:

Summary

Introduction

There are many problems where the variables are not divisible as fractions. Some examples are the number of operators that can be assigned to jobs, the number of airplanes that can be purchased, the number of plants operating, and so on. These problems form an important class called integer programming problems. Further, several decision problems involve binary variables that take the values 0 or 1. If some variables must be integers and others allowed to take fractional values, the problem is of the mixed integer type. Discrete programming problems are those problems where the variables are to be chosen from a discrete set of available sizes, such as available shaft sizes and beam sections, engine capacities, pump capacities.

In integer programming problems, treating the variable as continuous and rounding off the optimum solution to the nearest integer is easily justified if the involved quantities are large. Consider the example of the number of barrels of crude processed where the solution results in 234566.4 barrels. This can be rounded to 234566 barrels or even 234570 without significantly altering the characteristics of the solution. When the variable values are small, such as the number of aircraft in a fleet, rounding is no longer intuitive and may not even yield a feasible solution. In problems with binary variables, rounding makes no sense as the choice between 0 or 1 is a choice between two entirely different decisions. The following two variable example provides some characteristics of integer requirements.

Summary

Introduction

Optimization is the process of maximizing or minimizing a desired objective function while satisfying the prevailing constraints. Nature has an abundance of examples where an optimum system status is sought. In metals and alloys, the atoms take positions of least energy to form unit cells. These unit cells define the crystalline structure of materials. A liquid droplet in zero gravity is a perfect sphere, which is the geometric form of least surface area for a given volume. Tall trees form ribs near the base to strengthen them in bending. The honeycomb structure is one of the most compact packaging arrangements. Genetic mutation for survival is another example of nature's optimization process. Like nature, organizations and businesses have also strived toward excellence. Solutions to their problems have been based mostly on judgment and experience. However, increased competition and consumer demands often require that the solutions be optimum and not just feasible solutions. A small savings in a mass-produced part will result in substantial savings for the corporation. In vehicles, weight minimization can impact fuel efficiency, increased payloads, or performance. Limited material or labor resources must be utilized to maximize profit. Often, optimization of a design process saves money for a company by simply reducing the developmental time.

Summary

Introduction

Finite elements is a well known tool for analysis of structures. If we are given a structure, such as an airplane wing, a building frame, a machine component, etc., together with loads and boundary conditions, then finite elements can be used to determine the deformations and stresses in the structure. Finite elements can also be applied to analyze dynamic response, heat conduction, fluid flow, and other phenomena. Mathematically, it may be viewed as a numerical tool to analyze problems governed by partial differential equations describing the behavior of the system. Lucien Schmit in 1960 recognized the potential for combining optimization techniques in structural design [Schmit 1960]. Today, various commercial finite element packages have started to include some optimization capability in their codes. In the aircraft community, where weight and performance is a premium, special codes combining analysis and optimization have been developed. Some of the commercial codes are listed at the end of Chapter 1. The methodology discussed in this chapter assumes that a discretized finite element (or a boundary element) model exists. This is in contrast with classical approaches to optimization of structures that directly work with the differential equations governing equilibrium and aim for an analytical solution to the optimization problem.

Summary

This book is a revised and enhanced edition of the first edition. The authors have identified a clear need for teaching engineering optimization in a manner that integrates theory, algorithms, modeling, and hands-on experience based on their extensive experience in teaching, research, and interactions with students. They have strived to adhere to this pedagogy and reinforced it further in the second edition, with more detailed explanations, an increased number of solved examples and end-of-chapter problems, and source codes on multiple platforms.

The development of the software, which parallels the theory, has helped to explain the implementation aspects in the text with greater insight and accuracy. Students have integrated the optimization programs with simulation codes in their theses. The programs can be tried out by researchers and practicing engineers as well. Programs on the CD-ROM have been developed in Matlab, Excel VBA, VBScript, and Fortran. A battery of methods is available for the user. This leads to effective solution of problems since no single method can be successful on all problems.

The book deals with a variety of optimization problems: unconstrained, constrained, gradient, and nongradient techniques; duality concepts; multiobjective optimization; linear, integer, geometric, and dynamic programming with applications; and finite element–based optimization. Matlab graphics and optimization toolbox routines and the Excel Solver optimizer are presented in detail.

Summary

Introduction

Determination of the minimum of a real valued function of one variable, and the location of that minimum, plays an important role in nonlinear optimization. A one-dimensional minimization routine may be called several times in a multivariable problem. We show later that at the minimum point of a sufficiently smooth function, the slope is zero. If the slope and curvature information is available, minimum may be obtained by finding the location where the slope is zero and the curvature is positive. The need to determine the zero of a function occurs frequently in nonlinear optimization. Reliable and efficient ways of finding the minimum or a zero of a function are necessary for developing robust techniques for solving multivariable problems. We present the basic concepts involved in single variable minimization and zero finding.

Theory Related to Single Variable (Univariate) Minimization

We present the minimization ideas by considering a simple example. The first step is to determine the objective function that is to be optimized.

Example 2.1

Determine the objective function for building a minimum cost cylindrical refrigeration tank of volume 50 m3, if the circular ends cost $10 per m2, the cylindrical wall costs $6 per mm2, and it costs $80 per m2 to refrigerate over the useful life.

Control systems and optimization

Refine search

Refine search

Actions for selected content:

1474 results in Control systems and optimization

5 - Single- and multiple-object tracking in clutter: object-existence-based approach

Summary

Quasilinear Control

Complex-Valued Matrix Derivatives

7 - Direct Search Methods for Nonlinear Optimization

Summary

4 - Linear Programming

Summary

8 - Multiobjective Optimization

OPTIMIZATION CONCEPTS AND APPLICATIONS IN ENGINEERING

11 - Optimization Applications for Transportation, Assignment, and Network Problems

Summary

3 - Unconstrained Optimization

Contents

10 - Dynamic Programming

Summary

5 - Constrained Minimization

Summary

Frontmatter

9 - Integer and Discrete Programming

Summary

1 - Preliminary Concepts

Summary

12 - Finite Element-Based Optimization

Summary

Preface

Summary

Index

6 - Penalty Functions, Duality, and Geometric Programming

2 - One-Dimensional Unconstrained Minimization

Summary

Control systems and optimization

Refine search

Refine search

Actions for selected content:

Save Search

1474 results in Control systems and optimization

Summary

Quasilinear Control

Complex-Valued Matrix Derivatives

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary

Summary