Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 38 ยท Applications

Finance and Data Fitting with LP

Use linear programming beyond factories: least absolute deviation and minimax regression, absolute-value linearization, and minimum-CVaR portfolio optimization with scenarios, in SciPy.

Linear programming is not only for factories and trucks. Two other big application areas are data fitting (regression with unusual error measures) and finance (portfolios, risk, replication). The reason is a toolbox of tricks that turn nonlinear-looking objectives, such as sums of absolute values or maxima, into linear ones. Once you have them, LP solves problems in statistics and risk management efficiently, even with thousands of data points.

Linearizing absolute values and maxima

Three transformations cover most cases:

  1. Absolute value in a minimized objective. To minimize |z|, introduce e >= 0 with e >= z and e >= -z and minimize e. At the optimum e = |z|. This works because minimization pushes e to the lower of the two bounds.
  2. Maximum in a minimized objective (minimax). To minimize max_i f_i(x), introduce t with t >= f_i(x) for all i and minimize t.
  3. Positive part. To minimize max(0, z), use u >= 0, u >= z.

These work when the objective is convex and being minimized (or concave and maximized). They do not work for maximizing an absolute value, which is a non-convex problem.

Least absolute deviation regression

Ordinary least squares (OLS) minimizes squared residuals, so a single outlier with a large residual dominates the fit. Least absolute deviation (LAD) or L1 regression minimizes sum |y_i - a - b x_i| instead, which is far less sensitive to outliers, and it is a linear program:

TEXT
minimize    sum e_i
subject to  e_i >= y_i - a - b x_i
            e_i >= -(y_i - a - b x_i)
            e_i >= 0, a and b free

The minimax (Chebyshev) fit minimizes the largest absolute residual t and uses the same constraints with the single variable t in place of the e_i. It is the most outlier-sensitive of all: one bad point controls the whole fit.

Python OLS, LAD and minimax lines on data with outliers

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

LAD recovers a line close to the truth (slope near 1.5) despite the two outliers, OLS is pulled toward them, and the minimax fit is distorted badly because it must compromise on the worst point. Choose the error measure to match your data: L2 for clean Gaussian noise, L1 when outliers are likely, minimax when a hard worst-case tolerance matters (approximating a function or meeting a specification).

LAD estimates the conditional median while OLS estimates the conditional mean. Adding an asymmetric weight to the two error variables gives quantile regression, which is also an LP.

Portfolio optimization with scenarios

You hold money in n assets; weights w_i >= 0 add up to 1. Returns are uncertain. Classic mean-variance (Markowitz) optimization uses variance as risk and needs quadratic programming. But variance penalizes gains as well as losses and ignores fat tails. Conditional Value at Risk (CVaR) measures the average loss in the worst (1 - alpha) fraction of scenarios, for example the average of the worst 5% of outcomes at alpha = 0.95. Rockafellar and Uryasev showed that CVaR can be minimized with a linear program over a set of S historical or simulated return scenarios r_s:

TEXT
minimize    zeta + 1 / ((1 - alpha) S) * sum_s u_s
subject to  u_s >= -r_s ยท w - zeta          (u_s is the loss beyond zeta in scenario s)
            u_s >= 0
            sum w = 1,  w >= 0
            mean return  (1/S) sum_s r_s ยท w  >= target

The variable zeta ends up at the Value at Risk (the loss quantile) at the optimum, and the objective is the CVaR itself.

flowchart LR
    S["Scenarios<br/>of asset returns"] --> L["Portfolio loss<br/>in each scenario"] --> T["Average of the<br/>worst 5% of losses"] --> O["Minimize it<br/>subject to a return target"]
Python Minimum-CVaR portfolio for several return targets

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

As the required return rises, the optimizer shifts weight from the safe asset to the risky ones and the CVaR (the average loss in the worst 5% of scenarios) climbs. Plotting target against CVaR gives an efficient frontier, like Markowitz's, but with a risk measure that sees the tails. A negative CVaR would mean even the bad scenarios earn money.

More LP ideas in finance

  • Index tracking: minimize the sum of absolute deviations between portfolio and index returns, with a cap on the number of assets (needs binary variables).
  • Transaction costs: buying and selling as separate non-negative variables w = w0 + buy - sell, with proportional costs c(buy + sell).
  • Asset-liability matching and bond dedication: choose bonds whose cash flows cover a stream of liabilities at least cost; a pure LP.
  • Arbitrage detection: find a portfolio with zero cost and non-negative payoffs in all states, with at least one positive. Duality links this to the existence of risk-neutral prices.
  • Robust optimization: worst-case returns over a box of uncertainty also give linear programs.

Portfolio models fit historical scenarios, so the weights can look far better in-sample than they will do in the future. Real use needs out-of-sample tests, diversification limits and humility about estimation error. Nothing here is investment advice.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How do you linearize the objective 'minimize |z|'?

    At the optimum e equals the larger of z and -z, which is |z|, and everything stays linear.
  2. 2. Which regression criterion is least sensitive to outliers?

    L1 penalizes errors linearly, so a distant outlier has much less leverage than with squares or a maximum.
  3. 3. What does CVaR at the 95% level measure?

    CVaR averages the tail beyond the Value at Risk quantile.
  4. 4. Which problem is NOT linearizable by these tricks?

    Maximizing a convex function such as |z| is a non-convex problem; the epigraph trick only works in the convex direction.

Summary

  • Absolute values, maxima and positive parts in a minimized objective can be linearized with auxiliary variables.
  • LAD regression is an LP that is robust to outliers; minimax regression minimizes the worst error but is outlier-sensitive.
  • Minimum-CVaR portfolios are LPs over return scenarios and capture tail risk, unlike variance.
  • Many finance tasks (tracking, bond matching, arbitrage) reduce to LPs or MILPs.
  • Model results are only as good as the data; test out of sample.

Next: Project: Facility Location