how to get a feasible solution to dual program from a feasible solution to primal program? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T09:36:58Z http://mathoverflow.net/feeds/question/9469 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/9469/how-to-get-a-feasible-solution-to-dual-program-from-a-feasible-solution-to-primal how to get a feasible solution to dual program from a feasible solution to primal program? wander 2009-12-21T12:34:30Z 2010-01-12T11:59:53Z <p>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.</p> http://mathoverflow.net/questions/9469/how-to-get-a-feasible-solution-to-dual-program-from-a-feasible-solution-to-primal/9489#9489 Answer by Greg Kuperberg for how to get a feasible solution to dual program from a feasible solution to primal program? Greg Kuperberg 2009-12-21T17:07:29Z 2009-12-21T17:07:29Z <p>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)$.</p> <p>If "close to" means that only the minimum number of constraints are close to equalities, then you can use the same principle.</p> <p>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.</p> http://mathoverflow.net/questions/9469/how-to-get-a-feasible-solution-to-dual-program-from-a-feasible-solution-to-primal/9528#9528 Answer by Penghui Yao for how to get a feasible solution to dual program from a feasible solution to primal program? Penghui Yao 2009-12-22T03:45:10Z 2009-12-22T03:45:10Z <p>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.</p> http://mathoverflow.net/questions/9469/how-to-get-a-feasible-solution-to-dual-program-from-a-feasible-solution-to-primal/9770#9770 Answer by Shake Baby for how to get a feasible solution to dual program from a feasible solution to primal program? Shake Baby 2009-12-26T02:13:28Z 2010-01-12T11:59:53Z <p>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.</p> <p>But I can't see how this helps you to find a quasi-optimal solution to the dual. I guess it doesn't.</p> <p>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.</p>