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.

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.

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.

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.

Introduction

This chapter provides the tools for finding Hessians (i.e., second-order derivatives) in a systematic way when the input variables are complex-valued matrices. The proposed theory is useful when solving numerous problems that involve optimization when the unknown parameter is a complex-valued matrix. In an effort to build adaptive optimization algorithms, it is important to find out if a certain value of the complex-valued parameter matrix at a stationary point is a maximum, minimum, or saddle point; the Hessian can then be utilized very efficiently. The complex Hessian might also be used to accelerate the convergence of iterative optimization algorithms, to study the stability of iterative algorithms, and to study convexity and concavity of an objective function. The methods presented in this chapter are general, such that many results can be derived using the introduced framework. Complex Hessians are derived for some useful examples taken from signal processing and communications.

The problem of finding Hessians has been treated for real-valued matrix variables in Magnus and Neudecker (1988, Chapter 10). For complex-valued vector variables, the Hessian matrix is treated for scalar functions in Brookes (July 2009) and Kreutz-Delgado (2009, June 25th). Both gradients and Hessians for scalar functions that depend on complex-valued vectors are studied in van den Bos (1994a). The Hessian of real-valued functions depending on real-valued matrix variables is used in Payaró and Palomar (2009) to enhance the connection between information theory and estimation theory.

Introduction

Often in signal processing and communications, problems appear for which we have to find a complex-valued matrix that minimizes or maximizes a real-valued objective function under the constraint that the matrix belongs to a set of matrices with a structure or pattern (i.e., where there exist some functional dependencies among the matrix elements). The theory presented in previous chapters is not suited for the case of functional dependencies among elements of the matrix. In this chapter, a systematic method is presented for finding the generalized derivative of complex-valued matrix functions, which depend on matrix arguments that have a certain structure. In Chapters 2 through 5, theory has been presented for how to find derivatives and Hessians of complex-valued functions F: ℂN×Q × ℂN×Q → ℂM×P with respect to the complex-valued matrix Z∈ℂN×Q and its complex conjugate Z* ℂN×Q. As seen from Lemma 3.1, the differential variables d vec(Z) and d vec(Z*) should be treated as independent when finding derivatives. This is the main reason why the function F: ℂN×Q × ℂN×Q → ℂM×Pis denoted by two complex-valued input arguments F(Z, Z*) because Z ∈ ℂN×Q and Z* ∈ ℂN×Q should be treated independently when finding complex-valued matrix derivatives (see Lemma 3.1). Based on the presented theory, up to this point, it has been assumed that all elements of the input matrix variable Z contain independent elements.

Introduction

The definition of a complex-valued matrix derivative was given in Chapter 3 (see Definition 3.1). In this chapter, it will be shown how the complex-valued matrix derivatives can be found for all nine different types of functions given in Table 2.2. Three different choices are given for the complex-valued input variables of the functions, namely, scalar, vector, or matrix; in addition, three possibilities for the type of output that functions return, again, could be scalar, vector, or matrix. The derivative can be identified through the complex differential by using Table 3.2. In this chapter, it will be shown how the theory introduced in Chapters 2 and 3 can be used to find complex-valued matrix derivatives through examples. Many results are collected inside tables to make them more accessible.

The rest of this chapter is organized as follows: The simplest case, when the output of a function is a complex-valued scalar, is treated in Section 4.2, which contains three subsections (4.2.1, 4.2.2, and 4.2.3) when the input variables are scalars, vectors, and matrices, respectively. Section 4.3 looks at the case of vector functions; it contains Subsections 4.3.1, 4.3.2, and 4.3.3, which treat the three cases of complex-valued scalar, vector, and matrix input variables, respectively. Matrix functions are considered in Section 4.4, which contains three subsections. The three cases of complex-valued matrix functions with scalar, vector, and matrix inputs are treated in Subsections 4.4.1, 4.4.2, and 4.4.3, respectively. The chapter ends with Section 4.5, which consists of 10 exercises.

