Constraints, Lagrange Multipliers, and Duality

Unconstrained optimization asks which point minimizes f(x). Constrained optimization asks the same question over a feasible set defined by equalities, inequalities, or structural rules. The first famous instance of it in economics was a shopping list.

In 1945 George J. Stigler minimised the annual cost of food over 77 commodities, subject to nine daily nutrient allowances from the National Research Council: 3,000 calories, 70 g protein, 0.8 g calcium, 12 mg iron, 5,000 IU vitamin A, 1.8 mg thiamine, 2.7 mg riboflavin, 18 mg niacin, and 75 mg ascorbic acid. The objective was explicit. The feasible set was explicit. What Stigler did not have was a method, and he said so: “Thereafter the procedure is experimental because there does not appear to be any direct method of finding the minimum of a linear function subject to linear conditions.”

So he cut the 77 eligible foods to 15 by hand, then to 9, and reached $39.93 a year at August 1939 prices from five foods — wheat flour, evaporated milk, cabbage, spinach and dried navy beans. George B. Dantzig, writing in 1990, described exactly what that number was and was not: “since there was no technique that he was aware of to solve it, he invented a very clever heuristic to arrive at a diet that cost only $39.93 per year (1939 prices). He did not claim it to be the cheapest solution but gave good reasons for believing that the annual cost could not be reduced much.”

In machine learning the constraints encode budgets, fairness tolerances, probability-simplex requirements, physical laws or resource limits instead of calories and milligrams. The difficulty is the one Stigler met. Improving the objective may point straight out of the feasible set, so optimality has to balance objective descent against constraint geometry.

Each method enforces feasibility differently. A hard constraint optimizes directly over the feasible set. It preserves the stated rule exactly when the problem is solved, but may require specialized algorithms, and feasibility can be difficult to maintain — the right trade when violations are unacceptable. A penalty adds a cost for violation. It is easy to bolt onto an existing objective, but finite weights may still allow violations, large weights can worsen conditioning, and the whole approach needs a meaningful tradeoff scale. A barrier makes the objective diverge near a forbidden boundary. It keeps iterates in the interior, needs a feasible interior start in its common forms, and approaches the boundary only indirectly. A projection takes an ordinary update and maps it back to the feasible set. That is intuitive for simple convex sets, possibly expensive, and it changes the effective step direction, which is what projected gradient methods live with.

The barrier is not a fallback for problems too awkward to constrain properly. It turned out to be the same object as the most celebrated interior-point method. Narendra Karmarkar's 1984 linear-programming algorithm required O(n^3.5 L) arithmetic operations, a factor of O(n^2.5) better than the ellipsoid method. Margaret H. Wright reports the claim that made it famous: “In 1984, Narendra Karmarkar [21] announced a polynomial-time LP method for which he reported solution times that were consistently 50 times faster than the simplex method.”

Then the equivalence. Wright records that “it was shown in 1985 (and published the next year [15]) that there was a formal equivalence between Karmarkar's method and the classical logarithmic barrier method applied to the LP problem”, the barrier being B(x,μ) = f(x) − μ Σ ln c_j(x). Wright and four colleagues had proved it, in a 1986 paper whose abstract states: “This method is shown to be equivalent to Karmarkar's projective method for a particular choice of the barrier parameter.” Their implementation was also tested against the state-of-the-art simplex code MINOS, where, in Wright's summary, “the barrier method was faster on several of the problems and competitive on many others.”

Two enforcement mechanisms that look unrelated on a slide can be the same algorithm with one parameter set differently.

For an equality constraint h(x)=0, the Lagrangian is L(x,λ)=f(x)+λh(x). At a regular optimum, ∇f and ∇h balance through λ, and under suitable conditions λ also measures how the optimal value changes when the constraint boundary is relaxed. That sensitivity reading is why multipliers are called shadow prices. In at least one market the shadow price is not a metaphor. It is the number on the invoice.

Texas generation is dispatched by the Electric Reliability Council of Texas through Security Constrained Economic Dispatch. ERCOT's Business Practice for that dispatch defines the energy component of every price this way: “System Lambda, i.e. the Shadow Price for the Power Balance constraint, is equal to the change in the SCED objective function obtained by relaxing the Power Balance constraint by 1MW.” The same document states that “The maximum Shadow Prices for the transmission network constraints and the power balance constraint directly determine the Locational Marginal Prices (LMP) for the ERCOT Real Time Market in the cases of constraint violations”, and that the Power Balance Penalty “sets the maximum limit for this Shadow Price”.

That last clause is the interesting one, because a capped multiplier is a multiplier that has stopped measuring. The ceiling tracks the system-wide offer cap set by PUCT rule (16 TAC § 25.505(g)(6)), which was $9,000/MWh at the time of Winter Storm Uri. During the storm the Public Utility Commission of Texas ordered ERCOT to suspend the Low System-Wide Offer Cap and “continue to use the $9,000/MWh High System-Wide Offer Cap (HCAP) as the System-Wide Offer Cap”. It separately ordered that real-time prices account for firm load shed in EEA3, a system change ERCOT implemented effective at the 22:15 SCED interval on 15 February 2021.

