2
$\begingroup$

I have a question about the constraint qualification for KKT. As I've seen the theorem stated if $G(x^*)=(g_1(x^*),\dots,g_n(x^*))$ are the binding constraints at a local max $x^*$ then the jacobian $DG(x^*)$ must have rank $n$. Obviously this is impossible if $n>\text{length}(x)$. In the examples I can think of for this case, this simply means that we cannot find a unique multiplier $\lambda$.

E.g. $\max x_2$ subject to $x_1^2 + x_2^2\leq 1$, $x_2\leq x_1 + 1$, and $x_2\leq 1-x_1$ with $x^*=(0,1)$.

So my question is, if per the theorem, KKT requires rank $n$ so that these overdetermined cases fail the constraint qualification, what might be going wrong? The theorem does not require a unique multiplier. Could we relax the constraint qualification to $DG(x^*)$ has full rank?

Regarding the last question. Here is my proof sketch for why I think this is possible.

Suppose the original problem is to maximize $f$ on the constraint set $\mathcal{D}=U\cap \{x\in\mathbb{R}^n:G(x)\geq 0\}$ where $U$ is an open set. Assume all continuously differentiable.

Let $E=\{i:G^i(x^*)=0\}$ and suppose $|E|>n$ and rank($DG_E(x^*)$)$=n$. Then we can find $F\subsetneq E$ where rank($DG_F(x^*)$)$=n$.

Suppose $x^*$ is a local max of $f$ on the constraint set $\mathcal{D}'=U\cap \{x\in\mathbb{R}^n:G_F(x)\geq 0\}$ where $U$ is an open set. Then $x^*$ is also a local max on the constraint sets defined by $G_E$ and $G$ where the former includes superfluous effective constraints and the latter includes ineffective constraints so that the constraint set only gets smaller while still allowing $x^*$.

If we can find a vector $(x^*, \mu^*)$ that solves the KKT conditions from the problem max $f$ on $\mathcal{D}'$, then $(x^*, \lambda^*)$ solves the KKT conditions for the original problem if $\lambda_i=\mu_i$ for $i\in F$ and $\lambda_i = 0$ otherwise. This proves the claim because for $E$ where $|E|>n$ then we must be able to find an $F$ and $(x^*, \mu^*)$ from which we construct the solution to the original problem.

I think I'm just missing optima on $\mathcal{D}$ are also optima on $\mathcal{D}'$.

Edit: Thought of a counterexample--so long as I am not abusing any definitions or the statement of KKT.

$\max x_1$ subject to $g_1(x)=x_1\geq0$, $x_2\geq0$ and $x_2\leq x_1^2$.

The solution is the only point in the feasible region, $(0,0)$, which is therefore trivially a local max. All constraints bind. The Jacobian has rank 2, but the FOCs would require the multiplier on $g_1$ to be negative.

$\endgroup$
  • $\begingroup$ Sounds like your prof forgot to select only the active indices, those $g_i$ where $g_i(x^*) = 0$. $\endgroup$ – AlexR Sep 16 '14 at 12:23
  • $\begingroup$ I don't think that is it--that's exactly what I mean by binding. $\endgroup$ – Pburg Sep 16 '14 at 12:33
  • $\begingroup$ Note that those are not necessary. If the CQ hold, we know that the KKT must hold in a minimum (or maximum). If they don't, we are screwed and don't know anything. $\endgroup$ – AlexR Sep 16 '14 at 12:35
  • $\begingroup$ What do you mean by not necessary? As in if I am in $\mathbb{R}^m$ and I have $n>m$ binding constraints ($g_i(x^*)=0$), I can just throw away $n-m$? $\endgroup$ – Pburg Sep 16 '14 at 12:38
  • 1
    $\begingroup$ Indeed, in Sundaram's optimization theory, KKT is stated to require rank equal to the number of binding constraints. In Dixit's Optimization in Economic Theory, KKT is stated to only require full rank of the jacobian for binding constraints. $\endgroup$ – Pburg Sep 16 '14 at 13:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.