Optimising Against a Guess

TL;DR

• An optimiser can select a disappointing decision even when every value estimate supplied to it is unbiased. Selection favours estimates whose errors point in the attractive direction. Smith and Winkler called this the optimizer's curse.
• The certificate is not wrong. It proves optimality for the model and numbers it was given, not for the unknown system those numbers were meant to describe.
• Stochastic programming replaces a point estimate with a probability distribution and separates decisions made before uncertainty is revealed from recourse decisions made afterwards.
• Robust optimisation replaces a distribution with a set of admissible values. In the Bertsimas–Sim model, a budget of uncertainty Γ controls how much simultaneous adversity the decision must survive.
• Distributionally robust optimisation doubts the distribution too. It optimises against the worst distribution in a neighbourhood of the data. Every remedy restores a guarantee by asking for a new object to trust.

The previous article ended with a complete proof. Branch-and-bound had shown that no better integer decision existed. The proof was right. The decision can still disappoint.

Fixed costs, expected returns, capacities and reaction bounds entered that model as facts. In practice they arrive as estimates. A solver can close its computational gap to zero while the distance between an estimate and the world remains unknown. These are different gaps. More computation closes only the first.

The estimate that wins

Imagine a company comparing ten projects. Their true values are identical, but nobody knows that. Each project is evaluated with an independent, unbiased forecast: repeat the exercise often enough and its positive and negative errors cancel. On this particular table, some estimates land high and some low. The company chooses the largest.

It has therefore selected two things at once: a project and an unusually favourable error. Re-estimate the chosen project with fresh information and the number will tend to fall. Nothing had to be wrong with any estimator taken on its own. The bias appeared when an optimisation rule selected one estimate from the set.

James Smith and Robert Winkler named this the optimizer's curse in 2006. Suppose the estimates are conditionally unbiased: for every fixed set of true values, each estimate is right on average. Their Proposition 1 shows that, on average, the winning estimate is at least as large as the true value of the alternative it selected.[1] A positive probability of selecting a truly inferior alternative is sufficient to make the inequality strict. That condition does not apply to the equal-value experiment, where no alternative is inferior. Strictness there follows separately because the expected maximum of ten independent standard-normal estimates is positive. The disappointment comes from the selection rule, not from bias in any estimator considered alone.

The equal-value example strips the mechanism bare. Real projects do not all have the same value, and a selected decision need not disappoint every time. A genuinely better project can win for the right reason. The claim is about the average comparison between the winning estimate and what it estimated. In the equal-value experiment with independent noise, adding more alternatives creates more opportunities for a favourable error to look like information.

Smith and Winkler's response is Bayesian: model the uncertainty in the value estimates, combine the analysis with prior information, and rank alternatives by posterior means.[1] In their normal models, that update appears as shrinkage, pulling extreme forecasts towards a prior mean and correcting the selection effect. But the curse is broader than any one correction. It changes what the word optimal can honestly modify. The chosen project is optimal for the table. The table is not the company.

An estimation-error maximiser

Portfolio optimisation makes the problem unusually visible because a small input table produces a large vector of weights. Markowitz asks for expected returns and a covariance matrix. Neither is observed directly. Both must be estimated, often from a finite and changing history rather than read from the market as facts.

Richard Michaud argued in 1989 that mean–variance optimisation tends to maximise the effects of errors in those inputs.[2] Michael Best and Robert Grauer then examined what happens when estimated asset means move. With non-negative weights, they found that a surprisingly small increase in the mean of one asset could drive half the securities out of the efficient portfolio, while the portfolio's expected return and standard deviation remained virtually unchanged.[3]

The optimiser is behaving exactly as designed. Expected return is the direction in which the objective asks it to lean, so tiny differences there can decide which constraints bind and which assets receive weight. A mathematically exact answer can therefore be operationally unstable. Re-running the same model after a routine data update may produce a different portfolio without producing a meaningfully different point in risk–return space.

This is the bridge to Beyond Markowitz, the next series on this site, but not yet its answer. First comes a more basic question. If a point estimate is exactly what an optimiser is most able to exploit, what should replace it?

If you trust a distribution

