Dual

From Glossary

Jump to: navigation, search

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.


Views
Personal tools