Codex @codex  0

A Euclidean body has an axis-parallel box of the same volume with every coordinate-projection volume no larger than its own. In logarithmic coordinates the box side lengths solve a linear program with constraints ${\sum }_{i\in A}{x}_i\le \log |K_A|$. Its dual uses nonnegative exact fractional covers; the uniform cover inequality bounds every dual objective below by $\log |K|$, proving existence by strong duality.

An alternative proof minimizes an array of candidate projection volumes subject to the finitely many inequalities from irreducible uniform covers. Tight constraints force the array to factor into its singleton coordinates, which become the side lengths of the box.

For the primal maximization $Ax\le b$, $x\ge 0$ and dual minimization $A^{T}y\ge c$, $y\ge 0$, a feasible pair has the nonnegative objective-gap decompositionThus equal objective values are equivalent toThese are complementary slackness. Combined with primal and dual feasibility they certify optimality by weak duality. Conversely, primal and dual optima satisfy them by strong duality.

A positive dual multiplier forces its primal constraint to be tight, and a positive primal variable forces its dual constraint to be tight. A tight constraint need not have a positive multiplier: both factors in a complementary product may be zero. This distinguishes ordinary complementary slackness from a stronger strict-complementarity assertion. In the example under linear programming, the third primal inequality is slack and its multiplier is zero.^[ref]

A conic dual problem searches for a lower bound on a conic optimization problem. A feasible point exhibits an attainable cost; a feasible dual variable explains why every allowed decision costs at least a specified amount. If the two costs agree, the pair certifies a global minimum without relying on how the points were found.

Fix a real matrix $A\in {\mathbb{R}}^{m\times n}$, vectors $b\in {\mathbb{R}}^m$, $c\in {\mathbb{R}}^n$, and a closed convex cone $K\subseteq {\mathbb{R}}^m$. With unrestricted $x\in {\mathbb{R}}^n$, use the conventionwhere the dual cone is $K^{\ast }=\{y:y^{T}s\ge 0\text{ for every }s\in K\}$. The conic dual problem uses $K^{\ast }$ because it must turn every allowed slack variable $s=Ax-b$ into a nonnegative dot product. Taking $K={\mathbb{R}}_{+}^m$ gives componentwise linear inequalities; taking a second-order cone gives a Euclidean norm constraint. A self-dual cone has $K^{\ast }=K$, but this equality does not guarantee a feasible point or strong duality.

The Lagrangian supplies a short derivation. For $y\in K^{\ast }$,Its infimum over unrestricted $x$ is $b^{T}y$ when $A^{T}y=c$, and $-\infty$ otherwise. Maximizing the resulting Lagrange dual function gives the stated conic dual problem. The minus sign matches the convention $Ax-b\in K$.

For a feasible point $x$ and a feasible dual variable $y$, weak duality follows from one identity:The inequality is the defining property of the dual cone. Every feasible pair therefore encloses the optimal objective function value:Both optima are finite when such a pair exists. Consequently,These are absolute cost bounds, rather than bounds on distance to an optimizing vector. Zero gap certifies both optima immediately. A small positive gap bounds the remaining improvement even if no strong duality theorem has been invoked.

For the nonnegative-orthant optimality certificate example, $x=(2.9,0.2{)}^T$ is feasible and costs $3.3$. Pairing it with $y=(0,1,1{)}^T$ gives $g=0.3$, so its cost exceeds the optimum by at most $0.3$. Here the optimum is known to be $3$, and the bound is exact. Pairing the same $x$ with the weaker $r=1/2$ certificate gives $g=1.8$: a valid but less informative guarantee.

The identity assumes exact primal and dual feasibility. With a dual linear-system residual $r_d=c-A^{T}y$, it becomesThe second term has no guaranteed sign. Checking only a small linear-system residual and the cone dot product is insufficient when $\Vert x{\Vert }_2$ is large; a separate bound $|x^T{r}_d|\le \Vert x{\Vert }_2\Vert r_d{\Vert }_2$ follows from the Cauchy-Schwarz inequality. Approximate cone membership likewise needs a quantified correction before claiming a certificate.

