# Question About Fritz John Theorem and Slater Constraint Qualification

## 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 $$$$g_1(x_1, \dots, x_n) \leq b_1, \dots, g_k(x_1, \dots, x_n) \leq b_k.$$$$ Form the Lagrangian $$$$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],$$$$ 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 $$$$g_1(\mathbf{x}) \leq b_1, \dots, g_k(\mathbf{x}) \leq b_k.$$$$ 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: $$$$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$$$$

## 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!

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.