ORF523: Interior Point Methods

Khachiyan’s ellipsoid method was such a breakthrough that it made it to The New York Times in 1979. The next time that optimization theory was featured in The New York Times was only a few years later, in 1984, and it was to report a new breakthrough: Karmakar’s Interior Point Method to solve LPs. Similarly to the ellipsoid method, it was shown that Karmakar’s algorithm is a polynomial time algorithm for LPs, but this time it was also shown that the method had very good empirical performances! We will now describe the idea behind this new class of algorithms, following the presentation of Nesterov and Nemirovski.

 

Interior point methods

Consider the following standard optimization problem:

$latex \displaystyle \text{Find} \; x^* \in \mathrm{argmin}_{x \in \mathcal{X}} c^{\top} x , \; \text{where} \; \mathcal{X} \subset {\mathbb R}^n \; \text{is convex body.}&fg=000000$

Assume that we can construct a barrier $latex {F}&fg=000000$ for the set $latex {\mathcal{X}}&fg=000000$, that is a real-valued function $latex {F}&fg=000000$ defined on $latex {\mathrm{int}(\mathcal{X})}&fg=000000$ and such that

$latex \displaystyle F(x) \rightarrow_{x \rightarrow \partial \mathcal{X}} + \infty .&fg=000000$

Let us extend the function $latex {F}&fg=000000$ to $latex {{\mathbb R}^n}&fg=000000$ with $latex {F(x) = +\infty}&fg=000000$ for $latex {x \not\in \mathrm{int}(\mathcal{X})}&fg=000000$. Then, instead of the original problem, one could consider the following penalized version, for $latex {t \geq 0}&fg=000000$:

$latex \displaystyle \min_{x \in {\mathbb R}^n} t c^{\top} x + F(x) .&fg=000000$

Let $latex {x^*(t)}&fg=000000$ be a solution to the above problem, we call the curve $latex {(x^*(t))_{t \geq 0}}&fg=000000$ the central path. Note that $latex {x^*(0)}&fg=000000$ is simply the minimizer of $latex {F}&fg=000000$, we call this point the analytical center of $latex {\mathcal{X}}&fg=000000$. Remark also that $latex {x^*(t) \rightarrow_{t \rightarrow +\infty} x^*}&fg=000000$, that is the central path converges to the solution of our original problem.

The whole idea of interior point methods is to ‘boost’ an efficient locally convergent optimization algorithm, such as Newton’s method, with the following scheme: Assume that we have found $latex {x^*(t)}&fg=000000$ for some $latex {t>0}&fg=000000$. Then let $latex {t’>t}&fg=000000$, and use the locally convergent algorithm, initialized at $latex {x^*(t)}&fg=000000$, to find $latex {x^*(t’)}&fg=000000$. In other words the idea is to move along the central path, using some basic algorithm to do small steps along the central path. The ‘basic algorithm’ that is used in interior point methods is the Newton’s method, because of its very fast local convergence.

To make this (beautiful) idea more formal we need to take care of several things:

1. First we need to describe precisely the region of fast convergence for Newton’s method. This will lead us to define self-concordant functions, which are ‘natural’ functions for Newton’s method.
2. Then we need to evaluate how much larger $latex {t’}&fg=000000$ can be compared to $latex {t}&fg=000000$, so that $latex {x^*(t)}&fg=000000$ is still in the region of fast convergence of Newton’s method when optimizing the function $latex {x \mapsto t’ c^{\top} x + F(x)}&fg=000000$ (which is minimized at $latex {x^*(t’)}&fg=000000$). This will lead us to define $latex {\nu}&fg=000000$-self concordant barriers.
3. Can we find easily the analytical center $latex {x^*(0)}&fg=000000$ of $latex {\mathcal{X}}&fg=000000$?

 

Traditional analysis of Newton’s method

In this section we denote $latex {\|\cdot\|}&fg=000000$ for both the Euclidean norm on $latex {{\mathbb R}^n}&fg=000000$ and the operator norm on matrices (in particular $latex {\|A x\| \leq \|A\| \cdot \|x\|}&fg=000000$).

Let $latex {f: {\mathbb R}^n \rightarrow {\mathbb R}}&fg=000000$ be a $latex {C^2}&fg=000000$ function. Newton’s method is a simple iterative optimization scheme. Using a Taylor’s expansion of $latex {f}&fg=000000$ around $latex {x}&fg=000000$ one obtains

$latex \displaystyle f(x+h) = f(x) + h^{\top} \nabla f(x) + \frac12 h^{\top} \nabla^2 f(x) h + o(\|h\|^2) .&fg=000000$

