The seminal works are those of Gittins (1979, 1989), which presented the key insight and unlocked the multi-armed bandit problem, and Klimov (1974, 1978), which developed a frontal attack on the tax problem. Gittins had in fact perceived the essential step to solution by 1968, and described this at the European Meeting of Statisticians in 1972; see Gittins and Jones (1974). By this time Olivier (1972) had independently hit upon much the same approach. A direct dynamic programming proof of the optimality of the Gittins index policy was given in Whittle (1980), and then generalised to the cases of an open process and of the tax problem in Whittle (1981b, 2005).

For present purposes, we shall not follow the historical sequence of steps that suggested the Gittins index, but shall simply give the dynamic programming arguments that confirm optimality of the index policy and evaluate its performance. We consider only the undiscounted case, which shows particular simplifications and covers the needs of the text.

As mentioned in the text, there are at least two levels of aspiration to optimality in the undiscounted case. One is simply to minimise the average cost, and the second is to minimise also the transient cost: the extra cost incurred in passage from a given initial state to the equilibrium regime. As it turns out, the index policy is optimal at both levels.

Bandit processes

Consider a Markov decision process with the same dynamics over states as that supposed for items over nodes in Chapter 14.

In this book, we are going to examine various types of numerical problems and develop techniques for solving them. We will gradually build up the necessary tools and use a number of case studies to:

1. illustrate the process of formulating a problem, by which we mean translating from an intuitive idea of the problem by writing it down mathematically,

2. motivate and develop algorithms to solve problems, that is, descriptions of operations that can be implemented in software to take a problem specification and return a solution, and

3. illustrate how to match the formulation of the problem to the capabilities of available algorithms, involving, in some cases, transformation of the problem from its initial formulation.

We illustrate how to think about and describe problems to make them amenable to solution by optimization software. In brief: formulation of problems to facilitate their solution.

In the five parts of this book, we will consider five general problem classes. The first problem class is the solution of linear systems of equations (Part I). Solving linear systems of equations will turn out to be at the center of much of our subsequent work. For example, our second problem class, solving non-linear systems of equations (Part II), will be solved by an algorithm that requires repeated solution of linear systems of equations.

We will then go on to use these two algorithms as building blocks in algorithms for:

• unconstrained optimization (Part III), which will in turn form part of the algorithms for:

• equality-constrained optimization (Part IV), which will again form part of the algorithms for:

• inequality-constrained optimization (Part V).

In this chapter, we apply algorithms from Chapter 10 to the two case studies from Chapter 9. We consider the multi-variate linear regression case study in Section 11.1 and the power system state estimation case study in Section 11.2. Both of our case studies will be transformed into least-squares problems. Unconstrained optimization algorithms that exploit the special characteristics of leastsquares problems are described in [45, section 4.7] [84, chapter 13]; however, we will first apply our basic unconstrained optimization algorithm to these problems because in later chapters we will need to solve more general unconstrained problems.

In practice, a special purpose algorithm for least-squares problems can be expected to yield better performance on least-squares problems compared to the performance of a general purpose algorithm for unconstrained problems. That is, as we have discussed previously in Section 2.3.2, we should always in practice try to find the most specifically applicable algorithm for a problem [84, section 13.1]. We will consider such specific algorithms for least-squares problems using further transformations.

Multi-variate linear regression

In Section 11.1.1 we transform the objective of Problem (9.7) and in Section 11.1.2 we compare the transformed and original problem. In Sections 11.1.3 and 11.1.4 we calculate the derivatives of the transformed objective and present the optimality conditions. In Section 11.1.5, we transform the problem further to avoid numerical ill-conditioning issues. Then, in Section 11.1.6, we relate the optimality conditions to linear regression.

In this chapter we will introduce two case studies:

1. production, at least-cost, of a commodity from machines, while meeting a total demand (Section 12.1), and

2. state estimation in an electric power system where the power injections at some of the buses are known to high accuracy (Section 12.2).

Both problems will turn out to be equality-constrained optimization problems. The first will introduce several new ideas in problem formulation, while the second will build on the state estimation case study from Section 9.2.

