Question About Fritz John Theorem and Slater Constraint Qualification

Question

Background Information

I am studying constraint qualifications. Here are two theorems leading to my question:

Theorem 1$\space\space\space\space$ [Fritz John Theorem] Suppose that $f, g_1, \dots, g_k$ are $C^1$ functions of $n$ variables. Suppose that $x^*$ is a local maximizer of $f$ on the constraint set defined by the $k$ inequalities \begin{equation} g_1(x_1, \dots, x_n) \leq b_1, \dots, g_k(x_1, \dots, x_n) \leq b_k. \end{equation} Form the Lagrangian \begin{equation} L(x_1, \dots, x_n, \lambda_0, \lambda_1, \dots, \lambda_k) \equiv \lambda_0f(\mathbf{x}) - \lambda_1[g_1{\mathbf{x}} - b_1] - \dots - \lambda_k[g_k{\mathbf{x}} - b_k], \end{equation} with a multiplier $\lambda_0$ for the objective function. Then, there exist multipliers $\lambda^* = (\lambda_0^*, \lambda_1^*, \dots, \lambda_k)$ such that:

(a) $\frac{\partial L}{\partial x_1}(\mathbf{x}^*, \lambda^*) = 0, \dots, \frac{\partial L}{\partial x_n}(\mathbf{x}^*, \lambda^*) = 0$,
(b) $\lambda_1^*[g_1(\mathbf{x}^*) - b_1] = 0, \dots, \lambda_k^*[g_k(\mathbf{x}^*) - b_k] = 0$,
(c) $\lambda_1^* \geq 0, \dots, \lambda_k^* \geq 0$,
(d) $g_1(\mathbf{x}^*) \leq b_1, \dots, g_k(\mathbf{x}^*) \leq b_k$,
(e) $\lambda_0^* = 0$ or $1$, and
(f) $(\lambda_0^*, \lambda_1^*, \dots, \lambda_k^*) \neq (0, 0, \dots, 0)$.

Theorem 2$\space\space\space\space$ Let $f, g_1, \dots, g_k$ be as in Theorem 1, and suppose that $\mathbf{x}^* \in \mathbb{R}^n$ is a local maximizer of $f$ on the constraint set defined by \begin{equation} g_1(\mathbf{x}) \leq b_1, \dots, g_k(\mathbf{x}) \leq b_k. \end{equation} For ease of notation, suppose that $g_1, \dots, g_h$ yield binding constraints at $\mathbf{x}^*$ and that $g_{h+1}, \dots, g_k$ are not binding at $\mathbf{x}^*$. Suppose that the binding constraint functions satisfy one of the following properties:

(a) (Slater Constraint Qualification) There is a ball $U$ about $\mathbf{x}^*$ in $\mathbb{R}^n$ such that $g_1, \dots, g_h$ are convex functions on $U$ and there exists $\mathbf{z} \in U$ so that each $g_i(\mathbf{z} < b_i)$.
(b) $g_1, \dots, g_h$ are concave functions.
(c) $g_1, \dots, g_h$ are linear functions.

Then we can take $\lambda_0^* = 1$ in the conclusion of Theorem 1.

Problem

I was asked to determine which of the three constraint qualifications in Theorem 2 hold for the constraint functions in the following maximization problem: \begin{equation} Max\space\space\space\space f(x, y) = 2y^2 - x\\ \space\space\space\space\space\space\space\space\space\space\space\space s.t.\space\space\space\space g_1(x, y) \equiv x^2 + y^2 \leq 1\\ \space\space\space\space\space\space\space\space\space\space\space\space\space\space g_2(x, y) \equiv -x \leq 0\\ \space\space\space\space\space\space\space\space\space\space\space\space\space\space g_3(x, y) \equiv -y \leq 0 \end{equation}

My Question

The answer to this problem is (a). I was very confused about it. One can check that the local maximizer of the $f$ on the constraint set is $x = 0$, $y = 1$. In that case, the binding constraint functions would be $g_1$ and $g_2$. However, how is $g_1$ a convex function on a ball $U$ about $(0, 1)$? Wouldn't it be concave? What am I missing, or is my understanding of the theorem is wrong? I really appreciate any help!

Answer 1

Lets break down the statement:

1. There is a ball $U$ about $\mathbf{x}^*$ in $\mathbb{R}^n$. That is, let $U = \{ x \in \mathbb{R}^n : \| x - \mathbf{x}^* \| \leq \rho \}$ be a norm-ball with some unspecified radius $\rho$, having $\mathbf{x}^*$ at its center.

2. such that $g_1, \dots, g_h$ are convex functions on $U$. That is, if you restricted the domain of these functions from $\mathbb{R}^n$ to $U$ (or more generally, if $g_i : D_i \rightarrow \mathbb{R}$, from $D_i$ to $D_i \cap U$) then these domain-restricted functions would satisfy the definition of a convex function. Assuming $g_1, \dots, g_h$ are $C^2$ functions, this is equivalent to their Hessian matrices $H_{g_1}(x), \ldots, H_{g_h}(x)$ being positive semidefinite for all $x$ in this restricted domain.

3. and there exists $\mathbf{z} \in U$ so that each $g_i(\mathbf{z}) < b_i$. All functions, $g_1, \dots, g_h$ as well as $g_{h+1}, \dots, g_k$, must be nonbinding at the so-called Slater point $\mathbf{z} \in U$.

In your example, $g_1(x, y) = x^2 + y^2$ is a convex function on all of $\mathbb{R}^2$ and $g_2(x,y) = -x$ is linear (thus also convex) on all of $\mathbb{R}^2$. This means that there is no limit to the radius $\rho$ of the norm-ball $U$. We can thus choose $(x,y)=(0.5, 0.5)$ as our Slater point.