Thus, starting at $latex {x}&fg=000000$, in order to minimize $latex {f}&fg=000000$ it seems natural to move in the direction $latex {h}&fg=000000$ that minimizes

$latex \displaystyle h^{\top} \nabla f(x) + \frac12 h^{\top} \nabla f^2(x) h .&fg=000000$

If $latex {\nabla^2 f(x)}&fg=000000$ is invertible then the solution to this problem is given by $latex {h = – [\nabla^2 f(x)]^{-1} \nabla f(x)}&fg=000000$. Thus Newton’s method simply iterates this idea, starting at some point $latex {x_0 \in {\mathbb R}^n}&fg=000000$, and then

$latex \displaystyle x_{k+1} = x_k – [\nabla^2 f(x_k)]^{-1} \nabla f(x_k), k \geq 0 .&fg=000000$

While this method can have an arbitrarily bad behavior in general, if started close enough to a strict local minimum of $latex {f}&fg=000000$, it can have a very fast convergence:

Theorem 1 (Local quadratic convergence of Newton’s method) Assume that $latex {f}&fg=000000$ has a Lipschitz Hessian, that is $latex {\| \nabla^2 f(x) – \nabla^2 f(y) \| \leq M \|x – y\|}&fg=000000$. Let $latex {x^*}&fg=000000$ be local minimum of $latex {f}&fg=000000$ with strictly positive Hessian, that is $latex {\nabla^2 f(x^*) \succeq \mu I_n}&fg=000000$, $latex {\mu > 0}&fg=000000$. Suppose that the initial starting point $latex {x_0}&fg=000000$ of Newton’s method is such that

$latex \displaystyle \|x_0 – x^*\| \leq \frac{\mu}{2 M} .&fg=000000$

Then Newton’s method is well-defined and converges to $latex {x^*}&fg=000000$ at a quadratic rate:

$latex \displaystyle \|x_{k+1} – x^*\| \leq \frac{M}{\mu} \|x_k – x^*\|^2.&fg=000000$

Proof: We use the following simple formula, for $latex {x, h \in {\mathbb R}^n}&fg=000000$,

$latex \displaystyle \int_0^1 \nabla^2 f(x + s h) \ h \ ds = \nabla f(x+h) – \nabla f(x) .&fg=000000$

Now note that $latex {\nabla f(x^*) = 0}&fg=000000$, and thus with the above formula one obtains

$latex \displaystyle \nabla f(x_k) = \int_0^1 \nabla^2 f(x^* + s (x_k – x^*)) \ (x_k – x^*) \ ds ,&fg=000000$

which allows us to write:

$latex \displaystyle \begin{array}{rcl} x_{k+1} – x^* & = & x_k – x^* – [\nabla^2 f(x_k)]^{-1} \nabla f(x_k) \\ & = & x_k – x^* – [\nabla^2 f(x_k)]^{-1} \int_0^1 \nabla^2 f(x^* + s (x_k – x^*)) \ (x_k – x^*) \ ds \\ & = & [\nabla^2 f(x_k)]^{-1} \int_0^1 [\nabla^2 f (x_k) – \nabla^2 f(x^* + s (x_k – x^*)) ] \ (x_k – x^*) \ ds . \end{array} &fg=000000$

In particular one has

$latex \displaystyle \|x_{k+1} – x^*\| \leq \|[\nabla^2 f(x_k)]^{-1}\| \left( \int_0^1 \| \nabla^2 f (x_k) – \nabla^2 f(x^* + s (x_k – x^*)) \| \ ds \right) \|x_k – x^* \|.&fg=000000$

Using the Lipschitz property of the Hessian one immediately obtains that

$latex \displaystyle \left( \int_0^1 \| \nabla^2 f (x_k) – \nabla^2 f(x^* + s (x_k – x^*)) \| \ ds \right) \leq \frac{M}{2} \|x_k – x^*\| .&fg=000000$

Using again the Lipschitz property of the Hessian, the hypothesis on $latex {x^*}&fg=000000$, and an induction hypothesis that $latex {\|x_k – x^*\| \leq \frac{\mu}{2M}}&fg=000000$, one has

$latex \displaystyle \nabla^2 f(x_k) \succeq \nabla^2 f(x^*) – M \|x_k – x^*\| I_n \succeq (\mu – M \|x_k – x^*\|) I_n \succeq \frac{\mu}{2} I_n ,&fg=000000$

which concludes the proof. $latex \Box&fg=000000$

 

