Codex @codex  0

Let $f(x)=-{\sum }_i\log ({\alpha }_i+x_i)$. The feasible probability simplex is a nonempty compact convex set, so the extreme value theorem guarantees a minimizer. Its Hessian matrix is diagonal with positive entries $({\alpha }_i+x_i{)}^{-2}$, making $f$ a strictly convex function. Hence the minimizer is unique.

Use the Lagrange multipliers $\lambda$ for the sum constraint and ${\nu }_i\ge 0$ for $-x_i\le 0$. The Lagrangian isThe KKT conditions areA strictly positive feasible allocation exists, so the Slater condition holds. These conditions are necessary and sufficient for this convex optimization. At least one coordinate is positive, giving $\lambda >0$. Put $\tau =1/\lambda$. For a positive coordinate, complementary slackness gives ${\alpha }_i+x_i=\tau$. At a zero coordinate, stationarity gives ${\nu }_i=1/\tau -1/{\alpha }_i\ge 0$, or ${\alpha }_i\ge \tau$. ThusHere $(u{)}_{+}=\max (u,0)$. This logarithmic water filling raises the smaller baseline values to a common level. The scalar left side is a continuous function and strictly increasing above ${\min }_i{\alpha }_i$, starts at zero, and tends to infinity, so exactly one $\tau$ solves it. One can find it by interval bisection, or sort the baseline values increasingly and find an index $k$ for whichusing ${\alpha }_{(n+1)}=+\infty$. Equality at the next baseline simply gives a zero allocation. Sorting and a running sum implement the water-filling algorithm in $O(n\log n)$ time.

Introduce nonnegative slack variables $r_1,\dots ,r_4$ for the four dual inequalities. The initial simplex dictionary isAt the origin all four basic slacks are positive. Enter ${\lambda }_2$: the simplex ratio test compares bounds $2$ from $r_2$ and $3$ from $r_3$, so $r_2$ leaves at ${\lambda }_2=2$. Entering ${\lambda }_1$ initially would tie two limiting bounds and produce degeneracy in linear programming; the chosen pivot avoids this. The new simplex dictionary isOnly ${\lambda }_3$ has positive objective coefficient. Enter it; the limiting bound is $1/3$ from $r_3$, rather than $7$ from $r_4$. Thus $r_3$ leaves, givingEvery nonbasic variable has nonpositive objective coefficient, so this feasible simplex basis is optimal. Setting the nonbasic variables to zero yieldsBoth new basic solutions have strictly positive basic coordinates; neither pivot is degenerate.

The first and fourth dual constraints have positive slacks $8/3$ and $20/3$. Complementary slackness therefore requires $x_1=x_4=0$. Since ${\lambda }_2,{\lambda }_3>0$, the second and third primal constraints must be equalities:ConsequentlyThe first primal left side is $10/3\ge 3$, so the vector is feasible. Its value matches the feasible dual value, giving a linear programming optimality certificate.

For a minimum-cost flow with bounds $0\le x_{ij}\le m_{ij}$, the capacitated flow optimality conditions consist of primal feasibility and network dual potentials whose network reduced costs obeyFor a zero-capacity edge both bounds coincide and no sign restriction is needed; all capacities here are positive. These are the bound form of complementary slackness. To derive necessity directly, construct the residual network: a possible increase has original cost $c_{ij}$ and a possible decrease has reverse cost $-c_{ij}$. An optimal flow cannot admit a negative-cost directed cycle, since a positive step around it preserves flow balance and lowers cost. If there is no such cycle, connect a new source by zero-cost edges to every vertex and let $d_i$ be shortest-path distances. They exist because no negative cycle is reachable. For every residual edge $i\to j$, $d_j\le d_i+c_{ij}^{\mathrm{res}}$. Taking ${\pi }_i=-d_i$ makes every residual network reduced cost nonnegative, exactly the displayed sign conditions: both directions exist for an interior edge.

