Optimality conditions

Remark

Here, we consider a convex optimization problem with inequality conditions, where all and all 's are convex and continuously differentiable.

Theorem

If and satisfy the KKT conditions

  1. ,
  2. ,
  3. ,

then is a (global) optimal solution.

Proof:
Define Since we know is convex and continuously differentiable. (1) gives meaning is a global optimal solution for (since is convex). (2) gives that . Finally, suppose . By (4), , so by (3) and since , so is indeed optimal.

Definition: Regular convex problem

is regular if there exists an with .

Lemma

If is regular, then every feasible solution is regular.

Proof:
If we are done. Otherwise, let where . From convexity of the 's we get Whenever we have meaning . This means is a regular point, by this lemma.

Theorem

If is regular, then is a (global) optimal solution if and only if there exists a such that the KKT conditions are satisfied, i.e.,

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

Proof:
"If" is given by this previous theorem. "Only if" follows from the previous lemma saying that is regular, meaning we can use the usual KKT theorem.