8

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 \beta$ where $\beta < 1$ and $\mathbf{d}$ is the direction. This constraint is so that the new solution $\mathbf{x}+\mathbf{d}$ remains $> 0$ and thus feasible. $\mathbf{X}$ is a diagonal matrix with the elements of the variable vector $\mathbf{x}$ forming the diagonal.

However in the primal path method (related approach), 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 \beta$ 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 ($\mathbf{s}$ is the slack vector for slacks in the dual version of the problem). 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}$ (where $\mathbf{c'x}$ is the objective function of the original problem) in addition to the log terms in the barrier function so it 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.

Opt
  • 341
  • 1
  • 5
  • 1
    This questions assumes a ton of knowledge about common symbols and terms in the field of linear programming. I think it would be good to revise it so that $c$ and $s$, at the very least, are defined, and, preferably, so that $X$ and $d$ are defined and that potential reduction and primal path methods are linked to if not described as well. – Bill Barth Apr 13 '12 at 03:27
  • Clarified what $X$ is. Unfortunately I don't know of any good linkable references for the the two methods... – Opt Apr 13 '12 at 03:33
  • Maybe you could write up the descriptions (breifly). I feel like this is too jargon-heavy for anyone but an LP expert to understand. – Bill Barth Apr 13 '12 at 11:59
  • @Sid: I'm not sure whether this question is better suited to the mathematics site. I assume you have access to Nocedal/Wrights book? – Deathbreath Apr 13 '12 at 18:08
  • @Sid: The question isn't clear because you need to specify which potential-reduction method you are talking about. The classic ones, those of Tanabe and of Todd & Ye, are inherently primal-dual and act as merit functions, i.e., they can generate non-positive candidates and one must employ backtracking. Similarly, in the primal path-following method you need to specify if you're talking about the short-step method or another. Because of its special centrality parameter, the short-step method only generates positive iterates. It's not the case of other primal methods. – Dominique Jan 26 '13 at 20:42

0 Answers0