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.


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!


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.