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".
Best Answer
One reason is knowing when to stop.
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.