Convex Optimisation: Why Convexity Guarantees a Single Answer

Convexity is a statement about the shape of a problem rather than about how hard anybody worked on it. A set of allowed plans is convex when the halfway point between any two allowed plans is itself allowed. An objective bends one way when it never turns back up. Where both hold and the decisions slide rather than jump, every plan that beats its neighbours beats every allowed plan.

From the middle of a square room every corner is visible without taking a step. From the middle of an L shaped room one arm is hidden behind a wall, and reaching it means leaving the straight line between the starting point and the destination. The difference between a shape that can be crossed in a straight line and a shape that cannot is what convexity names. Convexity is that difference written down carefully enough to be argued with, and the reason anybody bothers is that the straight line room has exactly one high point while the L shaped one can have two.

The Amaltas workshop, an invented maker of crates, makes two things and nothing else: the plain crate and the lined crate. Three limits govern one day. Twenty boards arrive, and a plain crate takes one board while a lined crate takes two. The workshop counts twenty two bench hoursOne person at one workbench for one hour. What is left of the workshop's benches once the daily preparation time is taken off them, and where the count comes from is settled elsewhere. in a day, and a plain crate takes two hours while a lined crate takes one. Cloth goes into the lined crate alone, one roll per crate, and eight rolls turn up each morning. Neither count can drop below zero. A plain crate leaves Rs 300/- behind and a lined crate Rs 450/-, and that figure is the crate's contributionWhat one more of something leaves behind once the materials and labour that go into it are paid for. It is not profit, because the rent and the wages that would be owed whatever gets made have not been taken out of it yet.. Work all of that through and one plan beats every other the rules permit: 8 plain crates alongside 6 lined ones, Rs 5,100/- of contribution in a day. The best plan is worked out under linear programming and is taken as given here.

Two words are also already settled and get used freely below without being taken apart again. A plan that beats everything immediately around it is a local optimum. The plan that beats every allowed plan anywhere is the global one. How a search stops at the first without ever meeting the second is covered separately. The question left over is whether it can be known in advance that those two words describe the same plan. If it can, a search which halts has halted at the answer rather than at a resting place.

What does convex mean for a set of allowed plans?

Take any two plans the workshop is allowed to run, and write down the plan exactly halfway between them: the average of the plain crates, the average of the lined crates. If that halfway plan is always allowed too, whichever two plans the test starts from, the set of allowed plans is convex. The halfway point test is the whole of it, and it involves no calculus, no slopes and no second look at the objective.

In a picture the test says the region is one solid piece with no dents in its edge and no gaps in its middle. The square room passes for exactly that reason: every point can see every other point along a straight line that never leaves the room. An L shaped room fails, and so does a room with a pillar in the middle of it, and so does a building split into two blocks with a courtyard between them. All three failures are the same failure. Somewhere there are two allowed places and a straight line between them that leaves.

Run the test on the Amaltas workshop rather than trusting the drawing. Take the 84 plans made of whole cratesA plan whose two counts are round numbers, so eight plain crates rather than eight and a quarter. Whether a workshop is obliged to work in round numbers is a fact about the workshop, not about the arithmetic. that the three limits permit, cross every one of them with every other, and the result is 3,486 pairs. For each pair, averaging the two plain crate counts and averaging the two lined crate counts gives a halfway plan. Each halfway plan is then tested against all three limits. Not one of the 3,486 midpoints falls outside. The corner 11 plain and no lined crates paired with the corner 8 plain and 6 lined gives 9.5 plain and 3 lined. The halfway plan needs 15.5 boards and 22 bench hours, comfortably inside all three limits.

The last example quietly admits something that matters later. The halfway plan was 9.5 plain crates. The plan satisfies all three limits and it is not a round number. The test is being run on the region the three limits carve out, treating the crate counts as quantities that can slide, and the same test run on round numbers only would fail immediately.

What does convex mean for the objective itself?

The second half of the shape is about what counts as better, not about what is allowed. An objective bends one way when, along any fixed direction, it never turns back upward once it has started coming down. The objective may climb and then fall. Climbing the whole way is allowed, and so is falling the whole way. One thing it may not do is fall, flatten and climb again. A second climb is precisely where a second summit hides.

