Quadratic Programming: The Form Behind Portfolio Optimisation

Quadratic programming is optimisation where the objective holds a decision multiplied by a decision and every rule stays a straight line. One change, one visible consequence: the best answer no longer has to land on a corner of the region. At the Amaltas workshop the bent objective is best at 9 plain crates and 4 lined crates, partway along an edge, worth Rs 3,640/- a day.

Three results are taken as settled here. The Amaltas workshop makes exactly two things and has three limits on its day. A straight line objective over straight line rules tops out on a corner, and that result is settled separately, under linear programming. And the shape argument that gives such a problem a single top is settled separately too, under convex optimisation. Precisely one thing changes here, the objective. The rules stay exactly where they were, and everything that follows from the objective moves.

One habit everybody carries forward without noticing is what moves. Once the lesson that the answer lives at a corner has been learned, corners become where the eye goes, and looking there is fast, finite and satisfying. There are five corners at this workshop, all five can be priced in under a minute, and the highest one is obviously the answer. Bend the objective and that whole procedure keeps working perfectly and stops being correct. A procedure that keeps running while it gives the wrong answer is far more dangerous than one that breaks. Nothing errors. Nothing looks wrong. The comparison was run properly and the number it produced is Rs 140/- short.

What makes an objective quadratic rather than linear?

Somewhere in it, a decision is multiplied by a decision. A decision multiplied by a decision is the whole definition, and the definition is narrower than people expect. The words are worth holding exactly as they stand. Multiplying a decision by a fixed number is not it. Adding two decisions together is not it. Squaring is multiplying a thing by itself, and squaring a decision is it. Multiplying one decision by a different decision is it. A quadratic objective is one where at least one term contains two decision variablesA quantity that is chosen, as against one the world hands over. Here there are exactly two of them, and everything else follows from what they are set to. multiplied together, counting a variable multiplied by itself.

Here is what that means in plain terms, and it is easier to feel than to define. In the straight line case, a crate is worth what a crate is worth. The ninth one of the day pays exactly what the first one paid, and the workshop could make four hundred of them at that rate if the timber held out. In the quadratic case, what a crate is worth depends on how many of them there already are. The ninth is not the first. The difference is that single sentence, and everything else follows from it.

An everyday version sits in most kitchens. The first cup of tea of the morning is worth a great deal. The fourth is worth something. The seventh is doing nobody any favours at all. The amount per cup is not fixed. The amount falls as the cups pile up, and past some point the next cup is a cost rather than a benefit. Nobody would model the enjoyment of tea as a fixed amount per cup multiplied by cups. A falling amount per cup is a bent objective, and most people have been using one all their lives without writing it down.

Notice what has not changed. The rules stay straight lines throughout, and only the objective bends. The word programming inside the name is doing exactly that work. Boards, bench hours and cloth still add up the way they always did: a plain crate still takes one board and two hours, a lined one still takes two boards, one hour and one roll. The shape of the allowed region is untouched. Programming here means the whole set of methods that solve for a best answer under limits, and quadratic names the objective only. A problem with a bent rule and a straight objective is a different animal with a different name, and it is not this one.

Why would a workshop have a bent objective at all?

Because somebody made an arrangement, and arrangements are where bends come from. The Amaltas workshop has taken a standing wholesale order, and the terms of it are that the wholesale buyerSomebody who takes goods in quantity on agreed terms rather than one at a time over a counter. The price is settled in advance and can depend on how many arrive. pays a little less for each further crate of the same kind that turns up in one day. Nobody at the workshop chose to make the arithmetic harder. The workshop chose a buyer who takes everything, and the price ladder came attached.

The arrangement is familiar from the other side. A caterer quoting for a wedding does not charge the four hundredth plate what they charged the fortieth. A vegetable seller clearing the last crates at six in the evening is not asking the morning price. A printer quoting a thousand copies quotes less per copy than for fifty. In every one of those, the rate per unit slides as the count rises, and the moment a rate slides with the count, the total is no longer a rate multiplied by a count. The total is something bent.

Written out, the day's takings under these terms come to two expressions, one per crate type. The plain crates bring in 500 times the plain crate count, less 20 times that count multiplied by itself. The lined crates bring in 310 times the lined crate count, less 30 times that count multiplied by itself. Each expression has the count multiplied by the count sitting inside it. By the definition above that makes the objective quadratic, and the amount being taken off grows faster than the count does.