Potomac Economics, the Independent Market Monitor for the ERCOT wholesale market, explained the intent in May 2022: “When supply shortages prevent ERCOT from serving the load, prices should reflect the 'value of lost load' (VOLL) of $9,000 per MWh, which is also the system-wide offer cap”. It also recorded what happened when the shortage ended: “Transmission operators received the recall of the last of the firm load shed instructions just before midnight on February 17, but prices were held at the VOLL of $9,000 per MWh through mid-morning on February 19”. Earlier in the event prices had dipped “as low as approximately $1,200 per MWh on February 16, 2021”, and across 2021 intervals at or near the $9,000 cap totalled roughly 98 hours.

For a day and a half, the shadow price of the power-balance constraint was set by order rather than by the constraint it is defined to measure. That is the general lesson about multipliers as sensitivities. They report the value of relaxing a constraint only while the model, and the administrative machinery around it, actually lets the constraint speak.

Suppose weights wᵢ must be nonnegative and sum to one. Projecting onto that set is not a hand-wave. It is a constrained optimization problem with a closed-form answer, and the answer comes straight out of the KKT conditions.

Written down, the projection is this: minimise ½‖w − v‖² subject to Σ w_i = z and w_i ≥ 0. Duchi and three co-authors set out the Lagrangian in 2008 as L(w,ζ) = ½‖w − v‖² + θ(Σ w_i − z) − ζ·w — one multiplier θ for the equality, a nonnegative vector ζ for the bounds. The derivation then turns on one sentence: “The complementary slackness KKT condition implies that whenever wi > 0 we must have that ζi = 0.”

That is the whole argument. The output rule “w s.t. w_i = max{v_i − θ, 0}” follows, and it returns exact zeros on the boundary. Their abstract gives the cost: “The first performs exact projection in O(n) expected time, where n is the dimension of the space. The second works on vectors k of whose elements are perturbed outside the ℓ1-ball, projecting in O(k log(n)) time”. It also reports that “variants of stochastic gradient projection methods augmented with our efficient projection procedures outperform interior point methods, which are considered state-of-the-art optimization techniques.”

The problem has kept attracting exact solvers. In 2016 Laurent Condat reported another: “A new algorithm is proposed to project, exactly and in finite time, a vector of arbitrary size onto a simplex or an l1-norm ball.”

Start with the real rule before choosing a mathematical enforcement mechanism. First, state the rule: what must never happen, and what may trade off. The National Research Council allowances were the rule; the price of food was the objective. Second, write the feasible set: express the equality, inequality, discrete or probabilistic constraints explicitly, as 9 equations in 77 unknowns or as Σ w_i = z with w_i ≥ 0. Third, check geometry: convexity, smoothness, and whether projection is tractable. Exact projection onto the simplex costs O(n) expected time; other feasible sets have no closed form at all. Fourth, choose enforcement: direct constraints, reparameterization, penalties, barriers or projections — remembering that a barrier and an interior-point method can be the same algorithm under two names. Fifth, validate violations: report both objective quality and actual constraint satisfaction across slices, never a single blended loss.

The 1947 diet optimum met all nine allowances but ran a surplus in four of them, which is information a combined score would have destroyed. A real-time price pinned at $9,000/MWh for a day and a half after the last firm load-shed instruction was recalled is the same kind of fact. No objective value will ever reveal it.

At a smooth constrained optimum, the objective cannot improve along any feasible local direction. Draw the objective contours, with lower contours marking preferred values of f. Draw the feasible set, which removes otherwise attractive points. Find the best reachable contour, the one that meets the feasible boundary. Then compare normals, because the objective and active-constraint gradients balance there. The phrase carrying the weight is active: only the constraints that touch the optimum have nonzero multipliers, and the rest are slack.

Stigler's diet is where that became visible in numbers. George B. Dantzig's own account, from 1990: “In the fall of 1947, Jack Laderman of the Mathematical Tables Project of the National Bureau of Standards undertook as a test of the newly proposed simplex method the determination of a least cost adequate diet based on Stigler's data. It was the first 'large scale' computation in the field. The system consisted of 9 equations in 77 unknowns.” The cost of walking the boundary of that feasible set by hand: “Using hand-operated desk calculators (this was in the days before computers), the nine clerks took approximately 120 man days to obtain an optimal solution of $39.69.”

The same arithmetic was re-derived independently. Garille and Gass, revisiting the problem in 2001, report it as “In 1947, nine clerks, using hand-operated desk calculators, pivoted away for 120 clerk-days and found the linear-programming (LP) minimum cost of $39.69 (daily cost of $0.1087).” — against “Stigler's diet for 1939 data cost $39.93 per year (daily cost of $0.1093)”.

So Stigler's heuristic was 24 cents a year above the true constrained minimum, and proving that took 120 man-days. The optimum used five foods: wheat flour (299 lb, $10.78), dried navy beans (378 lb, $22.29), cabbage (111 lb, $4.10), spinach (23 lb, $1.83) and beef liver (2.57 lb, $0.69). Stigler's own five, except that a sliver of beef liver displaced his 57 cans of evaporated milk. And the solution ran a surplus in niacin, thiamine, protein and iron, which means fewer than nine of the nutrient constraints actually bound. Nine constraints were stated. Only some of them shaped the answer.