Local and Global Optima: Why the Solver Can Stop Too Early

A local optimum is a plan that beats everything close to it. A global optimum is a plan that beats everything allowed. A step by step search only ever compares a plan with its neighbours, so it stops at the first local optimum it meets and cannot tell which kind it has found. At the Amaltas workshop that search stops at 23 boards a day, Rs 360/- a day short of the best order.

One invented workshop carries every number in this guide. The Amaltas workshop makes two things and nothing else, a plain crate and a lined crate, and it was built small enough for a whole decision to be laid out in one place and checked with a pocket calculator. A plain crate adds Rs 300/- a day to what the workshop has left over and a lined crate adds Rs 450/-. Rs 300/- and Rs 450/- are the contributionWhat one item adds once the materials and the working time that item swallows have been paid for. A contribution is not profit. The bills that stay the same whatever gets made have not come out of it yet. of each crate, established earlier in these notes along with the three daily limits the workshop runs under.

Where the figures come from. Every one of the twenty one rows in the table below is arithmetic on the invented workshop and its invented supplier, so any row can be redone by hand in about fifteen seconds. None of the numbers moves with a market, a season or a supplier's mood, and the workings behind each one are set out in the table of sources at the end.

What is a local optimum, on its own?

Somebody arriving here straight from a search box needs the term handed to them before either half of any comparison is worth reading, so here it is on its own. A local optimum is a plan where every neighbouring plan is worse. That is the whole claim. Notice how small it is. The claim says nothing whatever about plans that sit far away, nothing about the best plan there is, and nothing about how much was looked at. The claim reports the outcome of a handful of comparisons against whatever counts as next door, and nothing more.

Which means the term is useless until somebody says what next door means. In a decision about how many boards to order a day, next door is one board more and one board fewer. In a decision about how many crates to build, next door might be one crate more of each kind. Change what counts as a neighbour and the test is handed a different set of things to lose to. The same plan can then stop being a local optimum.

Here is the everyday version, and it is worth carrying around. A walker crosses a field in the dark, wanting the highest ground. A step north goes down, a step south goes down, east down, west down. Every direction that can be felt from where the walker stands is lower, so the walking stops and the high ground is declared reached. The declaration may be right. The ground underfoot may equally be a low mound, with a proper hill two hundred yards away that nobody can see in the dark and nobody walked far enough to feel. Both situations feel identical from where the feet are. Feeling identical from where the feet are is the entire problem.

What is a global optimum, on its own?

Now the other one, also on its own, also in full. A global optimum is a plan that no allowed plan beats, near or far. Not the best one anybody found. Not the best one on the list somebody happened to try. The best one there is, out of every plan the rules permit.

The global claim is a much bigger claim than it looks, and the size of it is the thing to hold on to. To say a plan is a global optimum is to make a statement about the whole set of allowed plansEvery plan the rules permit, taken together as one collection. The set is an object worth studying on its own, and it is studied separately in these notes under the feasible set. at once, which means somebody had to account for all of it. There are only three honest ways to do that. The first is enumeration: listing every allowed plan and comparing them one against another. Enumeration works when the list is short. The second is argument: showing by reasoning that nothing outside what was checked could possibly do better, the way a number can be shown never to exceed a ceiling already computed. The third is the shape of the problem, where certain kinds of problem are built so that finding a local optimum settles the matter, and what makes a problem behave that way is set out separately in these notes under convex optimisation.

With none of the three, nothing remains. A claim that a plan is globally best, made by somebody who neither listed the alternatives nor gave an argument nor said anything about the shape of the problem, is not a weaker version of the claim. The claim is the same words with nothing behind them. Back on the dark field: to claim the highest ground in the county, the walker has to have walked the county, or hold a map of it, or know something about how the county was built.

Where exactly do the two ideas differ?

One line, and then the argument for it. The difference is not how good the answer is. The difference is how much was compared before the answer was called best.