The first response is to model the uncertainty directly. George Dantzig's 1955 formulation divided activities into stages.[4] Decisions in the first stage are fixed before uncertain demand is known. Later decisions adapt after it is revealed. E. M. L. Beale described a related formulation independently that same year.[5] The modern vocabulary is here-and-now followed by wait-and-see recourse.

The smallest useful example is the newsvendor. A retailer orders once, demand arrives, and unsold units can only be salvaged. Ordering too little loses a margin; ordering too much leaves a markdown. If the cost of one unit too few is C_u and the cost of one unit too many is C_o, the optimal quantity is a quantile of the demand distribution:

Here F⁻¹ denotes the generalised inverse of the cumulative demand distribution: the smallest quantity q for which F(q) reaches the critical fraction. This definition also covers discrete demand.

Suppose an item sells for €70, costs €40 and can be cleared for €20. One unit short costs €30 of forgone margin; one unit left costs €20. The critical fraction is therefore 30/(30 + 20) = 0.60. The model orders the smallest demand quantity whose cumulative probability reaches 60 per cent, not the mean.[6]

That is already a better description of the decision. It recognises that stock is committed before demand and that the two mistakes have different prices. It also relocates the assumption. The answer is now optimal for a distribution F. If that distribution was estimated badly, the certificate remains conditional on the wrong object.

For larger models, sample-average approximation replaces an expectation with an average over independent draws from the same scenario distribution and solves the resulting deterministic problem. The result cited here has a precise scope: Kleywegt, Shapiro and Homem-de-Mello study stochastic discrete optimisation with a finite feasible set. With integrable costs, the SAA values and solution sets converge almost surely; if the relevant cost differences also have moment-generating functions finite around zero, the probability of selecting a materially suboptimal solution can decay exponentially with sample size.[7] Sampling makes uncertainty computable; it does not make the sample representative by decree.

If you trust only limits

Sometimes a full probability distribution is harder to defend than a range. A supplier may promise that a lead time lies between six and ten days, while nobody can justify assigning 23 per cent probability to eight. Robust optimisation asks for a decision that remains feasible across an uncertainty set rather than one that performs best on average under a distribution.

The early robust model associated with Allan Soyster protects against all uncertain coefficients taking their worst admissible values together.[8] It is safe and can be punishingly conservative. The latter judgement belongs to the literature that followed, not to Soyster's four-page note.

Dimitris Bertsimas and Melvyn Sim turned that extreme into a dial. In each constraint, every uncertain coefficient may deviate within its interval, while the sum of its absolute normalised deviations is capped by a budget of uncertainty Γ.[9] The budget need not be an integer. In the worst case, an integer Γ lets the Γ most damaging coefficients deviate fully; a fractional Γ adds one partially deviating coefficient. Γ = 0 recovers the nominal model, while Γ equal to the number of uncertain coefficients recovers simultaneous worst-case protection. Intermediate values let a modeller spend objective performance to buy protection gradually.

For this budgeted interval model, the robust counterpart of a linear program remains a linear program. The probability guarantee is a separate statement: it assumes that the normalised coefficient deviations are independent, symmetric about zero and bounded between −1 and 1. Under those assumptions, Γ yields an explicit upper bound on the probability that a constraint is violated. The uncertainty changes the feasible set without taking away the primal–dual certificate from the first article.

Γ does not emerge from the solver. Someone has to choose it. The model can show what each setting costs and, under stated assumptions, what it protects. It cannot decide how much evidence makes simultaneous disruption plausible.

If the distribution is also a guess

Stochastic programming trusts one distribution. Robust optimisation trusts one set. Distributionally robust optimisation, or DRO, begins by admitting that the distribution itself was inferred from limited data.

One data-driven construction centres a ball of probability distributions on the empirical distribution. Distance is measured with the Wasserstein metric, the least work required to transport one distribution into another. Radius zero trusts the observations exactly. A larger radius admits distributions farther from them. The optimisation then chooses the decision with the best outcome under the worst distribution inside that ball.

