Short-step Methods Are Not Strongly Polynomial-Time

An algorithm for solving linear programming problems is said to be strongly polynomial-time if the required number of arithmetic operations is a polynomial in the numbers of variables and constraints, independent of the bit-length for encoding the problem instance. A major open problem in optimization and computer science is whether there exists a strongly polynomial-time algorithm for solving linear programming problems.

This paper is concerned with interior-point methods [17], which are an important class of algorithms for solving convex constrained optimization problems and enjoy great success in both theory and practice [9, 13, 17, 19]. In particular, we focus on the sub-class of path-following interior-point methods [17]. These methods are built upon the concept of self-concordant barriers [17]. A self-concordant barrier allows us to define a curve, called the central path, leading from a certain center of the feasible region to an optimal solution. Roughly speaking, the principle of path-following interior-point methods is to approximately trace the central path to move towards the optimal solution. The geometry of the central path therefore plays an important role in the studies of path-following interior-point methods.

By constructing a family of linear programming problems with ill-behaved central paths, it has been shown in [7] that the number of iterations of any path-following interior-point method is lower bounded by $\Omega(\sqrt{m/(\log m)^{3}})$, where $m$ is the number of constraints. Based on another family of linear programming problems, the recent paper [3] improved the lower bound to $\Omega(2^{m})$, see also [4]. This lower bound applies to and thus denies the strong polynomiality of a large class of path-following interior-point methods, including the short-step methods associated with the logarithmic barrier [10, 15], the long-step methods [11] and the predictor-corrector methods [14]. More instances of ill-behaved central paths are presented in [6, 8].

One way to generalize the short-step methods is to replace the logarithmic barrier by an arbitrary self-concordant barrier [17], such as the volumetric barrier [20], universal barrier [13, 17], entropic barrier [5] and Lee-Sidford barrier [12]. Such an idea has led to improved algorithms for solving linear programming problems, see [12, 20] for example.

In view of the above-mentioned results, it is interesting to ask whether the short-step method associated with a general self-concordant barrier is strongly polynomial-time. The purpose of this short paper is to settle this question negatively, see Corollary 1. Our study is also motivated by the paper [2], which proved that for a family of linear programming problems, slightly different from the one in [3], a certain limit of the central path associated with the entropic barrier coincides with the central path associated with the logarithmic barrier. This suggests that the exponential lower bound in [3] for short-step methods associated with the logarithmic barrier could possibly be generalized to short-step methods associated with a general self-concordant barrier. Our main result Corollary 1 partly fills this gap.

Finally, we should also point out that some sub-classes of linear programming problems do admit strongly polynomial-time algorithms [1, 18, 22].

Consider the linear programming problem

where $c\in\mathbb{R}^{n}$, $b\in\mathbb{R}^{m}$ and $A\in\mathbb{R}^{m\times n}$. Denote the feasible region of problem (P) and its interior by $\mathcal{F}$ and $\mathcal{F}^{\circ}$, respectively. We assume that $\mathcal{F}$ is bounded and that $\mathcal{F}^{\circ}$ is non-empty. For simplicity, we denote the optimality gap of a feasible point $x\in\mathcal{F}$ by

The notion of self-concordant barriers plays vital role in the study of interior-point methods. Let $\mathcal{K}\subseteq\mathbb{R}^{n}$ be a proper convex domain, i.e., a convex set with non-empty interior and containing no 1-dimensional affine subspace. A function $\phi:\mathrm{int}(\mathcal{K})\to\mathbb{R}$ is said to be a barrier on $\mathcal{K}$ if $\phi(x)\to+\infty\quad\text{as}\quad x\to\partial\mathcal{K}$. A three times continuously differentiable convex function $\phi$ is said to be self-concordant on $\mathcal{K}$ if for any $x\in\mathrm{int}(\mathcal{K})$ and $h\in\mathbb{R}^{n}$,

If $\phi$ additionally satisfies that for any $x\in\mathrm{int}(\mathcal{K})$ and $h\in\mathbb{R}^{n}$,