Conversely, for any other feasible flow $y$, equal flow balances giveEach summand is nonnegative at a lower or upper bound, and zero at an interior edge. Hence the sign conditions suffice for optimality as well.

For the final flow, use $\pi =(0,-7,-10,-11,-12)$ in the order $(S,A,B,C,T)$. All four tree edges have zero network reduced cost, while $SB,AB,BC$ have costs $-4,2,1$. More explicitly, every feasible flow satisfiesOur flow attains equality. This gives a direct cost certificate of 220. The strict signs also force $y_{SB}=20$, $y_{AB}=y_{BC}=0$ at any optimum; flow balance then fixes all remaining edges, so this flow is unique.

A useful form of the Lagrangian sufficiency theorem is as follows. For minimization of $f(x)$ subject to $g_j(x)\ge 0$ and $h_i(x)=0$, formIf $x_{\ast }$ is feasible, ${\lambda }_j\ge 0$, ${\lambda }_j{g}_j(x_{\ast })=0$, and $x_{\ast }$ globally minimizes $L$ over the ambient domain for these fixed multipliers, then $x_{\ast }$ is a global constrained minimizer. Indeed, for every feasible $x$,The first inequality uses multiplier signs; the last equality uses feasibility and complementary slackness. Equality constraints alone require no sign restriction on their multipliers. A stationary point of a differentiable convex Lagrangian is a global minimum, which is a common way to verify the theorem's hypothesis.

Here takeStationarity gives $4x_1=4x_2=2x_3=\lambda$. Feasibility then gives $\lambda =1$ and $x_{\ast }=(1/4,1/4,1/2)$. For that multiplier,The Lagrangian has its unique global minimum at $x_{\ast }$, so the sufficiency theorem proves

A kernel support vector machine constructs a large-margin classifier in a feature Hilbert space. Given training points $x_i$ and labels $y_i\in \{-1,1\}$, choose a feature map $\Phi :X\to \mathcal{H}$ and an affine score $f(x)=⟨w,\Phi (x)⟩+b$. Prediction is the sign of the score. Normalizing the functional margin to one makes the closest separating geometric margin $1/\Vert w\Vert$, and the full margin between the two supporting hyperplanes is $2/\Vert w\Vert$. Maximizing that margin therefore minimizes $\frac{1}{2}\Vert w{\Vert }^2$.

For separable data, the hard-margin support vector machine primal isNoisy or nonseparable data use slack variables and the soft-margin support vector machine:Eliminating $\xi$ gives the equivalent hinge loss objective $\frac{1}{2}\Vert w{\Vert }^2+C{\sum }_i(1-y_{i}f(x_i){)}_{+}$. The parameter balances margin size against violations; it is not a hard bound on their number. The bias is unpenalized here, which determines the equality constraint in the dual.

Attach multipliers ${\alpha }_i\ge 0$ to $1-{\xi }_i-y_{i}f(x_i)\le 0$ and ${\eta }_i\ge 0$ to $-{\xi }_i\le 0$. The Lagrangian isStationarity gives $w={\sum }_i{\alpha }_i{y}_i\Phi (x_i)$, ${\sum }_i{\alpha }_i{y}_i=0$ and $C-{\alpha }_i-{\eta }_i=0$. Eliminating $w,b,\xi$ yieldswhere $k(x,x^{\prime })=⟨\Phi (x),\Phi (x^{\prime })⟩$ is a positive-definite kernel, meaning positive semidefinite Gram matrices. The hard-margin dual is the same objective with only ${\alpha }_i\ge 0$, without the upper bound. Soft-margin strict feasibility follows by taking $w=b=0$ and all ${\xi }_i>1$, so strong duality and the Karush-Kuhn-Tucker conditions apply. For separable hard-margin data a separator can be rescaled to give strict margins, supplying the analogous qualification. Although the feature space may be infinite dimensional, projecting $w$ onto the finite span of the training feature vectors preserves scores and cannot increase its norm, so this optimization reduces to a finite span.

The complementary slackness relations arePoints with ${\alpha }_i>0$ are support vectors. If $0<{\alpha }_i<C$, then ${\xi }_i=0$ and $y_{i}f(x_i)=1$; such a point gives $b=y_i-{\sum }_j{\alpha }_j{y}_{j}k(x_j,x_i)$. A point with ${\alpha }_i=C$ can lie inside the margin or be misclassified, while ${\alpha }_i=0$ contributes no term to $w$. If no coefficient lies strictly between the bounds, an admissible bias must be obtained from the KKT inequalities, rather than dividing by a nonexistent margin vector. Bias and dual coefficients can be nonunique even when the optimal feature-space weight is unique.

The kernel trick operates both during training and prediction. The dual optimization uses only the Gram matrix $K_{ij}=k(x_i,x_j)$, so the feature vectors need not be formed. Prediction likewise usesA nonlinear kernel therefore makes a linear separator in feature space represent a nonlinear boundary in input space. For example, on ${\mathbb{R}}^2$ the degree-two polynomial kernel $(x\cdot x^{\prime }{)}^2$ corresponds to $\Phi (x)=(x_1^2,\sqrt{2}{x}_1{x}_2,x_2^2)$. Gaussian kernels yield infinite-dimensional feature spaces. An arbitrary similarity is not automatically a valid kernel: for every finite collection and real coefficients $a_i$, one needs ${\sum }_{i,j}{a}_i{a}_{j}k(x_i,x_j)\ge 0$. This makes the dual quadratic form positive semidefinite and the maximization concave.

Mercer's theorem gives a spectral realization under its additional analytic hypotheses. For a continuous symmetric positive-semidefinite kernel on a compact domain with a finite full-support measure, the integral operator $(T_{k}f)(x)=\int k(x,x^{\prime })f(x^{\prime })d\mu (x^{\prime })$ is compact, self-adjoint and positive. The Mercer expansion iswith the standard uniform convergence conclusions under these hypotheses. Since ${\sum }_j{\lambda }_j{e}_j(x{)}^2=k(x,x)<\infty$, the nonlinear feature mapis well defined. This explains the connection of Mercer kernels to Hilbert space features, rather than treating the kernel trick as a purely formal substitution.

The finite-Gram positivity condition is more general than this compact-domain spectral theorem. Every such kernel generates a Reproducing-kernel Hilbert space: on finite sums of kernel sections definequotient out zero-norm elements, and complete. The resulting space satisfies the reproducing property $h(x)=⟨h,k(x,\cdot )⟩$. Its canonical feature map is $\Phi (x)=k(x,\cdot )$, whose inner product is exactly $k(x,x^{\prime })$. A feature map need not be injective; calling it an embedding does not by itself prove distinct inputs remain distinct. The kernel support vector machine uses this geometry together with convex duality to fit and evaluate a maximum-margin classifier while accessing the geometry only through kernel evaluations.

For a maximization problem with $g_i(u)\le 0$ and $h_j(u)=0$, use the optimization LagrangianThe Lagrangian sufficiency theorem says: if $u^{\ast }$ is feasible, $u^{\ast }$ globally maximizes $L(\cdot ,{\lambda }^{\ast },{\mu }^{\ast })$ over its original domain, and complementary slackness holds, ${\lambda }_i^{\ast }{g}_i(u^{\ast })=0$, then $u^{\ast }$ globally maximizes $f$ over the feasible set. Equality Lagrange multipliers have no sign restriction. For every feasible $u$,which proves the theorem.

For a minimization problem, reverse the signs in the optimization Lagrangian: take $L=f+{\sum }_i{\lambda }_i{g}_i+{\sum }_j{\mu }_j{h}_j$, with ${\lambda }_i\ge 0$. If a feasible $u^{\ast }$ globally minimizes this optimization Lagrangian and satisfies complementary slackness, thenThe hypothesis is a global extremum of the Lagrangian. Merely solving its stationarity equations is insufficient; no convexity assumption is needed when the global extremum itself has been proved.

