Optimization refers to a branch of applied mathematics concerned with the minimization or maximization of a certain function, possibly under constraints. The birth of the field can perhaps be traced back to an astronomy problem solved by the young Gauss. It matured later with advances in physics, notably mechanics, where natural phenomena were described as the result of the minimization of certain “energy” functions. Optimization has evolved towards the study and application of algorithms to solve mathematical problems on computers.

Today, the field is at the intersection of many disciplines, ranging from statistics, to dynamical systems and control, complexity theory, and algorithms. It is applied to a widening array of contexts, including machine learning and information retrieval, engineering design, economics, finance, and management. With the advent of massive data sets, optimization is now viewed as a crucial component of the nascent field of data science.

In the last two decades, there has been a renewed interest in the field of optimization and its applications. One of the most exciting developments involves a special kind of optimization, convex optimization. Convex models provide a reliable, practical platform on which to build the development of reliable problem-solving software. With the help of user-friendly software packages, modelers can now quickly develop extremely efficient code to solve a very rich library of convex problems.

In this chapter we present a compact selection of numerical algorithms for performing basic matrix computations. Specifically, we describe the power iteration method for computing eigenvalues and eigenvectors of square matrices (along with some of its variants, and a version suitable for computing SVD factors); we discuss iterative algorithms for solving square systems of linear equations, and we detail the construction of the QR factorization for rectangular matrices.

7.1 Computing eigenvalues and eigenvectors

7.1.1 The power iteration method

In this section we outline a technique for computing eigenvalues and eigenvectors of a diagonalizable matrix. The power iteration (PI) method is perhaps the simplest technique for computing one eigenvalue/eigenvector pair for a matrix. It has rather slow convergence and it is subject to some limitations. However, we present it here since it forms the building block of many other more refined algorithms for eigenvalue computation, such as the Hessenberg QR algorithm, and also because interest in the PI method has been recently revived by applications to very large-scale matrices, such as the ones arising in web-related problems (e.g., Google PageRank). Many other techniques exist for computing eigenvalues and eigenvectors, some of them tailored for matrices with special structure, such as sparse, banded, or symmetric. Such algorithms are described in standard texts on numerical linear algebra.

Optimization is a technology that can be used to devise effective decisions or predictions in a variety of contexts, ranging from production planning to engineering design and finance, to mention just a few. In simplified terms, the process for reaching the decision starts with a phase of construction of a suitable mathematical model for a concrete problem, followed by a phase where the model is solved by means of suitable numerical algorithms. An optimization model typically requires the specification of a quantitative objective criterion of goodness for our decision, which we wish to maximize (or, alternatively, a criterion of cost, which we wish to minimize), as well as the specification of constraints, representing the physical limits of our decision actions, budgets on resources, design requirements that need be met, etc. An optimal design is one which gives the best possible objective value, while satisfying all problem constraints.

In this chapter, we provide an overview of the main concepts and building blocks of an optimization problem, along with a brief historical perspective of the field. Many concepts in this chapter are introduced without formal definition; more rigorous formalizations are provided in the subsequent chapters.

1.1 Motivating examples

We next describe a few simple but practical examples where optimization problems arise naturally. Many other more sophisticated examples and applications will be discussed throughout the book.

Dynamical systems are physical systems evolving in time. Typically, these systems are modeled mathematically by a system of ordinary differential equations, in which command and disturbance signals act as inputs that, together with pre-existing initial conditions, generate the evolution in time of internal variables (the states) and of output signals. These kinds of model are ubiquitous in engineering, and are used to describe, for instance, the behavior of an airplane, the functioning of a combustion engine, the dynamics of a robot manipulator, or the trajectory of a missile.

Broadly speaking, the problem of control of a dynamical system amounts to determining suitable input signals so as to make the system behave in a desired way, e.g., to follow a desired output trajectory, to be resilient to disturbances, etc. Even an elementary treatment of control of dynamical systems would require an entire text-book. Here, we simply focus on very few specific aspects related to a restricted class of dynamical systems, namely finite-dimensional, linear, and time-invariant systems.

We start our discussion by introducing continuous-time models and their discrete-time counterparts. For discrete-time models, we highlight the connections between the input-output behavior over a finite horizon, and static linear maps described by systems of linear equations. We shall show how certain optimization problems arise naturally in this context, and discuss their interpretation in a control setting.