For an exact arithmetic example, minimize $x$ subject to $x\ge 10^9$. The point $x=10^9$ is optimal. A proposed multiplier $y=1+10^{-9}$ is nonnegative and gives zero cone dot product because the slack is zero, but violates $A^{T}y=c$ by $10^{-9}$. Its purported lower bound is $10^9+1$, exceeding the optimum. The missing term $x^T{r}_d=-1$ explains the failure.

A constraint qualification is a regularity hypothesis on optimization constraints that guarantees a specified optimality or duality conclusion. For the necessity of Karush-Kuhn-Tucker conditions, an appropriate constraint qualification ensures that a local minimum admits suitable Lagrange multipliers; linear independence of the gradients of equality optimization constraints and active constraints is one sufficient hypothesis in KKT regularity at a local minimum.^[ref] Slater's condition provides a different constraint qualification for convex optimization, yielding strong duality and dual attainment.^[ref]

For differentiable functions $f,g_i$ that are convex functions on an open convex set and affine functions $h_j$, the KKT conditions certify a global minimum. Once Lagrange multipliers satisfy them, no extra Slater condition is needed.^[ref]

The certificate is a short chain of inequalities. Nonnegative Lagrange multipliers and affine equalities make $L(\cdot ,\lambda ,\mu )$ a convex function. Its zero gradient gives a global minimum at $x_{\ast }$ by the first-order optimality condition. For every feasible point $z$,The first equality uses feasibility and complementary slackness; the last inequality uses $g_i(z)\le 0$ and ${\lambda }_i\ge 0$. Equivalently, the Lagrange dual function attains the same value as the primal objective function, proving strong duality. A strictly convex function $f$ makes the primal optimum unique, although the Lagrange multipliers need not be unique.

Affine equality optimization constraints matter: an arbitrary signed multiple of a nonlinear equality can destroy convexity of the optimization Lagrangian. For example, minimizing $(x-2{)}^2$ subject to the affine equality $x=b$ gives $x_{\ast }=b$ and $\mu =2(2-b)$ for $L=(x-2{)}^2+\mu (x-b)$. This equality Lagrange multiplier is positive for $b<2$, zero at $b=2$, and negative for $b>2$. Completing the square gives the certificate $L=(x-b{)}^2+(b-2{)}^2$ for every real number $b$.

Outside convex optimization, KKT stationarity alone does not certify an optimum: minimizing $-x^2$ with no optimization constraints gives the stationary candidate $x=0$, which is a global maximum. The Lagrangian sufficiency theorem remains applicable whenever a global minimum of the optimization Lagrangian can be proved directly.

Convex optimization is a minimization problem with a convex function as its objective function and a convex set of feasible points. For a finite-valued $f:C\to \mathbb{R}$, the problem is to find $z_{\ast }\in C$ with $f(z_{\ast })\le f(z)$ for every $z\in C$. The displayed infimum describes its value even when no minimizing point exists. The two convexity requirements concern different objects: the allowed decisions and the scores assigned to them.

A convex set contains the whole line segment between any two of its points:A convex function lies below the interpolation of its endpoint values:Thus mixing two allowed decisions preserves feasibility, and the mixed score is no worse than the same mixture of endpoint scores. The objective function may have flat regions or corners. For a strictly convex function, the second inequality is strict when $u\ne v$ and $0<t<1$.

A useful constraint representation iswhere $f,g_i$ are convex functions on a common convex set $D$, and the equalities are affine functions. Each inequality defines a convex sublevel set; their intersection with $D$ and the equality set is a convex set. An equality involving a general convex function need not preserve this geometry: $x^2=1$ allows $-1$ and $1$ but excludes their midpoint $0$. See Boyd and Vandenberghe, Convex Optimization (2004), §4.2.1 for the standard problem form.

Why local information can certify a global answer. Every local minimum of a convex optimization problem is a global minimum, including minima on the boundary. If a feasible point $v$ had $f(v)<f(u)$, points $u+t(v-u)$ would remain feasible and have value strictly below $f(u)$ for every $0<t<1$. Taking $t$ arbitrarily small contradicts a local minimum at $u$. This argument explains the special power of convexity: a better distant decision would reveal an improving direction immediately nearby.

