# Duality Primal and Dual

Every optimisation problem has a dual whose optimum bounds the original.

**Rests on:** Lagrange Multipliers

**Leads to:** KKT Conditions

*Mathematical Foundations · Optimization*


## Why learn this

Imagine you are planning a road trip with a strict budget and a set of destinations you must visit. You want the fastest route, but you cannot spend more than $500 on gas and hotels. Solving this directly can be messy because every choice affects your remaining budget in complex ways. Duality gives you a different way to look at the same trip. Instead of trying to find the best route first, you assign a 'price' to every rule—like how much extra time it would cost to add one more stop to your list or how much your travel time would improve if your budget were $10 larger. These prices tell you the value of each constraint. Often, calculating these values is much easier than finding the exact route. Once you have these 'shadow prices,' they act as a reliable lower bound for the true cost. If the price of relaxing your constraints matches the cheapest possible trip, you know you have found the perfect solution. This technique is why systems that recommend flights, allocate factory resources, or train artificial intelligence models can find answers quickly and accurately.


## The intuition

Imagine you are trying to book a flight from Delhi to Mumbai for business. You need to get there by Friday afternoon. Your goal is to find the cheapest ticket price possible, but there is a rule: the total weight of your luggage, including checked bags, must be at least 20 kg because you have heavy prototypes to deliver. 

You look at several options. Airline A charges ₹4,000 but only allows 15 kg (too light). Airline B charges ₹6,000 and allows 30 kg (valid, but expensive). You search through the database and find the best valid option: a ticket for exactly 20 kg of luggage at a price of ₹4,200. This ₹4,200 is your minimum cost under the rule.

Now, let's look at this from the perspective of the rule itself. Ask yourself this question: How much more would you 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? Or ₹200 more? Let's say the answer is ₹100. This means the 'value' of that extra kilogram to your specific situation is ₹100. In optimization terms, this value is called the shadow price of the baggage constraint.

Here is the key insight: The shadow price (₹100) tells you how much the total cost would change if the rule changed slightly. But more importantly, it provides a check on your work. The original problem—finding the cheapest flight with at least 20 kg—is called the primal problem. The second question—calculating the value of relaxing that constraint—is called the dual problem.

The principle of weak duality states that the value derived from the dual perspective will never overestimate the true cost. In our example, if you calculated a shadow price that suggested your trip should only cost ₹3,000, you would know something is wrong, because you already found a valid ticket for ₹4,200. The dual provides a lower bound; it sets a floor. 

In many cases, particularly when the problem is 'well-behaved' (a property known as convexity), the two numbers meet exactly. This is strong duality. It means the minimum cost of the trip (₹4,200) is mathematically equal to the maximum value you place on relaxing the constraint. When this happens, solving the dual problem gives you the exact answer to the primal problem, often with far less computational effort.


## An analogy

Think of a city council deciding how to allocate a limited water supply among three districts during a drought. The council wants to minimize the total economic loss caused by water rationing, subject to the rule that the total water distributed must equal exactly 100 million gallons.

The primal problem asks: 'How much water should District A, B, and C get to minimize total loss?' This is hard to answer directly because you don't know how much each district values the water.

The dual problem flips the perspective. It asks: 'What price per gallon for water would cause each district to voluntarily request exactly their fair share, summing to 100 million gallons?' The council sets a price (the dual variable). If the price is too low, districts hoard water (demand exceeds supply). If the price is too high, they conserve too much (supply exceeds demand). The optimal dual solution is the exact price that balances supply and demand.

The analogy holds because finding the right price (dual) often requires fewer calculations than figuring out each district's specific needs (primal). When the market clears at the right price, the total loss in the primal view equals the revenue in the dual view. This equality is strong duality. The caveat is that real-world districts might have complex, non-linear pain curves for water shortages, whereas simple mathematical models assume straight-line relationships; however, the core logic of pricing constraints remains valid.


## Definition

For every optimization problem seeking to minimize cost under constraints (the primal), there exists a corresponding problem that maximizes the value of relaxing those constraints (the dual). The optimal value of the dual always provides a lower bound on the optimal value of the primal, and under specific conditions known as strong duality, the two values are equal.


## How it connects

This concept sits directly beside Linear Programming, which is the study of optimizing linear objectives subject to linear constraints, where every problem has a corresponding dual. It also connects closely with Lagrange Multipliers, which are the mathematical tools used to calculate the dual variables (shadow prices) by incorporating constraints into the objective function.


## The mathematics

