Dual Values :: SAS/OR(R) 12.1 User's Guide: Mathematical Programming

Dual Values

Background on Duality in Mathematical Programming
Minimization Problems
Maximization Problems

A dual value is associated with each constraint. To access the dual value of a constraint, use the constraint name followed by the suffix .dual.

For linear programming problems, the dual value associated with a constraint is also known as the dual price (also called the shadow price). The shadow price is usually interpreted economically as the rate at which the optimal value changes with respect to a change in some right-hand side that represents a resource supply or demand requirement.

For nonlinear programming problems, the dual values correspond to the values of the optimal Lagrange multipliers. For more details about duality in nonlinear programming, see Bazaraa, Sherali, and Shetty (1993).

From the dual value associated with the constraint, you can also tell whether the constraint is active or not. A constraint is said to be active (tight at a point) if it holds with equality at that point. It can be informative to identify active constraints at the optimal point and check their corresponding dual values. Relaxing the active constraints might improve the objective value.

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,

$\begin{array}{c@{\quad }l} \displaystyle \mathop \textrm{minimize}_{x} & f(x) \\ \textrm{subject to}& c_{i}(x) = 0, \quad i \in \mathcal E \\ & c_{i}(x) \le 0, \quad i \in \mathcal L \\ & c_{i}(x) \ge 0, \quad i \in \mathcal G \end{array}$

where $\mathcal E$ , $\mathcal L$ , and $\mathcal G$ denote the sets of equality, $\le$ inequality, and $\ge$ inequality constraints, respectively. Variables $x\in \mathbb {R}^ n$ are called the primal variables. The Lagrangian function of the primal problem is defined as

$L(x,\lambda ,\mu ,\nu )=f(x)-\sum _{i\in \mathcal E} \lambda _{i} c_{i}(x) - \sum _{i\in \mathcal L} \mu _{i} c_{i}(x) - \sum _{i\in \mathcal G} \nu _{i} c_{i}(x)$

where $\lambda _ i\in \mathbb {R}$ , $\mu _ i\le 0$ , and $\nu _ i\ge 0$ . By convention, the Lagrange multipliers for inequality constraints have to be nonnegative. Hence $\lambda$ , $-\mu$ , and $\nu$ 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:

$d(\lambda ,\mu ,\nu ) = \inf _ x\; L(x,\lambda ,\mu ,\nu )$

The dual problem is defined as

$\begin{array}{c@{\quad }l} \displaystyle \mathop \textrm{maximize}_{\lambda ,\mu ,\nu } & d(\lambda ,\mu ,\nu ) \\ \textrm{subject to}& \mu \le 0 \\ & \nu \ge 0. \end{array}$

The variables $\lambda$ , $\mu$ , and $\nu$ are called the dual variables. Note that the dual variables associated with the equality constraints ( $\lambda$ ) are free, whereas those associated with $\le$ inequality constraints ( $\mu$ ) have to be nonpositive and those associated with $\ge$ inequality constraints ( $\nu$ ) 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 $(\lambda ^*, \mu ^*, \nu ^*)$ is an optimal solution of the dual problem. The difference between the objective values of the primal and dual problems, $\delta = f(x^*) - d(\lambda ^*,\mu ^*,\nu ^*) \ge 0$ , 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 $\delta =0$ . 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

$\begin{array}{c@{\quad }l} \displaystyle \mathop \textrm{maximize}_{x} & f(x) \\ \textrm{subject to}& c_{i}(x) = 0, \quad i \in \mathcal E \\ & c_{i}(x) \le 0, \quad i \in \mathcal L \\ & c_{i}(x) \ge 0, \quad i \in \mathcal G, \end{array}$

the dual problem is

$\begin{array}{c@{\quad }l} \displaystyle \mathop \textrm{minimize}_{\lambda ,\mu ,\nu } & d(\lambda ,\mu ,\nu ) \\ \textrm{subject to}& \mu \ge 0 \\ & \nu \le 0. \end{array}$

where the dual function is defined as $\displaystyle d(\lambda ,\mu ,\nu )=\sup _ x\; L(x,\lambda ,\mu ,\nu )$ and the Lagrangian function $L(x,\lambda ,\mu ,\nu )$ is defined the same as earlier. In this case, $\lambda$ , $\mu$ , and $-\nu$ correspond to the Lagrange multipliers in $L(x,\lambda ,\mu ,\nu )$ .

Minimization Problems

For inequality constraints in minimization problems, a positive optimal dual value indicates that the associated $\ge$ inequality constraint is active at the solution, and a negative optimal dual value indicates that the associated $\le$ 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 $\ge$ 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 $\le$ 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 5.55.

Figure 5.55: Dual Values in Minimization Problem: Display

Problem Summary
Objective Sense	Minimization
Objective Function	z
Objective Type	Linear

Number of Variables	2
Bounded Above	0
Bounded Below	0
Bounded Below and Above	0
Free	2
Fixed	0

Number of Constraints	3
Linear LE (<=)	2
Linear EQ (=)	0
Linear GE (>=)	1
Linear Range	0

Constraint Coefficients	6

Performance Information
Execution Mode	On Client
Number of Threads	1

Solution Summary
Solver	LP
Algorithm	Dual Simplex
Objective Function	z
Solution Status	Optimal
Objective Value	13
Iterations	5

Primal Infeasibility	0
Dual Infeasibility	0
Bound Infeasibility	0

x	y
1	1

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

[1]	_ACON_.DUAL	_ACON_.BODY
1	1	5
2	-2	-4
3	0	2

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 5.56.

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

Figure 5.56: Dual Values in Minimization Problem: Interpretation

Problem Summary
Objective Sense	Minimization
Objective Function	z
Objective Type	Linear

Number of Variables	2
Bounded Above	0
Bounded Below	0
Bounded Below and Above	0
Free	2
Fixed	0

Number of Constraints	3
Linear LE (<=)	2
Linear EQ (=)	0
Linear GE (>=)	1
Linear Range	0

Constraint Coefficients	6

Performance Information
Execution Mode	On Client
Number of Threads	1

Solution Summary
Solver	LP
Algorithm	Dual Simplex
Objective Function	z
Solution Status	Optimal
Objective Value	12
Iterations	5

Primal Infeasibility	0
Dual Infeasibility	0
Bound Infeasibility	0

Problem Summary
Objective Sense	Minimization
Objective Function	z
Objective Type	Linear

Number of Variables	2
Bounded Above	0
Bounded Below	0
Bounded Below and Above	0
Free	2
Fixed	0

Number of Constraints	3
Linear LE (<=)	2
Linear EQ (=)	0
Linear GE (>=)	1
Linear Range	0

Constraint Coefficients	6

Performance Information
Execution Mode	On Client
Number of Threads	1

Solution Summary
Solver	LP
Algorithm	Dual Simplex
Objective Function	z
Solution Status	Optimal
Objective Value	10
Iterations	5

Primal Infeasibility	0
Dual Infeasibility	0
Bound Infeasibility	0

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 $\le$ inequality constraint is active at the solution, and a negative optimal dual value indicates that the associated $\ge$ 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 $\le$ 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 $\ge$ 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.