The Amaltas workshop's objective is the flattest case there is. The day is worth Rs 300/- for every plain crate plus Rs 450/- for every lined crate, and nothing in that expression squares anything or multiplies the two counts together. Drawn over the two crate counts it is a tilted flat plane, not a hill at all. A flat plane bends one way in the same sense that a straight road bends one way, by not bending, and that is the easiest possible condition to satisfy rather than a lucky accident of this workshop.

Where the shape becomes visible is on the walk. The walk fixes the lined crate count, asks what the limits still allow the plain crate count to be, and reads off the day. At no lined crates the workshop can run 11 plain crates, worth Rs 3,300/- for the day. At one lined crate the bindingA limit is binding when the plan uses every last unit of it, so the limit is what stops any further movement. A limit with something left over is not binding, and moving it does nothing. bench hours leave 10.5 plain, which is Rs 3,600/-. The climb continues at Rs 300/- a lined crate all the way to six, and then the boards run out before the hours do, the boundary lineThe edge a rule draws across the picture. Everything on one side of it satisfies that rule and everything on the other side breaks it, and the edge itself is where the rule is met exactly. that governs changes, and the day falls Rs 150/- a lined crate for the last two steps.

Read the fourth column downward and the shape is unmistakable. Six steps up at the same size, then two steps down at the same size, and no step anywhere that goes up after a step that went down. The slope changes at six lined crates and it changes only once, and changing size is not the same thing as changing direction. A road that climbs steeply, tips over a ridge and then descends gently has bent one way. A road that climbs, descends and climbs again has not, and the difference is not a matter of degree.

What follows when both shapes hold at once?

Here is the argument in one sentence, and it is short enough to be suspicious of. From any allowed plan that is not the best one, there is a small step toward the best plan that is itself allowed and is worth more. If that sentence is true, every plan except the best one has at least one direction that goes uphill and stays legal, so no plan except the best one can beat everything around it. There is therefore nowhere for a search to stop except at the answer.

The sentence has two halves and each half is carried by one of the two shapes. The step stays inside the allowed set because the set is convex: the whole straight line from the current plan to the best plan is made of allowed plans, so the first sliver of it is allowed too. The step is worth more because the objective bends one way: moving toward a higher point along a line that never turns back up means the value goes up immediately rather than dipping first. Take either half away and the sentence fails, and it fails in a different way each time.

The workshop shows it. Starting at 2 plain crates and 2 lined crates gives a modest day worth Rs 1,500/-. The best plan is 8 plain and 6 lined. A quarter of the way along the straight line between them lands on 3.5 plain and 3 lined. The quarter way plan needs 9.5 boards and 10 bench hours and 3 rolls of cloth, so all three limits have room to spare, and the day is worth Rs 2,400/-. Nothing has been solved. All that has been shown is that standing still at Rs 1,500/- was not forced, and the same demonstration works from every allowed plan in the region.

The two failures have a shape in a building. Without a convex set, the straight line from a desk to the exit runs through a wall, so the first step in the right direction is not a step that is allowed. Without a one way objective, the corridor to the exit dips through a basement first, so the first step in the right direction goes downhill and a search that only accepts improvements refuses it. A search needs the direction to be both open and immediately rewarding, and each half of the shape supplies exactly one of those two things.

What does convexity refuse to say?

The word in the heading above has to be handled with care. Convexity establishes one thing and one thing only: that where the two shapes hold, every plan that beats its neighboursThe plans reached by nudging the counts a little way from the current plan, in any direction. Nothing about the word says how far a nudge goes; it only has to be small. beats every allowed plan too. Everything else somebody might want it to say, it does not say.

Nothing in it makes the answer a good idea. Running 8 plain crates and 6 lined ones every day might be the wrong use of a workshop for a dozen reasons that never reach the arithmetic. Nor does it bless the objective: contribution is not profit, and maximising contribution while the workshop's standing costs quietly climb is answering a question nobody should have asked. Convexity has no opinion on whether the three limits describe the workshop honestly either. If a bench is out of service and nobody updated the hours, the shape stays perfectly convex around a set of plans that cannot be run. And it promises nothing about arrival: how long a method takes to get there is a separate subject from whether there is anywhere else for it to stop.

Convexity is a claim about the shape of the arithmetic and about nothing else, and reading it as a claim about outcomes is how a mathematical property gets turned into a promise it never made. The honest sentence is conditional all the way through: if the allowed set passes the halfway point test, and if the objective never turns back up, and if the decisions slide rather than jump, then the local answer and the global one are the same plan. Three conditions, one conclusion, and the conclusion is about peaks rather than about money in anybody's pocket.