A vector is a collection of numbers, arranged in a column or a row, which can be thought of as the coordinates of a point in n-dimensional space. Equipping vectors with sum and scalar multiplication allows us to define notions such as independence, span, subspaces, and dimension. Further, the scalar product introduces a notion of the angle between two vectors, and induces the concept of length, or norm. Via the scalar product, we can also view a vector as a linear function. We can compute the projection of a vector onto a line defined by another vector, onto a plane, or more generally onto a subspace. Projections can be viewed as a first elementary optimization problem (finding the point in a given set at minimum distance from a given point), and they constitute a basic ingredient in many processing and visualization techniques for high-dimensional data.

2.1 Vector basics

2.1.1 Vectors as collections of numbers

Vectors are a way to represent and manipulate a single collection of numbers. A vector x can thus be defined as a collection of elements x1, x2, …, xn, arranged in a column or in a row. We usually write vectors in column format:

Element xi is said to be the i-th component (or the i-th element, or entry) of vector x, and the number n of components is usually referred to as the dimension of x.

This book arose out of lecture notes for the graduate-level course AE584 Guidance, Navigation, and Avionics, taught in the Department of Aerospace Engineering at the University of Michigan at Ann Arbor. The course was originally introduced by Professor Emeritus Robert M. Howe and was taught for a number of years by the authors.

This book can be used as a textbook supporting a graduate-level formal course on aerospace navigation and guidance. It can also be used as a guide for self-study on the subject. Finally, it can be used as a reference text. To enhance its usability, the book contains numerous examples illustrating concepts and homework problems at the end of all chapters. A partial solution manual for these homework problems is available with limited circulation.

Although this book uses many mathematical results, it is not a mathematics text. The results are stated with some rigor, but only a few proofs of special interest are given. The interested reader may consult the bibliography listed at the end of each chapter for proofs and additional information.

The prerequisite knowledge includes undergraduate instruction in elementary linear algebra, differential equations, and flight mechanics, which are standard in aerospace engineering curricula. Key definitions and mathematical results are given in the appendix.

The intended audience for this book encompasses graduate students in engineering specializing in flight dynamics, guidance, navigation, and control, together with practicing engineers and researchers in the field. In the authors’ experience, this text maps to a two-semester graduate sequence, with the first semester covering roughly the first six chapters and the second semester covering roughly the last four chapters.

This chapter treats optimal control for the purpose of application to optimal guidance. Optimal control can be used to find, from among several candidates, the best trajectory to accomplish a mission.

Note that Chapter 8 provides the tools to perform optimization in finite dimensional spaces. In practice, trajectory optimization can be, through appropriate discretization, transformed into a finite dimensional optimization problem; see, for instance, Section 8.4. So, the reader may ask: Why study optimal control beyond finite dimensional optimization? There are at least two compelling pragmatic answers to this question. First, after discretization, evaluating the gradients of the objective function and the constraints is generally much more cumbersome than writing the differential equations stemming from optimal control. Second, optimal control reveals the special structure of the state - co-state dynamics, the Hamiltonian or symplectic structure, which can be exploited in both analysis and computation.

Section 9.1 introduces and formulates the optimal control problem. Section 9.2 gives examples of optimal guidance problems fitting the formulation. Section 9.3 extends the results of Section 8.4 to obtain necessary conditions for optimal control without control constraints. Section 9.4 treats the case of control constraints, yielding the maximum principle. Section 9.5 is devoted to dynamic programming, which provides sufficient conditions. Section 9.6 elucidates the relationship between the results on optimal control and dynamic programming. Sections 9.7, 9.8, and 9.9 present a summary of the key results in the chapter, bibliographic notes for further reading and homework problems, respectively.

Purpose and Motivation

The purpose of this book is to present fundamentals used in the navigation and guidance of aerospace vehicles. By fundamentals, we mean a body of knowledge that does not change with advances in technology. Aerospace vehicles encompass all kinds of craft flying in the atmosphere or in space. Navigation is concerned with the questions: Where is the vehicle? What is its velocity? And what are its angular orientation and angular rates? Guidance is concerned with the question: What maneuvers should we perform to cause the vehicle to go where we want, while meeting the specifications of the mission?

