Duality

Author: Claire Gauthier, Trent Melsheimer, Alexa Piper, Nicholas Chung, Michael Kulbacki (SysEn 6800 Fall 2020)

Steward: TA's name, Fengqi You

Introduction

Every linear programming optimization problem may be viewed either from the primal or the dual, this is the principal of duality. Duality develops the relationships between one linear programming problem and another related linear programming problem. For example in economics, if the primal optimization problem deals with production and consumption levels, then the dual of that problem relates to the prices of goods and services. The dual variables in this example can be referred to as shadow prices.

The shadow price of a constraint ...

Theory, methodology, and/or algorithmic discussions

Definition:

Primal

Maximize $z=\textstyle \sum _{j=1}^{n}\displaystyle c_{j}x_{j}$

subject to:

$\textstyle \sum _{j=1}^{n}\displaystyle a_{i,j}x_{j}\lneq b_{j}\qquad (i=1,2,...,m)$

$x_{j}\gneq 0\qquad (j=1,2,...,n)$

Dual

Minimize $v=\textstyle \sum _{i=1}^{m}\displaystyle b_{i}y_{i}$

subject to:

$\textstyle \sum _{i=1}^{m}\displaystyle a_{i,j}y_{i}\gneq c_{j}\qquad (j=1,2,...,n)$

$y_{i}\gneq 0\qquad (i=1,2,...,m)$

Between the primal and the dual, the variables $c$ and $b$ switch places with each other. The coefficient ($c_{j}$) of the primal becomes the Right Hand Side (RHS) of the dual. The RHS of the primal ($b_{j}$) becomes the coefficient of the dual. The less than or equal to constraints in the primal become greater than or equal to in the dual problem.

Constructing a Dual:

${\begin{matrix}\max(c^{T}x)\\\ s.t.Ax\leq b\\x\geq 0\end{matrix}}$ $\quad \longrightarrow \quad$${\begin{matrix}\\\min(b^{T}y)\\\ s.t.A^{T}x\geq c\\y\geq 0\end{matrix}}$

Duality Properties:

Weak Duality

• let $x=[x_{1},...,x_{n}]$ be any feasible solution to the primal
• let $y=[y_{1},...,y_{m}]$be any feasible solution to the dual
• $\therefore$(z value for x) $\leq$(v value for y)

The weak duality theorem says that the z value for x in the primal is always less than or equal to the v value of y in the dual.

Numerical Example

Construct the Dual for the following maximization problem:

maximize $z=6x_{1}+14x_{2}+13x_{3}$

subject to:

${\tfrac {1}{2}}x_{1}+2x_{2}+x_{3}\leq 24$

$x_{1}+2x_{2}+4x_{3}\leq 60$

For the problem above, form augmented matrix A. The first two rows represent constraints one and two respectively. The last row represents the objective function.

$A={\begin{bmatrix}{\tfrac {1}{2}}&2&1&24\\1&2&4&60\\6&14&13&1\end{bmatrix}}$

Find the transpose of matrix A

$A^{T}={\begin{bmatrix}{\tfrac {1}{2}}&1&6\\2&2&14\\1&4&13\\24&60&1\end{bmatrix}}$

From the last row of the transpose of matrix A, we can derive the objective function of the dual. Each of the preceding rows represents a constraint. Note that the original maximization problem had three variables and two constraints. The dual problem has two variables and three constraints.

minimize $z=24y-1+60y_{2}$

subject to:

${\tfrac {1}{2}}y_{1}+y_{2}\geq 6$

$2y_{1}+2y_{2}\geq 14$

$y_{1}+4y_{2}\geq 13$

References

1. https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec18_duality_thy.pdf
2. http://web.mit.edu/15.053/www/AMP-Chapter-04.pdf