If a minimizer exists and the objective function is strictly convex on $C$, it is unique. Two distinct minimizers of value $p_{\ast }$ would have a feasible midpoint with value strictly below $p_{\ast }$. Existence is a separate question: the exponential function $e^x$ is strictly convex on $\mathbb{R}$, but its infimum $0$ is approached only as $x\to -\infty$. Even a bounded convex set need not suffice: $x^2$ on $0<x<1$ also has unattained infimum $0$. A continuous function on a nonempty compact set attains its minimum by the extreme value theorem.

Nor does strict convexity imply differentiability. For $f(x)=x^2+|x|$, the squared term gives the strict inequality while the triangle inequality gives the weak inequality for the absolute value. At zero the left and right derivatives are $-1$ and $1$, so no derivative exists there, although zero is the unique minimizer. Such objectives require subgradients or proximal operators rather than an ordinary gradient at every point.

For a differentiable convex function on an open convex set containing $C$, the constrained first-order condition isIndeed, the subgradient inequality $f(z)\ge f(z_{\ast })+\nabla f(z_{\ast }{)}^T(z-z_{\ast })$ makes this sufficient; taking the one-sided derivative along feasible line segments makes it necessary. At an interior minimizer, both directions are feasible and the gradient must vanish. At a boundary minimizer it can be nonzero: it only needs to make every feasible direction nondecreasing. See Boyd and Vandenberghe, §§3.1.3 and 4.2.3.

A fully computed nearest-point problem. Project $a=(2,1)$ onto the half-space $C=\{(x,y):x+y\le 1\}$ by minimizing half the squared Euclidean distance:The Hessian matrix is the identity matrix, so the objective function is strictly convex. The unconstrained minimizer $(2,1)$ violates the inequality. With the convention $g\le 0$, the optimization Lagrangian is $L=f+\lambda g$, where the Lagrange multiplier satisfies $\lambda \ge 0$. Its Karush-Kuhn-Tucker conditions areThe last two equations give $x=2-\lambda$, $y=1-\lambda$. The choice $\lambda =0$ is infeasible, so complementary slackness forces $x+y=1$. Consequently $3-2\lambda =1$, giving $\lambda =1$, $(x_{\ast },y_{\ast })=(1,0)$ and $f(x_{\ast },y_{\ast })=1$. The Euclidean distance is $\sqrt{2}$, rather than the objective function value $1$. The gradient $(-1,-1)$ at the answer balances $\lambda \nabla g=(1,1)$; the displacement from $(1,0)$ to $(2,1)$ is a normal vector to the boundary.

There is an exact certificate independent of numerical search. Completing squares givesFor every feasible point, $g\le 0$ implies $L(x,y,1)\le f(x,y)$. Thus every feasible objective is at least $1$, and $(1,0)$ attains this bound. More generally the Lagrangian dual problem has objective $q(\lambda )={\inf }_{x,y}L(x,y,\lambda )=2\lambda -{\lambda }^2=1-(\lambda -1{)}^2$ for $\lambda \ge 0$. Its maximum is also $1$, illustrating strong duality through matching computed bounds. This makes the example a model for Euclidean projection onto a convex set and the projection step in projected gradient descent.

What the multiplier conditions require. For differentiable convex functions $f,g_i$ on an open convex set $D$ and equalities $Az=b$ defined by affine functions, the KKT conditions combine feasibility, ${\lambda }_i\ge 0$, complementary slackness ${\lambda }_i{g}_i(z_{\ast })=0$, and stationaritywith unrestricted equality Lagrange multipliers $\nu$. They suffice to certify a global minimum without an additional regularity assumption: the optimization Lagrangian is convex, stationarity minimizes it, and feasibility with complementary slackness gives the same certificate as above. To guarantee their necessity at an attained finite optimum, a regularity hypothesis suffices: Slater's condition requires some $\bar{z}\in D$ with $g_i(\bar{z})<0$ and $A\bar{z}=b$. The projection example has the strictly feasible point $(0,0)$. See Boyd and Vandenberghe, §§5.2.3 and 5.5.3. This hypothesis guarantees suitable multipliers, not existence of a primal minimizer.

Without regularity, necessity can fail even for convex functions: minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The sole feasible point $x=0$ is optimal, but stationarity would require $1+\lambda \cdot 0=0$. No Lagrange multiplier works. There is no strictly feasible point, and the gradient of the constraint vanishes at the answer.

The nonconvex contrast. The polynomial $h(x)=(x^2-1{)}^2+0.2x$ has derivative $h^{\prime }(x)=4x^3-4x+0.2$ and second derivative $h^{\prime \prime }(x)=12x^2-4$. Numerically solving the cubic gives stationary points $-1.024120300$, $0.050125947$, and $0.973994353$. Their objective values are respectively $-0.202440434$, $1.005006281$, and $0.197434153$, with second derivatives $8.585869$, $-3.969849$, and $7.383980$. Hence both outer points are local minima, and the middle point is a local maximum. Since $h(x)\to +\infty$ at both ends, its global minimum exists and must be one of the stationary minima: it is the left one. A method stopping at the right local minimum misses a better value by approximately $0.399874587$.

The practical appeal of convex optimization is the ability to check an answer globally using geometry and matching Lagrangian duality bounds. The projection certificate certifies every feasible alternative at once; the tilted quartic shows why a zero gradient alone cannot do that for general nonlinear optimization.

Historically, an early landmark is Kuhn and Tucker's ^[ref]. Its §3 explicitly states a regularity hypothesis for inequality-constrained Lagrange multipliers; its discussion of saddle points explains how concave functions support global conclusions for maximization. This documents an early formulation of the multiplier approach; it does not establish sole discovery of today's KKT conditions or of convex optimization as a whole.

For a convex perturbation function, defineThe primal and dual values are $p(0)$ and $q(0)$; the signed dual marginal $q$ is concave. The identity $p^{\ast }(y)=f^{\ast }(0,y)$ gives $q(0)=p^{\ast \ast }(0)$. If $p$ is proper and finite near zero, subgradients at zero prove strong duality with dual attainment. In finite dimensions the relative-interior condition $0\in \mathrm{ri}(\mathrm{dom}p)$ also suffices, provided $p(0)$ is finite. This does not itself prove primal attainment.

For finite primal and dual optimal values in a minimization problem, the duality gap is $p_{\ast }-d_{\ast }\ge 0$. Strong duality means this difference is zero.

Consider minimizing $f(x)$ over a specified domain with inequalities $g_i(x)\le 0$. Assume a primal minimizer exists and strong duality holds with an optimal nonnegative multiplier ${\lambda }^{\ast }$. Let $v(x)=\max (0,g_1(x),\dots ,g_m(x))$. For every $M>\Vert {\lambda }^{\ast }{\Vert }_1$, the exact maximum-violation penaltyhas the same minimum, and every penalized minimizer is feasible and primal optimal.

Indeed the optimal Lagrange dual function bound gives $f(x)+{\sum }_i{\lambda }_i^{\ast }{g}_i(x)\ge p^{\ast }$. Since ${\sum }_i{\lambda }_i^{\ast }{g}_i(x)\le \Vert {\lambda }^{\ast }{\Vert }_{1}v(x)$,A primal optimizer has $v=0$ and reaches $p^{\ast }$. Any infeasible point has strictly larger penalized value, proving the claim. The strict multiplier margin and zero-gap hypotheses explain why existence of an arbitrary optimal dual vector alone is insufficient.

If two nonnegative finite-valued convex functions are defined on all of a finite-dimensional space, their infimal convolution is finite, convex and continuous everywhere. Convex perturbation duality then gives strong duality and dual attainment at every argument. It does not require or imply attainment of the primal decomposition infimum.

More precisely, let $f,g:{\mathbb{R}}^n\to [0,\infty )$ be finite everywhere and write $h=f\square g$. Nonnegativity supplies a lower bound, while the two trial splits $(x,0)$ and $(0,x)$ giveMixing nearly optimal splits proves convexity, and continuity of a convex function applies because the effective domain is the entire finite-dimensional vector space. These statements concern the optimized value, rather than existence of an optimal split. For the continuity theorem and dual attainment under the equality constraint $u+v=x$, see Bertsekas, Convex Optimization Theory: A Summary, Propositions 1.3.11 and 5.3.3(a). The equality has a feasible point in the whole space for every $x$, and the displayed bound makes its optimal value finite.

A finite value without any optimal split. On $\mathbb{R}$, take the convex functions $f(u)=e^u$ and $g(v)=0$. Both are nonnegative and finite everywhere, butfor every $x$. The splits $(u,v)=(-k,x+k)$ have costs $e^{-k}\to 0$, yet the exponential function is strictly positive at every finite $u$. No split attains the infimum. The value function is even constant and differentiable; regularity of the value function does not prevent optimizing splits from escaping to infinity. For example, $k=1,3,6$ gives costs approximately $0.367879$, $0.049787$ and $0.002479$.

A sufficient extra condition for attainment at a fixed $x$ is that $u\mapsto f(u)+g(x-u)$ be a coercive function, meaning it tends to $+\infty$ as $\Vert u\Vert \to \infty$. Under the finite-valued assumptions it is a continuous function, so a sufficiently large closed ball contains a global minimum by the extreme value theorem. If this cost is also a strictly convex function, the optimal split is unique. The quadratic example above satisfies both conditions; the exponential function example does not satisfy coercivity.

Nonnegativity is sufficient, not necessary: finite lower bounds $f\ge A$, $g\ge B$ would give $h\ge A+B$ by the same argument. Removing all lower-bound control can lose finiteness even for finite convex functions: $f(u)=u$ and $g(v)=-v$ give $f(u)+g(x-u)=2u-x$, hence $h(x)=-\infty$. Nor does finiteness alone guarantee differentiability: choosing $f=g=|\cdot |$ gives $h(x)=|x|$ by the triangle inequality and the split $(x,0)$.

At a local minimum of continuously differentiable functions, a suitable constraint qualification guarantees the existence of Lagrange multipliers satisfying the KKT conditions. One sufficient local regularity assumption is that the gradients of the equality optimization constraints and the active constraints are jointly linearly independent. This assumption concerns the description of the feasible set, not just the smoothness of the objective function.^[ref]

To see why a hypothesis is needed, minimize $f(x)=x$ subject to $g(x)=x^2\le 0$. The feasible set is the singleton $\{0\}$, so $x_{\ast }=0$ is a global minimum. Yet $f^{\prime }(0)+\lambda g^{\prime }(0)=1$ for every finite Lagrange multiplier $\lambda$. Thus this convex optimization problem has an attained optimum without a KKT multiplier. The zero gradient of the active constraint has hidden the actual restriction $x=0$ from its first-order equation. Rewriting it as the equality $h(x)=x=0$ yields the unrestricted Lagrange multiplier $\mu =-1$.

For convex optimization, Slater's condition requires strict inequalities and affine equalities at a point in the relative interior of the common domain of a function. A finite optimum value then gives strong duality and dual attainment. Primal attainment and differentiability yield KKT multipliers. Affine inequalities may be nonstrict in the refined version.^[ref]

Slater's condition is sufficient, and need not hold for an optimum to exist. The singular example above also shows that mere primal attainment is not a substitute for a constraint qualification.

The Lagrange dual function is the infimum of a Lagrangian over its primal variables. It is concave in the multipliers, even before convexity of the primal problem is assumed. Maximizing it over sign-compatible multipliers gives a lower bound on a minimization problem by weak duality; appropriate convex qualifications give strong duality.

A feasible point gives an upper bound on a minimization problem's best value; a suitable Lagrange multiplier gives a lower bound. Lagrangian duality searches for the strongest bound obtainable this way. Matching bounds certify a global minimum.

Let $X$ be a nonempty decision domain on which the objective function $f$ and the constraint functions $g_i,h_j$ are finite. Write the primal problem and its optimization Lagrangian asThe inequality Lagrange multipliers obey ${\lambda }_i\ge 0$; the equality Lagrange multipliers ${\nu }_j$ are unrestricted real numbers. Define the Lagrange dual function and dual optimal value byThe inner infimum keeps $X$, but releases the displayed optimization constraints. It can be $-\infty$, giving an uninformative lower bound. A different domain changes the bound.^[ref]

Here is the entire weak duality argument. For any feasible point $z$ and allowable Lagrange multipliers,The first inequality is the definition of an infimum; the second uses ${\lambda }_i{g}_i(z)\le 0$ and $h_j(z)=0$. Taking the infimum over feasible $z$, then the supremum over allowable Lagrange multipliers, gives $d_{\ast }\le p_{\ast }$. No convexity is used.

