Inequality constraints

Remark

Here, we consider an optimization problem of the form where and are continuously differentiable.

Definition: Active indices

Let . Then is the corresponding active index set.

Remark

If , then is an interior point in and as such, if is a local optimal solution it follows from a previous theorem that .

Lemma

Suppose with is a local optimal solution. Then there does not exist a with Proof:
Suppose such a exists. It is then clear that a small step in the -direction lowers cost and stays feasible, contradicting the local optimality.

Farkas' Lemma

Let and . Then exactly one of the following is true:

  1. There exists an with and .
  2. There exists a with and .

Some intuition is that are all conic combinations of the columns of , which is a convex subset. Farkas' lemma says exactly that whenever a vector is not in it is possible to separate and with a hyperplane, being ; says that all columns of and thus all of lie on the same side of , while says that lies on the opposite side of .

Lemma

Let . Then exactly one of the following is true:

  1. There exists a such that .
  2. There exists a such that and .

Proof:
By introducing another variable one gets that (a) is equivalent to which is equivalent to (b) in Farkas' lemma giving that there is either a solution to this or to and if there is a solution to where we can just scale to get .

Lemma

Let with be a local optimal solution. Then there exists scalars and () such that Proof:
Taking a previous lemma says that there are no such that . The previous lemma then says that there exists a nonnegative nonzero such that if , which is precisely the statement.

Definition: Regular point

A feasible point is regular whenever either or there do not exist scalars not all zero such that

Lemma

Suppose with is a regular point and a local optimal solution. Then there exist scalars such that Proof:
In this previous lemma, if we would contradict being regular, so we have . Dividing by this we get the desired statement.

Theorem: KKT conditions

Suppose is a regular point and a local optimal solution to . Then there exists a vector such that:

  1. ,
  2. ,
  3. ,
  4. .

Proof:
Suppose . (2) is already known from being feasible. (1) and (3) follow from the previous lemma and this lemma (setting whenever ). Then, since also whenever , (4) follows too.

Now suppose . Then we get from this theorem that so we can choose .