Optimization, or finding the best choice/decision

1. Cost functions

A cost function maps a decision, or choice variable, to a monetary cost. Some costs are fixed: they do not depend on the batch size, like the €250 fee for each order. Other costs are variable: they change with the decision. For example, a larger batch means more pairs in the warehouse and therefore a higher holding cost. For now, we assume no lead time: an order arrives as soon as Karim places it. We begin with the annual ordering and holding costs.

Karim orders a batch of Q units, sells the stock down to zero and then receives the next batch of Q units. Plotted over time, the inventory has a sawtooth shape. It falls in a straight line from Q to 0 and jumps back to Q when the next order arrives, so the average inventory is $Q/2$. A larger batch quantity $Q$ leads to more stock in storage, and thus to higher holding costs. Holding one unit for a year costs $h$, so the annual holding cost is

$$\text{holding cost} = h \cdot \frac{Q}{2} = \frac{hQ}{2}.$$

We often omit the multiplication sign between symbols, so $hQ$ means $h\cdot Q$ and $Kd$ means $K\cdot d$. Between numbers we write the sign explicitly, as in $2.40\times600$.

Karim sells d units a year in batches of Q, so he places $d/Q$ orders per year. Each order costs K, so the annual ordering cost is

$$\text{ordering cost} = K \cdot \frac{d}{Q} = \frac{Kd}{Q}.$$

A larger batch quantity $Q$ leads to lower ordering costs, because it reduces the number of orders. For example, at $Q=1{,}200$ Karim places $12{,}000/1{,}200=10$ orders per year and holds 600 units on average. His ordering costs are $250\times10=2{,}500$ euros per year, while his holding costs are $2.40\times600=1{,}440$ euros per year.

Suppose also that Karim buys each unit from a supplier at a constant unit purchase price $c$. Buying $d$ units each year then costs $c\cdot d$, and the full annual cost is

$$TC_{\text{full}}(Q) = \underbrace{\frac{Kd}{Q}}_{\text{ordering}} + \underbrace{\frac{hQ}{2}}_{\text{holding}} + \underbrace{c\,d}_{\text{purchasing}}.$$

The annual purchasing cost $c\,d$ does not depend on $Q$, because Karim buys the same $d$ units each year whatever the batch size. Adding this constant raises the cost of every batch size by the same amount, so it does not change the optimal batch size. We therefore often omit purchasing costs and use $$TC(Q) = \frac{Kd}{Q} + \frac{hQ}{2}$$ when choosing $Q$. To report the full annual cost, add $c\,d$ back to $TC(Q)$.

Writing an optimization problem

Optimization means choosing the best feasible decision according to a stated criterion. To write an optimization problem, we name its parts. The objective function is the function we want to minimize or maximize. The choice variable is the quantity we control. Parameters are quantities we take as given while making the choice. Constraints restrict which choices are allowed. In Karim's problem, the objective function is the annual cost $TC(Q)$, which he wants to minimize. The choice variable is $Q$, and $K$, $d$ and $h$ are parameters. The only constraint is that the order quantity must be positive:

Read this as “among positive order quantities, choose one with the lowest annual cost.” We denote the optimal quantity by $Q^*$, so that $TC(Q^*)$ is the lowest annual cost among all feasible choices. Note that $Q^*$ is a quantity, while $TC(Q^*)$ is a cost.

We often have a limited set of feasible choices. For example, an order quantity must be positive. We may want to minimize an objective function, such as a firm's costs $C(x)$, or maximize one, such as a firm's profits $\pi(x)$. Both problems have the same structure:

The feasible set $\mathcal X$ contains the permitted choices. Without additional constraints, it is the function's stated domain. A storage capacity or a budget restricts this set further. For example, if Karim can store at most $Q_{\max}$ units, his problem becomes

The quantity must be positive and must fit within the storage capacity $Q_{\max}$. Karim may prefer a larger order, but it is not feasible. An unconstrained optimum can therefore become infeasible when such a limit is added. Section 5 extends this idea to two choice variables that share a budget.

2. The derivative: how a function changes

A derivative measures a function's local rate of change. For a cost function, $TC'(Q)$ tells us how annual cost responds to a small change in order quantity around the current $Q$. We start with an average rate of change, which divides the change in cost by the change in quantity:

For example, moving from 800 to 1,200 units gives

euros per year for each extra unit in $Q$. Geometrically, this is the slope of the straight line through two points on the cost curve. As we make $\Delta Q$ arbitrarily small, this line approaches the tangent to the curve at $Q$. If the limit exists, it defines the derivative:

For a small change in order quantity, we can use the derivative to approximate the change in cost:

This approximation is useful for small changes only. It may be inaccurate for larger changes. A negative derivative means that cost falls as $Q$ increases locally. A positive derivative means that cost rises as $Q$ increases locally.

