Does a Larger Dual Value corresponds to a Smaller Primal Value?

Question

I am confused about the relationship between primal and dual. I know in some cases we get optimal values of two equal to each other. But are there any relation between solutions to Primal and solutions to Dual? Can we convert one to another? If so, does a better dual solution always correspond to a better primal solution?

Answer 1

What you are looking for may be the the Strong Duality theorem. It says the following (cited from linear programming Robert J. Vanderbei)

If the primal problem has an optimal solution, $$ x^* = (x_1^*,x_2^*, \dots,x_n^*) $$ then the dual also has an optimal solution $$ y^* = (y_1^*,y_2^*, \dots,y_m^*) $$ such that $$ \sum_j c_jx_j^* = \sum_i b_iy_i^* $$

The idea is that as the simplex method solves the primal problem, it also implicitly solves the dual problem. Together with the Weak Duality theorem, we know the following \begin{array}{c|c|c|c} & \text{infeasible} & \text{has an optimal solution} & \text{unbounded} \\ \hline \text{infeasible} &\checkmark & \text{impossible}&\checkmark \\ \hline \text{has an optimal solution} &\text{impossible}&\checkmark& \text{impossible} \\ \hline \text{unbounded} &\checkmark & \text{impossible}&\text{impossible} \end{array}

Another theorem is the Complementary Slackness:

Suppose that $x = (x_1,x_2,\dots,x_n)$ is primal feasible and that $y = (y_1,y_2,\dots,y_m)$ is dual feasible. Let $(w_1,w_2,\dots,w_m)$ denote the corresponding primal slack variables, and let $(z_1,z_2,\dots,z_n)$ denote the corresponding dual slack variables. Then $x$ and $y$ are optimal for their respective problems iff $$ \begin{align*} &x_jz_j = 0 \quad for\ j = 1,2, \dots, n \\ &w_iy_i = 0 \quad for\ i = 1,2, \dots, m \end{align*} $$

It provides an alternative way to verify the optimality.

The extension of this will be the Strictly Complementary Slackness:

We can always find a pair of primal and dual feasible solutions which satisfy: for each $i$ and $j$

1. Exactly one of $x_j$ and $z_j$ is nonzero
2. Exactly one of $w_i$ and $y_i$ is nonzero

One more thing is that other than the Strict Complementary Slackness, you can prove the following

Consider the following linear program problem: \begin{align*} (P) \quad &\text{min} \quad &&c^Tx \\ &\text{s.t.} \quad &&Ax = b \\ & &&x \geq 0 \end{align*} and its dual problem is \begin{align*} (D) \quad &\text{min} \quad &&b^Ty \\ &\text{s.t.} \quad &&y^TA \leq c^T \\ \end{align*} Assume that both the $(P)$ and $(D)$ have optimal solutions. There exist optimal solutions to $(P)$ and to $(D)$ such that $$ x_i^*(c_i-y^{*^T}A_i) = 0 \quad \text{and} \quad x_i^* + (c_i-y^{*^T}A_i) > 0 $$ for every $i = 1,2, \dots, n$.

Side note: If you have a primal dictionary, you can use the negative transpose property to obtain the dual dictionary. However, I don't know if there is a formula to covert one feasible solution exactly to the other one.