Read the two definitions back to back and this falls out. The local claim rests on a small number of comparisons against whatever counts as next door. The global claim rests on accounting for the whole allowed set. Nothing in either definition says a word about the quality of the plan itself, and that is deliberate. The two are not a ranking of answers but a ranking of evidence.

Which leads straight to the trap. The two can be the same plan, and the number alone still cannot say which of the two claims is being handed over. A local optimum often is the global optimum, and on some problems it always is. But a report carrying the figure Rs 1,040/- looks exactly like a report carrying the figure Rs 1,400/-. Both are printed in the same font. Neither carries a little mark saying how many plans were weighed to produce it. Where the number is the only thing available, it is no evidence at all about which claim was made, and the honest move is to ask what was compared rather than to look harder at the figure.

What does the Amaltas workshop's board order look like as a decision?

Abstract definitions only bite once a real decision sits under them, so here is one. Every morning the Amaltas workshop has to tell its board supplier how many boards to send. The workshop can ask for anywhere between 20 and 40 a day. The order is the whole decision: one number, a whole numberA count with nothing after the decimal point. Twenty three boards or twenty four boards, and no order sitting in between the two., chosen once.

The supplier prices boards at Rs 120/- each, with one wrinkle. Order thirty or more in a day and the price drops to Rs 80/- a board, and the lower price applies to the whole order rather than only to the part above thirty. The drop in price is a rebateA cut in the price a supplier charges once an order passes a stated size. Here the cut applies to every board in the order, not merely to the boards beyond the line., and it is the only unusual thing in the entire problem. Everything else is plain arithmetic.

The quantity the workshop is trying to make large, its objectiveThe single quantity a decision is set up to push as high, or as low, as it will go. Choosing what belongs in it is a job of its own and is handled separately in these notes., is the day's surplusWhatever money is left at the end once every bill the day generated has been settled. Here it stands in for the day's result and no tax, interest or write off is in it.: the best contribution the workshop can reach with that many boards, less the board bill, less Rs 1,900/- a day of rent and wages that does not move whatever the workshop makes. Two of those three parts are fixed by the order alone. The first one takes a moment of thought. How much contribution the workshop can squeeze out depends on the boards it has, and also on its two other daily limits, its bench hoursWorking time on a bench, counted per bench rather than per person. Three benches open eight hours each give twenty four bench hours. The number of hands using them makes no difference. and its cloth, which do not change when the board order changes.

Work that through and the answer is short. At the workshop's standing orderA repeat order placed once and then left running, so the same quantity turns up every day without anybody deciding again. of 20 boards the best day is 8 plain crates and 6 lined crates, worth Rs 5,100/- in contribution. Each of the next three boards is worth another Rs 200/- of contribution, so 21 boards reach Rs 5,300/-, 22 reach Rs 5,500/- and 23 reach Rs 5,700/-, where the plan is 7 plain crates and 8 lined crates. The cloth runs out at 8 lined crates and the bench hours run out at the same moment, so after 23 boards the workshop cannot use another one at all. The twenty fourth board, and every board after it, adds exactly Rs 0/- of contribution. Where the Rs 200/- a board comes from, and why it stops when it does, is worked out separately in these notes under the pricing of a constraint. Here it is enough that it does.

The middle of that climb would otherwise trip a careful reader, so it needs one honest note. At 21 and 22 boards the best day involves a crate that is part built when the workshop closes. The Amaltas workshop counts the share of it that got done and finishes it first thing next morning. Counting a part built crate that way keeps the climb smooth at Rs 200/- a board rather than lumpy. At 20 boards and at 23 boards, the two rows the argument leans on hardest, the plans are whole crates with nothing left on the bench.

What does every row of the board order ladder come to?

Twenty one possible orders, twenty one rows, no gaps. Each row is the same three step sum: take the best contribution reachable at that many boards, take off the board bill, take off Rs 1,900/-. The board bill is the order times Rs 120/-, or times Rs 80/- from thirty boards upward.