Four examples of derivatives

Each line below gives a function and its derivative.

A constant function has zero slope. A straight line has a constant slope, equal to the coefficient of $x$. The slope of $x^2$ increases as $x$ increases. The fourth function, defined for $x>0$, is a scaled version of an inventory cost: its first term plays the role of the ordering cost and its second term the holding cost. Its slope is negative for small $x$ and positive for large $x$, so this cost first falls and then rises as the batch grows.

The next example shows how to use the limit definition of a derivative for a power function. In practice, we usually apply rules for functions whose derivatives are already known. We first expand the square, so that the $x^2$ terms cancel. We then divide by $\varepsilon$ and let $\varepsilon$ go to zero:

At $x=2$ the slope is $2\times2=4$. At $x=5$ it is $2\times5=10$. The derivative appendix collects the rules we will use, including the product rule and the chain rule.

With Karim's values, $Kd=250\times12{,}000=3{,}000{,}000$ and $h/2=1.2$. At $Q=800$,

euros per year for each extra unit. Adding 10 units to each batch therefore gives an approximate saving of $3.4875\times10\approx34.88$ euros per year. The exact saving, $TC(800)-TC(810)$, is about €34.30. The approximation is close because the change is small.

At the minimum, the tangent is horizontal

Geometrically, $TC'(Q)$ is the slope of the tangent line that touches the cost curve at Q. Where the curve falls steeply, the slope is a large negative number. Where it climbs steeply, the slope is a large positive number. At the minimum, the tangent is horizontal. In other words, the derivative is zero. This is the first-order condition (FOC): at an interior minimum of a differentiable function,

A zero slope alone does not tell us whether the point is a minimum. A constrained optimum also need not have a zero derivative, when the constraint prevents further improvement. Section 3 examines when the first-order condition is enough to conclude that we have found the minimum.

3. Convexity and global minima

A function is convex on an interval if every chord, the straight segment joining two points of the graph, lies on or above the graph. A convex function is U-shaped, like a cup. A function is concave if every chord lies on or below the graph. A concave function curves downward, like a dome. A useful mnemonic is that concave looks like a cave. These shapes are only reminders: a straight line satisfies both conditions, so it is both convex and concave. The second derivative $f''$ is the derivative of $f'$, and it measures how the slope changes. For a twice-differentiable function on an interval, $$\begin{aligned} f''(x)\ge0\text{ throughout the interval}&\quad\Rightarrow\quad f\text{ is convex}, \\ f''(x)\le0\text{ throughout the interval}&\quad\Rightarrow\quad f\text{ is concave}. \end{aligned}$$

A function can be convex on one interval and concave on another. An inflection point is a point where the curvature changes sign. To use convexity to establish a global minimum, the condition must hold throughout the domain. If $TC''(Q)\ge0$ for every $Q>0$, any stationary point minimizes cost over all positive order quantities. If $TC''(Q)>0$ throughout the domain, the function is strictly convex, and its minimum, if it exists, is unique. Convexity only near a stationary point establishes a local minimum.

A non-convex function can have several local minima. A stationary point may be a local minimum, a local maximum, or neither. The figure below shows why a zero derivative alone is not enough to identify the best choice.

Section 2 introduced the first-order condition. We can now state precisely what it does and does not deliver. $TC'(Q)=0$ is a necessary condition for an interior minimum of a differentiable function. It is not a sufficient condition, because the derivative is also zero at local maxima and at other stationary points. The second-order condition (SOC) checks the curvature. At a stationary point with $f'' > 0$, the function is locally convex (U-shaped) and the point is a local minimum. At a stationary point with $f'' < 0$, the function is locally concave and the point is a local maximum. If $f''=0$ at the stationary point, this test is inconclusive. For example, $f'(0)=f''(0)=0$ for each of $x^4$, $-x^4$ and $x^3$, but $x^4$ has a minimum at zero, $-x^4$ has a maximum there, and $x^3$ has neither.

A constrained optimum must be checked separately, because its derivative need not be zero. For example, suppose storage limits Karim to $0<Q\le1{,}000$. Cost falls throughout this feasible range, so the constrained optimum is $Q=1{,}000$, the largest quantity that storage allows. There, $TC'(1{,}000)=-3{,}000{,}000/1{,}000^2+1.2=-1.8\ne0$. Convexity of the objective on its whole domain is the global version of the second-order check. The figure below shows what can happen when this global property fails.

4. The Economic Order Quantity (EOQ)

We often want to measure the cost penalty from not choosing $Q^*$, for example because a supplier ships in fixed pack sizes. Write $q=Q/Q^*$ for the ratio of the chosen quantity to the optimal one. At the optimum, each cost component equals $TC(Q^*)/2$. Since $Kd/Q$ is proportional to $1/Q$ and $hQ/2$ is proportional to $Q$,