This concept draws on the branch of mathematics called optimisation. Optimisation is about finding the best value of something (like minimum cost or maximum profit) subject to rules. Before we get to duality, we need to understand the idea of a function and a constraint. A function is a rule that takes an input and gives an output. For example, the cost of a flight is a function of the airline and the time you book. A constraint is a rule that limits what input you can choose — you need at least 20 kg of baggage, or you cannot spend more than ₹5,000.

The primal problem is: find the input that makes the function as small (or large) as possible, while also satisfying all the constraints. The dual problem is built from the constraints. For each constraint, we imagine a price (a multiplier) that we would be willing to pay to relax that constraint by one unit. The dual problem asks: what is the maximum total price we could charge such that the function plus the priced constraints is still minimised? 

The dual's optimal value always gives a lower bound on the primal's optimal value (if the primal is a minimisation). This is called weak duality. In many practical problems, the two are equal; that is strong duality.

Now, let's put numbers to this. Consider a simple linear function: minimise 2x + 3y, subject to x + y ≥ 4 and x, y ≥ 0. The primal seeks the smallest value of 2x + 3y that satisfies the constraint.

The dual introduces a multiplier (call it λ) for the constraint x + y ≥ 4. The dual maximises something related to λ, specifically 4λ, but subject to constraints that the multipliers must satisfy: 2 – λ ≥ 0 and 3 – λ ≥ 0. This means λ ≤ 2 and λ ≤ 3, so the maximum λ is 2. Thus the dual's optimal value is 4 × 2 = 8.

In the primal, the minimum of 2x + 3y subject to x + y ≥ 4 is achieved at x = 4, y = 0, giving 8. So here the primal optimum equals the dual optimum: strong duality holds.

Primal (minimisation): min_x f(x) subject to g_i(x) ≤ 0 for i = 1..m.
Dual: max_{λ ≥ 0} L(λ) = min_x [ f(x) + Σ λ_i g_i(x) ].
Here λ_i are the dual variables (shadow prices). Weak duality: d* ≤ p* (for minimisation primal). Strong duality: d* = p*.
Symbol glossary: x is the variable vector; f(x) is the objective function to minimise; g_i(x) are the constraint functions (each must be ≤ 0); λ_i are the dual variables (nonnegative); L(λ) is the dual function; p* is the primal optimum; d* is the dual optimum.


## A worked example

```
Minimise f(x, y) = 2x + 3y subject to x + y ≥ 4 and x, y ≥ 0. (We'll see that the minimum is 8.)

Step 1: Try x = 0, y = 4: f = 2*0 + 3*4 = 12. Constraint: 0+4 ≥ 4 ok.   # A candidate point. f is 12.
Step 2: Try x = 4, y = 0: f = 2*4 + 3*0 = 8. Constraint: 4+0 ≥ 4 ok.   # Better, f is 8.
Step 3: Try x = 2, y = 2: f = 2*2 + 3*2 = 10. Constraint: 2+2 ≥ 4 ok.   # f is 10, worse than 8.
Step 4: The minimum seems to be 8, at (4,0) or (0,4)? Actually at (4,0) gives 8; at any point with x+y=4, f = 2x + 3(4-x) = 12 - x, which decreases as x increases, so the minimum is at x=4, y=0, f=8.   # Analysing the boundary.

Result: The primal optimum is 8, achieved at x=4, y=0.
```


## From scratch, in Python

```python

# Let's solve a tiny primal problem by hand and then compute the dual.
# Primal: minimise 2x + 3y subject to x + y >= 4 and x >= 0, y >= 0.

# The primal optimum we found is 8.
primal_value = 8

# Now compute the dual: maximise 4*lambda subject to 2 - lambda >= 0 and 3 - lambda >= 0.
best_dual = 0
best_lambda = 0
# Try all lambda from 0 to 3 in steps of 0.1
lambda_val = 0.0
while lambda_val <= 3.0:
    # Check constraints
    if (2 - lambda_val >= 0) and (3 - lambda_val >= 0):
        dual_value = 4 * lambda_val
        if dual_value > best_dual:
            best_dual = dual_value
            best_lambda = lambda_val
    lambda_val += 0.1

print("Primal optimum:", primal_value)
print("Best lambda found:", best_lambda)
print("Dual optimum (approx):", best_dual)

```


## What the code does

This code does a brute-force search over the dual variable λ. The primal is solved by reasoning, which we did by hand. The dual is maximised by trying all λ values from 0 to 3 in steps of 0.1, checking that the constraints 2 - λ ≥ 0 and 3 - λ ≥ 0 hold. For each feasible λ, we compute 4λ. The maximum found is at λ = 2, giving 8, which matches the primal. This demonstrates strong duality in a simple case.


