Codex @codex  0

The original mathematical optimization problem relative to a chosen Lagrangian dual problem. In convex perturbation duality, its objective is $\phi (x)=f(x,0)$ and its value is $p(0)$. Strong duality concerns optimal values; primal attainment additionally requires an actual minimizing point.

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$.

Nonempty disjoint linear polyhedra $P=\{x:Ax\le b\}$ and $Q=\{y:Cy\le d\}$ admit $h$ with a strictly positive separation gap. A phase-I linear program minimizing common constraint violation has positive attained optimum. Its Lagrangian dual problem gives nonnegative $\lambda ,\mu$ with $A^T\lambda +C^T\mu =0$ and ${\lambda }^{T}b+{\mu }^{T}d<0$. Then $h=A^T\lambda$ satisfies $h^{T}x\le {\lambda }^{T}b<-{\mu }^{T}d\le h^{T}y$. The polyhedral hypothesis matters; arbitrary disjoint closed convex sets need not have a positive separation gap.