What else has to hold besides the two shapes?

There is a third condition, used twice already, and in this workshop it is the one that bites first. The halfway point test only means something if a halfway plan is a plan the workshop could actually run. Averaging 11 plain crates with 8 plain crates gives 9.5 plain crates. If the Amaltas workshop can only ever deliver round crates, that plan cannot be made, and the set of plans that can be made is 84 scattered dots rather than a solid region.

Eighty four dots are not a convex set, and it takes only one pair to prove it: 2,629 of the 3,486 pairs have a midpoint that is not a round plan at all. So the argument from the previous block is not available to a workshop that works strictly in whole crates. The interesting question is whether losing the argument costs anything here. The cost turns out to be real, so this is not a technicality.

Take each of the 84 round plans, compare it with the eight round plans one crate away from it in each direction, and ask whether any neighbour is allowed and better. Three plans answer no. The best plan, 8 plain and 6 lined at Rs 5,100/-, answers no because it is the answer. But 6 plain and 7 lined answers no as well, at Rs 4,950/-, and so does 4 plain and 8 lined at Rs 4,800/-. Both are genuine resting places for a round crate search: every one of their eight round neighbours either breaks a limit or is worth less. From 6 plain and 7 lined the only way out is a move of two plain crates and one lined crate at once, landing exactly on 8 plain and 6 lined, and a search that changes one count by one at a time will never propose it.

Meanwhile the sliding version of the same problem has no such resting places, and that contrast is the point. From 6 plain and 7 lined a step of one hundredth of the way toward 8 plain and 6 lined is allowed and worth more, so on a sliding region there is nothing to stop at. The same three limits and the same two contribution figures give one peak or three, depending entirely on whether the crates are allowed to be fractions, and nothing about the word convex is doing that work.

How was the single peak actually checked here?

Everything above is an argument, and an argument about shapes is easy to nod along to and hard to believe at the level where money moves. So the claim was turned into a computation. A sweep of the whole allowed region at a quarter of a crate in each direction gives 1,161 plans. The ones already worth Rs 5,100/- are set aside. For every single one of the rest, the plan one hundredth of the way toward 8 plain and 6 lined is worked out, checked against all three limits, and checked to be worth more than the plan it came from.

All 1,161 pass. Not one allowed plan short of Rs 5,100/- a day is a place a search could honestly stop. There is no need to trust the picture, and there is no appeal to intuition about solid shapes. The check is a sweep with an assertion at every point, and if the region had a dent in it somewhere the sweep would have found a plan where the small step left the allowed set, printed it, and this block would read differently.

The relationship between the picture and the computation runs the way people usually assume it runs, but backwards. The computation is the evidence. The picture makes the evidence believable by presenting a shape in which the result is unsurprising. Nobody has to take 1,161 assertions on faith. A drawing is a reason to expect a result and never a reason to accept one, and the difference between the two is most of what separates a checked answer from a confident one.

What happens when one added rule breaks convexity?

The cloth cutter in the Amaltas workshop is replaced, and the new one has to be set up before it will cut anything at all. Setting it up eats most of a morning, so the workshop adopts a rule that any foreman would call obvious: either the day makes no lined crates, or it makes at least five. Nothing else changes. Twenty boards, twenty two bench hours, eight rolls of cloth, Rs 300/- and Rs 450/-, all exactly as before. One sentence has been added to a list of rules.

The halfway point test runs again on the pair that passed it comfortably earlier. Making no lined crates satisfies the new rule at its first branch, so eleven plain crates and no lined crates is still allowed. Six is at least five, so eight plain and six lined is still allowed. Halfway between them is 9.5 plain and 3 lined. Three lined crates is neither none nor at least five. The set stopped being convex at the instant a plan sitting between two allowed plans became not allowed, and the region that was one solid shape is now a shape floating above a line, with a forbidden band between them.

The picture is worth pausing on. The shape it shows is not quite the neat two blobs the description suggests. Above the band sits a proper region: every plan with five or more lined crates that also fits the three limits. Below the band sits something thinner, a single line running from no crates at all to 11 plain crates. Once lined crates are barred, the only choice left is how many plain crates to make. A search standing anywhere on that line can move left and right along it and nowhere else, and everything better than where it stands is on the other side of the band.

What does that one extra sentence cost the workshop?

