<p>I am studying constrained optimization using <em>Mathematics for Economists</em> by Simon and Blume, and I have some difficulties understanding the <em><strong>Non-Degenerated Constraint Qualification (NDCQ)</strong></em>. I would like to put the theorem of constrained optimization in Simon and Blume here first, in which the NDCQ is stated. Then, I will describe my question using example(s).</p>
<blockquote>
<p><strong>Theorem 18.6</strong><span class="math-container">$\space\space\space\space$</span> Suppose that <span class="math-container">$f, g_1, \dots, g_k, h_1, \dots, h_m$</span> are <span class="math-container">$C^1$</span> functions of <span class="math-container">$n$</span> variables. Suppose the <span class="math-container">$\mathbf{x^*} \in \mathbb{R}^n$</span> is a local <strong>minimizer</strong> of <span class="math-container">$f$</span> on the constraint set defined by the <span class="math-container">$k$</span> inequalities and <span class="math-container">$m$</span> equalities:
<span class="math-container">\begin{equation}
g_1(x_1, \dots, x_n) \geq b_1, \dots, g_k(x_1, \dots, x_n) \geq b_k, \\
h_1(x_1, \dots, x_n) = c_1, \dots, h_m(x_1, \dots, x_n) = c_m.
\end{equation}</span>
Without loss of generality, we can assume that the first <span class="math-container">$k_0$</span> inequality constraints are binding (i.e., the equality holds) at <span class="math-container">$\mathbf{x^*}$</span> and that the other <span class="math-container">$k - k_0$</span> inequity constraints are not binding (i.e., the strict inequality holds). Suppose that the following Non-Degenerate Constraint Qualification (NDCQ) is satisfied at <span class="math-container">$\mathbf{x^*}$</span>:<br />
<span class="math-container">$\space\space\space\space$</span> The rank at <span class="math-container">$\mathbf{x^*}$</span> of the Jacobian matrix of the equality constraints and the <em>binding</em> inequality constraints
<span class="math-container">\begin{equation}
\begin{pmatrix}
\frac{\partial g_1}{\partial x_1}(\mathbf{x^*}) &amp; \cdots &amp; \frac{\partial g_1}{\partial x_n}(\mathbf{x^*}) \\
\vdots &amp; \ddots &amp; \vdots \\
\frac{\partial g_{k_0}}{\partial x_1}(\mathbf{x^*}) &amp; \cdots &amp; \frac{\partial g_{k_0}}{\partial x_n}(\mathbf{x^*}) \\
\frac{\partial h_1}{\partial x_1}(\mathbf{x^*}) &amp; \cdots &amp; \frac{\partial h_1}{\partial x_n}(\mathbf{x^*}) \\
\vdots &amp; \ddots &amp; \vdots \\
\frac{\partial h_m}{\partial x_1}(\mathbf{x^*}) &amp; \cdots &amp; \frac{\partial h_m}{\partial x_n}(x^*)
\end{pmatrix}
\end{equation}</span>
is <span class="math-container">$k_0 + m$</span> -- as large as it can be.<br />
<span class="math-container">$\space\space\space\space$</span> Form the Lagrangian
<span class="math-container">\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}</span>
Then, there exist multipliers <span class="math-container">$\lambda_{1}^{*}, \dots, \lambda_{k}^{*}, \mu_{1}^{*}, \dots, \mu_{m}^{*}$</span> such that:<br />
<span class="math-container">$\space\space\space\space$</span> <span class="math-container">$(a)\space\space \frac{\partial L}{\partial x_1}(\mathbf{x^*}) = 0, \dots, \frac{\partial L}{\partial x_n}(\mathbf{x^*}) = 0,$</span><br />
<span class="math-container">$\space\space\space\space$</span> <span class="math-container">$(b)\space\space \lambda_{1}^{*}[g_1(\mathbf{x^*}) - b_1] = 0, \dots, \lambda_{k}^{*}[g_k(\mathbf{x^*}) - b_k] = 0,$</span><br />
<span class="math-container">$\space\space\space\space$</span> <span class="math-container">$(c)\space\space h_1(\mathbf{x^*}) = c_1, \dots, h_m(\mathbf{x^*}) = c_m,$</span><br />
<span class="math-container">$\space\space\space\space$</span> <span class="math-container">$(d)\space\space \lambda_{1}^{*} \geq 0, \dots, \lambda_{k}^{*} \geq 0,$</span> and<br />
<span class="math-container">$\space\space\space\space$</span> <span class="math-container">$(e)\space\space g_1(\mathbf{x^*}) \geq b_1, \dots, g_k(\mathbf{x^*}) \geq b_k.$</span></p>
</blockquote>
<p>Based on this theorem (and an analogous theorem for maximization), the steps of solving a constrained optimization problem should be:<br />
(1) Write down the objective function and the constraint set.<br />
(2) Check the NDCQ.<br />
(3) Form the Lagrangian.<br />
(4) Write down the F.O.C.<br />
(5) Solve the F.O.C.</p>
<p>My problem is with Step (2). <em><strong>When checking the NDCQ, if none of the critical point of <span class="math-container">$\mathbf{h} = (h_1, \dots, h_m)$</span> (i.e., the point that can make the rank of the Jacobian matrix of the equality constraints and the binding inequality constraints less than <span class="math-container">$k_0 + m$</span>) lies in the constraint set, then move to Step (3). If the constraint set does contain critical points of <span class="math-container">$\mathbf{h} = (h_1, \dots, h_m)$</span>, 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.</strong></em></p>
<p>In an example (Example 18.9), the way how Simon and Blume proceed is the following:</p>
<blockquote>
<p><strong>Example 18.9</strong><span class="math-container">$\space\space\space\space$</span> Consider the maximization problem:
<span class="math-container">\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\\
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}</span>
Check the NDCQ: The Jacobian of the constraint functions is
<span class="math-container">\begin{equation}
\begin{pmatrix}
1 &amp; 1 &amp; 1\\
-1 &amp; 0 &amp; 0\\
0 &amp; -1 &amp; 0\\
0 &amp; 0 &amp; -1
\end{pmatrix}.
\end{equation}</span>
It has rank 3. Since at most three of the four constraints can be binding at any one time, the NDCQ holds at any solution candidate.</p>
</blockquote>
<p>This argument does make sense in this example. However, I came up with the following example, in which if I were to adopt a similar argument might cause problem.</p>
<blockquote>
<p><strong>Problematic Example</strong><span class="math-container">$\space\space\space\space$</span> Consider the minimization problem:
<span class="math-container">\begin{equation}
Min\space\space\space\space f(x, y) = 2x^2 + 2y^2 - 2xy - 9y\\
s.t.\space\space\space\space g_1(x, y) \equiv -4x - 3y \geq -10\space\space\space\space\space\space\space\\
\space g_2(x, y) \equiv -4x^2 + y \geq \frac{31}{9}\\
g_3(x, y) \equiv x \geq 0\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\\
g_4(x, y) \equiv y \geq 0\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space
\end{equation}</span></p>
</blockquote>
<p>By adopting a similar argument as in Example 18.9, I would have argued:</p>
<blockquote>
<p>The Jacobian of the constraint functions is
<span class="math-container">\begin{equation}
\begin{pmatrix}
-4 &amp; -3\\
-8x &amp; 1\\
1 &amp; 0\\
0 &amp; 1
\end{pmatrix}.
\end{equation}</span>
It has rank 2. Since at most two of the four constraints can be binding at any one time, the NDCQ holds at any solution candidate.</p>
</blockquote>
<p>However, if <span class="math-container">$g_1(x, y)$</span> and <span class="math-container">$g_2(x, y)$</span> is binding, then <span class="math-container">$x = -\frac{1}{6}$</span> and <span class="math-container">$y = \frac{32}{9}$</span>. Then the Jacobian matrix of the equality constraints and the binding inequality constraints is
<span class="math-container">\begin{equation}
\begin{pmatrix}
-4 &amp; -3\\
\frac{4}{3} &amp; 1
\end{pmatrix},
\end{equation}</span>
which has rank 1. Thus the NDCQ does not hold in this case. Could someone please help me with this issue? What am I missing? I really appreciate it!</p>
<hr />
<p>I suspect that Simon and Blume's argument in Example 18.9 is not correct. I feel their argument should have been stated as:</p>
<blockquote>
<p>The Jacobian of the constraint functions is
<span class="math-container">\begin{equation}
\begin{pmatrix}
1 &amp; 1 &amp; 1\\
-1 &amp; 0 &amp; 0\\
0 &amp; -1 &amp; 0\\
0 &amp; 0 &amp; -1
\end{pmatrix}.
\end{equation}</span>
Any <span class="math-container">$3 \times 3$</span> submatrix of it has rank 3, any <span class="math-container">$2 \times 3$</span> 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.</p>
</blockquote>
<p>Is this correct? Thanks a lot for any help!</p>

