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 12 Apr '12, 20:01

Sid's gravatar image

Sid
5312917
accept rate: 18%

edited 13 Apr '12, 01:39

1

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.

(13 Apr '12, 01:24) Ehsan ♦

Thanks! All fixed.

(13 Apr '12, 01:40) Sid
Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×4

Asked: 12 Apr '12, 20:01

Seen: 758 times

Last updated: 13 Apr '12, 01:40

OR-Exchange! Your site for questions, answers, and announcements about operations research.