Stand a search at 11 plain crates and no lined crates, worth Rs 3,300/- a day, and test every small move it could make: one way in each of the four compass directions and one way along each of the four diagonals. Adding a plain crate breaks the bench hours limit, already used to the last minute at 22 hours. Adding a lined crate breaks the bench hours limit too, and the batch rule on top of it. Subtracting a plain crate is allowed and is worth Rs 300/- less. The diagonals fail for the same reasons in combination. Not one of the eight moves is both allowed and worth more, so the search stops, and it is right to stop.

Before the rule was added, exactly one of those eight moves worked: give up a sliver of a plain crate and take on a sliver of a lined crate. The trade frees an hour and a half of bench time for every hour it consumes, and it pays Rs 450/- for every Rs 300/- it gives up, so it goes uphill. The swap was the whole escape route. The batch rule closed it. Any lined crate at all, however small a sliver, must now be either none or at least five, and a sliver is neither.

The best allowed plan has not moved. Eight plain and six lined satisfies the batch rule, satisfies all three limits and is still worth Rs 5,100/- a day. So the arithmetic of the loss is a subtraction anybody can do: Rs 5,100/- less Rs 3,300/- is Rs 1,800/- a day, in a problem where nothing changed except one sentence about setting up a machine. That is what the missing convexity costs, and notice that it costs it without any error being made anywhere. The rule is sensible. The search is correct. The answer is still there. The answer simply cannot be got to from where the search happened to begin.

Where does non convexity come from in an ordinary week?

Reading the block above, it is tempting to file the batch rule as a curiosity: an unlucky sentence, unusual, the sort of thing that happens to workshops in teaching notes. The opposite is true. The four ordinary things that break convexity turn up in an ordinary week and none of them looks like mathematics when it arrives.

A setup cost is the first. Anything that has to be paid once if any are made at all, and not at all if none are, puts a step in the objective at zero. Fixing a jig, cleaning a die, changing a thread: the cost of the first unit is not the cost of the second. The second is a minimum batch, the Amaltas workshop's own case: once production starts, it starts properly, and everything between none and the minimum stops existing. The third is a price break at a volumeThe size of an order or a run, counted in units. A term used here only to say where a price changes; how to choose the size is a separate matter., where a supplier charges less per board from thirty boards upward, so the cost per unit drops the moment a line is crossed rather than sliding down toward it. And the fourth is a decision that is on or off rather than a quantity: hire the second van or not, open on Sunday or not, take the contract or leave it. There is no halfway van.

Each of the four has the same fingerprint underneath. Something in the problem jumps instead of sliding, and a jump is a place where a straight line between two allowed situations can pass through a situation that is not allowed, or where a value can dip and come back. An exotic problem is not needed to lose convexity, and the safe assumption is that it has been lost until a check says otherwise, rather than the other way round. The inversion is what convexity is worth in practice.

How can one tell whether a problem is convex?

Somebody handed a planning model to review, a credit officer reading a borrower's production schedule before agreeing a limit, and a household working out how to split a month between two side earnings are all in the same position, and not one of them is going to run a 1,161 point sweep before deciding anything. Four questions do most of that work, and all four are answered by reading the rules rather than by computing over them.

First, is every rule a straight line in the decisions? Twenty boards where a plain crate takes one and a lined crate takes two is a straight line. A rule that squares something, or multiplies two decisions together, or applies only above a level, is not. Second, does any rule contain the word either? Either none or at least five. Either open the second site or do not. The word either is the audible sound of a set splitting into two pieces. Third, does any cost or price step rather than slide? A rate that drops from thirty units upward is a step. Fourth, is any decision a yes or no rather than a how much? A van is bought or it is not.

One yes to any of the four is enough, and there is no arithmetic that averages the four answers into a score. When the answer to all four is no, and the objective is a straight line or a single smooth bend in the same direction, the small step argument applies and a stop is the answer. When any one of the four is yes, the honest report changes one word: not the best plan, but the best plan found, together with where the search started. On a set in more than one piece the starting point is part of the result.

The change of word is no formality, and it is not modesty either. The wording tells the person reading the report what question to ask next, namely whether anybody tried starting somewhere else. In the Amaltas workshop's case, starting anywhere with five or more lined crates leads straight to Rs 5,100/- a day, and starting at the plain crate end leads to Rs 3,300/-. A report that says best found invites that second run; a report that says best closes it off, and the difference between the two reports here is Rs 1,800/- a day.