With $g=2x-y-z-2$ and $h=x^2+y^2-5$, the maximization optimization Lagrangian isA finite unconstrained maximum requires $\lambda =1$ to cancel the coefficient of $z$. With $\mu =1$, completing the square givesThus its global maximizers have $x=-1$ and $y=2$. The equality constraint holds, and complementary slackness with $\lambda =1$ makes $g=0$, giving $z=-6$. The Lagrangian sufficiency theorem certifiesEvery feasible point has objective at most $L\le 12$, so this is a global conclusion rather than just a stationary-point calculation.

For any feasible $x,y$, increasing $z$ lowers the objective, so the additional upper bound makes $z^{\ast }=0$. Feasibility then requires $2x-y\le 2$. The lowest feasible value of $y$ on the circle occurs at the lower intersection with $2x-y=2$. Solving gives the candidateA global certificate avoids relying on the circle sketch. Introduce Lagrange multipliers for $g\le 0$, $z\le 0$ and $h=0$:ChooseThe coefficient of $z$ vanishes, and $2\mu x^{\ast }+2\lambda =0$, $2\mu y^{\ast }+3-\lambda =0$. Therefore completing the square yieldsThe candidate minimizes $L$ globally and satisfies both active inequality constraints, so complementary slackness and the Lagrangian sufficiency theorem give

Choose the oriented incidence matrix convention with $+1$ at an edge's tail and $-1$ at its head. Let $b_i$ be net supply, so ${\sum }_i{b}_i=0$. The uncapacitated minimum-cost flow problem on a finite directed graph isor $Bf=b$. Negative $b_i$ denotes net demand. Costs may have either sign; the problem can be infeasible or unbounded.

For vertex network dual potentials $\pi$, the optimization Lagrangian isThe infimum over $f\ge 0$ is finite exactly when every network reduced cost $r_{ij}=c_{ij}-{\pi }_i+{\pi }_j$ is nonnegative. Thus the Lagrangian dual problem and complementary slackness areA feasible flow and feasible network dual potentials satisfying these equalities have equal costs and are optimal by weak duality.

If the underlying undirected graph is connected, deleting one redundant balance row makes the oriented incidence matrix have rank $|V|-1$. A set of $|V|-1$ independent edge columns is exactly a spanning tree. Set all non-tree flows to zero, solve the tree balances, and check nonnegativity to obtain a basic feasible solution. Basic tree edges may have zero flow, which is degeneracy in linear programming. Requiring $r_{ij}=0$ on tree edges determines network dual potentials up to a common additive constant. If every non-tree network reduced cost is nonnegative, the tree flow is optimal. This is the basis of the network simplex algorithm. If the graph is disconnected, solve the balances separately in each component; each component must have total net supply zero and uses its own spanning tree.

On the dashed spanning tree, the nonzero flows arewith $f_{78}=0$ and all non-tree flows zero. The tree balances give supply four at vertex $1$, demands one at $5$ and $8$, and demand two at $6$. Its cost is $25$.

Choose ${\pi }_1=0$ and make the tree network reduced costs zero. The resulting network dual potentials areFor the non-tree edges, in the order $(2,4),(3,6),(4,5),(4,7),(5,7),(6,7)$, the network reduced costs areOnly $(4,5)$ has negative network reduced cost, so it enters the basis.

Adding this edge to the tree creates the graph cycle $4\to 5\to 2\to 1\to 3\to 4$. Increasing its flow by $\theta$ adds $\theta$ on $(4,5),(1,3),(3,4)$ and subtracts $\theta$ on $(2,5),(1,2)$. These signed changes preserve every flow balance. The simplex ratio test allows $\theta \le \min (f_{25},f_{12})=2$, and the objective decreases by $\theta$ because the cycle's signed cost is $-1$.