Amaltas is the same workshop under the same three daily rules, with a different arrangement with its buyer, and nothing about the workshop itself has changed. Twenty boards still arrive. There are still 22 bench hoursThe unit the workshop counts its capacity in. One person at one bench for sixty minutes is one of them, and the day has a fixed number of them to spend. in the day and 8 rolls of clothLining fabric wound on a roll, bought and counted a whole roll at a time. Nothing but the lined crate ever touches it. on the shelf. The figures of Rs 300/- and Rs 450/- of contributionWhat a crate leaves behind once the spending that rises with it has been taken off. Rent and wages still have to come out of the total, so it is not profit. a crate that the earlier work runs on belong to the arrangement where the price does not move, and they are perfectly correct there. The two figures simply describe a different deal. Mixing the two arrangements produces an answer that belongs to neither, so the two sets have to be kept apart.

What do the two tables actually say?

No calculus is needed here. Both expressions are worked out at every count the workshop could actually reach, and the result is two short tables that can be checked with a pencil. Crates come in whole cratesCounts that cannot carry a fraction. Two thirds of a crate is sawdust and half a plan, so every count here is a round one., the plain count can never pass eleven and the lined count can never pass eight, so between them the two tables hold every value the objective can take.

The third column of each table repays a careful reading. The whole argument is sitting in those two columns. Every further crate adds less than the crate before it, by Rs 40/- each time in the plain table and by Rs 60/- each time in the lined one, and the lined table stops adding anything at all after the fifth crate. The fifth lined crate is worth Rs 40/-, very little but still worth having. The sixth takes Rs 20/- off the day. The seventh takes off Rs 80/- and the eighth Rs 140/-.

The sixth lined crate is genuinely strange the first time, and it repays a moment's attention. The workshop has cloth left, boards left and hours left. Nothing anywhere says it cannot build a sixth lined crate, and building it makes the day worse. Under the arrangement where the price does not move, no such thing could happen: another lined crate was another Rs 450/-, full stop, and the only reason to stop was that a rule forced a halt. Now there is a second reason to stop, and it lives inside the objective rather than in the rules.

Where does the best plan sit, and why is it not a corner?

Under the bent objective, no allowed plan beats 9 plain crates with 4 lined ones. The figure reads straight off the two tables: nine plain crates are worth Rs 2,880/- and four lined ones are worth Rs 760/-, so the day comes to Rs 3,640/-. The rules hold as well. Boards: nine plus eight is seventeen, against the twenty that arrive. Bench hours: eighteen plus four is twenty two, against the twenty two available. Cloth: four rolls against eight. All three hold, so the plan is allowed, and no other allowed plan of whole crates reaches Rs 3,640/-.

The corner method says to price the five corners under the same objective. An empty day is Rs 0/-. Eleven plain with none lined gives Rs 3,080/- from the tables. Eight plain with six lined: Rs 2,720/- and Rs 780/-, so Rs 3,500/-. Four plain with eight lined: Rs 1,680/- and Rs 560/-, so Rs 2,240/-. None plain with eight lined is Rs 560/- flat. Lined up, the five are headed by Rs 3,500/-.

The corners miss the answer by Rs 140/- a day, and the answer sits partway along the bench hours edge rather than at either end of it. The gap of Rs 140/- is the entire claim, stated as a number. The plan 9 plain and 4 lined lies on the straight boundary running between the corner at eleven plain crates and the corner at eight plain with six lined, one step in from one end and two steps in from the other, and there is nothing at all special about the point except that it is where the bent objective happens to top out.

There is a detail in the reshuffle that is worth more than it looks. Under the arrangement where the price does not move, the five corners rank with eight plain and six lined on top. Under the bent objective they rank with eight plain and six lined on top as well. The bend genuinely reorders three of the five underneath, pushing eleven plain and no lined up from fourth to second, but the corner that wins does not change. So the corner method does not even offer a different corner to be suspicious about. The corner method returns the same familiar plan it always returned, and that plan is now wrong.

What does the answer leave unused?

Score the answer against each limit in turn and one of them is full while two are not. All 22 bench hours go into 9 plain crates and 4 lined ones, so there is nothing left there. Boards: seventeen of the twenty that arrived get cut, so three are still in the yard at the end of the day. Cloth: four of the eight rolls are opened, so four are still on the shelf. Three boards and four rolls sit idle at the best plan the workshop can reach, and the workshop is not being careless.

Compare that with what happened before. Under the arrangement where the price does not move, the best plan used every board and every bench hour, and left only two rolls of cloth. Boards were worth having, so the answer bought all it could. Now the answer walks away from three of them. The three boards stay in the yard because the tenth plain crate would only add Rs 120/- and the fifth lined crate only Rs 40/-, and neither of those is enough to be worth the bench hours it would take, given what has to be given up elsewhere to find them.