Least-cost production

Motivation

Consider a machine that makes a certain product, requiring some costly input to produce. In many industries it is possible to stock-pile the product at low cost from day to day, week to week, or even season to season. In this case, it is natural to try to operate the machine at constant output. Ideally, the constant value of machine output would be matched to either:

• the point of maximum operating efficiency of the machine, or

• some other desirable operating point of the machine.

When demand is lower than production, some of the production goes into the stockpile. When demand is higher than production, the stocks are used to help to meet demand.

However, if stock-piling is costly or inconvenient or if demand for the product varies rapidly, then to avoid over-supplies and shortages we have to vary production to follow variations in demand.

In this chapter, we will develop two case studies of problems that involve the solution of linear simultaneous equations:

1. the solution of Kirchhoff's laws in a simple electrical circuit (Section 4.1), and

2. the search for a set of inputs to a “discrete-time linear system” that will bring the system to a desired state (Section 4.2).

The first case study will be developed in some detail, while the second will be much more briefly described. As we proceed, we will introduce notation to help us express ideas concisely and precisely. We will try to describe the choices that are made in formulating a model. You may already be very familiar with these models; however, the reasoning we present here may help you to pose and answer questions that arise in formulating your own models. We emphasize that the formulation of a new problem may involve many stages and refinements and that our presentation hides some of this process.

Analysis of a direct current linear circuit

Motivation

In designing a large integrated circuit to be fabricated or even a large circuit consisting of discrete components, it is very important to be able to calculate the behavior of the circuit without going to the expense of actually building a prototype. Furthermore, because of manufacturing tolerances, manufactured component values may differ from nominal. The values may also drift over the lifetime of the circuit. Both manufacturing tolerances and drift of component values can be interpreted as changes in the values of components from their nominal values in the base-case circuit.

In this chapter we will introduce six case studies:

1. production, at least-cost, of a commodity from machines that have minimum and maximum machine capacity constraints (Section 15.1),

2. optimal routing in a data communications network (Section 15.2),

3. least absolute value estimation (Section 15.3),

4. optimal margin pattern classification (Section 15.4),

5. choosing the widths of interconnects between latches and gates in integrated circuits (Section 15.5), and

6. the optimal power flow problem in electric power systems (Section 15.6).

The first and third case studies will draw from the previous formulations in Sections 12.1 and 9.1, respectively. The sixth case study combines the formulations from Sections 15.1 and 6.2. These three case studies will be introduced briefly, concentrating on the extensions from the previous formulations. They further illustrate the idea of incremental model development. The second, fourth, and fifth case studies introduce new material and will be developed in more detail. All six of these case studies will turn out to be optimization problems with both equality and inequality constraints. The first three have linear constraints, while the last three have non-linear constraints. Transformations will be applied to the fourth and fifth to deal with the non-linear constraints.

Least-cost production with capacity constraints

This case study generalizes the least-cost production case study from Section 12.1.

Motivation

Recall the least-cost production case study discussed in Section 12.1.

In this chapter we will introduce two case studies:

1. multi-variate linear regression (Section 9.1), and

2. state estimation in an electric power system (Section 9.2).

Both problems will turn out to be unconstrained optimization problems of the special class of least-squares data fitting problems [84, chapter 13].

Multi-variate linear regression

Some of this section is based on [103] and further details can be found there. The development assumes a background in probability. See, for example, [31, 103].

Motivation

In many applications, we have a hypothesized functional relationship between variables. That is, we believe that there are some dependent variables that vary according to some function of some independent variables. The simplest relationship that we can imagine is a linear or affine relationship between the variables.

For example, we may be trying to estimate the circuit parameters of a black-box circuit by measuring the relationship between currents and voltages at the terminals of the circuit. We will have to try several values of current and voltage to characterize the circuit parameters. As in the circuit case study of Section 4.1, we could either:

• apply vectors of current injections and measure voltages, interpreting the currents as the independent variables and the voltages as the dependent variables, or

• apply vectors of voltages and measure currents, interpreting the voltages as the independent variables and the currents as the dependent variables.