For centuries, devices such as charts, magnetic compasses, drafting compasses, sextants, and clocks were sufficient to solve the navigation and guidance problems of the time. In those days, velocities over land and sea were relatively slow, navigators could count on a variety of visible references (such as landmarks, beacons, or stars), and a human pilot controlled the vehicle during the entirety of the trip. However, the advent of air and space travel has posed substantial new challenges to navigators. First, aerospace vehicles generally travel much faster and farther than their land and sea counterparts. Second, whereas navigation on land and sea can be based on visible references, an aerospace navigator may be deprived of such resources. Finally, many aerospace missions require a high level of automation, either because they are unmanned or to minimize crew fatigue.

In this chapter, we present the theory that is used in the analysis and design of ballistic guidance systems, with an emphasis on the principles rather than on the implementation. The trajectory of a ballistic missile typically consists of three phases: a powered lift-off, a free flight (this typically lasts about 80% of the engagement), and an aerodynamic reentry (see Figure 6.1). The purpose of ballistic guidance is then to determine the boundary conditions between the first and second phases that lead to a hit, and to analyze the miss due to navigation errors. Note that the optimization of the first phase leads to interesting “rocket staging” problems that can be treated with methods introduced in Chapter 8.

Section 6.1 describes the restricted two-body problem. Section 6.2 deals with the two-dimensional hit equation, whereas Section 6.3 contains the in-plane error analysis. Section 6.4 deals with three-dimensional error analysis, Section 6.5 with accounting for effects of the Earth's rotation. Section 6.6 considers the effect of the Earth's oblateness and geophysical uncertainties. Section 6.7 presents a general framework for numerical solution of general ballistic guidance problems. Sections 6.8, 6.9, and 6.10 present a summary of the key results in the chapter, bibliographic notes for further reading, and homework problems, respectively.

The Restricted Two-Body Problem

Assume that a ballistic missile, modeled as a particle, moves above the sensible atmosphere (i.e., above an altitude of 80 km). We assume that the Earth is nonrotating and perfectly spherical.

This chapter presents the fundamentals of deterministic systems theory that we use in the analysis and synthesis of aerospace navigation and guidance systems. The emphasis is on linear, time varying dynamic systems. This emphasis is justified in Section 2.1, where it is shown that when the trajectory of a nonlinear system undergoes a small perturbation, the time history of that perturbation can be approximated using a linear system. Thus, this linear approach is appropriate when the navigation and guidance errors are small. This, of course, implicitly assumes that we use successful navigation and guidance laws to ensure small errors.

In addition to system linearization, Section 2.1 surveys properties of linear dynamic systems: the state transition matrix and its features, various notions of stability and their criteria, the variation of constants formula, and the impulse response. Section 2.2 studies observability, which is a central concept in navigation. Section 2.3 considers the particular case of linear, time invariant dynamic systems. Section 2.4 presents the method of adjoints, which is invaluable in terminal guidance because it yields the miss distance due to a perturbation of the trajectory as a function of the time at which the perturbation is applied. Finally, Section 2.5 discusses controllability and the duality between controllability and observability. Sections 2.6, 2.7, and 2.8 present a summary of the key results in the chapter, bibliographic notes for further reading, and homework problems, respectively.

During this 10-chapter journey through Fundamentals of Aerospace Navigation and Guidance, the book endeavors to give an orderly account of the lay of this land. This orderliness should now be apparent through synergies between many items. By this we mean that, often, a newly introduced fundamental relies on past fundamentals, sheds new light on some of them, and foreshadows future ones. Let us give examples of such synergies.

1. Inequality (1.2) establishes that, in static systems, good navigation combined with good navigation-based guidance guarantees good guidance. This principle is extended to deterministic linear dynamic systems through inequality (7.54) under the umbrella of the deterministic separation principle. Then, it is further extended to systems with linear dynamics, quadratic cost, and Gaussian noise processes in Section 9.5.6 under the umbrella of the stochastic separation principle.

2. The controllability Gramian is introduced in Proposition 2.22 to settle the binary question of controllability of a state. However, after deriving optimization results in Section 8.4 and extending them to optimal control in Section 9.3, we show in Example 9.6 that the same controllability Gramian can also be used as a quantitative measure of controllability through (9.54).

3. The implicit function theorem, introduced in Section 6.3 to analyze the accuracy of ballistic shots, is also used in Proposition 8.6 to establish the existence of Lagrange multipliers in constrained optimization. This result is extended in Sections 8.4 and 9.3 to establish the existence of the time varying co-state vector.