# Why do we need to check both primal and dual feasibility in LP programs?

In in interior point method (and in fact in many practical optimization methods), a large part of the algorithm for finding the minimum is to follow a path called the central path while minimizing a potential function. Usually this is called the path finding algorithm or predictor-corrector method.

In the explanations of this algorithm, we make sure that the direction in which we traverse the path is in a direction that:

1) Remains feasible (i.e. satisfies $Ax=b$, when the primal is in standard form).

2) Remains dual feasible. Meaning that $yA \le c$ where $c$ is the cost vector for the objective function of the primal, and $y$ is the solution vector for the objective function of the dual.

I do not understand why it is necessary to remain both primal and dual feasible. If we have primal feasibility, why is it necessary to check that the direction we are traveling is also dual feasible?

This question helped a little bit, but I am still missing some intuition for this: primal and dual lp optimal?

edits: karger skoltech explains this in this lecture: https://www.youtube.com/watch?v=78sNnf3pOYs. He says, "our direction of movement must be feasible....and we also need dual feasibility".

• Thank you for the edits @RodrigodeAzevedo – guimption Jun 5 '17 at 14:18

If both primal iterate $x^k$ and the dual iterate $y^k$ are feasible for their respective LP problems, then by weak duality (assuming the primal is a minimization problem) $$c^T x^k \geq c^T x^* \geq b^T y^k$$ Thus, the "duality gap" $c^T x^k - b^T y^k$ measures how close you are to optimality. When this value is small enough, you can stop the algorithm and return the solution to the caller.
• Yes, I understand what you are saying @Alex. But, I thought that weak duality theorem for linear programming problems suggests that if we find a point $x$ that is feasible for the primal, then it is also feasible for the dual? Or is that not true? – guimption Jun 23 '17 at 3:48
• The primal feasible point $x$ cannot be also dual feasible. The dual feasible point lies in a different dimension! – Alex Shtof Jun 24 '17 at 9:01