then $\phi$ is said to be $\nu$-self-concordant on $\mathcal{K}$. This paper focuses on the proper convex domain $\mathcal{K}=\mathcal{F}$, which is a polytope defined by the linear inequalities $Ax\leq b$. A standard self-concordant barrier on $\mathcal{F}$ is the logarithmic barrier

Given a self-concordant barrier $\phi$ on $\mathcal{F}$, we consider the problem

From [16, Section 5.3.4], for any $\mu>0$, there exists a unique minimizer $x^{\phi}(\mu)$ to problem (P_μ). We call $x^{\phi}(\mu)$ the $\mu$-analytic center of problem (P) associated with the self-concordant barrier $\phi$. The central path of problem (P) associated with $\phi$ is then defined as (the image of) the curve $\mu\mapsto x^{\phi}(\mu)$ for $\mu>0$. By [16, Theorem 5.3.10], $x^{\phi}(\mu)$ converges to an optimal solution to problem (P) as $\mu\to 0$.

By [16, Theorem 5.1.6], $\nabla^{2}\phi(x)$ is positive definite for any $x\in\mathcal{F}^{\circ}$. This allows us to define a norm

and its dual norm

For any $\theta\in(0,1)$ and $\mu>0$, the $\ell_{2}$-neighbourhood of problem (P) is defined as

Note that $c+\mu\nabla\phi(x)$ is the gradient of the objective function of problem (P_μ). The $\ell_{2}$-neighbourhood is important and a natural choice for the design of path-following interior-point methods since the Newton’s method applied to problem (P_μ) converges quadratically to the optimal solution $x^{\phi}(\mu)$ [16, Theorem 5.2.2]. We write

which is also called the $\ell_{2}$-neighbourhood of problem (P). By the optimality condition of problem (P_μ), we can see that $x^{\phi}(\mu)\in\mathcal{N}^{\phi}_{\theta}(\mu)$ for any $\theta\in(0,1)$ and $\mu>0$.

A short-step method associated with $\phi$ is defined as an algorithm that generates a sequence of iterates $\{x^{k}\}_{k\geq 0}$ such that the polygonal (i.e., continuous piecewise linear) curve formed using the sequence $\{x^{k}\}_{k\geq 0}$ is contained in the $\ell_{2}$-neighbourhood $\mathcal{N}^{\phi}_{\theta}$ of problem (P) for some $\theta\in(0,1)$, where $k$ is the iteration counter, or more precisely,

Another popular choice of the neighbourhood for path-following algorithms for solving linear programming problems is the so-called wide neighbourhood [21]:

Similarly to the $\ell_{2}$-neighbourhood, we write

Our non-strong polynomiality result is based on the following family of linear programs introduced in [3]:

where $t>1$ is a real number and $r\geq 1$ is an integer. The notation ${\textbf{LW}}_{r}(t)$ follows from [3] and signifies that the central path of this linear program is long and winding.

To distinguish the properties of problem ${\textbf{LW}}_{r}(t)$ from those of a general linear program, we introduce an extra subscript $t$ to the notations. For instances, the feasible region, the $\mu$-analytic center associated with a self-concordant barrier $\phi$ and the wide neighbourhood of problem ${\textbf{LW}}_{r}(t)$ are denoted as $\mathcal{F}_{t}$, $x^{\phi}_{t}(\mu)$ and $\mathcal{W}_{\theta,t}$, respectively.

We can now present the main results of this paper, whose proofs are deferred to Section 4. The main contribution of this paper is the non-strong polynomiality of short-step methods.

The cruxes of the proof of Corollary 1 are the following theorems. The first shows a certain equivalence among the central paths of all self-concordant barriers. Geometrically speaking, it guarantees that when restricted to a constant-cost slice, all central paths are approximately equally close to (or away from) the boundary of the feasible region.

The second one bounds the optimality gap of analytic centers.

In this section, we prove the main results. Throughout this section, given a vector $\bar{x}\in\mathbb{R}^{n}$ and a positive definite matrix $Q$, we let $\mathcal{E}(Q,\bar{x})=\{x\in\mathbb{R}^{n}:(x-\bar{x})^{\top}Q(x-\bar{x})\leq 1\}$. Also, for any $\nu>0$, we let $C_{\nu}=\nu+2\sqrt{\nu}$.