Dividing both sides by $TC(Q^*)$ gives the relative cost $TC(Q)/TC(Q^*)=\tfrac12\left(q+1/q\right)$.

5. Constrained optimization: a shared inventory budget

The objective function is the total annual cost of both products, which Karim wants to minimize. There are now two choice variables, $Q_1$ and $Q_2$, and one budget constraint:

Here $B$ is the available budget in euros, and $c_iQ_i$ is the value of product $i$'s peak inventory. The constraint requires enough budget to cover both peaks together. This is a conservative assumption if deliveries occur at different times. Without the budget, the independent EOQs are $Q_1^*\approx1{,}581.14$ and $Q_2^*\approx777.09$. Their combined peak value is $8\times1{,}581.14+15\times777.09\approx24{,}305.48$ euros, so a smaller budget binds.

In the figure below, the horizontal axis is $Q_1$ and the vertical axis is $Q_2$. Each closed oval is a level curve: every point on it has the same total cost. The red line is the budget limit, and feasible quantities lie on or below it. The purple dot marks the unconstrained optimum, with each product at its own EOQ. The orange dot marks the best quantities for the selected budget. With a tight budget, the orange dot lies where the lowest feasible cost contour is tangent to the budget line. Once both EOQs are affordable, the two optima coincide, and the larger purple dot remains visible around the orange dot.

The Lagrangian is a technique for solving optimization problems with constraints. It adds the constraint to the objective function, multiplied by a new variable $\lambda\ge0$ called the Lagrange multiplier:

The multiplier attaches a cost to using the limited budget. For a given $\lambda$, we minimize the Lagrangian over positive quantities. We take the derivative with respect to each $Q_i$, keeping the other quantity fixed, and set it to zero. The derivation below shows that this gives

$$Q_i(\lambda) = \sqrt{\frac{2K_i d_i}{h_i + 2\lambda c_i}}.$$

We first try $\lambda=0$, which gives the independent EOQs. If they fit within the budget, they solve the problem. Otherwise, the budget binds, and we choose $\lambda>0$ so that the quantities use the full budget: $$c_1Q_1(\lambda)+c_2Q_2(\lambda)=B.$$ We find this $\lambda$ numerically by bisection, which repeatedly halves an interval that contains the solution.

The multiplier $\lambda$ is the shadow price of the budget. It measures how much the optimal annual cost falls per extra euro of budget. For a small budget increase $\Delta B$, the saving is approximately $\lambda\times\Delta B$. As with the derivative, this approximation is accurate for small changes only. For example, with a budget of €16,000 the multiplier is $\lambda\approx0.1636$. Raising the budget by €100 gives an approximate saving of $0.1636\times100\approx16.36$ euros per year, while the exact saving is about €16.18 per year. When the budget does not bind, $\lambda = 0$. An extra euro of budget then has no value, because Karim already orders both products at their EOQs.

6. Production planning: the optimal cycle

With a cycle of length T, there are $1/T$ cycles per year, and each cycle contains one setup per product. The annual setup cost is therefore $\frac1T\times\Sigma K=\Sigma K/T$, where $\Sigma K = \sum_i K_i$ is the total setup cost per cycle. Each batch covers one cycle's demand, so the batch size of product $i$ is $Q_i=d_iT$. Its average inventory, and hence its holding cost, grows in proportion to $T$. The annual holding cost of product $i$ is $h_i'd_iT/2$, where $h_i'$ is an adjusted holding cost explained below. (The prime in $h_i'$ is part of the name and does not denote a derivative.) Writing $\Sigma h'd = \sum_i h_i' d_i$ for the demand-weighted total holding cost, the annual cost is

$$TC(T) = \frac{\Sigma K}{T} + T\times\frac{\Sigma h'd}{2}.$$

Every formula in this session assumed that demand d is a known, fixed number. Session 1 showed how to model uncertain demand as a random variable. Session 3 brings this uncertainty back into the decision and shows how it changes the optimal order quantity.

Appendix · Derivative rules

Differentiate with respect to $x$. The letters $a,b,k$ denote constants, and $u$ and $v$ denote differentiable functions of $x$. Use each rule only where the original function and the derivative are defined. In particular, denominators must be nonzero.

Product rule: differentiate one factor at a time

The first term differentiates the first factor, $x^2$, and keeps the second. The second term keeps the first factor and differentiates the second, $3x+1$.

Keep the other factor unchanged in each term, then add. Multiplying the two derivatives would give the wrong answer.

Chain rule: outside derivative times inside derivative

The outside function squares its input, and the inside function is $3x+1$. The extra factor 3 is the derivative of the inside function: it measures how fast the input of the outside function changes. We will use the same rule when standardizing a normal variable: