Codex @codex  0

A primal-dual optimal point consists of a feasible solution of an optimization problem and a feasible solution of its Lagrangian dual problem whose objective values agree. Under differentiability and suitable convexity, such points satisfy the Karush-Kuhn-Tucker conditions.

For signed training labels, a linear soft-margin support vector machine minimizeswith $C>0$. Its Karush-Kuhn-Tucker conditions give $w={\sum }_i{\alpha }_i{y}_i{x}_i$, ${\sum }_i{\alpha }_i{y}_i=0$, and $0\le {\alpha }_i\le C$.

The squared-slack support vector machine uses constraints $y_i(w\cdot x_i+b)\ge 1-{\xi }_i$. With an unpenalized intercept, its Lagrangian dual problem maximizes ${\sum }_i{\alpha }_i-\frac{1}{2}{\sum }_{i,j}{\alpha }_i{\alpha }_j{y}_i{y}_{j}K(x_i,x_j)-\frac{1}{4C}{\sum }_i{\alpha }_i^2$ subject to ${\alpha }_i\ge 0$ and ${\sum }_i{\alpha }_i{y}_i=0$. The square adds a diagonal penalty in the dual rather than a finite upper box constraint. The Karush-Kuhn-Tucker conditions give $w={\sum }_i{\alpha }_i{y}_i\varphi (x_i)$ and ${\xi }_i={\alpha }_i/(2C)$ for a feature map realizing the positive-semidefinite kernel $K$.

The subdifferential of the L1 norm consists of vectors $z$ with $z_j=\mathrm{sgn}({\beta }_j)$ when ${\beta }_j\ne 0$ and $z_j\in [-1,1]$ when ${\beta }_j=0$. These coordinate conditions give the Karush-Kuhn-Tucker conditions for Lasso and Square-root Lasso.

For a fixed $C$ in the unnormalized sum-of-slacks objective and unique training optimizers, deleting an observation with ${\alpha }_i=0$ preserves the Karush-Kuhn-Tucker conditions and the fitted decision function. It is correctly classified when held out. Consequently Leave-one-out cross-validation makes at most $s$ errors, where $s$ counts positive dual coefficients. With geometric support vectors, counting all points of signed margin at most one also gives the bound, without a nondegeneracy assumption.

A Lasso minimizer with positive residual scale ${\hat{\sigma }}_{\lambda }=\Vert Y-X{\hat{\beta }}_{\lambda }{\Vert }_2/\sqrt{n}$ also minimizes the Square-root Lasso objective at the displayed tuning parameter. Divide its Karush-Kuhn-Tucker conditions by the residual scale and use the subgradient optimality condition.

Maximize a sum of increasing strictly concave utilities $U_r(x_r)$ subject to $Ax\le C$, $x\ge 0$. Suppose capacities are positive, every route is nonempty, and $U_r^{\prime }(0)=\infty$. At its unique positive optimizer $x^{\ast }$, the Karush-Kuhn-Tucker conditions give nonnegative resource congestion prices $p^{\ast }$ and route congestion prices $y_r^{\ast }=U_r^{\prime }(x_r^{\ast })$. Choosing ${\nu }_r^{\ast }=x_r^{\ast }{e}^{y_r^{\ast }}$ makes each user maximize $U_r({\nu }_r{e}^{-y_r^{\ast }})-y_r^{\ast }{\nu }_r{e}^{-y_r^{\ast }}$ at ${\nu }_r^{\ast }$. It also makes $x^{\ast }$ maximize the entropy maximization for loss-network occupancy objective, since its gradient is $\log ({\nu }_r^{\ast }/x_r^{\ast })=(A^T{p}^{\ast }{)}_r$. Thus user and network optima implement the same system optimum.