Optimality condition for a convex, linearly constrained problem

Theorem: optimality condition for convex, linearly constrained problems

Consider the linearly constrained optimization problem

 min_x : f_0(x) ~:~ Ax = b,

where f_0 : mathbf{R}^n rightarrow mathbf{R} is convex and differentiable, and A in mathbf{R}^{m times n}, b in mathbf{R}^m define the equality constraints.

A point x is optimal for the above problem if and only if it satisfies

 Ax = b, ;; nabla f_0(x) = A^T lambda.

for some vector lambda in mathbf{R}^m.

Proof: Let us re-formulate the optimality condition is

  x in mathbf{X} mbox{ and }  forall : y in mathbf{X} ~:~ nabla f_0(x) ^T (y-x) ge 0 .

where the feasible set mathbf{X} is now the affine set

 left{ x ~:~ Ax = b right}.

We can write the above as: Ax = b and

 forall : z , ;; Az = 0 ~:~ nabla f_0(x) ^T z ge 0 .

Since we can always flip the sign of vectors z with Az=0, we can express the above as

 forall : z , ;; Az = 0 ~:~ nabla f_0(x) ^T z = 0 .

This means that nabla f_0(x) should be orthogonal to the nullspace of A.

From the Fundamental theorem of linear algebra, this in turn says that nabla f_0(x) should belong to the range of the transpose matrix, mathbf{R}(A^T). In other words, the above condition is equivalent to

 exists : lambda in mathbf{R}^m ~:~ nabla f_0(x) = A^T lambda.

We conclude that the optimality conditions for x to be optimal are that there exists a vector lambda such that

 Ax = b, ;; nabla f_0(x) = A^T lambda.

This ends our proof.

Example: