Background on Duality in Mathematical Programming

For a minimization problem, there exists an associated problem with the following property: any feasible solution to the associated problem provides a lower bound for the original problem, and conversely any feasible solution to the original problem provides an upper bound for the associated problem. The original and the associated problems are referred to as the primal and the dual problem, respectively. More specifically, consider the primal problem,

where , , and denote the sets of equality, inequality, and inequality constraints, respectively. Variables are called the primal variables. The Lagrangian function of the primal problem is defined as

where , , and . By convention, the Lagrange multipliers for inequality constraints have to be nonnegative. Hence , , and correspond to the Lagrange multipliers in the preceding Lagrangian function. It can be seen that the Lagrangian function is a linear combination of the objective function and constraints of the primal problem.

The Lagrangian function plays a fundamental role in nonlinear programming. It is used to define the optimality conditions that characterize a local minimum of the primal problem. It is also used to formulate the dual problem of the preceding primal problem. To this end, consider the following dual function:

The dual problem is defined as

The variables , , and are called the dual variables. Note that the dual variables associated with the equality constraints () are free, whereas those associated with inequality constraints () have to be nonpositive and those associated with inequality constraints () have to be nonnegative.

The relation between the primal and the dual problems provides a nice connection between the optimal solutions of the problems. Suppose is an optimal solution of the primal problem and is an optimal solution of the dual problem. The difference between the objective values of the primal and dual problems, , is called the duality gap. For some restricted class of convex nonlinear programming problems, both the primal and the dual problems have an optimal solution and the optimal objective values are equal—that is, the duality gap . In such cases, the optimal values of the dual variables correspond to the optimal Lagrange multipliers of the primal problem with the correct signs.

A maximization problem is treated analogously to a minimization problem. For the maximization problem

the dual problem is

where the dual function is defined as and the Lagrangian function is defined the same as earlier. In this case, , , and correspond to the Lagrange multipliers in .

Minimization Problems

For inequality constraints in minimization problems, a positive optimal dual value indicates that the associated inequality constraint is active at the solution, and a negative optimal dual value indicates that the associated inequality constraint is active at the solution. In PROC OPTMODEL, the optimal dual value for a range constraint (a constraint with both upper and lower bounds) is the sum of the dual values associated with the upper and lower inequalities. Since only one of the two inequalities can be active, the sign of the optimal dual value, if nonzero, identifies which one is active.

For equality constraints in minimization problems, the optimal dual values are unrestricted in sign. A positive optimal dual value for an equality constraint implies that, starting close enough to the primal solution, the same optimum could be found if the equality constraint were replaced with a inequality constraint. A negative optimal dual value for an equality constraint implies that the same optimum could be found if the equality constraint were replaced with a inequality constraint.

The following is an example where simple linear programming is considered:

proc optmodel;
   var x, y;
   min z = 6*x + 7*y;
   con 
      4*x +   y >=  5,
       -x - 3*y <= -4,
        x +   y <=  4;
   solve;
   print x y;
   expand _ACON_ ;
   print _ACON_.dual _ACON_.body;

The PRINT statements generate the output shown in Figure 4.54.

Constraint _ACON_[1]: y + 4*x >= 5                                              
Constraint _ACON_[2]: - 3*y - x <= -4                                           
Constraint _ACON_[3]: y + x <= 4                                                

It can be seen that the first and second constraints are active, with dual values 1 and 2. Continue to submit the following statements. Notice how the objective value is changed in Figure 4.55.

   _ACON_[1].lb = _ACON_[1].lb - 1;
   solve;
   _ACON_[2].ub = _ACON_[2].ub + 1;
   solve;

The change is just as the dual values imply. After the first constraint is relaxed by one unit, the objective value is improved by one unit. For the second constraint, the relaxation and improvement are one unit and two units, respectively.

Note: The signs of dual values produced by PROC OPTMODEL depend, in some instances, on the way in which the corresponding constraints are entered. See the section Constraints for details.

Maximization Problems

For inequality constraints in maximization problems, a positive optimal dual value indicates that the associated inequality constraint is active at the solution, and a negative optimal dual value indicates that the associated inequality constraint is active at the solution. The optimal dual value for a range constraint is the sum of the dual values associated with the upper and lower inequalities. The sign of the optimal dual value identifies which inequality is active.

For equality constraints in maximization problems, the optimal dual values are unrestricted in sign. A positive optimal dual value for an equality constraint implies that, starting close enough to the primal solution, the same optimum could be found if the equality constraint were replaced with a inequality constraint. A negative optimal dual value for an equality constraint implies that the same optimum could be found if the equality constraint were replaced with a inequality constraint.

Caution: The signs of dual values produced by PROC OPTMODEL depend, in some instances, on the way in which the corresponding constraints are entered. See the section Constraints for details.