Primal & dual optimization

Imagine a marble that wants to reach \((2,2)\), but a wall says \(x+y\le 2\). The primal problem asks for the lowest point of the bowl that lies on the allowed side of the wall.

We measure how far the marble is from its preferred point with \[ f(x,y)=(x-2)^2+(y-2)^2. \] Each squared term measures miss-distance along one axis, so \(f\) is exactly squared Euclidean distance to \((2,2)\). Unconstrained, the answer is obviously \((2,2)\). With the rule, it is forbidden.

A direct primal technique is projected gradient descent: move downhill, then snap back to the nearest allowed point. That snap is called a projection.

In this special bowl, a step of size \(\eta=\tfrac12\) lands directly at \((2,2)\), because \[ \nabla f(x,y)=\bigl(2(x-2),\,2(y-2)\bigr) \] and therefore \((x,y)-\tfrac12\nabla f(x,y)=(2,2)\). Projecting that forbidden point onto \(x+y\le2\) gives \((1,1)\). Its cost is \[ p^\star=f(1,1)=(-1)^2+(-1)^2=2. \] The symbol \(p^\star\) means “the best primal value.”

Instead of physically forbidding \(x+y>2\), charge for it. Let \(g(x,y)=x+y-2\): it is positive beyond the wall, zero on the wall, and negative inside.

Multiply that signed rule value by a nonnegative price \(\lambda\), then add it to the original cost: \[ \underbrace{ \overbrace{L(x,y,\lambda)}^{-\infty\lt L\lt\infty} }_{\min_{(x,y)\in\mathbb R^2}} = \underbrace{ \overbrace{(x-2)^2+(y-2)^2}^{f(x,y)\ge0} }_{\min_{x,y}} + \underbrace{ \overbrace{\lambda}^{\lambda\ge0} }_{\max_{\lambda}\text{ later}} \underbrace{ \overbrace{(x+y-2)}^{-\infty\lt g(x,y)\lt\infty} }_{\text{require }g(x,y)\le0}. \] The product \(\lambda g(x,y)\) can lie anywhere in \(\mathbb R\), but it is always nonpositive at a feasible point because \(\lambda\ge0\) and \(g(x,y)\le0\). This combined score is the Lagrangian. The multiplier \(\lambda\) is not magic—it is simply the current unit price of pushing through the wall.

For a fixed price, the point behaves selfishly: it minimizes \(L\). Setting the two slopes to zero gives \[ \frac{\partial L}{\partial x}=2(x-2)+\lambda=0, \qquad \frac{\partial L}{\partial y}=2(y-2)+\lambda=0. \] So the price moves the bowl’s preferred point to \[ x(\lambda)=y(\lambda)=2-\frac{\lambda}{2}. \] At \(\lambda=0\), it ignores the rule and chooses \((2,2)\). At \(\lambda=2\), its selfish choice is exactly \((1,1)\), on the wall. A larger price over-corrects and pushes it farther inside.

Why an inequality price cannot be negative

For the rule \(g(x,y)\le0\), a valid dual price must satisfy \(\lambda\ge0\). Then every violation \(g>0\) receives a nonnegative charge \(\lambda g\), while every feasible point \(g\le0\) receives a nonpositive adjustment. A negative \(\lambda\) reverses both signs: it rewards violations and can raise the score of feasible points, destroying the lower-bound argument used by the dual.

The expression is not asking \(\lambda\), \(x\), and \(y\) to move at once. It describes a nested game: \[ \underbrace{\max_{\lambda\ge0}}_{\text{compare prices second}} \left[ \underbrace{\min_{(x,y)\in\mathbb R^2} L(x,y,\lambda)}_{\text{point best-responds first}} \right]. \] The operator closest to \(L\) acts first. Freeze one price \(\lambda\); let \((x,y)\) find the cheapest possible response; record that one number as \(q(\lambda)\). Repeat for other prices. Only then keep the largest recorded number.

The left view is still a problem with only two decision variables: horizontal position is \((x,y)\), and the added height is the score \(L(x,y,\lambda)\). Rendering that score as a third visual dimension turns “minimize \(L\)” into the literal act of finding the bottom of a bowl.

