In mathematics, optimization can generally be described as maximizing or minimizing an objective function subject to some set of constraints. An Objective function is the set of variables which you are trying to optimize in order to find an optimal solution and the constraints are equations which consist of variables limited by some sort resources or time. Depending on the structure of the constraints and objective function, we can utilize different sets of mathematical tools for different structured problems. In particular, if we assume that the constraints and objective function are convex, then the problem becomes easier and more reliable to solve, this is due in part by duality theory. Duality theory associates a given optimization problem (the primal) to another to optimization problem (the dual). As some dual problems are easier to solve than their primal counterpart, the notion of duality has had a huge on many mathematical problems. For example, in matrix form, we can express the primal problem as:
- maximize
- subject to
The corresponding dual problem is:
- minimize
- subject to
where y is used instead of x as variable vector. The number of constraints in the primal problem corresponds to the number of variables in the dual (and vice versa), it is this duality in linear programming which allows some problems to be solved easier in their dual space.
Filed under: Mathematics | Tagged: convex, dual, duality, Mathematics, optimization