CC BY-SA 4.0
2023-08-11T05:30:11.827Z
In their example, how do they get a 4 row Jacobi from 3 constraints?
Giskard
CC BY-SA 4.0
2023-08-11T14:28:50.220Z
@Giskard My bad. There should be a $z \geq 0$ as well. I have added it. Thanks!
Beerus
CC BY-SA 4.0
2023-08-11T15:37:40.063Z
I think you are right.
smcc
CC BY-SA 4.0
2023-08-11T16:10:47.043Z
But if $x=-1/6<0$ how can you say that $g_3$ is not binding?
BakerStreet
CC BY-SA 4.0
2023-08-11T16:34:50.217Z
@BakerStreet Well, actually, this example does have some flaw. But my point is that one can definitely make up an example where: (1) the Jacobian of the constraint functions is a $2 \times 4$ matrix of rank 2; (2) there exists a case when two of the constraint functions are binding, the rank of the Jacobian matrix of the equality constraints and the binding inequality constraints is 1. In such an example, the argument used in Simon and Blume is not correct. Because only checking the Jacobian of the constraint functions is not sufficient in this case.
Beerus
CC BY-SA 4.0
2023-08-11T17:10:46.540Z
I have to re-read carefully your question, forgive me but I hadn’t time, and I could misunderstand your problem. But my intuitive impression is, in your problematic example (but I will re-read your question if I have time),  that the problem arises from the fact that one cannot choose at will, arbitrarily, which constraints are binding and which are  not, it depends on the specific problem in consideration. You seemed to choose them arbitrarily:  I mean, you can’t take two of them as binding at will.
BakerStreet
CC BY-SA 4.0
2023-08-11T17:25:16.627Z
@BakerStreet I really appreciate your comment and help! Maybe I wasn't super clear with my question. Basically, I have problem with Simon and Blume's argument when checking the NDCQ. As I put in my post above, according to Simon and Blume (p. 420 first parageaph), When checking the NDCQ, if none of the critical point of $\mathbf{h} = (h_1, \dots, h_m)$ lies in the constraint set, then the NDCQ holds automatically and we can move on to form the Lagrangian and solve the F.O.C. (To Be Continued)
Beerus
CC BY-SA 4.0
2023-08-11T17:26:42.663Z
@BakerStreet (Cont'd) 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. (To Be Continued)
Beerus
CC BY-SA 4.0
2023-08-11T17:31:59.850Z
@BakerStreet (Cont'd) So maybe this example is easier to see: Consider the maximization problem: $Max$ $f(x, y)$ subject to $g_1(x, y) \equiv x^2 + y^2 \leq 1$, $g_2(x, y) \equiv -x \leq 0$, and $g_3(x, y) \equiv -y \leq 0$. When checking the NDCQ, Simon and Blume would argue that since $Dg(x, y) = \begin{pmatrix} 2x & 2y\\ -1 & 0\\ 0 & -1 \end{pmatrix}$ has rank 2, and since at most two of the three constraints can be binding, the NDCQ holds for any solution candidates. (To Be Continued)
Beerus
CC BY-SA 4.0
2023-08-11T17:35:07.427Z
Unfortunately I haven't Simon and Blume, it would be easier.
BakerStreet
CC BY-SA 4.0
2023-08-11T17:37:58.433Z
@BakerStreet (Cont'd) However, although the NDCQ does hold for any solution candidates in this specific example, the argument is not correct. Instead, I think one should argue that: At most 2 of the 3 constraints can be binding. If $g_2$ and $g_3$ is binding, then $x = y = 0$ and $\begin{pmatrix} -1 & 0\\ 0 & -1 \end{pmatrix}$ has rank 2. If $g_1$ and $g_2$ is binding, then $x = 0$, $y = 1$ and $\begin{pmatrix} 0 & 1\\ -1 & 0 \end{pmatrix}$ has rank 2. If $g_1$ and $g_3$ is binding, then $x = 1$, $y = 0$ and $\begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix}$ has rank 2. (To Be Continued)
Beerus
CC BY-SA 4.0
2023-08-11T17:40:28.817Z
@BakerStreet (Cont'd) and finally, if only one of three constraints is binding, there will be no zero row in $Dg(x, y)$. Thus the NDCQ holds for any solution candidates.  \\ Hopefully, this may clarify my question. And thanks a lot for your comment and help!
Beerus
CC BY-SA 4.0
2023-08-11T17:42:35.343Z
There is a typo, a part of your comment I can't see, but what I find misleading is what I said before: you can't say: if $g_1$ and $g_2$ are binding, this happens, instead if $g_2 $and $g_3$ are binding that happens and so on. Which constraints are binding is determined by the specific function $f(x,y)$, you can't do all these cases.
BakerStreet
CC BY-SA 4.0
2023-08-11T17:44:43.773Z
Aniway, I will think again about your question.
BakerStreet
CC BY-SA 4.0
2023-08-12T14:21:09.050Z
@BakerStreet The argument in the example from Simon and Blume is to rule out the possibility of there being **any** points in the constraint set violating the NDCQ. To show this, it **is** necessary to look at all the possible cases. ("What if $g_1$ and $g_2$ are binding? "What if $g_2$ and $g_3$ are binding?" ...) If, after doing so, one finds there are points in the constraint set that do not satisfy the NDCQ, then those points have to be investigated to see if they are solutions (they have to be compared to any points that satisfy the conditions (a) to (e).).
smcc
CC BY-SA 4.0
2023-08-12T14:28:34.563Z
My point is that not all possible cases are possible, because we can't know in advance which constraints are binding and which are not., we can't choose the binding costraints at will. In the problematic example in the question Beerus chooses  $g_1$ and $g_2$ as bonding constraint, but in that case we see that $x=-1/6<0$ , so that $g_3$ must be binfining. As the binding constraints cannot be more than two, this means that the choice of $g_1$ and $g_2$ is not correct.
BakerStreet
CC BY-SA 4.0
2023-08-12T14:29:55.603Z
Of course we must look at all the possible case, but indeed the *possible* cases, not all the combination of constraints freely, at will. I think that Simone and Blume is correct, but I hope to look at the book and think again about it.
BakerStreet
CC BY-SA 4.0
2023-08-12T20:16:37.483Z
Maybe I can explain this better in the following way. To look at *all cases* means to consider all optimal points, and check if in any case the rank condition is fulfilled there, taking the constraints that are binding at each optimal point. But which constraints are binding at each optimal point is determined by the problem, you cannot choose them at random. Therefore, to look at all possible case does not mean that we take all the possible combination of constraints at will.
BakerStreet
CC BY-SA 4.0
2023-08-17T00:35:23.573Z
@BakerStreet I think what you said does make sense. Thanks a lot! But I still have one more question: What if the optimal point (i.e., the solution to the optimization problem) is not one of the critical points of the Lagrangian? Then if I only check NDCQ for the critical points of the Lagrangian,  wouldn't it be insufficient?
Beerus
CC BY-SA 4.0
2023-08-17T10:31:04.473Z
I think yoy are right, it is insufficient, because if at a point NDCQ holds, you can apply the theorem, but if at a point it doesn't hold you don't know anything, and such a point could be the optimal point indeed. So you have to include these point among the candidates for an optimum. I hope I understand correctly your questions, because as I said I didn't read Simone and Blume, I hope to look at it as soon is possible. –
BakerStreet
CC BY-SA 4.0
2023-08-17T10:32:33.853Z
If you have the possibility, look at Sydsater, Hammond, *Further Mathematics for Economic Analysis,* it explain exactly this issue and illustrates the practical steps to solve the problem.
BakerStreet
<microeconomics><mathematical-economics><optimization><linear-algebra><linear-programming>
Question About Non-Degenerated Constraint Qualification (NDCQ)
Beerus
# Question About Non-Degenerated Constraint Qualification (NDCQ)

(Asked by: username_0 on 2023-08-10)

I am studying constrained optimization using *Mathematics for Economists* by Simon and Blume, and I have some difficulties understanding the ***Non-Degenerated Constraint Qualification (NDCQ)***. I would like to put the theorem of constrained optimization in Simon and Blume here first, in which the NDCQ is stated. Then, I will describe my question using example(s).

> **Theorem 18.6**$\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 **minimizer** of $f$ on the constraint set defined by the $k$ inequalities and $m$ equalities:
> \begin{equation}
> g\_1(x\_1, \dots, x\_n) \geq b\_1, \dots, g\_k(x\_1, \dots, x\_n) \geq 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$ 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^\*}) \geq b\_1, \dots, g\_k(\mathbf{x^\*}) \geq b\_k.$

Based on this theorem (and an analogous theorem for maximization), the steps of solving a constrained optimization problem should be:  
(1) Write down the objective function and the constraint set.  
(2) Check the NDCQ.  
(3) Form the Lagrangian.  
(4) Write down the F.O.C.  
(5) Solve the F.O.C.

My problem is with Step (2). ***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 move to Step (3). 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.***

In an example (Example 18.9), the way how Simon and Blume proceed is the following:

> **Example 18.9**$\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\\
> 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}
> It has rank 3. Since at most three of the four constraints can be binding at any one time, the NDCQ holds at any solution candidate.

This argument does make sense in this example. However, I came up with the following example, in which if I were to adopt a similar argument might cause problem.

> **Problematic Example**$\space\space\space\space$ Consider the minimization problem:
> \begin{equation}
> Min\space\space\space\space f(x, y) = 2x^2 + 2y^2 - 2xy - 9y\\
> s.t.\space\space\space\space g\_1(x, y) \equiv -4x - 3y \geq -10\space\space\space\space\space\space\space\\
> \space g\_2(x, y) \equiv -4x^2 + y \geq \frac{31}{9}\\
> g\_3(x, y) \equiv x \geq 0\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\\
> g\_4(x, y) \equiv y \geq 0\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space\space
> \end{equation}

By adopting a similar argument as in Example 18.9, I would have argued:

> The Jacobian of the constraint functions is
> \begin{equation}
> \begin{pmatrix}
> -4 & -3\\
> -8x & 1\\
> 1 & 0\\
> 0 & 1
> \end{pmatrix}.
> \end{equation}
> It has rank 2. Since at most two of the four constraints can be binding at any one time, the NDCQ holds at any solution candidate.

However, if $g\_1(x, y)$ and $g\_2(x, y)$ is binding, then $x = -\frac{1}{6}$ and $y = \frac{32}{9}$. Then the Jacobian matrix of the equality constraints and the binding inequality constraints is
\begin{equation}
\begin{pmatrix}
-4 & -3\\
\frac{4}{3} & 1
\end{pmatrix},
\end{equation}
which has rank 1. Thus the NDCQ does not hold in this case. Could someone please help me with this issue? What am I missing? I really appreciate it!

---

I suspect that Simon and Blume's argument in Example 18.9 is not correct. I feel their argument should have been stated as:

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

Is this correct? Thanks a lot for any help!

**Tags:** microeconomics, mathematical-economics, optimization, linear-algebra, linear-programming
> **Comments:**
> **username_1**: In their example, how do they get a 4 row Jacobi from 3 constraints?  
> **username_0**: @Giskard My bad. There should be a $z \geq 0$ as well. I have added it. Thanks!  
> **username_2**: I think you are right.  
> **username_3**: But if $x=-1/6<0$ how can you say that $g_3$ is not binding?  
> **username_0**: @BakerStreet Well, actually, this example does have some flaw. But my point is that one can definitely make up an example where: (1) the Jacobian of the constraint functions is a $2 \times 4$ matrix of rank 2; (2) there exists a case when two of the constraint functions are binding, the rank of the Jacobian matrix of the equality constraints and the binding inequality constraints is 1. In such an example, the argument used in Simon and Blume is not correct. Because only checking the Jacobian of the constraint functions is not sufficient in this case.  
> **username_3**: I have to re-read carefully your question, forgive me but I hadn’t time, and I could misunderstand your problem. But my intuitive impression is, in your problematic example (but I will re-read your question if I have time),  that the problem arises from the fact that one cannot choose at will, arbitrarily, which constraints are binding and which are  not, it depends on the specific problem in consideration. You seemed to choose them arbitrarily:  I mean, you can’t take two of them as binding at will.  
> **username_0**: @BakerStreet I really appreciate your comment and help! Maybe I wasn't super clear with my question. Basically, I have problem with Simon and Blume's argument when checking the NDCQ. As I put in my post above, according to Simon and Blume (p. 420 first parageaph), When checking the NDCQ, if none of the critical point of $\mathbf{h} = (h_1, \dots, h_m)$ lies in the constraint set, then the NDCQ holds automatically and we can move on to form the Lagrangian and solve the F.O.C. (To Be Continued)  
> **username_0**: @BakerStreet (Cont'd) 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. (To Be Continued)  
> **username_0**: @BakerStreet (Cont'd) So maybe this example is easier to see: Consider the maximization problem: $Max$ $f(x, y)$ subject to $g_1(x, y) \equiv x^2 + y^2 \leq 1$, $g_2(x, y) \equiv -x \leq 0$, and $g_3(x, y) \equiv -y \leq 0$. When checking the NDCQ, Simon and Blume would argue that since $Dg(x, y) = \begin{pmatrix} 2x & 2y\\ -1 & 0\\ 0 & -1 \end{pmatrix}$ has rank 2, and since at most two of the three constraints can be binding, the NDCQ holds for any solution candidates. (To Be Continued)  
> **username_3**: Unfortunately I haven't Simon and Blume, it would be easier.  
> **username_0**: @BakerStreet (Cont'd) However, although the NDCQ does hold for any solution candidates in this specific example, the argument is not correct. Instead, I think one should argue that: At most 2 of the 3 constraints can be binding. If $g_2$ and $g_3$ is binding, then $x = y = 0$ and $\begin{pmatrix} -1 & 0\\ 0 & -1 \end{pmatrix}$ has rank 2. If $g_1$ and $g_2$ is binding, then $x = 0$, $y = 1$ and $\begin{pmatrix} 0 & 1\\ -1 & 0 \end{pmatrix}$ has rank 2. If $g_1$ and $g_3$ is binding, then $x = 1$, $y = 0$ and $\begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix}$ has rank 2. (To Be Continued)  
> **username_0**: @BakerStreet (Cont'd) and finally, if only one of three constraints is binding, there will be no zero row in $Dg(x, y)$. Thus the NDCQ holds for any solution candidates.  \\ Hopefully, this may clarify my question. And thanks a lot for your comment and help!  
> **username_3**: There is a typo, a part of your comment I can't see, but what I find misleading is what I said before: you can't say: if $g_1$ and $g_2$ are binding, this happens, instead if $g_2 $and $g_3$ are binding that happens and so on. Which constraints are binding is determined by the specific function $f(x,y)$, you can't do all these cases.  
> **username_3**: Aniway, I will think again about your question.  
> **username_2**: @BakerStreet The argument in the example from Simon and Blume is to rule out the possibility of there being **any** points in the constraint set violating the NDCQ. To show this, it **is** necessary to look at all the possible cases. ("What if $g_1$ and $g_2$ are binding? "What if $g_2$ and $g_3$ are binding?" ...) If, after doing so, one finds there are points in the constraint set that do not satisfy the NDCQ, then those points have to be investigated to see if they are solutions (they have to be compared to any points that satisfy the conditions (a) to (e).).  
> **username_3**: My point is that not all possible cases are possible, because we can't know in advance which constraints are binding and which are not., we can't choose the binding costraints at will. In the problematic example in the question Beerus chooses  $g_1$ and $g_2$ as bonding constraint, but in that case we see that $x=-1/6<0$ , so that $g_3$ must be binfining. As the binding constraints cannot be more than two, this means that the choice of $g_1$ and $g_2$ is not correct.  
> **username_3**: Of course we must look at all the possible case, but indeed the *possible* cases, not all the combination of constraints freely, at will. I think that Simone and Blume is correct, but I hope to look at the book and think again about it.  
> **username_3**: Maybe I can explain this better in the following way. To look at *all cases* means to consider all optimal points, and check if in any case the rank condition is fulfilled there, taking the constraints that are binding at each optimal point. But which constraints are binding at each optimal point is determined by the problem, you cannot choose them at random. Therefore, to look at all possible case does not mean that we take all the possible combination of constraints at will.  
> **username_0**: @BakerStreet I think what you said does make sense. Thanks a lot! But I still have one more question: What if the optimal point (i.e., the solution to the optimization problem) is not one of the critical points of the Lagrangian? Then if I only check NDCQ for the critical points of the Lagrangian,  wouldn't it be insufficient?  
> **username_3**: I think yoy are right, it is insufficient, because if at a point NDCQ holds, you can apply the theorem, but if at a point it doesn't hold you don't know anything, and such a point could be the optimal point indeed. So you have to include these point among the candidates for an optimum. I hope I understand correctly your questions, because as I said I didn't read Simone and Blume, I hope to look at it as soon is possible. –  
> **username_3**: If you have the possibility, look at Sydsater, Hammond, *Further Mathematics for Economic Analysis,* it explain exactly this issue and illustrates the practical steps to solve the problem.  

---

## 0 answers

