how to get a feasible solution to dual program from a feasible solution to primal program?

Question

If a feasible solution to a linear programming is known, and the corresponding value of the objective function is close to the optimum, can we get a feasible solution to the dual programming which also reaches a value close to the optimal value, or only the value of objective function, but no solution? Thanks.

Answer 1

I don't know what "close to" really means, so let's suppose that you simply did obtain the optimal solution $\vec{x}$. In the generic situation, the objective $f(\vec{x})$ is a unique linear combination of the inequalities of the original program that are equalities for $\vec{x}$. The coefficients of that linear combination are the dual solution $\vec{y}$, and the linear combination proves the optimal value of $f(\vec{x})$. For example, suppose that in two dimensions the constraints are $$c_1(\vec{x}) = x_1 + 2x_2 \le 1 \qquad c_2(\vec{x}) = 2x_1 + x_2 \le 1,$$ and the objective is $f(x) = 3x_1 + 3x_2$. Then $f = c_1 + c_2$, and this expression proves that $f(\vec{x}) \le 2$, which is the optimum. In this example, $\vec{x} = (\frac13,\frac13)$ and $\vec{y} = (1,1)$.

If "close to" means that only the minimum number of constraints are close to equalities, then you can use the same principle.

If many constraints are equalities at the optimum $\vec{x}$, then there are many ways to take linear combinations of them to obtain the objective $f$. Some of these combinations have non-negative coefficients and some do not. The coefficients $\vec{y}$ of any non-negative combination are an optimum for the dual program. Finding a non-negative combination is exactly the question of finding a feasible point in a second linear program that can be anything. Geometrically speaking, $\vec{x}$ is a vertex of a polytope $P$ of feasible points. You would like a positive linear combination of the facet equations at $\vec{x}$ to match a supporting hyperplane that corresponds to the objective $f$. This is a matter of finding a feasible point to a certain problem which is dual to the cone at $\vec{x}$. This cone can be any convex polytopal cone in principle; so finding $\vec{y}$ is a general linear programming problem.

Answer 2

The primal feasible point gives you a bound for the optimum value of the dual. Since you have a quasi-optimal primal point, and there is no duality gap, the primal function value at this point is also a good approximation for the optimum value of the dual problem.

But I can't see how this helps you to find a quasi-optimal solution to the dual. I guess it doesn't.

Edit: I just heard of a process calling "pricing out" the primal. Given a basic feasible solution to the primal, define z'=cb'B^(-1), where B is the basis associated to this solution and cb the corresponding basic primal cost. When the primal solution is optimal, the same happens with the dual. The thing is that when the primal solution is quasi-optimal, it turns out that the dual solution is quasi-feasible. I think this is the best notion to associate a dual solution to a primal one.

Answer 3

Thanks. The "close to" means that the value of the objective function that the feasible solution gives is close to the optimal value of the objective function. In your example, x_1=x_2=0.33 is "close to" the optimum because it is feasible and the corresponding objective value is 1.98, which is close to 2. The "close to" in the dual case is same.