1
$\begingroup$

I have been studying some of the interior point methods recently, and there is one in particular that I find most intuitive: The path-following method method. In this method, we put the inequality constraints into the objective function, and vary $\mu$ from $\infty$ to $0$. This variation allows us to follow what is called the "central path".

But from my point of view any variation in $\mu$ towards 0 will allow us to reach the optimum eventually. So, why is it si important that we follow the special "central path" instead of just following some other route to the optimum?

EDIT: it is maybe true that I am missing understanding some of the properties of the central path. Some of the properties are covered here on slide 21: https://web.stanford.edu/class/msande310/lecture11.pdf. If someone can understand these better than me, then maybe I can see why following the central path is so important here.

SECOND EDIT: I am talking about $\mu$ in the sense of a modified objective function (usually called a barrier objective function) like this: $b^Ty+\mu\Sigma log(x_j)$ s.t. $x_j \ge 0$. Just as it shows in the link I posted.

Related question that might benefit from this: primal-dual interior-point method picking value of $\mu$

$\endgroup$
  • $\begingroup$ By varying $\mu$ you, by definition, follow the central path, because it is simply defined as the curve of optimal points obtained for all $\mu$. $\endgroup$ – Alex Shtof Jun 25 '17 at 8:10
  • $\begingroup$ yes, @Alex I understand that. But why not set $\mu$ to something very small, and optimize that instead of varying $\mu$? It should get you to the optimum faster, right? Why does we needs to follow the central path? Thanks. $\endgroup$ – jaja Jun 25 '17 at 18:45
  • $\begingroup$ Numerical reasons only. If you had infinite precision arithmetic as fast as floating point arithmetic, you could have done it in "one take" by choosing a tiny $\mu$ from the very beginning. $\endgroup$ – Alex Shtof Jun 25 '17 at 19:28
  • $\begingroup$ I don't exactly follow you...can you post an answer pls @Alex? $\endgroup$ – jaja Jun 25 '17 at 21:39
  • 2
    $\begingroup$ @Alex even in exact arithmetic it is generally better to follow the central path than to pick a single, small $\mu$. That's because if you start from very small $\mu$, it is very likely that you are "far" from the optimum solution, and Newton's method takes quite a few iterations to get to the region of quadratic convergence. On the other hand, the larger values of $\mu$ tend to get you to quadratic convergence sooner---and then if you reduce $\mu$ in a controlled fashion, you stay in this high-performance region. $\endgroup$ – Michael Grant Jun 25 '17 at 22:02
2
$\begingroup$

Let us look at a small example: $$ \begin{aligned} \min_x & \quad c^T x \\ \text{s.t.} &\quad e^T x \leq 1 \\ &\quad x_i \geq 0 \end{aligned} $$ where $e = (1, \dots, 1)^T$ and $c$ is some arbitrary vector in $\mathbb{R}^n$.

Now, let us look at the very simple case of a primal interior point method. The reason I am simplifying everything is because I want to demonstrate a point.

For a given $\mu$, the objective is to minimize $$ f(x) = c^T x - \frac{1}{\mu} \log(1 - \mathrm{e}^T x ) - \frac{1}{\mu}\sum_{i=1}^n \log(-x_i) $$

Let us see how this functions is minimized with Newton's method. The negative gradient is $$\nabla f(x) = \frac{1}{\mu} \underbrace{\left[ \mu c - \frac{1}{(1 - e^T x)} e - \left(\frac{1}{x_1}, \dots, \frac{1}{x_n}\right)^T \right]}_{g(x)}$$ The Hessian is $$ \nabla^2 f(x) = \frac{1}{\mu} \underbrace{\left[\frac{1}{\mu(1 - e^T x)^2} e e^T + \operatorname{diag}\left(\frac{1}{x_1^2}, \dots, \frac{1}{x_n^2}\right) \right]}_{H(x)} $$ In each iteration of Newton's method, we find the descent direction $d$ by solving the system $$ \nabla^2 f(x) d = -\nabla f(x) $$ or, equivalently, $$ H(x) d = -g(x) $$

