IPM Part 2: The Lee-Sidford Barrier

• These notes are based on my semester research project in the Theoretical Computer Science Lab at EPFL, where I was supervised by Prof. Kapralov and Kshiteej Sheth.
• To understand the context in which the objects presented here are used, read my notes on Interior Point Methods.

1. Warm-Up: The Logarithmic Barrier

One simple barrier that one can consider for linear constraints is the logarithmic barrier :

Definition 1: Logarithmic barrier - Let the $n$-dimentional polytope with $m$ constraints $K=\{Ax\ge b\}={\cap }_{i\in [m]}\{a_i^{\top }x\ge b_i\}$. The logarithmic barrier is defined as

$$\varphi (x)=-\sum _{i=1}^m\text{ln}(a_i^{\top }x-b_i)$$

To study its self-concordance, we start by proving the following lemma

Lemma 1: If ${\varphi }_1$ and ${\varphi }_2$ are ${\nu }_1$- and ${\nu }_2$-self-concordant barriers on $K_1$ and $K_2$ respectively, then ${\varphi }_1+{\varphi }_2$ is a ${\nu }_1+{\nu }_2$-self-concordant barrier on $K_1\cap K_2$.

Proof. The two properties of $\nu$-self-concordance (Definition 4) are validated by just combining the inequalities of self-concordance of ${\varphi }_1$ and ${\varphi }_2$ (and using triangle inequality for the second property).

Lemma 2: The Logarithmic barrier $\varphi (x)=-{\sum }_{i=1}^m\text{ln}(a_i^{\top }x-b_i)$ is $m$-self-concordant.

Proof. Take any $i\in [m]$ and ${\varphi }_i(x)=-\text{ln}(a_i^{\top }x-b_i)$. Let $s_i=a_i^{\top }x-b_i$.

$$\text{D}{\varphi }_i(x)[v]=⟨\nabla {\varphi }_i(x),v⟩=\nabla {\varphi }_i(x{)}^{\top }v=-\frac{a_i^{\top }v}{s_i}$$

$${\text{D}}^2{\varphi }_i(x)[v,v]=⟨\nabla \text{D}{\varphi }_i(x)[v],v⟩=\frac{a_i^{\top }v}{s_i^2}{a}_i^{\top }v={\left(\frac{a_i^{\top }v}{s_i}\right)}^2$$

$${\text{D}}^3{\varphi }_i(x)[v,v,v]=⟨\nabla {\text{D}}^2{\varphi }_i(x)[v,v],v⟩=-2\frac{(a_i^{\top }v{)}^2}{s_i^3}{a}_i^{\top }v=-2{\left(\frac{a_i^{\top }v}{s_i}\right)}^3\le 2{\left(\frac{a_i^{\top }v}{s_i}\right)}^{2\frac{3}{2}}=2({\text{D}}^2{\varphi }_i(x)[v,v]{)}^{\frac{3}{2}}$$

and we just proved the first property of self-concordance for ${\varphi }_i(x)$.
Now,

$$\nabla {\varphi }_i(x)=-\frac{a_i}{s_i}{\nabla }^2{\varphi }_i(x)=\frac{a_i{a}_i^{\top }}{s_i^2}$$

$$\begin{array}{rl}{\Vert \nabla {\varphi }_i(x)\Vert }_{{\nabla }^2{\varphi }_i(x{)}^{-1}}^2={\Vert {\nabla }^2{\varphi }_i(x{)}^{-1}\nabla {\varphi }_i(x)\Vert }_{{\nabla }^2{\varphi }_i(x)}^2& =\nabla {\varphi }_i(x{)}^{\top }{\nabla }^2{\varphi }_i(x{)}^{-1}\nabla {\varphi }_i(x)\\ & =\frac{a_i^{\top }}{s_i}{s}_i^2(a_i{a}_i^{\top }{)}^{-1}\frac{a_i}{s_i}\\ & =a_i^{\top }(a_i{a}_i^{\top }{)}^{-1}{a}_i\\ & =1\end{array}$$

Thus, ${\varphi }_i(x)$ is 1-self-concordant, for any $i\in [m]$.

Since $\varphi (x)={\sum }_{i=1}^m{\varphi }_i(x)$ and by Lemma 1., $\varphi (x)$ is $m$-self-concordant.

