Why must Lagrange multipliers for inequality constraints be non-negative?

Question

In this question about whether Lagrange multipliers can be negative, the top comment states the following:

The Lagrange multipliers for enforcing inequality constraints are non-negative. The Lagrange multipliers for equality constraints can be positive or negative depending on the problem and the conventions used.

Why must multipliers be non-negative in the inequality case?

Answer 1

An inequality constrained problem \begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & f(x) \\ & \text{subject to} & & g_i(x) \leq 0, \; i = 1, \ldots, m. \end{aligned}\tag{ICP} \end{equation*} can be written as an equality constraint one

\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & f(x) \\ & \text{subject to} & & g_i(x) = 0, \; \forall j \in \mathcal{A}(x^*) \end{aligned}\tag{ECP} \end{equation*} where $\mathcal{A}(x) = \{ i \colon g_i(x) = 0\}$ is the set of active inequality constraints. For the ECP we have from the First Order Optimality conditions that of $x^*$ is regular, there exist unique Lagrange multipliers $\mu_j^*$ with $j\in\mathcal{A}(x^*)$ such that

$$\nabla f(x^*) + \sum_{j\in\mathcal{A}(x^*)}\mu_j^*\nabla g_j (x^*) = 0.\tag{1}$$ Assigning zero Lagrange multipliers to the inactive constraints, we obtain $$\nabla f(x^*) + \sum_{j=1}^r\mu_j^*\nabla g_j (x^*) = 0\tag{2}$$ with $$\mu_j^*=0 \quad \forall j \notin \mathcal{A}(x^*).\tag{3}$$

Then, define $g_j^+(x) = \max \{0, g_j(x) \}$ which is continuously differentiable function with $\nabla g_j^+(x) = 2 g_j^+(x)\nabla g_j(x)$. Also, define the penalized problem

\begin{equation*} \begin{aligned} & \underset{x}{\text{minimize}} & & F^k(x) \stackrel{\Delta}{=} f(x) + \frac{k}{2} \sum_{j=1}^r (g_j^+(x))^2 + \frac{\alpha}{2} \|x - x^*\|^2 \\ & \text{subject to} & & x \in \mathcal{S} \end{aligned}\tag{PP} \end{equation*} where $\mathcal{S} = \{x \colon \|x - x^*\| \leq \epsilon \}$ and $\epsilon > 0$. From the first order necessary condition we have for sufficiently large $k$ that

$$0 = \nabla F^k (x^k) = \nabla f(x^k) + kg_j^+(x)\nabla g_j(x) + a (x^k -x^*).\tag{4}$$ Ficebn that $x^*$ is regular, we have that $\nabla g_j(x)$ ghas rank $r$ and we can write

$$kg_j^+(x^k) = - \left(\nabla g_j(x^k)^T\nabla g_j(x^k)\right)^{-1}\nabla g_j(x^k)^T \left(\nabla(x^k) + \alpha (x^k -x^*)\right)\in \mathbb{R}.\tag{5}$$ By taking the limit as $k \to \infty$ and $x^k \to x^*$ we see that $\{kg_j^+(x^k)\}$ converges to

$$\mu_j^* = -\nabla g_j(x^*)^T\nabla g_j(x^*)^{-1}\nabla g_j(x^*)^T \nabla f(x^*)\tag{6}$$. The latter can also be written as

$$\mu_j^* = \lim_{k \to \infty} kg_j^+(x^k).\tag{7}$$ By taking the limit as $k\to \infty$ in $(4)$ we have

$$\nabla f(x^*) + \nabla g (x^*)\mu_j^* = 0 \tag{8}$$ proving the first order optimality condition for problem $(PP)$. Using this along with the fact that $g_j^{+} (x^k)\geq 0$ in $(6)$ we get that $\mu_j^* \geq 0$.

Answer 2

The proof I know comes from the KMT conditions, and uses the Gordan's theorem that states the following

Given a $m\times n$ matrix, then one and only one of the following has solution

There exists some $x\in\mathbb{R^n}$ such as $Ax<0$

There exists some $y\in\mathbb{R^m}$ such as $A^{t}y=0$ and $0\leq y$, $y\not=0$.

The KKT conditions are proven from the Fritz-John's conditions and use the lemma. So te positivity of multipliers come from the second solution to the system because $Ax<0$ never holds.