Let us analyze some phenomena.

  • Case 1: $x$ is close to the boundary of the feasible set, and $\mu$ is moderate. In that case, some of the values $\{1 - e^T x, x_1, \dots, x_n\}$ are close to zero, while others are not. Thus, the matrix $H(x)$ becomes very ill-conditioned, and, in addition, some of the entries of $g(x)$ might be very small while others are very large. Both phenomena destroy any hope of accurately solving the Newton system.

  • Case 2: $x$ is far from the boundary of the feasible set, and $\mu$ is large. In that case, all of the values in the set $\{1 - e^T x, x_1, \dots, x_n\}$ are far away from zero, but the entries of $\mu c$ are very large. Thus, when computing $g(x)$ we add numbers of different orders of magnitude, causing serious round off errors. The same phenomena happen when computing $H(x)$. Thus, both $g(x)$ and $H(x)$ are inaccurate, and therefore our Newton direction $d$ is inaccurate.

  • Case 3: $x$ is far to the boundary, and $\mu$ is moderate. In that case, for the same reasoning above, both $g(x)$ and $H(x)$ are computed quite accurately, without entries of substantially different orders of magnitude. In addition $H(x)$ is not ill-conditioned, and we can find $d$ quite accurately.

  • Case 4: $x$ is close to the boundary, and $\mu$ is very large.The entries of $\mu c$ are become very large, some of the values in $\{1 - e^T x, x_1, \dots, x_n\}$ are close to zero while others are not. Thus, it seems that we are, again, adding numbers of different orders of magnitude. However, in this case it works in our favor, since near the boundary we should follow a direction that is similar to $c$, and thus making the rest of the terms when computing $g(x)$ negligible is not bad. The matrix $H(x)$ can be ill-conditioned and inaccurately computed. However, looking closer we observe that $g(x)$ is a sum of $\mu c$ and the dominant Eigenvectors of $H(x)$, and thus the Newton system is solved quite accurately.

Following the central path ensures that we always fall in cases 3 and 4.

$\endgroup$
  • 1
    $\begingroup$ I'd say this is pretty good, but I don't agree with your analysis of Case 2. Adding numbers of greatly different magnitudes does not introduce serious roundoff errors. Consider, for instance, $1+10^{-10]$. Even if our precision is low enough that we arrive at the result $1$---we have completely lost the second term---we still have a relative accuracy of $10^{-10}$, which is plenty adequate. The problems we encounter in numerical solutions are really not roundoff errors but cancellation errors: when two numbers of approximately the same magnitude are subtracted. $\endgroup$ – Michael Grant Jun 27 '17 at 5:34
  • $\begingroup$ I am confused about the precision here as well...this resource seems to also think that precision is lost when adding two numbers of different magnitude. Thank you guys for your continued attention to this question. $\endgroup$ – jaja Jun 28 '17 at 16:06
  • $\begingroup$ @Alex one more question for you: You say we follow the central path for “numerical reasons only”. I am surprised, because the central path also guarantees that we are dual feasible. Your answer here you say that we have to stay dual feasible “knowing when to stop”. I thought we would be following the central path in order to remain dual feasible for the reasons mentioned in this other question. $\endgroup$ – jaja Jun 30 '17 at 14:49
  • $\begingroup$ So, which one is it: 1) we follow the central path to guarantee that we are dual feasible to guarantee that we can know when to stop. OR 2) We guarantee that we are dual feasible in order to follow the central path, to guarantee that we do not run into numerical issues. which one? $\endgroup$ – jaja Jun 30 '17 at 14:49
  • 1
    $\begingroup$ Seems that @MichaelGrant is correct, and my analysis of the source of error is incorrect. He is also correct in saying that following the central path ensures that we stay close to the region of convergence of Newton's method, thus increasing the speed of the algorithm. $\endgroup$ – Alex Shtof Jul 3 '17 at 10: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.