From our IPM framework, we conclude that using the logarithmic barrier yields an $O(\sqrt{m})$ iteration algorithm for solving Linear Programs. The main problem with this is that since $m$ can get exponential in $n$, this can get very inefficient, for example when the LP has a lot of repeated (or very similar) constraints. The next logical step is to try and reweigh the constraints, and give less weight to the ones that are repeated.

2. The Weighted Logarithmic Barrier

We are looking for a barrier that behaves like $-{\sum }_{i=1}^m{w}_i\ln (a_i^{\top }x-b_i)$ for $w_i$ to be determined later. We thus define $\psi (x)=-{\sum }_{i=1}^m{w}_i\ln (a_i^{\top }x-b_i)$ and we will study its self concordance.

Lemma 3: We have

$$\nabla \psi (x{)}^{\top }({\nabla }^2\psi (x){)}^{-1}\nabla \psi (x)\le \sum _i{w}_i$$

And

$$D^3\psi (x)[h,h,h]\le 2\underset{i}{\max }\left|\frac{{\sigma }_i(\sqrt{W}{A}_x)}{w_i}\right|(D^2\psi (x)[h,h]{)}^{\frac{3}{2}}$$

where ${\sigma }_i(\sqrt{W}{A}_x)$ is the leverage score of $A_x\sqrt{W}$, namely ${\sigma }_i(\sqrt{W}{A}_x)=(\sqrt{W}{A}_x(A_x^{\top }W{A}_x{)}^{-1}{A}_x^{\top }\sqrt{W}{)}_{i,i}$

Proof. We have that $\nabla \psi (x)=A_x^{\top }w$ and ${\nabla }^2\psi (x)=A_x^{\top }W{A}_x$. Hence,

$$\nabla \psi (x{)}^{\top }({\nabla }^2\psi (x){)}^{-1}\nabla \psi (x)={\sqrt{w}}^{\top }(\sqrt{W}{A}_x(A_x^{\top }W{A}_x{)}^{-1}{A}_x^{\top }\sqrt{W})\sqrt{w}$$

But $\sqrt{W}{A}_x(A_x^{\top }W{A}_x{)}^{-1}{A}_x^{\top }\sqrt{W}$ is an orthogonal projection matrix, so its operator norm is smaller than $1$. We can then conclude that

$$\nabla \psi (x{)}^{\top }({\nabla }^2\psi (x){)}^{-1}\nabla \psi (x)\le {\sqrt{w}}^{\top }\sqrt{w}\le \sum _i{w}_i$$

For the second part of the proof, let $s_i=a_i^{\top }x-b_i$ be the $i$th slack condition. We have

$$D^3\psi (x)[h,h,h]=-2\sum _i{w}_i{\left(\frac{a_i^{\top }h}{s_i}\right)}^3\le 2\underset{i}{\max }\left|\frac{a_i^{\top }h}{s_i}\right|\sum _i{w}_i{\left(\frac{a_i^{\top }h}{s_i}\right)}^2$$

Furthermore,

$$\left|\frac{a_i^{\top }h}{s_i}\right|=\left|\frac{a_i^{\top }(A_x^{\top }W{A}_x{)}^{-\frac{1}{2}}(A_x^{\top }W{A}_x{)}^{\frac{1}{2}}h}{s_i}\right|\le (A_x(A_x^{\top }W{A}_x{)}^{-1}{A}_x^{\top }{)}_{i,i}\Vert h{\Vert }_{{\nabla }^2\psi (x)}$$

Hence, we have

$$D^3\psi (x)[h,h,h]\le 2\underset{i}{\max }\left|\frac{{\sigma }_i(\sqrt{W}{A}_x)}{w_i}\right|(D^2\psi (x)[h,h]{)}^{\frac{3}{2}}$$

Rescaling $\psi$ by a constant, we get that

$$D^3\psi (x)[h,h,h]\le 2\sum _i{w}_i\underset{i}{\max }\left|\frac{{\sigma }_i(\sqrt{W}{A}_x)}{w_i}\right|(D^2\psi (x)[h,h]{)}^{\frac{3}{2}}$$

