In this chapter, we will develop two case studies of problems that involve the solution of non-linear simultaneous equations. Both case studies will involve circuits, but the non-linearities will arise in different ways. The case studies are:

1. the solution of Kirchhoff's laws in a non-linear direct current (DC) circuit (Section 6.1), and

2. the solution of Kirchhoff's laws in a linear alternating current (AC) circuit where the variables of interest are not currents and voltages but instead are power (and “reactive power”) injections (Section 6.2).

The first case study will draw on the development from the linear circuit study described in Section 4.1 and we will not repeat in detail those issues that were already presented in Section 4.1. The second case study will be discussed in considerable detail.

The progression from the case study of Section 4.1 to the case studies of Sections 6.1 and 6.2 are examples of model extension and development. By developing the model incrementally, we can treat a few issues at a time without being overwhelmed by trying to analyze all the issues at once. In developing your own models, you might also build them step-wise, rather than all-at-once. Even an unrealistically simple initial model can provide valuable insights into more realistic cases. For example, most DC circuits in practice include at least some non-linear components. Nevertheless, formulation of the linear DC circuit case study in Section 4.1 has provided most of what we need to formulate a non-linear DC circuit case study.

In Chapter 5, we introduced triangular factorization and forwards and backwards substitution as a direct algorithm for solving linear equations. In a finite number of steps (assuming infinite precision arithmetic) we could solve the linear equations exactly. We have already remarked in Section 2.4.1.2 that no direct algorithm exists for general non-linear simultaneous equations.

Our approach to solving non-linear simultaneous equations will be iterative. We will start with an initial guess of the solution and try to successively improve on the guess. We will continue until the current iterate becomes sufficiently close to the solution according to a suitable criterion. In general, we will not be able to provide an exact solution, even if we could calculate in infinite precision. The theme of iterative progress towards a solution will recur throughout the rest of the book.

In Section 7.1, we discuss an iterative algorithm called the Newton–Raphson method. Then, in Section 7.2 we will introduce some variations on the basic Newton–Raphson method. In Section 7.3 we discuss local convergence of the iterates to a solution, while in Section 7.4 we discuss global convergence. Finally, we discuss sensitivity and large change analysis in Section 7.5.

The key issues discussed in this chapter are:

• approximating non-linear functions by a linear approximation about a point,

• using the linear approximation to improve our estimate of the solution of the non-linear equations and then re-linearizing about the improved solution in an iterative algorithm,

• convergence of the sequence of iterates produced by repeated re-linearization,

• variations that reduce computational effort, and

• sensitivity and large change analysis.

There are many excellent books on optimization and it is important to justify the need for yet another one. The motivation for this book stems from my observations of the orientation of typical optimization texts used in optimization courses compared to the needs of students in our engineering program. Many optimization books and courses concentrate on the design of algorithms, with less attention to adapting a problem to make it amenable to solution by an existing algorithm. That is, many optimization books are about how to design optimization algorithms, about how to write optimization software, or about how to apply optimization software to an existing problem formulation.

While this book is about the solution of simultaneous equations and optimization problems, it is not primarily about how to design algorithms, write software, or solve existing problems. Instead, it is about how to formulate new problems so that they can be solved by existing software.

Given the fabulous panoply of well-written optimization software available today, the skill of formulating a problem so that it is solvable with standard software is the most widely applicable skill for most engineers in our graduate program. Increasingly, the “scarce resource” is the ability to formulate problems, rather than the hardware or optimization software itself. This book is primarily designed for people who have a simultaneous equations problem or an optimization problem in mind and who want to formulate it so that it is solvable with standard software.

In this chapter we consider ways to transform problems. Such transformations are critical in matching a problem to the characteristics of an algorithm. Sometimes the transformation is done implicitly by formulating the problem in a particular, perhaps non-obvious, way. In several of the examples in this book, however, we will first formulate the problem in what might be considered a “natural” way and then look for ways to transform the problem to allow an algorithm to be effective. We will see that problem transformation is one of the key elements in matching a problem to an effective algorithm.

For example, we can think of transforming:

1. the variables or equations of a system of simultaneous equations, or

2. the objective, variables, or constraints of an optimization problem,

to create a new problem. Typically, to be useful, the numbers of variables and constraints (or equations) in such a transformed problem should be not significantly larger than the numbers of variables and constraints (or equations) in the original problem. We could then consider the original and transformed problems to be “equivalent” if:

1. given a solution of the original simultaneous equations it was easy to calculate a solution of the transformed simultaneous equations and vice versa, or

2. given the optimum and an optimizer of the original optimization problem it was easy to calculate the optimum and an optimizer of the transformed optimization problem and vice versa.

More formal notions of problem equivalence and of “easy” can be found in [40].

In this chapter we will define the various types of problems that we will treat in the rest of the book and define various concepts that will help us to characterize the problems. In Section 2.1, we first define the notion of a decision vector. In Section 2.2 we define two problems involving solution of simultaneous equations. Then in Section 2.3 we describe three optimization problems.

For each problem, we will provide an elementary example, without any context, to illustrate the type of problem. The case studies in later chapters will provide more interesting problems and contexts. In this chapter we will concentrate on basic definitions without explicitly considering applications.

In later chapters, we will also develop algorithms to solve the problems, starting with the elementary example problems introduced here and then progressing to solution of the case studies. We will explicitly define what we mean by an algorithm in Section 2.4 in reference to two general schemata:

• direct algorithms, which, in principle, obtain the exact solution to the problem in a finite number of operations, and

• iterative algorithms, which generate a sequence of approximate solutions or “iterates” that, in principle, converge to the exact solution to the problem.

We will also consider some of the issues involved in ensuring that these algorithms provide useful solutions. In particular, in Section 2.5, we will discuss solutions of simultaneous equations problems, introducing the concepts of a monotone function and of convex sets and presenting conditions for uniqueness of solutions of simultaneous equations.