Introduction to the Book

To solve increasingly complicated open research problems, it is crucial to develop useful mathematical tools. Often, the task of a researcher or an engineer is to find the optimal values of unknown parameters that can be represented by complex-valued matrices. One powerful tool for finding the optimal values of complex-valued matrices is to calculate the derivatives with respect to these matrices. In this book, the main focus is on complex-valued matrix calculus because the theory of real-valued matrix derivatives has been thoroughly covered already in an excellent manner in Magnus and Neudecker (1988). The purpose of this book is to provide an introduction to the area of complex-valued matrix derivatives and to show how they can be applied as a tool for solving problems in signal processing and communications.

The framework of complex-valued matrix derivatives can be used in the optimization of systems that depend on complex design parameters in areas where the unknown parameters are complex-valued matrices with independent components, or where they belong to sets of matrices with certain structures. Many of the results discussed in this book are summarized in tabular form, so that they are easily accessible. Several examples taken from recently published material show how signal processing and communication systems can be optimized using complex-valued matrix derivatives. Note that the differentiation procedure is usually not sufficient to solve such problems completely; however, it is often an essential step toward finding the solution to the problem.

In many engineering problems, the unknown parameters are complex-valued matrices, and often, the task of the system designer is to find the values of these complex parameters, which optimize a certain scalar real-valued objective function.

This book is written as an engineering-oriented mathematics book. It introduces the field involved in finding derivatives of complex-valued functions with respect to complex-valued matrices, in which the output of the function may be a scalar, a vector, or a matrix. The theory of complex-valued matrix derivatives, collected in this book, will benefit researchers and engineers working in fields such as signal processing and communications. Theories for finding complex-valued derivatives with respect to both complex-valued matrices with independent components and matrices that have certain dependencies among the components are developed and illustrative examples that show how to find such derivatives are presented. Key results are summarized in tables. Through several research-related examples, it will be shown how complex-valued matrix derivatives can be used as a tool to solve research problems in the fields of signal processing and communications.

This book is suitable for M.S. and Ph.D. students, researchers, engineers, and professors working in signal processing, communications, and other fields in which the unknown variables of a problem can be expressed as complex-valued matrices. The goal of the book is to present the tools of complex-valued matrix derivatives such that the reader is able to use these theories to solve open research problems in his or her own field. Depending on the nature of the problem, the components inside the unknown matrix might be independent, or certain interrelations might exist among the components. Matrices with independent components are called unpatterned and, if functional dependencies exist among the elements, the matrix is called patterned or structured.

Introduction

A theory developed for finding derivatives with respect to real-valued matrices with independent elements was presented in Magnus and Neudecker (1988) for scalar, vector, and matrix functions. There, the matrix derivatives with respect to a real-valued matrix variable are found by means of the differential of the function. This theory is extended in this chapter to the case where the function depends on a complex-valued matrix variable and its complex conjugate, when all the elements of the matrix are independent. It will be shown how the complex differential of the function can be used to identify the derivative of the function with respect to both the complex-valued input matrix variable and its complex conjugate. This is a natural extension of the real-valued vector derivatives in Kreutz-Delgado (2008) and the real-valued matrix derivatives in Magnus and Neudecker (1988) to the case of complex-valued matrix derivatives. The complex-valued input variable and its complex conjugate should be treated as independent when finding complex matrix derivatives. For scalar complex-valued functions that depend on a complex-valued vector and its complex conjugate, a theory for finding derivatives with respect to complex-valued vectors, when all the vector components are independent, was given in Brandwood (1983). This was extended to a systematic and simple way of finding derivatives of scalar, vector, and matrix functions with respect to complex-valued matrices when the matrix elements are independent (Hjørungnes & Gesbert 2007a). In this chapter, the definition of the complex-valued matrix derivative will be given, and a procedure will be presented for how to obtain the complex-valued matrix derivative.