Inequality constraints, alternative

Remark

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

Begin by noting that whenever all constraints are fulfilled strictly, we are in the interior of and thus whenever local optimal points are there, we will find them by solving , i.e. finding stationary points. The rest of this page will discuss finding optimal solutions on the boundary of , which is significantly harder.

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 .

Definition: Regular point

A point is regular whenever are conically independent.

With this lemma this definition becomes much more intuitive: is regular whenever there is a direction in which all active constraints become inactive, i.e. if it "touches" the interior of .

Theorem: KKT conditions

Let be regular and a local optimal solution. Then there are Lagrange multipliers such that

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

Proof:
Let and . Suppose together with are conically independent. Then, by this lemma, there is a direction in which and for all , meaning is a feasible descent direction, contradicting local optimality of . Since is regular, are conically independent meaning that makes conically dependent, so for some . Now take such that whenever and otherwise. This gives which is condition (1). (2) is clear since is feasible, and (3) is clear by the construction above. (4) follows since is nonzero only when which means .