Are KKT points necessarily saddle points of the Lagrangian?

Question

Consider this simple toy example of an optimization problem using the method of KKT-multipliers:

minimize $3x$ s.t. $x\le3, x\ge-1$

This gives us the following Lagrangian: $L(x,u,v)=3x+u(-x-1)+v(x-3)$.

Obviously, the optimal solution $x^*=-1$, which corresponds to KKT point (-1,3,0). This nullifies the partial of L w respect to $x$ i.e. $\nabla_xL =3-u+v = 3-3+0=0$. It also obviously fulfills the other KKT criteria (primally and dually feasible, complementary slackness).

However, since there is no x that can both fulfill $-x-1=0$ and $x-3=0$, (the partials with respect to the KKT multipliers) the full $\nabla L$ can never be zero and there can be no stationary and thus no saddle point of the Lagrangian. Yet many sources, including wikipedia talk about KKT points in relation to saddle points. For example: https://en.wikipedia.org/wiki/Karush–Kuhn–Tucker_conditions (The main theorem and the introductary sentences mentioning "saddle-point-theorem".

https://sites.math.washington.edu/~burke/crs/516/notes/saddlepoints.pdf states

Conversely, if ̄x is a solution to P at which the Slater C.Q. is satisfied, then there is a ̄y ∈K such that ( ̄x, ̄y) is a saddle point for L

Slater's conditions is obviously fulfilled for this problem, since every involved function is affine and there exists a strictly feasible x.

Where am I going wrong?

Am I confused about KKT multipliers or is saddle point simply meant to mean "stationary w.r.t x" in this context?

Answer 1

The part of the saddle point that is confusing you is: $$ L(x^*,u^*,v^*) \ge L(x^*,u,v) $$ for all $u\ge0$, $v\ge0$. These inequality constraints on the multipliers to inequality constraints need to be taken into account.

This saddle point property is true for your case: $$ L(x^*,u,v) = 3x^*+u(−x^*−1)+v(x^*−3) = -3 -4v. $$ (for $x^*=-1$). This is maximal over non-negative $u,v$ if $v=0$.

Answer 2

The KKT point is only a saddle point of the unconstrained Lagrangian when there are no inequality constraints.

When there are inequality constraints, the KKT is a saddle point of the Lagrangian subject to the dual feasibility constraints (in your case, $u\geq 0$ and $v\geq 0$).

In your case, the point $(x,u,v) = (-1,3,0)$ is a saddle point in this sense (the gradient, projected onto the feasible set, is zero; and the Lagrangian increases in the $(-1,1,0)$ direction and decreases in the $(1,1,0)$ direction.)