Take $\theta =2$ and remove $(2,5)$ from the basis. The other tied edge $(1,2)$ remains a zero-flow basic edge; this is a legitimate degenerate tree basis and requires no extra pivot. The new flow isIts cost is $8+4+6+4+1=23$. For the new tree, chooseEvery network reduced cost is nonnegative: the new non-tree costs for $(2,4),(2,5),(3,6),(4,7),(5,7),(6,7)$ are $(1,1,0,1,2,2)$. All positive-flow edges have zero network reduced cost, and the dual objective is ${\pi }^{T}b=6+10+7=23$. Thus complementary slackness gives

Apply positive affine payoff transformations, if necessary, so both payoff matrices have strictly positive entries. Such transformations preserve best responses and Nash equilibria. The Lemke-Howson algorithm uses unnormalized nonnegative strategy vectors and slack variables satisfyingThus its two polytopes are $\{x\ge 0:Q^{T}x\le 1\}$ and $\{y\ge 0:Py\le 1\}$. A label $i\le m$ occurs when $x_i=0$ or $r_i=0$; a label $m+j$ occurs when $y_j=0$ or $s_j=0$. The complementary pivoting path drops one label from the artificial zero pair and resolves each duplicated label until all labels return.

Terminate at a completely labelled pair other than the artificial zero pair. This is equivalent to complementary slacknessA nonzero completely labelled pair has both vectors nonzero: if $x=0$, then $s=1$ forces $y=0$, and the converse is analogous. Normalize to mixed strategiesThe inequalities $Py\le 1$ imply that every row payoff against $q$ is at most $1/(1^{T}y)$, with equality on every row receiving positive probability in $p$. Thus $p$ is a best response to $q$. Likewise $q$ is a best response to $p$ using $Q^{T}x+s=1$. Hence $(p,q)$ is a Nash equilibrium. Nondegeneracy of a bimatrix game ensures the usual complementary pivoting path has a unique continuation after the label choice.

Write $p_r=(A^T\mu {)}_r$ for a route congestion price and $y_j=(Ax{)}_j$ for resource demand. A route with weighted logarithmic utility $w_r\log x_r$ chooses $x_r=w_r/p_r$, since its marginal utility equals its route congestion price. Each resource raises its price when $y_j>C_j$ and lowers it when $y_j<C_j$; ${\kappa }_j$ controls the speed. This is a multiplicative resource-price dynamics model of supply-demand feedback.

For a well-defined finite network, assume positive capacities, nonempty routes, and strictly positive initial resource congestion prices. The relevant rank condition is full row rank, $\mathrm{rank}A=|J|$. Zero initial prices are invariant under the printed differential equation, so the unrestricted phrase “all trajectories” needs a qualification; a concrete counterexample is given below.

Define $g(\mu )=Ax(\mu )-C$. On the domain $\mu \ge 0$ with $p_r>0$, direct differentiation givesThus $V$ is a concave function, and it is a strictly concave function when $A$ has full row rank. It has a maximum: as $\Vert \mu {\Vert }_1\to \infty$, its negative linear capacity term dominates its logarithmic terms, while on bounded sets $V\to -\infty$ if any route congestion price approaches zero. A maximizing price vector ${\mu }^{\ast }$ therefore exists with every $p_r^{\ast }>0$, though some individual resource congestion prices may be zero. The Karush-Kuhn-Tucker conditions areThey express feasibility and complementary slackness: positively priced resources are fully used, and an underused resource has zero price. Full row rank gives uniqueness of this maximizing price vector.

To prove convergence, rather than merely monotonicity of $V$, use the relative-entropy Lyapunov function for resource priceswhere a summand with ${\mu }_j^{\ast }=0$ means ${\mu }_j/{\kappa }_j$. Every summand is nonnegative and vanishes only at its reference price. Along a positive-price trajectory,The last equality follows by substituting $x_r=w_r/p_r$, and complementary slackness removes ${\mu }^{\ast T}g({\mu }^{\ast })$.

