Chapter 3: Course outline

This section provides a sketch of the course. The material is divided into 11 topics, which are described in much more depth in section 5.0. Here, I summarize each of the topics, focusing on the development of key concepts.

The course will transition from the simplest (but nontrivial) decision problems to more complex settings. We will start with basic machine learning problems partly because they are very familiar today, but also because they are well motivated and easy to understand. The machine learning problems will also lay the foundation for how we handle random observations in sequential decision problems which are of fundamental importance (since so many real problems are, in fact, sequential in nature).

The lectures are organized to follow a natural progression from simpler decisions (binary, discrete, continuous scalar) to more complex ones (continuous vectors, integer variables, nonlinear functions). Our emphasis is on formulating optimization models, including the critical (but historically overlooked) problem of understanding how to handle decision problems when they are made sequentially over time. We present algorithms when one or both of the following applies:

• An understanding of the algorithm can help students appreciate the behavior of the solution, even if they never implement an algorithm.
• Students may need to program the algorithm if they are to solve the problem (we limit these to relatively simpler algorithms).

This document presents the course as a series of “topics” that can be adapted to the interests of the faculty member, and the background and interests of the students. Most topics can be presented in 1 to 3 lectures, but some topics can be extended to as many as 6-8 lectures depending on the interests of the faculty member and the skills and background of the students.

Below I will list each topic and describe the key points being covered, emphasizing the transition from simpler to more complex problems. This is a sharp departure from introductory courses in “optimization” that turn out to be courses in “linear programming with extensions.”

• Topic 1 – Machine learning – We start with fitting a linear model to introduce the idea of solving a convex optimization problem exactly. Students should learn the minimum amount of data required to fit a linear model (for example, $n \geq p$) in addition to other conditions on the data. We then transition to nonlinear models and introduce gradient search and the issue of multiple optima (a major topic with neural networks that are so prominent today). Also note that with nonlinear estimation, we no longer require $n \geq p$, implying that we can fit, say, a neural network with 100 million parameters with a single datapoint.

A particularly important piece of pedagogy in Topic 1 is the idea (often overlooked) that estimation problems are, in fact, stochastic optimization problems, where random variables are replaced with sampled observations. This is going to set the style for handling uncertainty which will run throughout our handling of sequential decision problems. We note that this style allows students to do “stochastic optimization” without any training in stochastic optimization, probability, or even a course in statistics.

• Topic 2 – Sequential decision problems – We next introduce the concept of a sequential decision problem, and then use some important and visible problems to illustrate how to model these. Most important is the concept of a policy which is a method (that is, a function) for making decisions, that is controlled by tunable parameters. This closely parallels fitting a model to data (as we do in Topic 1). We start with a basic example for selling an asset that uses historical data, and then transition to an inventory problem where we need to randomly generate observations. This is done using a very basic introduction to Monte Carlo sampling.

The policies we introduce are both forms of policy function approximations (PFAs) which are widely used by individuals as well as corporations. PFAs help us create a natural bridge to estimating functions in machine learning, but students also learn how to set up an objective function for sequential decision problems. This skill will stay with us as we progress to more complex decision problems.

• Topic 3 – Adaptive optimization – In this topic I use the newsvendor problem to introduce the idea of using sampled information to compute a gradient. This is widely known as a stochastic gradient in the literature, but the gradient is based on a sample, which means we are taking the derivative of a deterministic function. This problem will require generating random variables dynamically rather than creating a sample in advance as we did in Topic 2. It is important to recognize that while the newsvendor problem is perhaps the most widely studied stochastic optimization problem, the algorithm is quite simple, and outside of generating random samples, all of the steps use deterministic methods.

• Topic 4 – Optimal learning – This is a topic where the optimization problem is making decisions of what to observe, such as how a patient responds to a drug, how many clicks a website attracts, and the market demand for a product at a particular (discretized) price (applications of this model are endless, and familiar to everyone). We use a policy called interval estimation (a form of upper confidence bounding) that is very popular with tech companies (e.g. Google and Facebook) for maximizing ad-clicks. Optimal learning will also play a role any time we need to do parameter tuning, which will turn out to be a common type of optimization problem.

Upper confidence bounding policies represent a form of “cost function approximation” (CFA) where the policy for making decisions has an imbedded optimization problem. For UCB policies, this optimization problem involves a simple sort, but it introduces the idea of a policy that involves solving an optimization problem to make a decision. This means we have an optimization problem (the sort) within a larger optimization problem of tuning the parameter in the UCB policy.

• Topic 5 – Shortest path problems – Here we introduce our first nontrivial static, deterministic optimization problem which is also a very special form of linear program (but that comes later). This is the only time we use Bellman’s equation in the course, although there are problems (in Topic 10) where we could draw on Bellman again.

After presenting the model and algorithm for a deterministic, static shortest path problem, we then transition to show how this can be used in a dynamic setting, as would happen if we are modeling a path through a dynamic network. We show how to model this problem, and then show how to create a classic deterministic dynamic lookahead approximation (deterministic DLA). We show how to evaluate the shortest path problem as a policy, and how to parameterize it so that it works better in a stochastic, dynamic environment.

We are going to copy this setting as we move into more general optimization problems. We will start by presenting a basic, static optimization problem (this could be a linear, nonlinear or integer program), and then show how it is often used as a policy in a dynamic setting. In my experience, the vast majority of “optimization problems” are actually policies used in a sequential problem setting, something that is typically overlooked in standard texts on optimization.