Read the last column downward and the shape is unmistakable. Each board adds Rs 200/- of contribution and costs Rs 120/-, so from 20 boards the surplus climbs Rs 80/- a board. The climb tops out at Rs 1,040/- at 23 boards. The boards after that add nothing and still cost Rs 120/- each, so the surplus falls Rs 120/- a board for six straight rows and bottoms out at Rs 320/- at 29 boards. Then at 30 the whole order reprices at Rs 80/- a board, the bill drops from Rs 3,480/- to Rs 2,400/-, and the surplus jumps to Rs 1,400/-. From there it falls again, Rs 80/- a board, down to Rs 600/- at 40.

So the last column has two peaks: Rs 1,040/- at 23 boards and Rs 1,400/- at 30 boards, with a floor of Rs 320/- at 29 boards sitting between them. Those two are peaks in the strict sense the first block set out. At 23 boards both neighbours are worse, Rs 960/- below and Rs 920/- above. At 30 boards both neighbours are worse, Rs 320/- below and Rs 1,320/- above. Nothing else in the twenty one rows has that property. Run down the column and no other row is higher than the two rows either side of it.

Where does a step by step search stop, and does the start matter?

Now something runs over that ladder. The search is the simplest one anybody would write on the back of an envelope, and a pencil is enough to run it. The search stands on some order, looks at the order one board lower and the order one board higher, and moves to whichever neighbour is better. Then it repeats. The run stops when neither neighbour beats the order it is standing on.

Start it at the standing order of 20 boards. Rs 800/- there. Look at 21: Rs 880/-, better, move. Look at 22: Rs 960/-, better, move. Look at 23: Rs 1,040/-, better, move. Now from 23 look both ways: 22 is Rs 960/- and 24 is Rs 920/-. Both worse. Stop. The search reports 23 boards a day, worth Rs 1,040/-.

Nothing about that run is careless. Every comparison it made was correct, it never accepted a worse plan, and its stopping rule fired exactly when it was supposed to. Now start the identical search one board further along, at 29. Rs 320/- there. Look at 30: Rs 1,400/-, better, move. Look both ways from 30: 29 is Rs 320/- and 31 is Rs 1,320/-. Both worse. Stop. The search reports 30 boards a day, worth Rs 1,400/-.

Do that from all twenty one possible starts and the pattern is clean enough to be uncomfortable. Started anywhere from 20 to 28 boards, the search ends at 23. Started anywhere from 29 to 40, it ends at 30. There is no middle case and no other stop anywhere on the ladder. The answer depends on where the search began, and nothing in the search reports that.

What does stopping at the lower peak actually cost?

Rs 1,400/- less Rs 1,040/- is Rs 360/- a day. The gap is what a search that started at 20 boards gives up against a search that started at 29, and the workshop gives it up every single day the standing order stays where it is. Over three hundred working days the gap comes to Rs 1,08,000/-. A daily figure this small is easy to wave away, so the yearly one is worth stating once.

But the size is not the interesting part. The stop at 23 boards is a completely genuine peak. Both its neighbours are worse. The search did not miss anything it was looking at. Reaching the better order means first walking down from Rs 1,040/- at 23 boards to Rs 320/- at 29 boards: six steps, a descent of Rs 720/- a day, and only then does the ground rise again. A search that only ever looks one board either way cannot see 30 boards from 23, so it would have to make that descent with no information at all telling it a climb waits on the other side.

Which is the real point. Walking down a valley means accepting a worse plan, and refusing worse plans is the only rule the search has, so no search that keeps only improvements will ever walk down a valley. The refusal is not a defect in this search. The refusal is the search. Take the refusal away and what is left no longer terminates at all, and becomes something else entirely.

What made a second peak possible in the first place?

One thing did, and it is worth naming precisely because it is the only unusual ingredient in the whole problem. The price break at thirty boards put a step into the thing the workshop is trying to make large, and that step is where the second peak came from.