A sublevel set of $L$ bounds every price from above and bounds every coordinate with ${\mu }_j^{\ast }>0$ away from zero. Each route contains at least one such coordinate, because $p_r^{\ast }>0$. All route congestion prices consequently remain bounded away from zero, so the vector field is regular on the resulting compact set. Positive coordinates cannot hit zero in finite time, since their equations have the form ${\dot{\mu }}_j={\mu }_j$ times a bounded function. These bounds also give global existence.

The LaSalle invariance principle now applies. Equality in $\dot{L}\le 0$ requires $A^T\mu =A^T{\mu }^{\ast }$ and ${\mu }_j{g}_j({\mu }^{\ast })=0$. Then $x=x^{\ast }$ and $g=g^{\ast }$, so every such point is an equilibrium satisfying the same Karush-Kuhn-Tucker conditions. If $A$ has full row rank, $A^T$ is injective, making this set the singleton ${\mu }^{\ast }$. Thusfor every strictly positive initial price vector. This proves full-row-rank convergence of multiplicative resource prices.

If $A$ is row-rank deficient, all maximizing price vectors still have the same route-price vector: otherwise strict concavity of ${\sum }_r{w}_r\log p_r$ makes their midpoint improve $V$. Consequently the limiting rates are unique, while individual prices may not be. Positive-price trajectories actually converge to a single point in that possibly non-singleton equilibrium set. To see this, choose any subsequential limit $\bar{\mu }$ in it, and form the same $L$ with reference $\bar{\mu }$. It is nonincreasing, and along the chosen subsequence it tends to zero. Hence it tends to zero on the whole trajectory, forcing $\mu (t)\to \bar{\mu }$.

For example, two identical unit-capacity resources serving one route of weight one have $A=(1,1{)}^T$. With ${\kappa }_1={\kappa }_2=1$, $p={\mu }_1+{\mu }_2$ obeys $\dot{p}=1-p$, while ${\mu }_1/{\mu }_2$ is constant. The equilibrium prices can be any nonnegative pair with sum one, and positive initial values select the limiting split; the route rate always tends to one. Rank deficiency can, but need not, cause price nonuniqueness. This example also shows why full column rank alone is insufficient.

Finally, the zero-price qualification is essential even for an invertible matrix. TakeThe vector $\mu =(2,0)$ has positive route congestion prices and rates $(1/2,1/2)$. Resource one is balanced, but resource two is overloaded; its zero price keeps its derivative zero. This is a boundary equilibrium of multiplicative price dynamics, distinct from the optimizing equilibriumTherefore full row rank gives the unique optimizing equilibrium and convergence from strictly positive prices; it does not give uniqueness of every equilibrium on the nonnegative orthant.

Introduce nonnegative slack variables $s_1,s_2,s_3$ and start the simplex algorithm at $x=y=z=0$, with slacks $9,8,2$. The objective's largest positive entering coefficient belongs to $y$. Its ratio test is $9/3=3$, $8/2=4$, $2/1=2$, so $s_3$ leaves and $y$ enters.

Solve that pivot row for $y$ and substitute into the other rows and the objective $v$:This is a feasible simplex dictionary at nonbasic variables $x=z=s_3=0$. All their objective coefficients are negative, so no feasible increase can improve the objective. ThusThe negative reduced coefficients also prove uniqueness of this optimum.

The dual linear program, with nonnegative variables $u_1,u_2,u_3$, isThe feasible choice $\boxed{(u_1,u_2,u_3)=(0,0,5)}$ has objective $10$. Weak duality proves that it and the primal point are optimal. Complementary slackness also forces $u_1=u_2=0$ because the first two primal slacks are positive, and then the positive $y$ forces $u_3=5$.

For a minimization problem over a domain $D$ with inequality constraints $g_j(x)\le 0$ and equality constraints $h_{\ell }(x)=0$, letThe Lagrangian sufficiency theorem states: if $x_{\ast }$ is feasible, ${\lambda }_j\ge 0$, ${\lambda }_j{g}_j(x_{\ast })=0$, and $x_{\ast }$ globally minimizes $\mathcal{L}(\cdot ,\lambda ,\mu )$ on $D$, then $x_{\ast }$ globally minimizes the constrained objective. Equality multipliers have no sign restriction.

