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.
No comments:
Post a Comment