Linear Programming

Let us consider a constrained optimization problem in the form $$\begin{array}{rl}\underset{\mathbf{x}}{\max }& {\mathbf{c}}^{\top }\mathbf{x}\\ \text{s.t.}& \mathbf{A}\mathbf{x}\le \mathbf{b}\\ & \mathbf{x}\ge 0.\end{array}$$

As both the objective function and constraints are linear the problem is convex. For this reason KKT conditions are not only necessary but also sufficient if a feasible $x$ w.r.t the constraints exists.

KKT conditions

The KKT conditions of this problem can be states as: $$\begin{array}{rlr}\mathbf{c}+{\mathbf{A}}^{\top }{\mathbf{\mu }}_1-{\mathbf{\mu }}_2& =0& \text{stationarity}\\ \mathbf{A}\mathbf{x}& \le \mathbf{b}& \text{primal feasibility}\\ \mathbf{x}& \ge 0& \\ {\mathbf{\mu }}_1& \ge 0& \text{dual feasibility}\\ {\mathbf{\mu }}_2& \ge 0& \\ {\mathbf{\mu }}_1^{\top }(\mathbf{A}\mathbf{x}-\mathbf{b})& =0& \text{complementary slackness}\\ -{\mathbf{\mu }}_2^{\top }\mathbf{x}& =0& \end{array}$$

Dual problem

The dual problem of the LP problem can be written as $$\begin{array}{rl}\underset{{\mathbf{\mu }}_1,{\mathbf{\mu }}_2}{\max }& \underset{q({\mathbf{\mu }}_1,{\mathbf{\mu }}_2)}{\underbrace{\underset{\mathbf{x}}{\min }L(\mathbf{x},{\mathbf{\mu }}_1,{\mathbf{\mu }}_2)}},L(\mathbf{x},{\mathbf{\mu }}_1,{\mathbf{\mu }}_2)=-{\mathbf{c}}^{\top }\mathbf{x}-{\mathbf{\mu }}_1^{\top }\mathbf{x}+{\mathbf{\mu }}_2^{\top }(\mathbf{A}\mathbf{x}-\mathbf{b})\\ \text{s.t.}& {\mathbf{\mu }}_1\ge 0\\ & {\mathbf{\mu }}_2\ge 0\\ & ({\mathbf{\mu }}_1,{\mathbf{\mu }}_2)\in \{{\mathbf{\mu }}_1,{\mathbf{\mu }}_2\mid q({\mathbf{\mu }}_1,{\mathbf{\mu }}_2)>-\infty \},\end{array}$$ where the Lagrangian can be manipulated into the form $$L(\mathbf{x},{\mathbf{\mu }}_1,{\mathbf{\mu }}_2)={\mathbf{x}}^{\top }({\mathbf{A}}^{\top }{\mathbf{\mu }}_2-{\mathbf{\mu }}_1-\mathbf{c})-{\mathbf{b}}^{\top }{\mathbf{\mu }}_2.$$ As we are only looking for bound solutions (last constraint) the condition $${\mathbf{A}}^{\top }{\mathbf{\mu }}_2-{\mathbf{\mu }}_1-\mathbf{c}=0$$ must be satisfied and therefore $${\mathbf{\mu }}_1={\mathbf{A}}^{\top }{\mathbf{\mu }}_2-\mathbf{c}$$ When substituted back into the original dual problem, after basic manipulations, we attain $$\begin{array}{rl}\underset{{\mathbf{\mu }}_2}{\min }& {\mathbf{b}}^{\top }{\mathbf{\mu }}_2\\ \text{s.t.}& {\mathbf{A}}^{\top }{\mathbf{\mu }}_2\ge \mathbf{c}\\ & {\mathbf{\mu }}_2\ge 0\end{array}$$