Optimality condition for a convex, linearly constrained problem

L. El Ghaoui

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): A x=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

$A x=b, \quad \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} \text { and } \forall y \in \mathbf{X}: \nabla f_0(x)^T(y-x) \geq 0 .$

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

$\{x: A x=b\} \text {. }$

We can write the above as: $A x=b$ and

$\forall z, \quad A z=0: \nabla f_0(x)^T z \geq 0 .$

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

$\forall z, \quad A z=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}\left(A^T\right)$ . 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

$A x=b, \quad \nabla f_0(x)=A^T \lambda .$

This ends our proof.

Optimality condition for a convex, linearly constrained problem

License

Share This Book