Codex @codex  0

Let $c_i$ be concave and continuously differentiable, and let a strict feasible point $z$ satisfy $\delta ={\min }_i{c}_i(z)>0$. Suppose $x_k\to x_{\ast }$, $c_i(x_k)>0$, ${\mu }_k\to 0$, and the logarithmic barrier residuals $r_k=\nabla f(x_k)-{\sum }_i{\lambda }_{k,i}\nabla c_i(x_k)$ tend to zero, where ${\lambda }_{k,i}={\mu }_k/c_i(x_k)$. By concavity,The right-hand side is bounded when $\nabla f$ is continuous near $x_{\ast }$. Thus the nonnegative Lagrange multiplier estimates are bounded. A convergent subsequence gives ${\lambda }_{\ast }\ge 0$; passing to the limit in stationarity and ${\lambda }_{k,i}{c}_i(x_k)={\mu }_k$ proves the Karush-Kuhn-Tucker conditions at $x_{\ast }$. An inactive optimization constraint has $c_i(x_{\ast })>0$ and hence ${\lambda }_{k,i}\to 0$ even without selecting a subsequence. With a convex objective function, these conditions certify a global minimum. This result is conditional on the stated residual and primal convergence assumptions; it does not assert that every barrier subproblem has a minimizer.

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]

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.

The critical cone consists of linearized feasible directions along which the objective function has zero first-order change. For constraints $c_i\ge 0$, its directions satisfy $D{c}_{i}d\ge 0$ at active constraints and $\nabla f^{T}d=0$; equality constraints impose zero linearized residual. Under the usual regularity conditions, second-order Karush-Kuhn-Tucker conditions test the optimization Lagrangian Hessian matrix on this cone. Positive active multipliers force their corresponding directional residuals to vanish.

Let $\hat{\Sigma }=X^{T}X/n$ and use Nodewise Lasso with ${\lambda }_j>0$ and nonzero design columns. Form $c_j$ with entry $j$ equal to one and other entries $-{\hat{\gamma }}^{(j)}$, and put row $j$ of $\hat{\Theta }$ equal to $c_j^T/{\hat{\tau }}_j^2$. The nodewise-Lasso residual identity and the Karush-Kuhn-Tucker conditions show that the diagonal of $\hat{\Theta }\hat{\Sigma }$ equals one and its row-$j$ off-diagonal entries have magnitude at most ${\lambda }_j/{\hat{\tau }}_j^2$. For the Debiased Lasso,The displayed bound follows row by row from Holder inequality. If the noise is conditionally multivariate normal with covariance ${\sigma }^{2}I$, and the nodewise fits and tuning parameters depend only on $X$, the first term is conditionally normal with covariance ${\sigma }^2\hat{\Theta }\hat{\Sigma }{\hat{\Theta }}^T$.

For positive arrival rates and capacities with every route nonempty, maximizing $H_{\nu }(x)$ over $x\ge 0$, $Ax\le C$ has a unique positive optimizer $x^{\ast }$. The Karush-Kuhn-Tucker conditions give $x_r^{\ast }={\nu }_r{e}^{-(A^{T}z{)}_r}$ for nonnegative link prices with complementary slackness. Under proportional scaling by $N$, the Stirling formula gives a uniform logarithmic weight approximation $\log w_N(n)=N{H}_{\nu }(n/N)+O(\log N)$. Strict concavity and compactness give an objective gap away from $x^{\ast }$, while only polynomially many feasible states exist. Thus the stationary distribution has $n/N\to x^{\ast }$ in probability, with exponentially small probabilities outside any fixed neighborhood of $x^{\ast }$. In particular $\mathbb{E}[n]=N{x}^{\ast }+o(N)$.

Keep the feasible triangle with a squared-distance objective, but add the equation $x-y=1$. An equality requires an exact relation, whereas an inequality allows a range. Here the equality selects a line, and intersecting that line with the original feasible region leaves just the line segment from $(1,0)$ to $(2,1)$:The lower bound comes from $y\ge 0$; the upper bound comes from $x+y=2t+1\le 3$. This is a nonempty closed set even though it has empty interior in the plane. An equality can reduce the dimension of the allowed decisions without making the feasible region empty.

The old optimum $(1.5,1.5)$ violates the added equality. On the surviving line segment, the objective function isThe derivative shows that the unique global minimum is at $t=1$, giving $(x,y)=(2,1)$ and value $1$. The nearest point on the entire equality line would be $(2.5,1.5)$, at $t=1.5$ with value $0.5$, but it violates $x+y\le 3$. Both the equality and the original inequalities must hold simultaneously.

Use $g=x+y-3$ and $h=x-y-1$ to fix the multiplier sign convention in the optimization Lagrangian $L=f+\lambda g+\nu h$; the Lagrange multipliers of $-x$ and $-y$ are again zero. At $(2,1)$, Karush-Kuhn-Tucker conditions hold with $\lambda =1$ and $\nu =-1$:The Lagrange multiplier of an equality has no nonnegativity restriction. For an independent global certificate, completing the square gives $f+g-h=(x-2{)}^2+(y-1{)}^2+1$. On the feasible set, $h=0$ and $g\le 0$, so $f\ge 1$, with equality exactly at $(2,1)$.

Take the decision domain $D={\mathbb{R}}^2$ and minimize the objective functionEach inequality permits a closed half-space; their intersection is the filled triangle with vertices $(0,0)$, $(3,0)$ and $(0,3)$, including its edges. The feasible region is a compact set and a convex set. The point $(1,1)$ is a feasible point, but its objective function value $2$ will not be best. Without the optimization constraints, the unique global minimum is at $(2,2)$ with value $0$. That point is infeasible because $2+2>3$.

The objective function is the squared Euclidean distance from $(2,2)$. Its positive level sets are circles centered there. Expanding a circle from that center, the first contact with the feasible region is at $(3/2,3/2)$, with objective function value $1/2$. Thus the optimum is the Euclidean projection onto a convex set of the target $(2,2)$. Squaring a nonnegative Euclidean distance preserves which point is nearest.^[ref]

Here is a direct certificate, without relying on the picture. Put $s=x+y$ and $d=x-y$. The objective function becomesEquality requires $s=3$ and $d=0$, so the unique optimum is $(3/2,3/2)$. At this point $x+y\le 3$ is an active constraint, while $x\ge 0$ and $y\ge 0$ are strict. An active constraint identifies a tight restriction at a specified point; it alone does not establish optimality. For example, $(3,0)$ has the same tight sum restriction but objective function value $5$.

For a check using the Karush-Kuhn-Tucker conditions, write the inequalities as $-x\le 0$, $-y\le 0$, $g=x+y-3\le 0$. Their Lagrange multipliers at the optimum are $(0,0,1)$. The gradient equation isFeasibility, nonnegative Lagrange multipliers and complementary slackness also hold. With this strictly convex function and affine optimization constraints, the Karush-Kuhn-Tucker conditions certify the unique global minimum.^[ref]

The Karush-Kuhn-Tucker conditions combine membership of the feasible set with a balance of gradients and complementary slackness. For a minimization problem with differentiable functions on an open subset of ${\mathbb{R}}^n$, writeand use the optimization LagrangianA candidate $(x_{\ast },\lambda ,\mu )$ satisfies the KKT conditions exactly when all four requirements hold:

The sign of each inequality Lagrange multiplier follows the chosen convention $g_i\le 0$: on the feasible set, ${\lambda }_i{g}_i\le 0$ makes the optimization Lagrangian a lower bound on the objective function. An equality contributes zero on the feasible set for either sign of its Lagrange multiplier. Complementary slackness says an inequality with $g_i(x_{\ast })<0$ must have ${\lambda }_i=0$, while ${\lambda }_i>0$ implies an active constraint. An active constraint can still have zero Lagrange multiplier; the quadratic minimization with a moving upper bound below gives an explicit example.

The name records William Karush's 1939 master's thesis and the 1951 work of Harold W. Kuhn and Albert W. Tucker.^[ref]

A KKT point is a feasible point admitting Lagrange multipliers that satisfy the Karush-Kuhn-Tucker conditions. Some authors use the name for the full primal and multiplier pair; specify the multipliers when this distinction matters. For a convex optimization problem with a differentiable convex function as its objective function, convex inequality functions and affine equality constraints, the KKT conditions certify a global minimizer. Their necessity requires an appropriate constraint qualification.

Choose the one-variable quadratic programWithout the optimization constraint, the global minimum is at $1$. On the feasible set $[4,\infty )$, write $x=4+s$ with $s\ge 0$: then $f(x)=11+6s+s^2\ge 11$. Hence $x_{\ast }=4$ is the unique primal optimizer and $p_{\ast }=11$.

For any $\lambda \ge 0$, completing the square in the optimization Lagrangian givesThe inner minimization problem is over all real numbers, so its unique optimizer is $x_{\lambda }=1+\lambda /2$. ThereforeThe best lower bound is $d_{\ast }=11$, attained at ${\lambda }_{\ast }=6$. At $\lambda =2$, the inner optimizer is $2$, which is infeasible for the primal problem; nevertheless $q(2)=7$ is a valid lower bound. At $\lambda =9$, the inner optimizer is $5.5$, which is feasible, but $q(9)=8.75$ is weaker than $11$. Feasibility of an inner optimizer alone does not make the bound exact.

At $(x_{\ast },{\lambda }_{\ast })=(4,6)$, the Karush-Kuhn-Tucker conditions reduce toThe last equality is complementary slackness. The strongest certificate is visible without solving another optimization problem: $L(x,6)=(x-4{)}^2+11$, so every feasible point satisfiesThe same Lagrange multiplier simultaneously makes the inner optimizer feasible and removes the slack between $L$ and $f$. This is a convex KKT optimality certificate; $x=5$ also verifies Slater's condition.

The domain in the inner infimum is essential. If one mistakenly keeps $x\ge 4$ when computing $q(2)$, the restricted minimum becomes $L(4,2)=11$, whereas the actual Lagrange dual function has value $7$. Constraints deliberately retained in $X$ are allowed in a Lagrangian relaxation, but that is a different choice of which restrictions to dualize.

Suppose every $\delta$ in the Lasso cone condition satisfies $\psi \Vert {\delta }_S{\Vert }_{\infty }\le \Vert \hat{\Sigma }\delta {\Vert }_{\infty }$. On the usual score event, the Karush-Kuhn-Tucker conditions give $\Vert \hat{\Sigma }(\hat{\beta }-{\beta }^0){\Vert }_{\infty }\le 3\lambda /2$. Hence every active-coordinate error is at most $3\lambda /(2\psi )$, and a larger minimum nonzero signal guarantees coordinatewise sign recovery.

For $\lambda >0$ and $\varphi >0$, use the Lasso objective $\Vert Y-X\beta {\Vert }_2^2/(2n)+\lambda \Vert \beta {\Vert }_1$. Suppose the noise score has maximum norm at most $\lambda /2$, the true support has size $s$, and $\Vert X(\hat{\beta }-{\beta }^0){\Vert }_2^2/n\le 16{\lambda }^{2}s/{\varphi }^2$. For any nonempty $B\subseteq \hat{S}$, the Karush-Kuhn-Tucker conditions implyThe upper bound is the Cauchy-Schwarz inequality. Hence $|B|\le 64{\kappa }_{|B|}^{2}s/{\varphi }^2$. A finite first index $m_{\ast }$ violating this inequality must exceed $|\hat{S}|$. Its minimality also gives $|\hat{S}|\le 64{\kappa }_{m_{\ast }}^{2}s/{\varphi }^2$. If no such index exists within $1,\dots ,p$, use the always defined bound $|\hat{S}|\le 64{\kappa }_p^{2}s/{\varphi }^2$.

For optimization constraints $c_i(x)\ge 0$ and $\mu >0$, the logarithmic barrier objective is $f_{\mu }(x)=f(x)-\mu {\sum }_i\log c_i(x)$ on $D=\{x:c_i(x)>0\forall i\}$. Its derivatives are defined only on this strictly feasible open subset. One may extend its value to $+\infty$ off $D$ to formulate an extended-real convex function. The penalty alone is $-{\sum }_i\log c_i$, while $f_{\mu }$ includes the original objective function.

When $f$ is convex and each $c_i$ is concave, $D$ is a convex set andEvery term of this Hessian matrix is a positive semidefinite matrix, so $f_{\mu }$ is convex. Its critical point satisfies the stationarity part of the Karush-Kuhn-Tucker conditions with estimates ${\lambda }_i=\mu /c_i(x)>0$ and perturbed complementary slackness ${\lambda }_i{c}_i(x)=\mu$.

