Duality Primal and Dual

Understanding duality unlocks the reason SVMs work the way they do and why kernels can plug in so elegantly. It is also the foundation for understanding constrained optimisation, which appears throughout machine learning. Once you see the primal and the dual as two views of the same problem, you will recognise the pattern whenever a model is trained with constraints — from regularisation to support vector machines. This concept is also the stepping stone to the KKT conditions, which describe exactly when a constrained optimum is found. Master this and you will be ready for the next topics in your library: Convex Optimisation, Lagrange Multipliers, and Linear Programming.

Imagine you are trying to find the cheapest flight from Delhi to Mumbai. You have a list of airlines, each with different prices and different baggage allowances. Your goal is to minimise the price, subject to the constraint that you can carry at least 20 kg of luggage. Now, an airline might offer a price that is low but with only 15 kg allowed — that is not allowed. Another airline might allow 30 kg but charge a lot. You search through all the options and find the cheapest fare that still allows at least 20 kg. That is your answer: say, ₹4,200.

Now consider a different question: what is the maximum amount you would be willing to pay for one extra kilogram of baggage allowance? If you could carry 21 kg instead of 20, would you pay ₹50 more? ₹200 more? The value of that extra kilogram is called the shadow price of the baggage constraint. In this example, the shadow price is the maximum you'd pay for one extra kg. If the shadow price is ₹100, then the airline could charge you up to ₹100 for the 21st kg and you'd still take it.

The duality idea connects these two questions. The original problem — find the cheapest flight with at least 20 kg — is called the primal. The second question — what is the maximum value of relaxing the constraint — is the dual. The key insight is that the answer to the dual always gives a lower bound on the primal. In other words, the maximum you'd pay for extra allowance is never more than the actual price you pay. This is weak duality. In some cases, the two numbers are exactly equal: the cheapest price equals the maximum shadow price. That is strong duality, and it's the special case that makes duality so powerful.

Now extend this to a real optimisation problem. Suppose you have a function f(x) you want to minimise, but only among x that satisfies some constraints. The primal asks: what is the minimum value of f(x) subject to the constraints? The dual asks a related question: how much would the minimum change if you relaxed each constraint? This turns out to be a different optimisation problem, but its optimal value is always a lower bound on the primal's optimal value. For a large class of problems, the two are equal — and that equality is what allows you to solve the easier one and get the answer to the harder one.

Think of a government trying to set a tax on polluting factories. Each factory wants to minimise its own cost of production, but the government wants to limit total pollution to 100 units. The primal problem: choose production levels for each factory such that total pollution ≤ 100 and total production cost is minimised. The dual problem: the government asks, 'What is the maximum price we could set for one unit of pollution such that each factory would choose to reduce pollution rather than pay the tax?' That price is the shadow price of the pollution constraint.

If the government sets the tax too low, factories pollute more, and the dual's answer (the maximum tax that would still keep total pollution at 100) is below the minimum cost achievable under the constraint. If the tax is set exactly right, the total tax paid equals the extra cost of reducing pollution — the primal and dual optima coincide. That is strong duality.

The analogy breaks down because in real optimisation, constraints are often not linear and variables can be continuous, but the core idea — the dual is a pricing problem — holds. Note that in the taxi example, the dual is a different optimisation problem, not just a single number. The government is optimising over the tax rate; that optimisation is the dual.

Every optimisation problem (the primal) has a companion optimisation problem (the dual) whose optimal value provides a bound on the primal's optimal value; under strong duality, the two optima are equal.

The learner's library notes on Lagrange Multipliers and KKT Conditions are the natural neighbours here. Lagrange multipliers introduce the idea of folding constraints into the objective with multipliers; those multipliers are exactly the dual variables. The KKT conditions describe the conditions under which a solution is optimal, and complementary slackness says that a constraint is either tight or its multiplier is zero — that is a duality statement. Linear programming has a famous dual, and the simplex method works because of duality. Convex optimisation is where strong duality holds most often, which is why duality is so useful there. Note that deep learning is nonconvex, so strong duality rarely holds in that setting — duality is more useful in traditional machine learning models like SVMs and linear programming.