Self-concordant functions

Let $latex {A}&fg=000000$ be an invertible $latex {n \times n}&fg=000000$ matrix. We will use the following simple formulas:

$latex \displaystyle \nabla (x \mapsto f(A x) ) =A^{\top} \nabla f(A x) , \; \text{and} \; \nabla^2 (x \mapsto f(A x) ) =A^{\top} \nabla^2 f(A x) A . \ \ \ \ \ (1)&fg=000000$

Let us try to get some insight into the ‘geometry’ of Newton’s method by looking at the iteration that would be performed using the function $latex {\phi(y) = f(A^{-1} y)}&fg=000000$. In other words, we view $latex {A}&fg=000000$ as a mapping from $latex {{\mathbb R}^n}&fg=000000$ (the ‘$latex {x}&fg=000000$-space’) to $latex {{\mathbb R}^n}&fg=000000$ (the ‘$latex {y}&fg=000000$-space’), and the function $latex {\phi}&fg=000000$ is defined on the ‘$latex {y}&fg=000000$-space’, so that its evaluation at a point $latex {y=Ax}&fg=000000$ coincides with the evaluation of $latex {f}&fg=000000$ at $latex {x}&fg=000000$. Assume that we start Newton’s method on $latex {f}&fg=000000$ in the ‘$latex {x}&fg=000000$-space’ at $latex {x_0}&fg=000000$, and on $latex {\phi}&fg=000000$ in the ‘$latex {y}&fg=000000$-space’ at $latex {y_0 = Ax_0}&fg=000000$. The next iterations are then given by the following formulas:

$latex \displaystyle x_{k+1} = x_k – [\nabla^2 f(x_k)]^{-1} \nabla f(x_k) , \; \text{and} \; y_{k+1} = y_k – [\nabla^2 \phi(y_k)]^{-1} \nabla \phi(y_k) .&fg=000000$

Using (1) one can see in a few lines that $latex {y_{k+1} = A x_{k+1}}&fg=000000$, that is Newton’s method is affine invariant, it follows the same trajectory in the ‘$latex {x}&fg=000000$-space’ and the ‘$latex {y}&fg=000000$-space’!

This fact casts some concerns on the assumptions of the previous analysis: indeed the Lipschitz assumption on the Hessian is not affine invariant. The idea of self-concordance is to improve this situation.

Assume from now on that $latex {f}&fg=000000$ is $latex {C^3}&fg=000000$. Consider the third order differential operator $latex {\nabla^3 f(x) : {\mathbb R}^n \times {\mathbb R}^n \times {\mathbb R}^n \rightarrow {\mathbb R}}&fg=000000$. Then the Lipschitz assumption on the Hessian that we used can be written as:

$latex \displaystyle \nabla^3 f(x) [h,h,h] \leq M \|h\|^3 .&fg=000000$

The left-hand side in the inequality is affine invariant, but not the right-hand side. A natural idea to make the right-hand side affine invariant is to replace the Euclidean metric by the metric given by the function $latex {f}&fg=000000$ itself at $latex {x}&fg=000000$, that is:

$latex \displaystyle \|h\|_x = \sqrt{ h^{\top} \nabla^2 f(x) h }.&fg=000000$

Definition 2 Let $latex {\mathcal{X}}&fg=000000$ be a convex set with non-empty interior, and $latex {f}&fg=000000$ a $latex {C^3}&fg=000000$ convex function defined on $latex {\mathrm{int}(\mathcal{X})}&fg=000000$. Then $latex {f}&fg=000000$ is self-concordant (with constant $latex {M}&fg=000000$) if for all $latex {x \in \mathrm{int}(\mathcal{X}), h \in {\mathbb R}^n}&fg=000000$,

$latex \displaystyle \nabla^3 f(x) [h,h,h] \leq M \|h\|_x^3 .&fg=000000$

We say that $latex {f}&fg=000000$ is standard self-concordant if $latex {f}&fg=000000$ is self-concordant with constant $latex {M=2}&fg=000000$.

An easy consequence of the definition is that a self-concordant function is a barrier for the set $latex {\mathcal{X}}&fg=000000$. The main example to keep in mind of a standard self-concordant function is $latex {f(x) = – \log x}&fg=000000$ for $latex {x > 0}&fg=000000$. The next definition will be key in order to describe the region of quadratic convergence for Newton’s method on self-concordant functions. Recall first that for an arbitrary norm $latex {\|\cdot\|}&fg=000000$ on $latex {{\mathbb R}^n}&fg=000000$, its dual norm $latex {\|\cdot\|^*}&fg=000000$ is defined by