## Common misconceptions

**Duality is only for linear programming** — I thought duality only applies to linear programming, not other optimisation problems.

Duality is a general concept in optimisation. Any optimisation problem with constraints has a dual, though the dual may be hard to solve. Linear programming is just one special case where the dual takes a nice form. In fact: Duality applies to any constrained optimisation problem. The dual is defined by taking the Lagrangian and minimising over the primal variables. The quality of the dual bound depends on convexity.

**Strong duality always holds** — If the primal has an optimum, the dual must have the same optimum.

Strong duality only holds under certain conditions, e.g., convexity and constraint qualification. In nonconvex problems, the dual may be strictly less than the primal, giving a gap. In fact: Weak duality always gives a bound; strong duality is special and must be verified.

**Dual variables are the same as Lagrange multipliers** — I thought dual variables are just another name for Lagrange multipliers, but they seem different.

They are the same concept in the context of constrained optimisation. Lagrange multipliers in the primal KKT conditions are exactly the dual variables. In fact: The dual variables are the Lagrange multipliers. Their values indicate the sensitivity of the optimum to the constraint.

**Solving the dual is always easier** — The whole point of the dual is to make the problem easier, so it is always simpler to solve than the primal.

Sometimes the dual is easier, sometimes not. In SVMs, the dual has only as many variables as the number of support vectors, which can be few. But in general, the dual may be just as hard. In fact: The dual is useful because it may be easier to solve or interpret, but it is not guaranteed to be easier.


## In short

Every optimisation problem has a companion called the dual. The primal looks for the best value subject to constraints; the dual prices the constraints. Weak duality always gives a bound: the dual optimum never exceeds the primal optimum (for minimisation). Strong duality, when the two are equal, is what makes the dual a reliable substitute. The dual variables are the shadow prices — the rate at which the optimum changes as you relax a constraint. In machine learning, SVMs are solved in the dual, which is what makes kernels work. Remember: weak duality is a guarantee; strong duality is a gift.


## Where this is used

In machine learning, duality appears most famously in Support Vector Machines (SVMs). The SVM training problem is usually written as a constrained optimisation: maximise the margin subject to the constraint that all points are correctly classified. That is the primal. Rather than solving the primal directly, practitioners solve the dual, which is a quadratic program in the dual variables (the multipliers). The dual formulation has a key benefit: the data points appear only in dot products with each other. This is what allows the kernel trick — you can replace those dot products with a kernel function and get a non-linear classifier without ever computing coordinates in the high-dimensional space. A developer using scikit-learn calls SVC(kernel='rbf') and the library solves the dual internally, using a solver like libsvm.

In large language models, duality is not directly used in the training loop (which is nonconvex gradient descent), but it appears in the theory of optimisation that underpins distributed training and in the analysis of convex subproblems. For example, federated learning sometimes uses dual methods to decouple the optimisation across devices. In small models running on phones, the model is trained once and deployed; the training might have used dual methods for certain layers, but inference does not.

In retrieval-augmented generation, the embedding and similarity machinery is based on dot products, which are also central to dual formulations. However, duality is not the mechanism there; it is more relevant to the training of the embedding models, which often involve contrastive losses that can be seen as constrained optimisation.

In agentic systems that plan and call tools, the planning can be framed as an optimisation problem — e.g., maximising expected reward subject to a token budget. Duality can be used to solve such constrained MDPs, providing a way to trade off reward and cost. A developer might use a library like CVXPY to solve the dual and get the optimal policy.

In everyday applied machine learning, duality shows up in regularised regression (ridge, lasso). The primal is the least-squares objective with a penalty; the dual involves the constraints on the residuals. Solving the dual can be more efficient when the number of features is huge. Tools like scikit-learn's Ridge and Lasso use coordinate descent or SVD, but the theory guarantees that the dual solution is equivalent.

What a developer actually writes: for SVMs, they write `svm.SVC(kernel='rbf')` and fit it; the underlying solver (e.g., libsvm) solves the dual. For linear programming, they might use `scipy.optimize.linprog` and specify the primal; the solver automatically handles the dual internally. If they write custom constrained optimisation, they might use CVXPY, where you define the primal problem and the library automatically constructs and solves the dual. What breaks when done badly: ignoring dual feasibility can lead to incorrect bounds; using a dual solver on a nonconvex problem may give garbage because strong duality does not hold.


---

Read this on the web: https://basavapurushottam.com/learn-ai/duality-primal-and-dual