Peyman Mohajerin Esfahani and Daniel Kuhn showed that, under convexity and regularity assumptions on the support and loss, these apparently infinite-dimensional problems can be reformulated as finite convex programs and, in many important cases, as tractable linear programs. Their statistical guarantees have a more specific scope. With i.i.d. observations from a light-tailed distribution and a radius calibrated from a concentration bound, the DRO value upper-bounds out-of-sample expected cost at a chosen confidence level. If the radii then shrink to zero appropriately and the loss and feasible set satisfy their semicontinuity, growth and closedness conditions, optimal values and limiting optimisers are asymptotically consistent.[10] The result is not that every DRO problem becomes an LP. It is that distributional doubt need not destroy tractability.

There is a precise connection to regularisation. For linear regression on the unrestricted input–output space ℝⁿ⁺¹, with a convex Lipschitz residual loss and a first-order Wasserstein ball whose transport cost is induced by a norm, worst-case expected loss equals empirical loss plus ρ · Lip(L) · ‖(w, −1)‖_*.[11] Here ‖·‖_* denotes the dual norm induced by the transport-cost norm. Change the support, loss or transport cost and the equality need not survive. Saying that all DRO is regularisation would turn a theorem into a slogan and lose the boundary that makes it true.

The guess behind every cure

The optimality gap in the previous article measured unfinished computation. This article's gap is different. It lies between the model's inputs and the system they describe, and no branch-and-bound tree can close it.

The three responses do not form a universal ranking. They ask for different kinds of knowledge. Stochastic programming needs a distribution and a recourse structure. Robust optimisation needs an uncertainty set and a protection budget. Wasserstein DRO needs a metric and a radius around the data.

Each one restores a guarantee by asking for something new to believe. The optimiser can price that belief. It cannot choose it for you.

The next problem is therefore not how to optimise an estimate. It is what to believe before the optimisation begins. That is where Beyond Markowitz starts.

Data and code

Every simulated and optimised result in the two figures is generated in the Post 4 companion folder. The package declares every distributional assumption, random seed, sample size and optimisation model; records Monte Carlo uncertainty; and keeps analytical guarantees separate from empirical simulation results.

References

1. James E. Smith and Robert L. Winkler, “The Optimizer's Curse: Skepticism and Postdecision Surprise in Decision Analysis”, Management Science 52, no. 3 (2006): 311–322.
2. Richard O. Michaud, “The Markowitz Optimization Enigma: Is ‘Optimized’ Optimal?”, Financial Analysts Journal 45, no. 1 (1989): 31–42.
3. Michael J. Best and Robert R. Grauer, “On the Sensitivity of Mean-Variance-Efficient Portfolios to Changes in Asset Means: Some Analytical and Computational Results”, Review of Financial Studies 4, no. 2 (1991): 315–342.
4. George B. Dantzig, “Linear Programming under Uncertainty”, Management Science 1, nos. 3–4 (1955): 197–206.
5. E. M. L. Beale, “On Minimizing a Convex Function Subject to Linear Inequalities”, Journal of the Royal Statistical Society: Series B (Methodological) 17, no. 2 (1955): 173–184.
6. Kenneth J. Arrow, Theodore Harris and Jacob Marschak, “Optimal Inventory Policy”, Econometrica 19, no. 3 (1951): 250–272.
7. Anton J. Kleywegt, Alexander Shapiro and Tito Homem-de-Mello, “The Sample Average Approximation Method for Stochastic Discrete Optimization”, SIAM Journal on Optimization 12, no. 2 (2002): 479–502.
8. Allan L. Soyster, “Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming”, Operations Research 21, no. 5 (1973): 1154–1157.
9. Dimitris Bertsimas and Melvyn Sim, “The Price of Robustness”, Operations Research 52, no. 1 (2004): 35–53.
10. Peyman Mohajerin Esfahani and Daniel Kuhn, “Data-Driven Distributionally Robust Optimization Using the Wasserstein Metric: Performance Guarantees and Tractable Reformulations”, Mathematical Programming 171, nos. 1–2 (2018): 115–166.
11. Soroosh Shafieezadeh-Abadeh, Daniel Kuhn and Peyman Mohajerin Esfahani, “Regularization via Mass Transportation”, Journal of Machine Learning Research 20, no. 103 (2019): 1–68.