Take it out and see. Suppose the supplier charged Rs 120/- a board at every quantity with no rebate at all. Then the board bill would rise smoothly at Rs 120/- a board all the way from 20 to 40, and the surplus would climb Rs 80/- a board to Rs 1,040/- at 23 boards and then fall Rs 120/- a board for the whole rest of the ladder, seventeen straight falls, ending at minus Rs 1,000/- at 40 boards. One peak. No valley. No second climb. A search from any start would walk to 23 boards and stop, and it would be right to stop, because 23 really would be the best order there was.

So the trap is not made by the limits and it is not made by the two contribution figures. The trap is made by the step. Steps are everywhere in an actual workshop, so the general version is worth carrying away. A rebate at a quantity is a step. A minimum order is a step. A second machine that is either hired for the month or not is a step. A licence that costs the same whether it is used once or a thousand times is a step. A delivery charge that vanishes above some size is a step. Every one of those breaks the smooth relationship between what is decided and what comes back. Wherever the quantity being made large moves in a jump rather than a slope, a second peak is possible until somebody has looked.

The other side of that is that some problems are built so that a local optimum has to be the global one, and a search stopping anywhere is then all the proof anybody needs. The property that does it, and how to recognise it, is set out separately in these notes under convex optimisation.

Why does the better order buy boards it never uses?

Look hard at the row for 30 boards and something odd surfaces. The cloth and the bench hours stopped the workshop going further long ago, so at 30 boards it still makes 7 plain crates and 8 lined crates, exactly the plan it makes at 23 boards. So the workshop uses 23 boards and buys 30. Seven boards go straight to the corner of the room and stay there.

Yet it is the better order, and the arithmetic saying so is one line. Thirty boards at Rs 80/- is Rs 2,400/-. Twenty three boards at Rs 120/- is Rs 2,760/-. The bigger order costs Rs 360/- less. The contribution is identical at both orders, Rs 5,700/- either way, so the entire Rs 360/- gap between the two peaks is the board bill and nothing else. Buying seven boards that will never be touched is cheaper than not qualifying for the rebate.

Everyday version. A household buys a twenty kilogram sack of rice for less than two five kilogram packets cost, even though it will eat ten kilograms this month. The rice in the sack is not waste. The extra ten kilograms are the price of the price. A plan can be right and still look wasteful, and looking wasteful is not an argument against it. The test is the number at the bottom of the column, not how tidy the plan looks on the way there.

How to work when a second peak is possible

Four habits, all of them modest. None is a technique and none needs anything beyond what is already to hand. The four are what somebody handed a search result does before believing it, whether that somebody runs a workshop, checks a model at a lender, or reads a note an analyst wrote.

First, start from several places and see whether the answers agree. This is the cheapest defence there is and on this ladder it works immediately: of the twenty one possible starts, twelve land on 30 boards and nine land on 23. Try four or five starts spread across the range and the disagreement shows up at once. A disagreement is information, and it proves at least one of the answers is not the best there is. Agreement is weaker evidence, but it is still evidence, and it costs one more run.

Second, look at the whole picture when the decision is small enough to draw. Twenty one rows fit on one screen. A person who prints the table finds both peaks in ten seconds and needs no search at all. On a small decision the honest global claim is available for the price of a table, so ask whether the decision can simply be listed out before reaching for a search.

Third, the kind of claim being made is stated outright. Near best and best are different statements and they should not be written the same way. A line reading that 23 boards is the best order the search reached from a start of 20 is honest and complete. A line reading that 23 boards is the best order is neither, and the difference between the two sentences is the whole difference between a near best claim and a best one.

Fourth, when a price break, a minimum order or an on or off choice sits anywhere in the problem, a second peak is to be assumed until somebody has looked. The assumption is not a suspicion. The rebate above showed as much: those features put steps into the quantity being made large, and steps are what make second peaks. Finding one costs a few extra runs. Missing one costs Rs 360/- a day for as long as nobody checks.

The Amaltas workshop, its plain crate and lined crate, and its board supplier are invented.
Educational material. Not advice on any investment, tax, budget or market position.