The Lagrange dual function is a concave function, since each fixed decision makes $L$ an affine function of the Lagrange multipliers.^[ref] Explicitly, write $y=(\lambda ,\nu )$ and choose two points where $q$ is finite. For $0\le t\le 1$ and every $x\in X$,Taking the infimum over $x$ proves the defining concavity inequality. Thus even a difficult primal problem supplies a dual with useful geometry, although evaluating $q$ can itself be difficult.

For finite optimal values, strong duality means $d_{\ast }=p_{\ast }$, or zero duality gap. It need not imply dual attainment. For convex optimization, Slater's condition is a sufficient constraint qualification for both when $p_{\ast }$ is finite.^[ref] The Strong Lagrangian property requires an actual finite Lagrange multiplier achieving equality. Convex perturbation duality interprets such a bound as a supporting slope of the perturbed value function.

Linear programming duality pairs the standard maximization problemwith the minimization problemThe dual variables form nonnegative combinations of primal inequalities. If $x$ and $y$ are feasible, thenThis is weak duality, giving independently checkable bounds before any algorithm reaches an optimum.

For a feasible primal with finite optimal value, strong duality for finite-dimensional linear programs ensures attained primal and dual optima with equal values. Their objective difference decomposes into nonnegative products of variables and opposite slacks, yielding complementary slackness. The worked allocation in linear programming has primal point $(2,2)$ and dual multipliers $(2,1,0)$, both with value ten. Sign conventions change for minimization, equality rows and unrestricted variables; a dual formula belongs to its declared primal form.

Set $x_i=\log b_i$ for candidate axis-parallel box side lengths. Its coordinate-projection constraints are the displayed linear program. The dual feasible weights are fractional uniform covers. Its optimal extreme point is rational, so the uniform covers theorem forces its objective to be at least $\log |S|$. Weight one on the full coordinate set attains that value. Strong duality therefore supplies box side lengths with volume $|S|$ and no larger coordinate projections.

For a finite flow network with finite nonnegative real flow network edge capacities, the greatest strength of a flow of a feasible flow equals the least cut capacity of a source-to-sink cut of a flow network:For a maximum flow, the vertices reachable from the source in the residual network define a minimum cut whose outgoing original edges are saturated and whose incoming original edges carry zero flow.^[ref]

Why is a cut of a flow network an upper bound? Sum flow conservation on its source side $S$. Internal edge contributions cancel, leavingOnly directed edges leaving $S$ contribute to cut capacity. Directed edges entering $S$ are subtracted in net flow, so adding their capacities to the upper bound would lose the intended bottleneck. This inequality is weak duality; the theorem says the bound is attained, an instance of strong duality. Its beauty is that a routing plan and a separating boundary independently witness each other's optimality.

In the running flow network, the two internal vertices give four possible source sides. For $S=\{s\}$, the cut capacity is $c_{sa}+c_{sb}=3+2=5$. For $S=\{s,a\}$ it is $c_{sb}+c_{ab}+c_{at}=2+1+2=5$. For $S=\{s,b\}$ it is $c_{sa}+c_{bt}=3+3=6$; the incoming edge $a\to b$ contributes nothing to that cut capacity. Finally, $S=\{s,a,b\}$ gives $c_{at}+c_{bt}=2+3=5$. Thus the minimum cut has cut capacity $5$, matching the explicitly computed maximum flow.

Ford and Fulkerson's 1956 paper opens with a railway-capacity question attributed there to T. Harris and proves a minimal-cut theorem as Theorem 1. Its original formulation uses graph paths carrying nonnegative amounts; the residual reachability certificate for maximum flow below gives the finite directed flow network proof used here.^[ref]

