[Intermediate → Advanced] — When the objective or constraints curve: diminishing returns, risk, physics. Corners stop being special, convexity becomes the thing that matters, and Lagrange multipliers and the KKT conditions take over from shadow prices and the simplex method.
Source: [reference] — see the domain note. The numbers in the worked example were checked by hand; the SciPy script itself has not been run yet — see “Still to run” in the index.
Before you start
You need partial derivatives and the gradient (the vector of partial derivatives) → partial derivatives, and the idea of a shadow price → note 05. The vault’s numerical-methods note covers the algorithms in more depth than this one → numerical optimisation.
After this lesson you will be able to:
- Say whether a problem is convex, and why that decides whether a “best” answer can be trusted.
- Solve an equality-constrained problem with Lagrange multipliers, and read the multiplier as a shadow price.
- Check whether a point satisfies the KKT conditions for an inequality-constrained problem.
- Set up a minimum-variance portfolio as a quadratic program.
Study route: sections 1–3. Stop after the fence example and redo it on paper. Then KKT (section 4), the portfolio and the code.
The kid version
Back in note 03, the field was a flat tilted plane, so the top was always at a corner. Now imagine a field with a real hill in it — a smooth round mound. The highest point might be in the middle of the field, nowhere near a fence. And if the field had several hills, standing on top of one wouldn’t tell you whether a taller one is somewhere else. Nonlinear optimisation is finding the top when the ground curves — and the most important question is whether there’s only one hill.
Where the analogy stops working. You can see a whole field. An algorithm can only feel the slope where it’s standing, like walking in fog. On a single smooth hill, always walking uphill works. On ground with many hills, it gets you to a top, with no way of knowing it’s the top.
1. Why this exists
Linearity fails in ways that matter:
- Diminishing returns. Advertising spend: the first ₦1 million reaches new people; the tenth mostly reaches the same people again.
- Risk. An investment portfolio’s risk is the variance of its return, which involves products of holdings — quadratic, not linear.
- Physics and engineering. Drag rises with the square of speed; a beam’s strength depends on the cube of its depth.
- Prices that respond. If you set the price and demand falls as price rises, revenue = price × quantity is a product of two things you influence.
Terms used in nonlinear optimisation
- Gradient: This is the vector of partial derivatives of a function, written . It points in the direction the function increases fastest, and its length is how fast.
- Stationary point: This is a point where the gradient is zero — the ground is flat. It can be a minimum, a maximum, or a saddle.
- Local optimum: This is a point that’s better than every point near it, but not necessarily better than every point everywhere.
- Global optimum: This is a point that’s better than every feasible point anywhere.
- Convex function: A function is convex when the straight line between any two points on its graph lies on or above the graph — it curves upwards, like a bowl. is convex; isn’t.
- Convex problem: A minimisation problem is convex when its objective is convex and its feasible region is a convex set. (For maximisation, the objective must be concave: bowl upside-down.)
- Lagrange multiplier: This is a number attached to each constraint, written , which measures how much the optimal objective changes per unit change in the constraint. It’s the nonlinear shadow price.
- Lagrangian: This is the objective with each constraint added in, multiplied by its multiplier: .
- KKT conditions: KKT stands for Karush–Kuhn–Tucker, after the three people who found them. These are the conditions any optimum of an inequality-constrained problem must satisfy (under mild assumptions), generalising “gradient equals zero”.
- Quadratic program: This is also known as a QP. This is a problem with a quadratic objective and linear constraints. Portfolio optimisation is the classic example.
2. Convexity is the dividing line
For a convex problem, every local optimum is a global optimum.
That one sentence is why convexity matters more than linearity. Why it’s true, in words: suppose a point is a local minimum but some other point is better. Walk along the straight line from to . Because the region is convex, the line stays feasible. Because the function is convex, it lies below the line joining and , so it’s below even right next to . That contradicts being a local minimum.
So:
- Convex problems (LPs, least squares, minimum-variance portfolios, many engineering designs) can be solved reliably, at scale, with a guarantee.
- Non-convex problems (most neural network training, many design problems, anything with integer variables) can only be solved locally, unless you’re willing to pay for a global search.
How to check convexity in practice:
- A sum of convex functions is convex. A positive multiple of a convex function is convex.
- Linear functions are both convex and concave.
- , , and are convex.
- A twice-differentiable function of one variable is convex when its second derivative is never negative. For several variables, the matrix of second derivatives (the Hessian) must be positive semi-definite.
- Constraints with convex , and linear equality constraints, give a convex region. A nonlinear equality constraint generally doesn’t.
3. Equality constraints: Lagrange multipliers
The problem: a farmer has 40 metres of fence and wants the largest rectangular pen. Width , length :
The idea in words. At the optimum, you can’t move along the constraint and improve the objective. That means the objective’s gradient must point straight across the constraint, not along it. So the objective’s gradient and the constraint’s gradient must be parallel: one is a multiple of the other.
The method states that at an optimum of subject to , there is a number with .
Apply it. and , so:
- .
- .
- .
From 1 and 2, . From 3, , so , and . The best pen is a 10 × 10 square with area 100 m².
Now read . One more metre of fence should add about square metres. Check: with fence , the best pen is a square of side , area . Its derivative is , which at is 5. ✓
The Lagrange multiplier is the shadow price of the constraint, exactly as in note 05. LP duality is the linear special case of this.
4. Inequality constraints: the KKT conditions
Real constraints are usually inequalities: budgets, capacities, limits. Then a constraint might be binding at the optimum, or might not matter at all.
The example:
The objective is the squared distance from the point . Without the constraint, the answer is itself. But , so that’s infeasible. The best you can do is the closest point on the line .
The KKT conditions, for minimising subject to , state that at an optimum there is a multiplier such that:
- Stationarity: . The objective’s downhill direction is blocked exactly by the constraint.
- Primal feasibility: .
- Dual feasibility: . The constraint can only push, not pull.
- Complementary slackness: . Either the constraint is binding, or its multiplier is zero — note 05’s rule again.
Apply them. Write the constraint as . Guess it’s binding.
- Stationarity: and . So , i.e. .
- Binding: , so , .
- Then . That’s . ✓
Optimum: , objective , multiplier .
If the guess had produced , it would mean the constraint was “pulling” the solution, which inequality constraints can’t do — so the guess was wrong, and you’d try the constraint as non-binding instead.
For convex problems, the KKT conditions are sufficient as well as necessary: a point that satisfies them is the global optimum. For non-convex problems, they only identify candidates.
5. A quadratic program: the minimum-variance portfolio
Harry Markowitz’s 1952 insight, which won a Nobel prize: an investor should care about risk as well as return, and combining risky assets can produce something less risky than any of them.
Two assets. Asset 1 has standard deviation (risk) 20% a year; asset 2 has 30%. Their returns are uncorrelated. Put a fraction in asset 1 and in asset 2. The portfolio’s variance is:
This is a convex quadratic in . Set its derivative to zero: , so .
Put 69% in asset 1 and 31% in asset 2. Variance: , so risk — lower than either asset alone. That’s diversification, made exact.
With assets, a target return and a no-short-selling rule, it becomes:
where is the covariance matrix and the expected returns. It’s a convex QP, and solvers handle thousands of assets. The weakness is the input: expected returns are notoriously hard to estimate, and the optimiser magnifies the errors.
6. How solvers work, briefly
- Unconstrained: gradient descent steps downhill, . Newton’s method uses second derivatives to jump towards the bottom of a local quadratic approximation, converging much faster near the optimum. Quasi-Newton methods (BFGS) approximate the second derivatives cheaply. → numerical optimisation
- Constrained: sequential quadratic programming (SQP) repeatedly solves a QP approximation of the problem. Interior-point methods (the same family as note 04’s) handle large convex problems.
- Non-convex, global: multistart (run a local method from many starting points), or spatial branch and bound, which works like note 07 but branches on continuous variables.
Worked example — KKT with SciPy
Runnable. SciPy 1.0+.
# kkt.py — note 09: minimise (x-3)^2 + (y-2)^2 subject to x + y <= 4
from scipy.optimize import minimize
f = lambda v: (v[0] - 3) ** 2 + (v[1] - 2) ** 2
cons = [{"type": "ineq", "fun": lambda v: 4 - v[0] - v[1]}] # scipy wants g(v) >= 0
res = minimize(f, x0=[0, 0], constraints=cons, method="SLSQP")
print("x, y =", res.x.round(4), " objective =", round(res.fun, 4))uv run --with scipy python kkt.pyExpected output:
x, y = [2.5 1.5] objective = 0.5
Notice the sign convention: SciPy’s "ineq" means fun(v) >= 0, the opposite of this note’s . Getting it backwards silently solves a different problem — always check the answer is feasible.
Common pitfalls and traps
- Trusting a local optimum on a non-convex problem. Run from several starting points. If they disagree, you’ve learned something important.
- Nonlinear equality constraints. They make the region non-convex in general, even if everything else is convex.
- Bad scaling. Variables in millions alongside variables in thousandths make gradient methods crawl. Rescale so all variables are roughly of order 1.
- Treating a Lagrange multiplier as valid far from the optimum. Like a shadow price, it’s a local rate.
- Non-smooth objectives. and have kinks where the gradient doesn’t exist, which confuses gradient-based solvers. Use note 02’s tricks to make them linear constraints instead.
Check your understanding
- Is convex? (Hint: try and .)
- In the fence problem, the farmer is given 44 metres instead of 40. Estimate the new area using , then compute it exactly.
- In the KKT example, what would happen if the constraint were ?
- Why does the two-asset portfolio have less risk than either asset alone? Would that still be true if the two assets were perfectly correlated?
After your attempt — answers
- Yes. Along : . Along : . Both bowl upward; in general its Hessian has eigenvalues 1 and 3, both positive, so it’s convex.
- Estimate: m². Exact: an 11 × 11 square, 121 m². The multiplier is a local rate, so it slightly underestimates a 4-metre change.
- The unconstrained optimum has , so it’s feasible. The constraint is slack, by complementary slackness, and the answer is with objective 0.
- When one asset has a bad year, the other often doesn’t, so losses partly cancel. With perfect positive correlation they rise and fall together; the portfolio’s risk is then just the weighted average of the two, , which is never below 20%. The diversification benefit comes entirely from imperfect correlation.
Practice — independent task
- Predict, then solve: the farmer’s pen is against a wall, so only three sides need fencing: s.t. . Solve it with a Lagrange multiplier by hand, then check with
minimize(maximise by minimising ). - Apply — a three-asset portfolio. Expected returns 8%, 12%, 15%; risks 15%, 20%, 30%; correlations , , . Build the covariance matrix (), and use
minimizeto find the minimum-variance portfolio with no short selling, then the minimum-variance portfolio with expected return at least 12%. - Explain: for part 2, which constraints are binding at each answer, and what does that say about the trade-off between risk and return?
Done when: part 1 matches by hand and by code; part 2 gives weights summing to 1, all non-negative, meeting the return target, and you can name the binding constraints.
Answer to part 1 — after your attempt
, so , . Then , : , , area 200 m². The wall doubles the area — and each extra metre of fence is now worth 10 m².
Before moving on
You’re ready when you can say whether a problem is convex and why it matters, solve a two-variable Lagrange problem and interpret , and check the four KKT conditions at a given point.
Recap:
- Convexity, not linearity, is what makes optimisation reliable: in a convex problem every local optimum is global.
- Lagrange: at an equality-constrained optimum, the gradients are parallel, and the multiplier is the shadow price.
- KKT: stationarity, feasibility, , complementary slackness. Sufficient for convex problems.
- Portfolios are convex QPs; diversification falls out of the maths.
Next: Heuristics and Metaheuristics — what to do when no method can promise the optimum in reasonable time.
Related
- Numerical optimisation — the algorithms in depth
- Duality and Sensitivity — the linear version of multipliers
- Optimal control and LQR — quadratic optimisation over time
- AI and machine learning — training a model is (usually non-convex) nonlinear optimisation
- Operations research map
Software engineering
Infrastructure & security
Computer science
Hardware & engineering