2
$\begingroup$

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".

$\endgroup$
  • $\begingroup$ Thank you for the edits @RodrigodeAzevedo $\endgroup$ – guimption Jun 5 '17 at 14:18
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – guimption Jun 23 '17 at 3:48
  • $\begingroup$ The primal feasible point $x$ cannot be also dual feasible. The dual feasible point lies in a different dimension! $\endgroup$ – Alex Shtof Jun 24 '17 at 9:01
  • $\begingroup$ Yes, you are right. I've discovered a fundamental flaw in my understanding of weak duality, @Alex. So, you are saying that it is not mandatory that we stay dual feasible in our search for a solution. However, it does help with the stopping conditions, correct? The thing is, I do not recall seeing this step of checking dual feasibility in other methods (e.g. the ellipsoid method). $\endgroup$ – guimption Jun 24 '17 at 20:43
  • $\begingroup$ Correct. As for the Ellipsoid method, it can find an exact solution, unlike an interior point method. So its stopping criterion is simply "when the solution is found". However, you can use other stopping criteria, such as the volume of the ellipsoid. $\endgroup$ – Alex Shtof Jun 25 '17 at 7:41
  • $\begingroup$ Got it. So when the volume of the ellipsoid is very small, we can stop. Thank you. $\endgroup$ – guimption Jun 25 '17 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.