• Topic 6 – General concepts – We pause at this point to discuss two important dimensions of sequential decision problems:

  • Classes of policies – So far, we have illustrated four ways of making decisions, each of which come from the four classes of policies. These four classes cover every possible method that we might use to make decisions, including any method people are already using.
  • Evaluating policies – The biggest difference between people who make decisions in an ad hoc way versus someone with formal training is their understanding of the concept of a policy, and how to evaluate it. In this topic (typically a single lecture) we start by reviewing how we have evaluated policies in topics 2 – 5. We then list different ways of evaluating policies such as cumulative reward for online learning, and final reward for learning in a lab. We also differentiate between expected performance versus risk. While the academic literature deals with risk with a considerable amount of mathematical sophistication, we are going to show students how to model risk in a way that can be easily computed in a spreadsheet.

• Topic 7 – Linear programming – Here is where we introduce linear programming. This can be done in a single lecture (which I recommend for an introductory optimization course) or expanded given the time available, interests of the students, and the interests of the faculty member teaching the course.

Our preferred style for an introductory course is to teach the idea of a linear program and then transition to the idea that “algorithms exist” for solving it. An in-depth presentation of the simplex algorithm is simply not appropriate at this stage, since no-one is ever going to implement their own simplex algorithm. Modern implementations of the simplex algorithm use a variety of sophisticated strategies to improve performance; these strategies are never discussed in textbook treatments of the simplex algorithm, so it is not clear what a student is learning from these streamlined presentations. In addition, production implementations might combine strategies such as dual simplex or even interior point methods. This material is simply not appropriate for an introductory course.

This said, we illustrate the simplex algorithm graphically using a network problem which helps students understand, in a highly visual way, the concept of a basis, pivoting, and most important, dual variables. This can be done without any linear algebra, but we do have a section where we present the simplex algorithm (for a network problem) both graphically, and then algebraically. We leave it to the instructor to decide which presentation best suits their students.

We begin by presenting linear programming as the solution to a static problem, but we then transition to using linear programming as a policy for sequential decision problems. We suspect that most linear programming applications arise in the context of sequential decision problems (and this is certainly true of the original motivating applications used by George Dantzig). I think the recognition that linear programs are often used as policies for sequential decision problems is one of the great failures of the math programming community. Topic 8 illustrates how a deterministic linear program might be used in a sequential inventory problem.

• Topic 8 – Dynamic inventory problem – Here we are going to copy what we did for our dynamic shortest path problem but use the context of an energy storage problem in a highly dynamic setting with rolling forecasts (a topic that has been completely overlooked in the operations research literature). This requires solving a series of simple linear programs, even though the decision at a point in time is a scalar (we get the LP because we are optimizing over a planning horizon, which means our decision variable is now a vector). The lookahead LP will be parameterized to help mitigate the errors in the rolling forecasts, and we will show that this produces a much better result than using typical point forecasts. The challenge, as always, will be the tuning, a problem we first saw in the machine learning problem in Topic 1. We will suggest a strategy that is fairly easy to implement.

• Topic 9 – Integer programming – Here we introduce the idea of integer variables in the context of a facility location problem. As with our shortest path problem, we will start with a simple, static facility location problem. Then, Topic 10 shows how the static model can be used as a policy in a fully sequential problem.

Optimization books tend to become drawn into the fairly sophisticated algorithms required to solve integer programs. However, since year 2000, commercial packages have conquered wide classes of even very large integer programs, although some care has to be used since there is a wide range of integer programming problems, and some still require specialized algorithms. The best packages (such as Gurobi and Cplex) can be dramatically better than free software that students can download over the internet. As with algorithms for linear programs, teaching algorithms for integer programs is pointless for an introductory course – these algorithms are quite sophisticated and no-one today would implement their own. However, it is important for students to be able to recognize which types of integer programming problems are likely to be solvable with a general purpose package.

• Topic 10 – Dynamic facility location – As we did with linear programming, we start by presenting a static integer programming problem using facility location, and then extend it here to a dynamic setting. We start by making the case that any facility location problem would have to be implemented in a stochastic environment. We separate the decision of where to locate facilities, which is made using forecasted demands, and the “real world” decisions of how to meet demands which are revealed after we make the decision to locate facilities.

We then recognize that decisions to locate facilities are themselves decisions that are made over time, in the presence of the uncertainties about demands. We illustrate a few strategies for solving the dynamic facility location problem.

• Topic 11 – Nonlinear programming – We have already seen nonlinear programming in topic 1 when we fitted a nonlinear model, but here we are going to address this rich topic in more depth. As with linear and integer programming, we are going to present nonlinear programming in two stages: first as a static problem, and then as a policy in a fully sequential problem. Nonlinear programming is a rich topic that can be introduced in a single lecture but can span an entire course. It is up to the professor to decide how much time to spend on this topic given the interests of the students.

We are going to introduce students to a quadratic programming problem that arises when optimizing investments over a portfolio. We will first introduce this problem in its classical formulation as a static problem, and then transition to solving it sequentially over time, treating it as a policy in a fully sequential decision problem (based on actual practice on Wall St.). This will be a sophisticated (but very real) extension of the asset selling problem we introduced in Topic 2.