$latex \displaystyle \|h\|^* = \sup_{x \in {\mathbb R}^n : \|x\| \leq 1} x^{\top} h .&fg=000000$

In particular, by definition, Hölder’s inequality holds: $latex {|x^{\top} h| \leq \|x\| \cdot \|h\|^*}&fg=000000$. Recall also that for a norm of the form $latex {\|x\| = \sqrt{x^{\top} A x}}&fg=000000$, the dual norm is given by $latex {\|h\|^* = \sqrt{h^{\top} A^{-1} h}}&fg=000000$.

Definition 3 Let $latex {f}&fg=000000$ be a standard self-concordant function on $latex {\mathcal{X}}&fg=000000$. For $latex {x \in \mathrm{int}(\mathcal{X})}&fg=000000$, we say that $latex {\lambda_f(x) = \|\nabla f(x)\|_x^*}&fg=000000$ is the Newton decrement of $latex {f}&fg=000000$ at $latex {x}&fg=000000$.

We state the next theorem without a proof.

Theorem 4 Let $latex {f}&fg=000000$ be a standard self-concordant function on $latex {\mathcal{X}}&fg=000000$, and $latex {x \in \mathrm{int}(\mathcal{X})}&fg=000000$ such that $latex {\lambda_f(x) < 1}&fg=000000$, then

$latex \displaystyle \lambda_f\Big(x – [\nabla^2 f(x)]^{-1} \nabla f(x)\Big) \leq \left(\frac{\lambda_f(x)}{1-\lambda_f(x)}\right)^2 .&fg=000000$

In other words the above theorem states that, if initialized at a point $latex {x_0}&fg=000000$ such that $latex {\lambda_f(x_0) \leq 1/4}&fg=000000$, then Newton’s iterates satisfy $latex {\lambda_f(x_{k+1}) \leq 2 \lambda_f(x_k)^2}&fg=000000$. Thus, Newton’s region of quadratic convergence for self-concordant functions can be described as a ‘Newton decrement ball’ $latex {\{x : \lambda_f(x) < 1\}}&fg=000000$.

 

$latex {\nu}&fg=000000$-self-concordant barriers

Let us go back to our central path idea. Assume that we have computed $latex {x^*(t) = \mathrm{argmin}_{x \in {\mathbb R}^n} F_t(x)}&fg=000000$, where $latex {F_t(x) = t c^{\top} x + F(x)}&fg=000000$ and $latex {F}&fg=000000$ is a standard self-concordant function on $latex {\mathcal{X}}&fg=000000$. We want to use Newton’s method to compute $latex {x^*(t’)}&fg=000000$, starting at $latex {x_0 = x^*(t)}&fg=000000$. Thus, using the analysis of the previous section, we need to ensure that

$latex \displaystyle \lambda_{F_{t’}}(x^*(t) ) < 1/4 .&fg=000000$

Since the Hessian of $latex {F_{t’}}&fg=000000$ is the Hessian of $latex {F}&fg=000000$, one has with $latex {\|h\|_x = \sqrt{ h^{\top} \nabla^2 f(x) h }}&fg=000000$,

$latex \displaystyle \lambda_{F_{t’}}(x^*(t) ) = \|t’ c + \nabla F(x^*(t)) \|_{x^*(t)}^* .&fg=000000$

Now, by the first-order optimality condition, one has $latex {t c + \nabla F(x^*(t)) = 0}&fg=000000$, which yields

$latex \displaystyle \lambda_{F_{t’}}(x^*(t) ) = (t’-t) \|c\|^*_{x^*(t)} .&fg=000000$

Thus we can take $latex {t’ = t + \frac{1}{4 \|c\|^*_{x^*(t)}}}&fg=000000$, and according to the analysis of the previous section the Newton’s method will converge very rapidly to $latex {x^*(t’)}&fg=000000$. Now to obtain a reasonable optimization method overall, we need to make sure that we are increasing $latex {t}&fg=000000$ fast enough. That is we need to control $latex {\|c\|^*_{x^*(t)} = \frac1{t} \|\nabla F(x^*(t))\|_{x^*(t)}^*}&fg=000000$. In particular we could do this if we had a uniform control over $latex {\|\nabla F(x)\|_x^*}&fg=000000$. There is a natural class of functions for which such a control exist. This is the set of functions such that

$latex \displaystyle \nabla^2 F(x) \succeq \frac1{\nu} \nabla F(x) [\nabla F(x) ]^{\top} . \ \ \ \ \ (2)&fg=000000$