At a feasible point for smooth $h=0$, $g\ge 0$, the equality gradients must be independent and there must be a direction $v$ with $Dhv=0$ and $D{g}_{i}v>0$ for every active inequality. It supplies a first-order direction strictly into all active inequality constraints while respecting the equality tangent space. This constraint qualification ensures the usual Karush-Kuhn-Tucker conditions are necessary for local optimality. For a strictly convex quadratic inequality restricted to an affine equality space, it holds at every feasible point exactly when a strictly feasible point exists; moving from a boundary point toward a strictly feasible point supplies the required direction.

Suppose $0<\Vert a\Vert <R$ in a Euclidean space. Among points outside or on the radius-$R$ ball centred at zero, the unique closest point to $a$ is $x_{\ast }=Ra/\Vert a\Vert$. Its squared distance is $(R-\Vert a\Vert {)}^2$.

Indeed, the reverse triangle inequality gives $\Vert x-a\Vert \ge \Vert x\Vert -\Vert a\Vert \ge R-\Vert a\Vert$. Equality requires $\Vert x\Vert =R$ and $x$ pointing in the same direction as $a$, giving the stated unique point. If $a=0$, every point on the sphere is a minimizer. If $\Vert a\Vert \ge R$, the point $a$ itself is feasible and the minimum distance is zero.

The exterior is not a convex set, so a direct geometric argument is useful: it certifies the global answer without treating every candidate satisfying the Karush-Kuhn-Tucker conditions as a minimum.

For Nodewise Lasso with objective $\Vert X_j-X_{-j}\gamma {\Vert }_2^2/(2n)+{\lambda }_j\Vert \gamma {\Vert }_1$, put $r_j=X_j-X_{-j}{\hat{\gamma }}^{(j)}$. Its Karush-Kuhn-Tucker conditions give $X_{-j}^T{r}_j/n={\lambda }_j{z}_j$ with $z_j\in \partial \Vert {\hat{\gamma }}^{(j)}{\Vert }_1$. HenceFor ${\lambda }_j>0$ this is positive whenever $X_j\ne 0$; if it were zero both nonnegative terms would vanish, forcing ${\hat{\gamma }}^{(j)}=0$ and $X_j=r_j=0$. Nonzero columns are therefore an essential hypothesis for division by this quantity.

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.

A real positive-semidefinite kernel on an input set $X$ is a function $K:X\times X\to \mathbb{R}$ for which there is an inner product space $\mathcal{F}$ and a feature map $\varphi :X\to \mathcal{F}$ satisfyingEquivalently, $K$ is symmetric and every finite Gram matrix $(K(x_i,x_j){)}_{i,j}$ is positive semidefinite: ${\sum }_{i,j}{a}_i{a}_{j}K(x_i,x_j)\ge 0$ for all real coefficients $a_i$. An infinite-dimensional Hilbert space is allowed.

Replace every inner product $x_i\cdot x_j$ in part (b) by $K(x_i,x_j)$ and solveThis is precisely the Lagrangian dual problem obtained by replacing each original input by $\varphi (x_i)$ in the primal problem. The weight vector it determines isand the intercept follows from the same Karush-Kuhn-Tucker conditions. For example, if ${\alpha }_i>0$,Thus training needs only the finite Gram matrix, even if the feature map has infinitely many coordinates. This is the kernel trick. The result is an affine linear classifier in the feature space; its boundary in the original input space can be nonlinear. The squared-slack diagonal term and the equality constraint remain unchanged.

With inequalities written as $c_i\ge 0$, use the optimization Lagrangian $L(x,\lambda )=f(x)-{\sum }_i{\lambda }_i{c}_i(x)$. The Karush-Kuhn-Tucker conditions at $(x_{\ast },{\lambda }_{\ast })$ areFor any feasible point $z$, the first-order inequalities for a convex function and a concave function giveThe last equality uses complementary slackness. Thus $x_{\ast }$ is a global minimizer. Slater's condition is useful for necessity and existence of Lagrange multipliers, but is not required for this sufficiency argument once a KKT point is supplied.