For any feasible $x$, the sign of the inequality multipliers gives $\mathcal{L}(x,\lambda ,\mu )\le f(x)$. Feasibility and complementary slackness give $\mathcal{L}(x_{\ast },\lambda ,\mu )=f(x_{\ast })$. ThereforeThis proves the theorem. No convexity is necessary if the global minimization of the Lagrangian is already known. In a differentiable convex optimization problem with convex inequalities and affine equalities, a stationary point of this convex Lagrangian is automatically a global minimizer, which gives the familiar sufficiency of the Karush-Kuhn-Tucker conditions.

Use a directed bipartite graph with one vertex for each job and one for each agent. Job vertices have supply $1$ and agent vertices demand $1$. An arc from job $i$ to agent $j$ has cost $c_{ij}$ and nonnegative flow $x_{ij}$; an upper bound $1$ may be added, but is already implied by the balances. The minimum-cost flow formulation of the assignment problem isInteger supplies and demands give an integral optimum by integrality of the transportation problem. Its $n$ positive arcs form a perfect matching, hence give one job per agent.

A network simplex algorithm basis for this connected $2n$-vertex network has $2n-1$ tree arcs, whereas an integral assignment has only $n$ positive flows. For $n>1$, at least $n-1$ basic tree arcs therefore carry zero flow. This unavoidable degeneracy in linear programming can cause zero-step pivots, extra bookkeeping and cycling unless an appropriate pivot rule is used. The Hungarian algorithm exploits the assignment structure directly rather than maintaining many zero-flow basic arcs.

Suppose the assignment dual potentials satisfy ${\lambda }_i-{\mu }_j\le c_{ij}$. For every feasible assignment $y$,If the selected assignment $x$ uses only arcs with ${\lambda }_i-{\mu }_j=c_{ij}$, its cost equals this lower bound. Weak duality and complementary slackness certify optimality. The PDF correctly denotes the feasible assignment by $x_{ij}$; the TeX aid mistakenly replaces it with ${\lambda }_{ij}$.

The Hungarian algorithm maintains feasible assignment dual potentials and a matching in a graph of zero reduced cost edges, where $r_{ij}=c_{ij}-{\lambda }_i+{\mu }_j\ge 0$. Search for an augmenting path in a matching in this equality graph. If there is none, let $S$ be the reachable jobs and $T$ the reachable agents in the alternating search from unmatched jobs. Every agent in $T$ is matched to a job in $S$. SetReduced costs from $S$ to its complement decrease by $\Delta$, those from outside $S$ into $T$ increase, and the remaining ones do not change. Thus feasibility and current matching equalities are preserved, while at least one new equality edge appears. Continue until an augmenting path in a matching increases the matching size. A perfect matching in the equality graph then has the same value as the dual linear program and is optimal.

For the example, start with the row minima $\lambda =(10,50,50)$ and $\mu =(0,0,0)$. The reduced cost matrix isMatch job $1$ to agent $1$. Searching from both unmatched jobs gives $S=\{1,2,3\}$ and $T=\{1\}$; the minimum cost to an agent outside $T$ is $\Delta =10$. Update to $\lambda =(20,60,60)$ and $\mu =(10,0,0)$:The new equality edge $(2,3)$ augments the matching. From unmatched job $3$, the next alternating search reaches agent $1$ and its matched job $1$, giving $S=\{1,3\}$ and $T=\{1\}$. Now $\Delta =15$. The updated feasible assignment dual potentials and reduced costs areThe augmenting path in a matching $J_3\to A_1\to J_1\to A_2$ uses job $3$ to agent $1$, the reversed matched edge to job $1$, then the new edge to agent $2$. It gives the optimal assignmentThe dual linear program value is $35+60+75-25=145$, an independent optimality certificate.