 # Dual

Another mathematical program with the property that its objective is always a bound on the original mathematical program, called the primal. Suppose the dual is $LaTeX: \min \{ F(y): y \in Y\}$. Then, $LaTeX: F(y) \ge f(x)$ for all feasible $LaTeX: x$ in the primal and all $LaTeX: y$ in Y. This immediately implies that if the primal is feasible, the dual cannot be unbounded, and vice versa: if the dual is feasible, the primal cannot be unbounded. It also implies that if the dual is unbounded, the primal must be infeasible (and vice versa). A dual provides a sufficiency test for optimality, for if feasible $LaTeX: x$ and $LaTeX: y$ can be found such that $LaTeX: f(x)=F(y)$, it follows that $LaTeX: x$ is optimal in the primal and $LaTeX: y$ is optimal in the dual. Weak duality is when this sufficient condition is all that can be guaranteed. Strong duality is when a finite optimal value to one problem ensures the existence of an optimal solution to the other and that their optimal objective values are equal. There are particular duals of significance.