I am studying constrained optimization, and I am a bit confused by the Non Degenerate Constraint Qualification (NDCQ), its intuition and application. First, I would like to put the theorem of constrained optimization, in which the NDCQ is stated. Then I will describe my question.
Background Information
Theorem$\space\space\space\space$ Suppose that $f, g_1, \dots, g_k, h_1, \dots, h_m$ are $C^1$ functions of $n$ variables. Suppose the $\mathbf{x^*} \in \mathbb{R}^n$ is a local maximizer of $f$ on the constraint set defined by the $k$ inequalities and $m$ equalities: \begin{equation} g_1(x_1, \dots, x_n) \leq b_1, \dots, g_k(x_1, \dots, x_n) \leq b_k, \\ h_1(x_1, \dots, x_n) = c_1, \dots, h_m(x_1, \dots, x_n) = c_m. \end{equation} Without loss of generality, we can assume that the first $k_0$ inequality constraints are binding (i.e., the equality holds) at $\mathbf{x^*}$ and that the other $k - k_0$ inequity constraints are not binding (i.e., the strict inequality holds). Suppose that the following Non-Degenerate Constraint Qualification (NDCQ) is satisfied at $\mathbf{x^*}$:
$\space\space\space\space$ The rank at $\mathbf{x^*}$ of the Jacobian matrix of the equality constraints and the binding inequality constraints \begin{equation} \begin{pmatrix} \frac{\partial g_1}{\partial x_1}(\mathbf{x^*}) & \cdots & \frac{\partial g_1}{\partial x_n}(\mathbf{x^*}) \\ \vdots & \ddots & \vdots \\ \frac{\partial g_{k_0}}{\partial x_1}(\mathbf{x^*}) & \cdots & \frac{\partial g_{k_0}}{\partial x_n}(\mathbf{x^*}) \\ \frac{\partial h_1}{\partial x_1}(\mathbf{x^*}) & \cdots & \frac{\partial h_1}{\partial x_n}(\mathbf{x^*}) \\ \vdots & \ddots & \vdots \\ \frac{\partial h_m}{\partial x_1}(\mathbf{x^*}) & \cdots & \frac{\partial h_m}{\partial x_n}(x^*) \end{pmatrix} \end{equation} is $k_0 + m$ -- as large as it can be.
$\space\space\space\space$ Then, form the Lagrangian \begin{equation} L(x_1, \dots, x_n, \lambda_1, \dots, \lambda_k, \mu_1, \dots, \mu_m) \\ \equiv f(\mathbf{x}) - \lambda_1[g_1(\mathbf{x}) - b_1] - \cdots - \lambda_k[g_k(\mathbf{x}) - b_k] - \mu_1[h_1(\mathbf{x}) - c_1] - \cdots - \mu_m[h_m(\mathbf{x}) - c_m]. \end{equation} Then, there exist multipliers $\lambda_{1}^{*}, \dots, \lambda_{k}^{*}, \mu_{1}^{*}, \dots, \mu_{m}^{*}$ such that:
$\space\space\space\space$ $(a)\space\space \frac{\partial L}{\partial x_1}(\mathbf{x^*}) = 0, \dots, \frac{\partial L}{\partial x_n}(\mathbf{x^*}) = 0,$
$\space\space\space\space$ $(b)\space\space \lambda_{1}^{*}[g_1(\mathbf{x^*}) - b_1] = 0, \dots, \lambda_{k}^{*}[g_k(\mathbf{x^*}) - b_k] = 0,$
$\space\space\space\space$ $(c)\space\space h_1(\mathbf{x^*}) = c_1, \dots, h_m(\mathbf{x^*}) = c_m,$
$\space\space\space\space$ $(d)\space\space \lambda_{1}^{*} \geq 0, \dots, \lambda_{k}^{*} \geq 0,$ and
$\space\space\space\space$ $(e)\space\space g_1(\mathbf{x^*}) \leq b_1, \dots, g_k(\mathbf{x^*}) \leq b_k.$
Here is a statement of checking the NDCQ:
When checking the NDCQ, if none of the critical point of $\mathbf{h} = (h_1, \dots, h_m)$ (i.e., the point that can make the rank of the Jacobian matrix of the equality constraints and the binding inequality constraints less than $k_0 + m$) lies in the constraint set, then we proceed to form the Lagrangian and solve the F.O.C.
If the constraint set does contain critical points of $\mathbf{h} = (h_1, \dots, h_m)$, then we include these points among our candidates for a solution to the original constrained maximization problem, along with the critical points of the Lagrangian.
Here is an example of solving a constrained optimization problem by the above theorem. I omitted the steps of forming the Lagrangian and solving F.O.C., because that is not where I have problem. It is the NDCQ that I feel confused.
Example$\space\space\space\space$ Consider the maximization problem: \begin{equation} Max\space\space\space\space f(x, y, z) = xyz\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\\ s.t.\space\space\space\space\space g_1(x, y, z) \equiv x + y + z \leq 1\space\\ g_2(x, y, z) \equiv -x \leq 0\\ g_3(x, y, z) \equiv -y \leq 0\\ g_4(x, y, z) \equiv -z \leq 0 \end{equation} Check the NDCQ: The Jacobian of the constraint functions is \begin{equation} \begin{pmatrix} 1 & 1 & 1\\ -1 & 0 & 0\\ 0 & -1 & 0\\ 0 & 0 & -1 \end{pmatrix}. \end{equation} Any $3 \times 3$ submatrix of it has rank 3, any $2 \times 3$ submatrix of it has rank 2, and there is no zero row. Since at most three of the four constraints can be binding at any one time, the NDCQ holds at any solution candidate.
My Question:
(1) What is the intuition of checking the NDCQ? According to the statement above, it seems to me that checking the NDCQ is for examining the cases where the optima is not a critical point of the Lagrangian. Could someone please provide an intuitive explanation for this?
(2) What if the number of binding constraints is bigger than the number of variables? How should I proceed my argument then? The NDCQ stated in the above Theorem implies that the number of equality constraints and binding inequality constraints must be less than or equal to the number of variables (i.e., $k_0 + m \leq n$). But this might not be always satisfied. For instance, consider the following example:
Example$\space\space\space\space$ Consider the maximization problem: \begin{equation} Max\space\space\space\space f(x, y)\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\\ \space \space s.t.\space\space\space\space g_1(x, y) \equiv -\sin x + y \leq 0\\ \space\space\space\space\space\space\space\space\space\space\space\space g_2(x, y) \equiv x + y - 2\pi \leq 0\\ g_3(x, y) \equiv -x \leq 0\\ g_4(x, y) \equiv -y \leq 0 \end{equation}
When checking NDCQ, we calculate \begin{equation} Dg(x, y) = \begin{pmatrix} -\cos x & 1\\ 1 & 1\\ -1 & 0\\ 0 & -1 \end{pmatrix} \end{equation}
However, in this case, there could be 3 inequality constraints being binding at one time, namely $g_1$, $g_3$, and $g_4$. Then how should I proceed to check the NDCQ?
Thanks a lot for any help!
Source: Mathematics for Economists by Simon and Blume
I have attempted to answer your two questions below.
1.
To understand the intuition for why we need to check the NDCQ it helps to consider examples of where the solution to the optimization problem does not satisfy the NDCQ.
Here is one such example:
$$\text{$\max_{x,y} -(x^2+y^2)$ subject to $(x−1)^3−y^2=0$}$$
We can solve this problem geometrically. The level curves of the objective function are circles of raidus zero centred at the origin. The constraint curve consists of the points where $x\geq 1$ and $y=\pm (x-1)^{3/2}$. The maximizer is $(1,0)$ and the constraint curve has a cusp there.
If you form the Lagrangian for this problem you will find it has no stationary points.
The issue is that the NDCQ is not satisfied at the maximizer $(1,0)$. We have
$$Dh(x,y)=\begin{pmatrix}3(x-1)^2 & -2y\end{pmatrix}$$
so that $Dh(1,0)=\begin{pmatrix}0 & 0\end{pmatrix}$.
In this case the Lagrangean method fails because at the maximizer the constraint curve is not smooth. The idea behind why the Lagrangean works is that if the level curves are smooth then a necessary condition for an optimum is that at the optimum the level curve of the objective function is tangent to the constraint curve. If the constraint curve is not smooth at the optimum, then the tangency condition is not necessary (if the constraint curve is not smooth at the optimum then the constraint curve has no tangent line there).
2.
In your example, at the point $(0,0)$ where $g_1$, $g_3$ and $g_4$ all bind the NDCQ is not satisfied; the rank of the $3\times 2$ matrix is only two.
It is not possible for the NDCQ to hold at points where more constraints bind than the number of variables.