Optimal partition

From Glossary

Jump to: navigation, search

Consider a primal-dual pair of linear programs:

\min \left \{cx: x \ge 0, Ax \ge b \right \} \mbox{ and } \max \left \{yb: y \ge 0, yA \le c \right \}.

Define primal surplus variables, LaTeX: s = Ax - b, and dual slack variables, LaTeX: d = c - yA. For any non-negative vector, LaTeX: v, define its support set as those indexes for which the coordinate value is positive: LaTeX: \textstyle I(v)= \left \{j: v_j > 0 \right \}. In an optimal solution, complementary slackness must hold, so that LaTeX: \textstyle j \in I(x) implies LaTeX: j \notin I(d), and LaTeX: \textstyle i \in I(s) implies LaTeX: i \notin I(y). Thus, the intersections, LaTeX: \textstyle I(x) \land I(d) and LaTeX: \textstyle I(s) \land I(y), are empty. If the solution is strictly complementary, these support sets yield partitions because then LaTeX: \textstyle I(x) \lor I(d) = \left \{1, \dots, n \right \} and LaTeX: \textstyle I(s) \lor I(y) = \left \{1, \dots, m \right \}. A strictly complementary solution is an interior solution (and conversely), so each interior solution yields a partition of these index sets.

A key fact is that every LP with an optimal solution must have an optimal interior solution. Further, every optimal interior solution yields the same partition, so it is called the optimal partition.

Personal tools