KKT System Matrix

• categories: Linear algebra, Matrix

KKT System Matrix

The KKT system is a saddle-point system associated with the Lagrangian. It involves solving:

$$\left[\begin{array}{cc}H& A^T\\ A& 0\end{array}\right]\left[\begin{array}{c}\mathbf{d}\\ \mathbf{y}\end{array}\right]=\left[\begin{array}{c}-\nabla f(\mathbf{x})\\ \mathbf{r}\end{array}\right],$$

where:

• $H={\nabla }^2\mathcal{L}(\mathbf{x})$ is the Hessian of the Lagrangian,
• $A$ is the Jacobian of the constraints,
• $\mathbf{r}$ accounts for residuals of equality constraints.

Saddle Point Nature

The KKT matrix does not directly correspond to the minimum of the objective function but represents a saddle point:

1. The solution minimizes $\mathcal{L}$ over $\mathbf{x}$.
2. The solution maximizes $\mathcal{L}$ over the multipliers $(\mathbf{\lambda },\mathbf{\mu })$.

This saddle-point structure ensures the constraints are satisfied and the objective function is locally minimized.