In both the potential reduction and primal path following interior point methods for linear programming, a barrier function is constructed which contains the terms ( -sum log x_j ) where (x_j) are the variables. This is to keep the variables from being 0 and thus keep the current solution feasible. However, in potential reduction, the new direction to move the current solution to is found by solving a linear program which contains as the single inequality constraint (||mathbf{X^{-1}d}|| leq eta) where (eta < 1), (mathbf{X}) is a diagonal matrix with (mathbf{x}) making up the diagonal, and (mathbf{d}) is the direction. This constraint is so that the new solution (mathbf{x+d}) remains (> 0) and thus feasible. However in the primal path method, one can just solve the Lagrangian dual of the barrier function problem and the new solution is guaranteed to be feasible - i.e. the property (||mathbf{X^{-1}d}|| leq eta) is guaranteed to be satisfied. Is there some good intuition as to why primal path can get away with just solving the Lagrangian dual (and thus not have to deal with inequalities) while potential reduction cannot? The best I can think of is that the barrier function in the potential reduction algorithm contains the term (log mathbf{s'x}) where (mathbf{s'x}) is the duality gap. This term thus strongly pulls (mathbf{x+d}) into a potentially infeasible region. The barrier function for the primal path only has the term (mathbf{c'x}) as part of the barrier function which does not exert as strong a pull (as it will not for instance go to (-infty) when (mathbf{c'x}) goes to 0 unlike (log mathbf{s'x}) which will). However I don't know how to formalize this.
asked
Sid |

Your current equations are somehow hard to read. For inline equations you should put your equations and/or variables between backslash-backslash-( and backslash-backslash-). I tried correcting them, but I got stuck with some of the equations.

Thanks! All fixed.