LP Dual Generator

This page is a collection of interactive cheat sheets for deriving duals of linear programs (converting primals into duals), for deriving versions of Farkas' Lemma (theorems of the alternative), and for obtaining KKT conditions. Useful if you can never remember which way the inequalities go.

💡 Click highlighted elements to customize the problems.

Linear Programming Duality

Primal
maximize   \(c_1\) \(x_1\) \(+\) \(c_2\) \(x_2\) \(+\) \(c_3\) \(x_3\)
subject tos.t.   \(a_{11}\) \(x_1\) \(+\) \(a_{12}\) \(x_2\) \(+\) \(a_{13}\) \(x_3\) \(\ge\) \(b_1\)
\(a_{21}\) \(x_1\) \(+\) \(a_{22}\) \(x_2\) \(+\) \(a_{23}\) \(x_3\) \(\ge\) \(b_2\)
\(a_{31}\) \(x_1\) \(+\) \(a_{32}\) \(x_2\) \(+\) \(a_{33}\) \(x_3\) \(\ge\) \(b_3\)
\(x_1\) \(\ge\) \(0\)
\(x_2\) \(\ge\) \(0\)
\(x_3\) \(\in\) \(\mathbb{R}\)
Dual
minimize   \(b_1\) \(p_1\) \(+\) \(b_2\) \(p_2\) \(+\) \(b_3\) \(p_3\)
subject tos.t.   \(a_{11}\) \(p_1\) \(+\) \(a_{21}\) \(p_2\) \(+\) \(a_{31}\) \(p_3\) \(\ge\) \(c_1\)
\(a_{12}\) \(p_1\) \(+\) \(a_{22}\) \(p_2\) \(+\) \(a_{32}\) \(p_3\) \(\ge\) \(c_2\)
\(a_{13}\) \(p_1\) \(+\) \(a_{23}\) \(p_2\) \(+\) \(a_{33}\) \(p_3\) \(\ge\) \(c_3\)
\(p_1\) \(\ge\) \(0\)
\(p_2\) \(\ge\) \(0\)
\(p_3\) \(\in\) \(\mathbb{R}\)

Farkas' Lemma

If this program has no solutions...
\(a_{11}\) \(x_1\) \(+\) \(a_{12}\) \(x_2\) \(+\) \(a_{13}\) \(x_3\) \(\le\) \(b_1\)
\(a_{21}\) \(x_1\) \(+\) \(a_{22}\) \(x_2\) \(+\) \(a_{23}\) \(x_3\) \(\le\) \(b_2\)
\(a_{31}\) \(x_1\) \(+\) \(a_{32}\) \(x_2\) \(+\) \(a_{33}\) \(x_3\) \(\le\) \(b_3\)
\(x_1\) \(\ge\) \(0\)
\(x_2\) \(\ge\) \(0\)
\(x_3\) \(\ge\) \(0\)
...then this program has a solution
\(b_1\) \(p_1\) \(+\) \(b_2\) \(p_2\) \(+\) \(b_3\) \(p_3\) \(<\) \(0\)
\(a_{11}\) \(p_1\) \(+\) \(a_{21}\) \(p_2\) \(+\) \(a_{31}\) \(p_3\) \(\ge\) \(0\)
\(a_{12}\) \(p_1\) \(+\) \(a_{22}\) \(p_2\) \(+\) \(a_{32}\) \(p_3\) \(\ge\) \(0\)
\(a_{13}\) \(p_1\) \(+\) \(a_{23}\) \(p_2\) \(+\) \(a_{33}\) \(p_3\) \(\ge\) \(0\)
\(p_1\) \(\ge\) \(0\)
\(p_2\) \(\ge\) \(0\)
\(p_3\) \(\in\) \(\mathbb{R}\)

Karush–Kuhn–Tucker (KKT) conditions

Optimization Problem
maximize   \(f(x_1, x_2, x_3)\)
subject to   \(g_1(x_1, x_2, x_3)\) \(\ge\) \(0\)
\(g_2(x_1, x_2, x_3)\) \(\ge\) \(0\)
\(g_3(x_1, x_2, x_3)\) \(\ge\) \(0\)
Lagrangian

\( \mathcal{L} = f(\vec{x}) \) \(-\) \( \lambda_1 g_1(\vec{x}) \) \(-\) \( \lambda_2 g_2(\vec{x}) \) \(-\) \( \lambda_3 g_3(\vec{x}) \)

First-Order Conditions

\( \frac{\partial f}{\partial x_1} = \frac{\partial f}{\partial x_2} = \frac{\partial f}{\partial x_3} = 0 \)

Dual Feasibility

\( \lambda_1 \geqslant 0 \) \( \lambda_2 \geqslant 0 \) \( \lambda_3 \geqslant 0 \)

Complementary Slackness

\( \lambda_1 g_1(\vec{x}) \) \(=\) \( \lambda_2 g_2(\vec{x}) \) \(=\) \( \lambda_3 g_3(\vec{x}) \) \(=\) \( 0 \)

Recommended Reading