Which gives us a self-concordance factor of ${\sum }_i{w}_i{\max }_i\left|\frac{{\sigma }_i(\sqrt{W}{A}_x)}{w_i}\right|$. It depends on $x$, but if $w_i={\sigma }_i(\sqrt{W}{A}_x)$, note that we have that ${\sum }_i{w}_i{\max }_i\left|\frac{{\sigma }_i(\sqrt{W}{A}_x)}{w_i}\right|={\sum }_i{\sigma }_i(\sqrt{W}{A}_x)\le n$ because of the properties of leverage scores.

Hence with this intuition, we can see how one can try to look for a $O(n)$ self-concordant barrier. The next section will present the actual barrier found by Lee and Sidford, and give some details about it.

3. The Lee-Sidford Barrier

As seen in the previous section, we want to weight the $i$th constraint with a weight $w_i$ such that $w_i={\sigma }_i(\sqrt{W}{A}_x)$. This corresponds exactly to the definition of the ${\ell }_{\infty }$ Lewis weights. By their recursive nature, it's very hard to compute them exactly, so one can try to relax those condition to taking $w$ to be the vector of the ${\ell }_p$ Lewis weights, with $p$ large enough.

Lee and Sidford introduced the following barrier :

$${\varphi }_p(x)=\underset{w_i\ge 0}{\max }\log \det (A_x^{\top }{W}^{1-\frac{2}{p}}{A}_x)-(1-\frac{2}{q})\sum _{i=1}^m{w}_i$$

And proved the following result :

Theorem 1: If $A$ has full rank, then for any $p>0$, ${\varphi }_p$ is a $O(n{m}^{\frac{1}{p+1}})$ self concordant barrier. In particular, for $p=\Theta (\log m),{\varphi }_p$ is a $O(n{\log }^{O(1)}m)$ self concordant barrier.

The proof is lengthy and can be found in Reference 1, but one insight that might be interesting is the following (proof omitted):

Lemma 4: We have

$$A_x^{\top }{\Sigma }_p(x)A_x⪯{\nabla }^2{\varphi }_p(x)⪯(1+p)A_x^{\top }{\Sigma }_p(x)A_x$$

Where ${\Sigma }_p(x{)}_{i,i}$ is the $i$th ${\ell }_p$ Lewis weight of $A_x$.

This lemma is insightful because it shows that the hessian of ${\varphi }_p$ is spectrally close to $A_x^{\top }{\Sigma }_p(x)A_x$, which is the Hessian of the ${\ell }_p$ Lewis weights reweighted logarithmic barrier, and this can justify why the Lee-Sidford barrier behaves as wanted.

4. Putting it all together

We have exhibited a $\tilde{O}(n)$ self-concordant barrier, which can be used to get a $\tilde{O}(\sqrt{n}\log (1/ϵ)$ iteration algorithm to solve Linear Programs. One important thing to study now is the per iteration cost, in particular the cost to compute the barrier. The Lee-Sidford is very costly to compute because it involves determinants, and ${\ell }_p$ Lewis weights. Not being careful about how one computes it might ruin all our previous efforts.

The idea is to compute the barrier iteratively: the broad picture is that from ${\varphi }_p(x)$, $x$, and $x^{\prime }$, if $x$ and $x^{\prime }$ are close enough, one can estimate ${\varphi }_p(x^{\prime })-{\varphi }_p(x)$ with satisfactory precision, because ${\varphi }_p$ is smooth enough. Furthermore, computing ${\varphi }_p(x^{\prime })$ from ${\varphi }_p(x)$ only takes a logarithmic number of linear systems to solve. We can now state the final result of Lee and Sidford :

Theorem 2: Given an interior point $x_0$ of a Linear Program, there exists an algorithm that outputs a feasible point $x$ such that $c^{\top }x\le \text{OPT}+ϵ$ with constant probability in $\tilde{O}(\sqrt{n}\log (1/ϵ){\mathcal{T}}_w)$ time, where ${\mathcal{T}}_w$ is the work needed to compute $(A^{\top }DA{)}^{-1}q$ for a positive diagonal matrix $D$ and a vector $q$.

Depending on the nature of the Linear Program, ${\mathcal{T}}_w$ might vary, and as such, the most general result with state of the art techniques states that one can solve approximately a Linear Program in time $\tilde{O}((nnz(A)+rank(A{)}^{\omega })\sqrt{n}\log (1/ϵ))$ where $\omega$ is the constant multiplication matrix.

References

1. Y. T. Lee, A. Sidford - Solving Linear Programs with sqrt(rank) linear system solves