Use Lagrange multipliers ${\alpha }_i\ge 0$ for $1-{\xi }_i-y_i(w\cdot x_i+b)\le 0$ and ${\mu }_i\ge 0$ for $-{\xi }_i\le 0$. The optimization Lagrangian isThe Lagrange dual function is the infimum over the now unconstrained primal variables. The first-order optimality conditions in $w$ and $b$ giveIf the latter equality fails, the infimum over $b$ is $-\infty$. The first-order optimality condition in ${\xi }_i$ givesSubstitution, or completing the square separately in $w$ and each ${\xi }_i$, producesprovided ${\sum }_i{\alpha }_i{y}_i=0$. For fixed nonnegative ${\alpha }_i$, this expression is maximized over ${\mu }_i\ge 0$ at ${\mu }_i=0$. Thus the simplest Lagrangian dual problem isIn particular, there is no upper box constraint ${\alpha }_i\le C$. That constraint belongs to the linear-slack penalty; squared slack instead contributes the displayed diagonal quadratic penalty. With $Y=\mathrm{diag}(y_1,\dots ,y_m)$ and Gram matrix $G_{ij}=x_i\cdot x_j$, the objective can also be writtenSince $G$ is positive semidefinite and $C>0$, the matrix in parentheses is positive-definite. The objective of the Lagrangian dual problem is therefore strictly concave, and the feasible maximizer is unique.

The primal problem is a convex optimization problem, and $w=0,b=0,{\xi }_i=2$ is strictly feasible for both families of inequalities. Slater's condition gives strong duality, so an optimum of the Lagrangian dual problem yields a primal optimum. The Karush-Kuhn-Tucker conditions supplyFor any $i$ with ${\alpha }_i>0$, the intercept is consequentlyAll such choices agree at an exact optimum. If all labels have one sign, the optimal coefficients can all be zero: choose $w=0$, $\xi =0$, and any constant intercept of that sign with magnitude at least one.

Regard the two kinds of agents as the two sides of a complete bipartite graph, with edge weight $c_{ij}$. Pairing everyone is a perfect matching, and its maximum total weight is $P$. Consider the capacitated linear programIt is feasible and bounded. Every optimum has all row and column sums equal to one: otherwise the equal total deficits of the two sides give a row $i$ and column $j$ both below one. Increasing $x_{ij}$ by the smaller of their positive deficits remains feasible and increases the objective because $c_{ij}>0$, a contradiction.

Thus an optimum is a doubly stochastic matrix. By the Birkhoff-von Neumann theorem it is a convex combination of permutation matrices, so at least one corresponding perfect matching has weight at least its objective. Conversely every such perfect matching gives a feasible matrix. Hence $P_{\mathrm{LP}}=P$. One way to justify the decomposition is to apply Hall's marriage theorem to the positive-entry support, subtract the smallest entry on a supported perfect matching, and repeat after rescaling the nonzero remainder; each subtraction removes a positive entry, so the process terminates.

The dual linear program assigns nonnegative dual variables $p_i,q_j$ to the row and column capacity constraints:These are exactly the permitted payments and all the pairwise acceptance conditions, so its optimal value is $Q$. It is feasible, for example by taking $p_i={\max }_j{c}_{ij}$ and $q_j=0$. Strong duality now gives $P=P_{\mathrm{LP}}=Q$. In particular, the nonnegative payment restriction has been retained throughout; using capacity inequalities rather than equality constraints avoids introducing unrestricted prices.

For a direct weak duality check, sum $p_i+q_{\pi (i)}\ge c_{i,\pi (i)}$ over any pairing $\pi$. Its revenue never exceeds the company's total offered payment. The linear programming duality and integrality argument prove that this lower bound on payments is attained.

For fixed $y$, $s=c-A^{T}y$ is fixed. The relaxed inequality and $\theta \ge 0$ say preciselyThe objective $b^{T}y-\theta$ strictly decreases with $\theta$, so its best choice is always equality. Replacing any feasible relaxed point by that choice preserves feasibility and improves or leaves unchanged the objective. Conversely every point satisfying equality is feasible for the relaxed problem. Thus the two dual formulations have the same optimal value and the same optimal $y,s$, with equality at any optimizer.

This algebraic equivalence in fact does not require Slater's condition. Under the stipulated condition, strong duality additionally identifies their attained optimum with the primal optimum. With $Q^{-1/2}s$ as a linear coordinate, the relaxed constraint is $\Vert Q^{-1/2}s{\Vert }_2\le \theta$, so the relaxed formulation is a second-order cone program.