The practical gift of the whole method costs nothing. Under a straight line objective a limit expected to bind normally does bind. A limit left with room to spare at the answer is therefore the visible tell that the objective has bent. Noticing it takes no inspection of anybody's formulas. The solved plan and the limits are enough: when something that seemed certain to be tight comes back loose, the objective is worth reading before the answer is trusted.

What does the shape around the answer look like?

Stand at the answer and take one step each way along the same edge. Every plan on that edge uses all 22 bench hours, so a step is a trade: one more plain crate costs two bench hours, and the only place to find them is by giving up two lined crates. Step down to 8 plain and 6 lined and the day is Rs 2,720/- plus Rs 780/-, or Rs 3,500/-. Step up to 10 plain and 2 lined and the day is Rs 3,000/- plus Rs 500/-, or Rs 3,500/- again. One step either way costs exactly the same Rs 140/-, and that is arithmetic rather than coincidence.

Here is why it has to come out that way. A bend of this kind is symmetric about its own top. Walk away from the top in one direction and the fall follows the same shape as walking away in the other, so equal steps cost equal amounts. Reading anything into the two figures matching would be a mistake, and so would hunting for a connection between the plan with six lined crates and the plan with two. There is no connection. The match is what the top of a bend looks like from the inside, and it would happen at the top of any bend like this one.

The symmetry is also a useful test. Given a plan said to be the best one, one step each way, priced both times, settles it. Two steps that cost roughly the same is consistent with standing at a top. One step that costs a lot and one that costs almost nothing means the plan is on a slope and the top is further along in the cheap direction. The test takes two multiplications and is available to anybody, whatever solved the problem in the first place.

Does the single peak property survive the bend?

Here, yes, and for a reason that can be stated. Both expressions bend the same way, downward, so the whole objective is one hill rather than a landscape with several. The allowed region is still one unbroken shape, unchanged from before. One downward hill over one unbroken region means the shape argument settled separately under convex optimisation still applies, so there is one top and any honest climb finds it. Walking the plain crate count from none to eleven, the readings run Rs 800/-, Rs 1,280/-, Rs 1,720/-, Rs 2,120/-, Rs 2,480/-, Rs 2,800/-, Rs 3,080/-, Rs 3,320/-, Rs 3,520/-, Rs 3,640/-, Rs 3,500/- and Rs 3,080/-. Nine climbs, then two falls. One top, and it is not at either end.

Now the limit of that claim, and it matters more than the claim. The property comes from which way the objective bends, not from the word quadratic, and an objective that bends upward in one decision while bending downward in another does not have it. Suppose the buyer had offered the opposite kind of lined crate arrangement: a bulk bonus that grows, so each further lined crate pays more than the one before it rather than less. The plain side keeps its downward bend, the lined side now bends upward, and the objective is a hill in one direction and a valley in the other.

The right hand column reads the same way as the left. The column climbs to Rs 4,080/- at four plain crates, drops, climbs again to Rs 4,170/- at six, drops, climbs again to Rs 4,160/- at eight, and then falls away. Three tops rather than one. A search that moves one crate at a time and keeps only improvements sets off from the bottom, reaches four plain crates, finds that five is worse, and halts on Rs 4,080/- while Rs 4,170/- sits two crates further on. The search is short by Rs 90/-, and it has no way of knowing.

So quadratic is not a synonym for safe, and it never was. Quadratic names the form of the objective and nothing about its behaviour. The thing actually worth knowing is the direction of every bend in it, and that is a separate question, to be asked separately, every time.

Where is this form most often met, and where is that taught?

Not in a workshop. The best known use of quadratic programming by a wide margin is the problem of settling what share of a total to put into each of several holdingsOne of the things somebody has put money into and still has. Holding is a stock word rather than a workshop word, used only to name where a subject lives., where one quantity has to be traded off against another, and where the arithmetic of that trade off multiplies one holding by another. The multiplication of one holding by another is what makes it the same form as the workshop's day. The problem has a name, the allocationDeciding how much of a total goes to each of several places. The word is used here to name a subject, not to work one. problem, and it has a name because it has a home.

The allocation problem is covered separately, under portfolio construction and investment management. Every quantity above is a crate, a board, a bench hour or a roll of cloth.

The claim made here is narrower and more useful than it might look. The form is the same form. Everything set out above carries across to it without a single change: the answer need not be at a corner, so a corner search will quietly miss it; limits can come back with room to spare at the answer, and that is a tell rather than an error; steps either side of the top cost about the same; and whether there is one top at all depends on which way each part of the objective bends. The four points just listed, learned on crates where everything can be counted by hand, are recognisable at once in the subject where they live.