Indeed in that case one has:

$latex \displaystyle \|\nabla F(x)\|_x^* = \sup_{h : h^{\top} \nabla F^2(x) h \leq 1} \nabla F(x)^{\top} x \leq \sup_{h : h^{\top} \left( \frac1{\nu} \nabla F(x) [\nabla F(x) ]^{\top} \right) h \leq 1} \nabla F(x)^{\top} x = \sqrt{\nu} .&fg=000000$

Thus a safe choice to increase the penalization parameter is $latex {t’ = \left(1 + \frac1{4\sqrt{\nu}}\right) t}&fg=000000$. Note that the condition (2) can also be written as the fact that the function $latex {F}&fg=000000$ is $latex {\frac1{\nu}}&fg=000000$-exp-concave, that is $latex {x \mapsto \exp(- \frac1{\nu} F(x))}&fg=000000$ is concave. We arrive at the following definition.

Definition 5 $latex {F}&fg=000000$ is a $latex {\nu}&fg=000000$-self-concordant barrier if it is a standard self-concordant function, and it is $latex {\frac1{\nu}}&fg=000000$-exp-concave.

Again the canonical example is the logarithmic function, $latex {x \mapsto – \log x}&fg=000000$, which is a $latex {1}&fg=000000$-self-concordant barrier for the set $latex {{\mathbb R}_+}&fg=000000$. We state the next (difficult) theorem without a proof.

Theorem 6 Let $latex {\mathcal{X} \subset {\mathbb R}^n}&fg=000000$ be a closed convex set with non-empty interior. There exists $latex {F}&fg=000000$ which is a $latex {(c \ n)}&fg=000000$-self-concordant barrier for $latex {\mathcal{X}}&fg=000000$ (where $latex {c}&fg=000000$ is some universal constant).

A key property of $latex {\nu}&fg=000000$-self-concordant barriers is the following inequality:

$latex \displaystyle c^{\top} x^*(t) – \min_{x \in \mathcal{X}} c^{\top} x \leq \frac{\nu}{t} . \ \ \ \ \ (3)&fg=000000$

 

Path-following scheme

Let us recap what we have seen so far. The basic path-following scheme with a $latex {\nu}&fg=000000$-self-concordant barrier $latex {F}&fg=000000$ for $latex {\mathcal{X}}&fg=000000$ goes as follows. Assume that we can find $latex {x_0 \in \mathrm{argmin}_{x \in {\mathbb R}^n} t_0 c^{\top} x + F(x)}&fg=000000$ for some small value $latex {t_0 >0}&fg=000000$. Then for $latex {k \geq 0}&fg=000000$, let

$latex \displaystyle \begin{array}{rcl} & & t_{k+1} = \left(1 + \frac1{4\sqrt{\nu}}\right) t_k ,\\ & & x_{k+1} = x_k – [\nabla^2 F(x_k)]^{-1} (t_{k+1} c + \nabla F(x_k) ) . \end{array} &fg=000000$

Using the machinery that we developed it is not hard to analyze the above scheme. Indeed it is reasonable to expect that $latex {x_k}&fg=000000$ will be ‘close’ to $latex {x^*(t_k)}&fg=000000$, and thus an inequality similar to (3) should hold for $latex {x_k}&fg=000000$. This is indeed the case, up to a multiplicate numerical constant. Furthermore, since one has $latex {t_{k} = \left(1 + \frac1{4\sqrt{\nu}}\right)^{k} t_0}&fg=000000$, this leads to the following bound:

$latex \displaystyle c^{\top} x_k – \min_{x \in \mathcal{X}} c^{\top} x = \frac{\nu}{t_0} \exp( – O(k / \sqrt{\nu}) ) .&fg=000000$

In other words, with $latex {k_{\epsilon} = O\left( \sqrt{\nu} \log \frac{\nu}{t_0 \epsilon} \right)}&fg=000000$ one can get an $latex {\epsilon}&fg=000000$-optimal point with the path-following scheme.

At this point we still need to explain how one can get close to an intial point $latex {x^*(t_0)}&fg=000000$ of the central path. This can be done with a damped Newton method on $latex {F_{t_0}}&fg=000000$, which uses the following iterates:

$latex \displaystyle x_{k+1} = x_k – \frac{1}{1+ \lambda_{F_{t_0}}(x_k)} [\nabla^2 F_{t_0}(x_k)]^{-1} \nabla F_{t_0}(x_k) .&fg=000000$

The complexity of this step is roughly of the same order than the rest of the path-following scheme.