Constrained Optimization
Constrained Optimization · Finding the best option within conditions you must meet
In real-world decisions, maximizing profit or minimizing cost isn’t enough on its own, because there are conditions you must meet, such as a budget, production capacity, safety standards, or minimum quality. In Ch. 06, we saw that a single cap on ad spending was enough to change the optimal solution. In this lesson, we look at how to handle constraints systematically.
What is constrained optimization?
Constrained optimization maximizes or minimizes an objective function while satisfying the given constraints at the same time. For example, even when a company wants to maximize production profit, production costs can’t exceed the budget, output can’t exceed equipment capacity, and quality has to meet a set standard. The key is to express these conditions mathematically and find the best solution within the range that satisfies them.
Objective function and constraints
| Symbol | Meaning |
|---|---|
| x | Decision variables |
| f(x) | The objective function to minimize or maximize |
| gᵢ(x) | Inequality constraints |
| hⱼ(x) | Equality constraints |
| m, p | Numbers of inequality and equality constraints |
A condition that the budget be $2,000 or less is an inequality constraint; if the budgets assigned to two projects must add up to exactly $2,000, that’s an equality constraint. A maximization problem can be turned into a minimization problem by multiplying the objective function by −1, so it can be handled in the same framework.
Example: maximizing ad effectiveness within a budget
Suppose a company is splitting a total budget of 6 units between search ads (x) and social media ads (y). The ad effectiveness function is a simplified, hypothetical model.
In this model, effectiveness grows as ad spending grows, but by less and less. Without constraints, you take the partial derivative with respect to each variable and set it to 0.
But the two budgets add up to 9, over the limit of 6, so this can’t be carried out. We need to find the optimum again with the constraint taken into account.
The method of Lagrange multipliers
The method of Lagrange multipliers combines the objective function and an equality constraint g(x) = 0 into a single function.
λ is the Lagrange multiplier. Solving these conditions gives candidate points that satisfy the constraint. In the ad example, the unconstrained optimum went over budget, so we look on the boundary where the whole budget is spent, x + y = 6.
10 − 2x − λ = 0, 8 − 2y − λ = 0, x + y = 6
x = 3.5, y = 2.5, λ = 3, R(3.5, 2.5) = 35 + 20 − 12.25 − 6.25 = 36.5
Subtracting the two partial-derivative conditions gives 2 − 2x + 2y = 0, that is, x − y = 1, and solving this together with x + y = 6 gives the solution above. Numerical optimization (SLSQP) confirmed the same solution, (3.5, 2.5), and 36.5.
Figure 1 shows contours joining points of equal ad effectiveness. The contours are centered on (5, 4), and effectiveness drops as you move outward. The highest contour inside the feasible region (green) is R = 36.5, which just touches the budget line, and at that point of contact the gradient of the objective function, ∇R = (3, 3), is parallel to the budget line’s normal (1, 1). The constant of proportionality is exactly λ = 3. Because the objective function in this problem is concave and the constraint is linear, this candidate point is the global optimum. In general, you need to check the properties of the objective function and constraints further to know whether a candidate from the Lagrange conditions is actually optimal.
KKT conditions
Lagrange multipliers are useful for equality constraints, but in reality the budget only has to be 6 or less; you don’t have to spend all of it. The KKT (Karush–Kuhn–Tucker) conditions handle inequality constraints systematically. For the minimization problem min f(x) s.t. gi(x) ≤ 0, the following four must hold.
| Condition | Formula | Meaning | Check in the ad example |
|---|---|---|---|
| ① Stationarity | ∇f(x) + Σ λᵢ∇gᵢ(x) = 0 | The gradients of the objective and the constraints balance | (−3, −3) + 3·(1, 1) = 0 ✓ |
| ② Primal feasibility | gᵢ(x) ≤ 0 | The original constraints are satisfied | 3.5 + 2.5 − 6 = 0 ≤ 0 ✓ |
| ③ Dual feasibility | λᵢ ≥ 0 | Sign condition on the inequality multipliers | λ = 3 ≥ 0 ✓ |
| ④ Complementary slackness | λᵢ gᵢ(x) = 0 | Whether the constraint actually limits the solution | 3 × 0 = 0 ✓ |
Rewriting the example in minimization form gives f = −R and g = x + y − 6, so ∇f = (−3, −3). The nonnegativity conditions x, y ≥ 0 have slack, so their multipliers are 0. The complementary slackness condition λigi(x) = 0 means that, for each constraint, one of the following holds.
If a constraint has strict slack at the optimum (gᵢ < 0), its multiplier is 0.
If λᵢ > 0, that constraint holds with equality at the boundary (it’s active).
Under suitable differentiability conditions, the KKT conditions are necessary conditions for an optimum. In convex optimization problems, if a regularity condition (e.g., Slater’s condition) is met, the KKT conditions become a powerful test for identifying the global optimum. In nonconvex problems, a point can satisfy the KKT conditions and still not be the global optimum (Ch. 06, Figure 3).
Active and inactive constraints
An active constraint is one that holds with equality at the optimum, and an inactive constraint is one that still has slack at the optimum.
On the left of Figure 2, with a budget of 6, the unconstrained optimum (5, 4) lies outside the feasible region, so the solution is pushed onto the budget line at (3.5, 2.5). The budget constraint is active and λ = 3. On the right, with a budget of 10, (5, 4) lies inside the feasible region and is optimal with 1 unit of budget left over, so the constraint is inactive and λ = 0. Under the standard KKT conditions, an inactive constraint’s multiplier is 0; conversely, an active constraint’s multiplier isn’t necessarily positive (with a budget of exactly 9, the constraint is active but λ = 0).
What does the Lagrange multiplier mean?
With everything else held fixed and within the range where sensitivity analysis applies, the Lagrange multiplier tells you how much the objective value changes when you change the right-hand side of the constraint slightly. It’s interpreted as a shadow price, or marginal value (the same concept as the dual price in Ch. 03).
Figure 3 shows the optimal ad effectiveness R* re-solved as the budget B changes. For 1 ≤ B < 9, the solution is x = (B + 1)/2, y = (B − 1)/2, and λ = 9 − B. At a budget of 6 the tangent slope is λ = 3, so increasing the budget very slightly raises effectiveness by about 3 per unit. In fact, raising the budget to 7 gives R* = 39, an increase of 2.5, a bit less than the 3 predicted by λ because the marginal value falls from 3 to 2 as the budget grows. The multiplier is an approximation for small changes, and once the budget exceeds 9 the constraint becomes inactive and extra budget is worth 0. The sign and interpretation of the multiplier can depend on whether you’re maximizing or minimizing and on which way the constraint is written.
Where constrained optimization is used
| Field | Example constraints |
|---|---|
| Production management | Production capacity, raw materials, working hours |
| Finance | Portfolio weights, risk limits, capital constraints |
| Marketing | Total budget, minimum · maximum spending per channel |
| Logistics | Vehicle capacity, delivery times, meeting demand |
| Engineering | Safety standards, design limits, performance requirements |
| Energy | Generation ranges, meeting demand, operating limits |
The point of constrained optimization isn’t simply to find the largest or smallest value; it’s to find the best choice within the conditions you actually have to meet.
Assuming ad effectiveness R(x, y) = 10x + 8y − x² − y², the optimal allocation was found subject to a total budget of 6 or less. The unconstrained optimum (5, 4) required a budget of 9 and could not be carried out; the optimal allocation found with Lagrange multipliers was 3.5 for search ads and 2.5 for social media ads (R = 36.5). All KKT conditions were satisfied, and the budget constraint’s multiplier was λ = 3, so a small budget increase is expected to raise effectiveness by about 3 per unit.
At the optimum, the gradient of the objective balances the gradients of the active constraints, and the ratio is the value of the constraint.
- Constrained optimization: Optimizes an objective function while satisfying equality and inequality constraints.
- Lagrange multipliers: Combine equality constraints with the objective function to find candidate optima.
- KKT conditions: Stationarity, primal · dual feasibility, and complementary slackness sum up optimality for problems with inequality constraints.
- Active · inactive: An active constraint is one that’s at its boundary at the optimum; an inactive constraint has slack left and a multiplier of 0.
- Shadow price: The Lagrange multiplier is the rate of change of the objective value when the constraint is relaxed slightly; for large changes it’s only an approximation.
Up next: 08 Multi-Objective Optimization. We’ll look at how to find a good alternative among several conflicting goals, such as cost and quality, or efficiency and risk.