One of the Interior Point Methods is the Primal/Dual path following method. In this method we decrease the log barrier term of the Barrier function, while still remaining primal and dual feasible. At each iteration we need to solve the equations for the KKT conditions, including complementary slackness. the complementary slackness means that the equations are non-linear, so we need to use newtons method to solve these equations. Newton's method only gives you directions in which you can move to stay feasible, but then you have to decide how far to move in those directions. So, essentially we need to know two things:
1) The direction to move each of the variables.
2) How far to move in each of those directions.
I'm confused on how far to move in those directions.
- I see one resource here which seems to say on slide 10 that you can just move as far as possible that allows you to stay feasible. Basically it says $\alpha_p = max(\alpha \ge 0 \vert s+\alpha\Delta s \ge 0)$ for the primal, and $\alpha_d = max(\alpha \ge 0 \vert z+\alpha\Delta z \ge 0)$ for the dual.
- I see another resource in the book Bertisimas and Tsitsiklis that suggests taking the minimum of these two values (on page 434): $\beta_p = min(1, \alpha * min (\frac{x^k_i}{d^k_x}))$ and for the dual: $\beta_d = min(1, \alpha * min (\frac{s^k_i}{d^k_s}))$. Apparently this will allow us to stay feasible, although it is not clear to me how.
How will these two approahces above allow us to stay feasible in the dual and primal sense?
Finally, Why can we not pick different different alpha values for the two dual variables, $d$ and $s$? Both of these methods seem to agree that we must move the same amount for all of the dual variables.
Your question misquotes the formulas from page 10 of the lecture slides- you might want to correct this.
In practical implementations of the primal-dual interior point method, it's typical to find the largest step size that is less than or equal to one and that keeps the primal and dual iterates feasible with respect to the nonnegativity constraints. In your notation, that means finding the largest $\alpha_{p}$ such as $x+\alpha_{p} \Delta x \geq 0$.
Both of your sources describe such a rule, although they use different notation. You can max
$\max_{x+\alpha \Delta x \geq 0} \alpha $
by using a ratio test and finding the minimum ratio of $x_{i}/(- \Delta x_{i})$ where the minimum is taken only over values of $\Delta x_{i}$ that are negative.
e.g. if $x_{1}=2$ and $\Delta x_{1}=-4$, then we must have $\alpha \leq 2/4=0.5$ to keep $x_{1}+\alpha \Delta x_{1} \geq 0$.
To answer your second question: If you use a different step length for the two dual variables, then you can move from a point that is feasible with respect to the dual equality constraints to a point that is infeasible with respect to the dual equality constraints. You want to retain feasibile with respect to these constraints.