I got the following problem, but I have difficulties understanding part of its solution. I would really appreciate it if someone could explain it for me!
Problem
Present a geometric proof that in the problem of minimizing $f(x, y)$ on the constraint set $g(x, y) \geq b$, the gradient of $f$ and the gradient of $g$ point in the same direction at a minimizer for which the constraint is binding.
Solution
Let $(x^*, y^*)$ be a minimizer of $f$ on the set $g(x, y) \geq b$ where $g(x^*, y^*) = b$. Then $\nabla g(x^*, y^*)$ points onto the constraint set since it points into region of higher $g$-values. Since $(x^*, y^*)$ minimizes $f$ on the constraint set, $f$ increase as one moves into the constraint set. So, $\nabla f(x^*, y^*)$ points into the constraint set too. $\nabla g(x^*, y^*)$ and $\nabla f(x^*, y^*)$ point along the same line and both point into the constraint set. So they point in the same direction.
More rigorously, if the Non-Degenerate Constraint Qualification (NDCQ) holds, $\nabla g(x^*, y^*) \cdot h > 0$ implies $\nabla f(x^*, y^*) \cdot h \geq 0$. Write $\nabla f(x^*, y^*) = \nabla g(x^*, y^*) + w$, where $w \cdot \nabla g(x^*, y^*) = 0$. If $w \neq \mathbf{0}$, then the system $\nabla g(x^*, y^*) \cdot h = 0$ and $w \cdot h < 0$ has a solution, so $\nabla f(x^*, y^*) \cdot h < 0$. Perturbing a solution gives an $h$ such that $\nabla g(x^*, y^*) \cdot h > 0$ and $\nabla f(x^*, y^*) \cdot h < 0$, a contradiction. Consequently $w = \mathbf{0}$. If $\lambda < 0$, again $\nabla g(x^*, y^*) \cdot h > 0$, and again implies $\nabla f(x^*, y^*) \cdot h < 0$, a contradiction.
My Question
I have no problem understanding the first paragraph, which is similar to my own attempt. However, I completely lost in the second paragraph of the solution:
(1) Why would $\nabla g(x^*, y^*) \cdot h > 0$ implies $\nabla f(x^*, y^*) \cdot h \geq 0$ instead of $\nabla f(x^*, y^*) \cdot h > 0$. I feel that the second paragraph is a continuation of the first. So if $\nabla f$ and $\nabla g$ point to the same direction, and if $\nabla g(x^*, y^*) \cdot h > 0$, wouldn't it imply that $\nabla f(x^*, y^*) \cdot h > 0$? (My feel/understanding may not be correct...).
(2) How does $w \neq \mathbf{0}$ imply the system $\nabla g(x^*, y^*) \cdot h = 0$ and $w \cdot h < 0$ has a solution?
(3) What does it mean by "perturbing a solution gives an $h$ such that $\nabla g(x^*, y^*) \cdot h > 0$ and $\nabla f(x^*, y^*) \cdot h < 0$"?
(4) Why is it that "if $\lambda < 0$, again $\nabla g(x^*, y^*) \cdot h > 0$, and again implies $\nabla f(x^*, y^*) \cdot h < 0$".
Note
There is no $\lambda$ in the question. So I guess it refers to the Lagrange multiplier. The theorem I learned, which contains a definition of NDCQ, about the constrained minimization problem is the following:
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 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.$
So, I think the version for a theorem about a minimization problem with single constraint and two variables should be like this:
Theorem Suppose that $f$ and $g$ are $C^1$ functions on $\mathbb{R}^2$ and that $(x^*, y^*)$ minimizes $f$ on the constraint set $g(x, y) \geq b$. If $g(x^*, y^*) = b$, suppose that the NDCQ holds: \begin{equation} \frac{\partial g}{\partial x}(x^*, y^*) \neq 0\space\space\space\space or\space\space\space\space \frac{\partial g}{\partial y}(x^*, y^*) \neq 0. \end{equation} Then, there is a multiplier $\lambda^*$ such that:
(a) $\frac{\partial L}{\partial x}(x^*, y^*, \lambda^*) = 0$;
(b) $\frac{\partial L}{\partial y}(x^*, y^*, \lambda^*) = 0$;
(c) $\lambda^* \cdot [g(x^*, y^*) - b] = 0$;
(d) $\lambda^* \geq 0$;
(e) $g(x^*, y^*) \geq b$
Thanks a lot for any help!