The right-hand plot is not a different problem or an approximation. It is the exact slice of the 2D Lagrangian along the dashed diagonal \(x=y=t\). Symmetry forces the best response to lie on that diagonal, so the minimum of the 1D slice is the same point and the same height as the minimum of the full 2D bowl. The dashed turquoise curve is the original cost \(f(t,t)\); the gold curve is \(L(t,t,\lambda)\). At the default active law \(x+y\le2\) and \(\lambda=3\), the response is \(t=0.5\), so \(g=-1\). The vertical drop shows the resulting rebate: \(f=4.5\), \(\lambda g=-3\), and \(L=4.5-3=1.5\). Switch to \(x+y\le5\) to see the opposite case: \((2,2)\) is already legal, so the best dual price is \(\lambda=0\).

Why maximize over the price?

First, \(\lambda\) is not itself a cost and the dual does not try to make \(\lambda\) numerically large. The product \(\lambda g(x,y)\) is the cost adjustment: \(\lambda\) says how many units of objective value one unit of rule violation is worth. The actual outer objective is \[ \max_{\lambda\ge0}\; \underbrace{q(\lambda)}_{\min_{x,y}L(x,y,\lambda)}, \] so we choose the price whose best response gives the highest valid lower bound.

The price is a feedback signal. At the point that currently minimizes \(L\), the slope of the dual curve is the remaining rule value: \[ q'(\lambda) =g\bigl(x(\lambda),y(\lambda)\bigr) =2-\lambda. \] If the best response still violates the rule, \(g>0\), increasing \(\lambda\) raises \(q\). If the response is too far inside, \(g<0\), increasing \(\lambda\) lowers \(q\), so maximization moves the price back down. The peak occurs at \(g=0\): the price is just strong enough that the selfish best response lands on the wall.

Why not send \(\lambda\) to infinity? Because the point is allowed to respond after every price change. Once \(\lambda>2\), its cheapest response moves inside the allowed region, where \(g<0\). The term \(\lambda g\) then becomes increasingly negative, so \(q(\lambda)\) falls. The outer player cannot raise the bound without accounting for the inner player’s response.

Fix any \(\lambda\ge0\), and let the point minimize the Lagrangian over all of the plane—even forbidden points. Call that cheapest possible score \(q(\lambda)\). This is the dual function.

Why is it a lower bound? For any feasible point, \(x+y-2\le0\), so \[ L(x,y,\lambda) =f(x,y)+\lambda(x+y-2) \le f(x,y). \] And \(q(\lambda)\), being the minimum of \(L\), is no larger than that: \[ q(\lambda)=\min_{x,y}L(x,y,\lambda) \le L(x,y,\lambda) \le f(x,y). \] Thus every nonnegative price certifies a number below the primal optimum. The dual problem chooses the tightest such certificate: maximize \(q(\lambda)\) over \(\lambda\ge0\).

Hold one response \((x',y')\) fixed and change only the price \(\lambda\). At that frozen point, both \(f(x',y')\) and \(g(x',y')\) are just numbers, so \[ L(x',y',\lambda)=\underbrace{f(x',y')}_{\text{offset}}+\lambda \underbrace{g(x',y')}_{\text{slope}} \] has exactly the familiar line form “offset + horizontal coordinate times slope.” The horizontal coordinate is \(\lambda\), the fixed cost \(f(x',y')\) is the offset (or intercept), and the fixed rule value \(g(x',y')\) is the slope.

This slope has a useful meaning. A response that violates the rule has \(g(x,y)>0\), so charging a higher price makes its line rise. A response safely inside the rule has \(g(x,y)<0\), so its line falls: it receives a larger rebate. A response exactly on the wall has \(g(x,y)=0\), so its line is horizontal. Drag the point below to see its cost and rule value become the intercept and slope of one concrete line.

Why do we maximize \(q(\lambda)\)? For every nonnegative price and every feasible response, \(g(x,y)\le0\), so \[ L(x,y,\lambda)=f(x,y)+\lambda g(x,y)\le f(x,y). \] Since \(q(\lambda)\) is the minimum of \(L\) over all responses, it is no larger than the cost of every feasible response—in particular, no larger than the best feasible cost \(p^\star\). Thus each \(\lambda\ge0\) gives a valid lower-bound certificate \(q(\lambda)\le p^\star\). We want the strongest certificate, so we maximize \(q(\lambda)\). This does not mean making \(\lambda\) itself as large as possible: beyond the dome’s peak, the best response moves safely inside the wall, \(g<0\), and a larger price lowers \(q\) instead.

Hold any response \((x,y)\) fixed. Its score \[ L(x,y,\lambda)=f(x,y)+\lambda g(x,y) \] is a straight line in \(\lambda\): \(f(x,y)\) is its intercept and \(g(x,y)\) is its slope. The dual function keeps the lowest such line at every price: \[ q(\lambda)=\min_{x,y}L(x,y,\lambda) =\text{their lower envelope}. \]

A lower envelope of straight lines is always concave. Pick two prices \(\lambda_1,\lambda_2\) and mix them with \(0\le\theta\le1\). Because every \(L(x,y,\lambda)\) is affine in \(\lambda\), \[ \begin{aligned} q\!\left(\theta\lambda_1+(1-\theta)\lambda_2\right) &=\min_{x,y}\left[ \theta L(x,y,\lambda_1)+(1-\theta)L(x,y,\lambda_2)\right]\\ &\ge \theta\min_{x,y}L(x,y,\lambda_1) +(1-\theta)\min_{x,y}L(x,y,\lambda_2)\\ &=\theta q(\lambda_1)+(1-\theta)q(\lambda_2). \end{aligned} \] The middle inequality says: forcing one response \((x,y)\) to serve both prices cannot beat letting each price choose its own cheapest response. This is exactly the definition of concavity—the curve lies above every chord. Notice that this argument never assumed the primal problem was convex; the dual function is concave regardless.

For this bowl, \(x(\lambda)=y(\lambda)=2-\lambda/2\), so \[ q(\lambda)=2\lambda-\frac{\lambda^2}{2}. \] The dome peaks at \(\lambda^\star=2\), where \(q(2)=2=p^\star\): this convex example has no duality gap.

At the solution, four simple facts hold at once. Together they are the Karush–Kuhn–Tucker conditions, or KKT conditions.

One more condition links slack and price: \[ \lambda(x+y-2)=0. \] This is complementary slackness. If the wall blocks the answer, the rule is tight and may carry a positive price. If the wall is loose, its price must be zero. A rule cannot be simultaneously slack and expensive.

For the original wall \(b=2\), the solution is \((1,1)\). The objective gradient there is \((-2,-2)\), while \(\nabla g=(1,1)\). Stationarity forces \[ (-2,-2)+\lambda(1,1)=(0,0), \] so \(\lambda=2\). Geometrically, the objective’s urge to cross the wall is exactly cancelled by the wall’s price force.

Move the wall past \(b=4\). Now \((2,2)\) is already feasible, the constraint stops mattering, and complementary slackness turns its price off: \(\lambda^\star=0\).

The primal variables \(x,y\) want to make \(L\) smaller. The dual variable \(\lambda\) wants to make the lower bound larger. A primal–dual algorithm updates both directions together.

# one simultaneous primal–dual step
x ← x − η [2(x − 2) + λ]
y ← y − η [2(y − 2) + λ]
λ ← max(0, λ + η [x + y − 2])

The first two lines descend the Lagrangian. The last line ascends in price: if the point violates the wall, \(x+y-2>0\), the price rises; if the point sits safely inside, the price falls. The \(\max(0,\cdot)\) keeps the inequality multiplier nonnegative.

Watch the negotiation: the point first chases the unconstrained minimum and crosses the wall. The violation raises \(\lambda\); the higher price pushes the next primal steps back. The oscillation shrinks until the point settles at \((1,1)\) and the price at \(2\)—the same KKT pair we found analytically.

This toy exposes three common techniques. Primal methods optimize \(x\) directly and enforce feasibility, often by projection. Dual methods optimize prices and repeatedly solve or approximate \(\min_x L(x,\lambda)\). Primal–dual methods update both at once, which is useful when exact projection and exact inner minimization are both expensive.