Superlinear convergence of IPMs, I

Solution concepts and asymptotic convergence of interior-point methods

The presentation is based on [1][2][3]. The primal-dual pair of Linear Program is as below

$$\tag{P} \begin{array}{rcl} \min & c^\top x & \\ \text{s.t.}~ & Ax = b \\ & x \in \mathbb{R}^n_+ \end{array}$$

and the dual problem is

$$\tag{D} \begin{array}{rcl} \max & b^\top y & \\ \text{s.t.}~ & A^\top y + s = c \\ & s \in \mathbb{R}^n_+, y \in \mathbb{R}^m \end{array}$$

The feasible set is usually defined as $\mathcal{F}_P, \mathcal{F}_D$ for (P) and (D), respectively. For simplicity,

$$\begin{align*} & T_{A}=\left\{x \in \mathbb{R}^n ; A x=b\right\}, \\ & \mathcal{F}_P=\left\{x ; x \in S_{A}, x \geqslant 0\right\}, \\ & \mathcal{F}_P^\circ=\left\{x ; x \in S_{A}, x>0\right\}, \\ & T_{A^\top}=\left\{(y, s) \in \mathbb{R}^m \times \mathbb{R}^n ; A^\top y+s=c\right\}, \\ & \mathcal{F}_D=\left\{(y, s) ;(y, s) \in T_{A^\top}, s \geqslant 0\right\}, \\ & \mathcal{F}_D^\circ=\left\{(y, s) ;(y, s) \in T_{A^\top}, s>0\right\} . \end{align*}$$

A feasible point is said to be strictly feasible if it is feasible and positive. We say that $(x, s)$ is a (strictly) feasible pair for (P) and (D) if $x$ is (strictly) feasible for (P) and $s$ is (strictly) feasible for (D).

Strictly feasibility is a property of the problem.

Solution concepts

Linear programming is to determine a partition of zero-nonzero components of the primal solution $x$.

Partition by basis. The first such partition is the partition by basis. We could define the optimal basis and the optimal basic solution (BS). A problem can have an optimal face of solutions. The basic solution is a bit more restrictive (but useful). A square matrix $B$, a subset of columns of $A$, is called primal-optimal if $B^{-1} b$ is an optimal solution for (P). Denote, as usual, by $c_B$, the restriction of $c$ to the components corresponding to the columns of $B$. A basis $B$ is called dual-optimal if $(B^\top)^{-1} c$, is an optimal solution for (D).

With such a concept, the fundamental theorem of linear programming can be stated as follows.

If there is a feasible solution $x\in\mathcal{F}_p$, then, there is a basic feasible solution.

One can imagine by cutting the feasible region with a level set. The subset of feasible region always forms a face. We thus have a concept of primal-dual degeneracy.

A basic solution $x_B$ is called primal degenerate if some $x_j = 0, j\in B$. For the dual, if some $s_j = 0, j\in N$, then the solution $(y_N, s_N)$ is called dual degenerate.

Partition by strictly complementarity. A similar concept, to basic/non-basic partition can be defined according to the strictly complementary (SC) pair. For linear program, the complementary slackness relation holds as usual for a convex optimization problem in linear conic form or set of convex inequalities. For example, let $\sigma(x) = \lbrace i: x_i > 0\rbrace$ be the positive index set of $x$. Then, the complementary slackness relation is:

$$x_i s_i = 0, ~x_i + s_i \ge 0, \quad \forall i = 1, \ldots, n$$

A notable feature for linear programming is the existence of strictly complementary solutions if there is an optimal solution.

[4] If (P) and (D) have feasible solutions, then both problems have strictly complementary solutions. Let $x^\ast$ be such a solution for (P) and $(y^\ast, s^\ast)$ be the solution for (D). Then,

$$x_i^\ast s_i^\ast = 0, ~x_i^\ast + s_i^\ast > 0, \quad \forall i = 1, \ldots, n$$

That is, there exists a strict complementary partition of $x^\ast$ and $s^\ast$.

$$\begin{align*} &\sigma_P := \sigma(x^\ast), ~\sigma_D := \sigma(s^\ast) \\ &\sigma_P \cup \sigma_D = \{1, \ldots, n\}, \quad \sigma_P \cap \sigma_D = \emptyset. \end{align*}$$

(e.g., [4][3]) The SC partition is invariant across all SC solutions. Besides, all complementary solutions satisfy the following:

$$\sigma(x^\ast) \subseteq \sigma_p, ~\sigma(s^\ast) \subseteq \sigma_d = \{1, ..., n\} \setminus \sigma_p.$$

Clearly, note a pair of (non-strictly) complementary solution does not necessarily present enough information to determine the optimal partition. Besides, the concept of the SC solution is interesting only for degenerate problems. The following example shows that, we can associate a degenerate primal BS with a non-basic dual to construct a SC.

Consider the following LP:

$$\begin{array}{rrrrl} \min & -x_{1} \\ \text{s.t.}~ & x_{1} & +~x_{2} & &= 1, \\ & x_{1} &&+ ~x_{3} &= 1, \\ &&& x_{j} &\ge 0. \end{array}$$

In matrix form:

$$A = \begin{bmatrix} 1 & 1 & 0 \\ 1 & 0 & 1 \end{bmatrix},\quad b = \begin{bmatrix}1\\1\end{bmatrix},\quad c = \begin{bmatrix}-1\\0\\0\end{bmatrix}, \quad x = \begin{bmatrix}x_{1}\\u_{1}\\u_{2}\end{bmatrix}.$$

Choosing basis $B=[1, 2], N=[3]$ gives,

$$x = [1, 0, 0]^\top, \quad s = [0, 0.4, 0.6]^\top, \quad y = [-0.4, -0.6]^\top$$

which is optimal, $x$ is a BS but degenerate, $s$ is a non-BS but non-degenerate. $(x,s)$ is a SC solution.

Generally, if a primal degenerate BS $x_B$ satisfies strict complementarity, then we must have some $x_j = 0, x_j > 0, j\in B$ -- it would be non-basic. While the existence of SC is shown, how to find the SC solution is another question. Early work on this topic using simplex method appeared as the Balinski-Tucker optimal Tableau [5].

Is optimal (non-basic) solutions helpful? A basic understanding should be pointed out. Knowing the either the primal or dual solution (not both) makes it no easier to solve the general LP. [6] showed that:

  • If there exists a strongly polynomial time algorithm that finds an optimal basis, given an optimal solution for either the primal or the dual, then there exists a strongly polynomial algorithm for the general linear programming problem.
  • However, if both the primal and dual solutions are given, then finding the optimal basis is strongly polynomial.

Asymptotic convergence of IPMs

IPM is not a finite algorithm like the simplex in terms of finding the exact solution. Here, the exact solution means a mathematical solution form using basic arithmetic operations, such as the solution of a consistent system of linear equations or the solution of a least-squares problem. Alternatively, when solving LP, this means the following task:

$$\textrm{an exact solution} \quad\Leftarrow\quad \textrm{a basic solution or the optimal face} \quad\Leftarrow\quad \textrm{the "partition"}.$$

Hence, for IPM, it is important to discuss the finite convergence of the sequence and hence how a criterion is used to terminate, even without the goal of finding the exact solution. Several questions are connected to this topic.

  • When the algorithm enters the neighborhood of the solution, how fast does the sequence converge to the solution, asymptotically?
  • How to terminate the algorithm when the sequence is in the neighborhood of the solution? For finding basic solutions?

The first task may sound irrelevant in the first glance. With some iterate by IPM, a correct early guess of partition, on occasion, is certainly possible, especially in the case of a nondegenerate optimal vertex, in general one needs to be very close to the solution set in order to guarantee a correct guess.

We say the sequence $\lbrace(x_k, s_k)\rbrace$ satisfying $\langle x_k, s_k \rangle \to 0$ is R-superlinearly convergent to $(x^\ast, s^\ast)$ if

$$\lim _{k \rightarrow \infty} \tfrac{x_{k+1}^{T} s_{k+1}}{x_k^{T} s_k}=0$$

and quadratically convergent if

$$\lim\sup_{k \rightarrow \infty} \tfrac{x_{k+1}^{T} s_{k+1}}{\langle x_k, s_k \rangle^2} < \infty.$$

Early superlinear convergence for LP: [7][8] and an early unpublished report by [9]. As typical in IPMs, the assumptions needed for different convergence are

  1. A1: a strictly feasible pair $\left(x_0, s_0\right)$ exists.
  2. A2: the iteration sequence $\left\lbrace\left(x_k, s_k\right)\right\rbrace$ converges. Note that this may be a consequence of Hoffman's lemma to ensure primal sequence $\lbrace x_k\rbrace$'s convergence to the optimal set.
  3. A3: the linear program is nondegenerate. A3 implies A2 if duality converges to zero. A1 is always assumed for superlinear convergence, and could be taken as an acceptable assumption. A3 is needed for quadratic convergence but far from being realistic. This restriction of needing A2 and A3 is bypassed in [2] by using MTY IPM. I would like to quote the comment by Ye:

It has been observed in practice that the $\mathcal{O}(\sqrt{n}L)$ algorithms that have been tested so far are generally less effective than are some of the $\mathcal{O}(nL)$ algorithms (or other non-polynomial algorithms). Zhang, Tapia and Dennis [7] argued that several of these $\mathcal{O}(\sqrt{n}L)$ algorithms possess particularly poor Q-convergence properties, i.e., they exhibit Q-linear convergence with convergence constants near 1 for large $n$. Therefore, some researchers may have embraced the belief that the $\mathcal{O}(\sqrt{n}L)$ algorithms were less effective because none of them could achieve superlinear convergence.

But however, the results of [2] closed this gap. The $\mathcal{O}(\sqrt{n}L)$ algorithm is slower not because of the asymptotic behavior.

Now, we have demonstrated that a particular $\mathcal{O}(\sqrt{n}L)$ algorithm actually has what we consider to be the optimal convergence rate for degenerate or nondegenerate problems. If, perchance, numerical experimentation still favors the $\mathcal{O}(nL)$ algorithms, then we must conclude that their advantage is not due to their asymptotic behavior, but to some other, as yet unexplained, phenomenon.

References
  1. [1] Ye, Y.:On the finite convergence of interior-point algorithms for linear programming. Mathematical Programming, 57(1), 325–335 (1992).
  2. [2] Ye, Y., Güler, O., Tapia, R.A., Zhang, Y.:A quadratically convergent O(√nL)-iteration algorithm for linear programming. Mathematical Programming, 59(1), 151–162 (1993).
  3. [3] Ye, Y.:Interior Point Algorithms: Theory and Analysis. Wiley (1997).
  4. [4] Goldman, A.J., Tucker, A.W.:Theory of Linear Programming. In: Linear Inequalities and Related Systems, 53–98. Princeton University Press (1956).
  5. [5] Balinski, M.L., Tucker, A.W.:Duality theory of linear programs: a constructive approach with applications. SIAM Review, 11(3), 347–377 (1969).
  6. [6] Megiddo, N.:On finding primal- and dual-optimal bases. ORSA Journal on Computing (1991).
  7. [7] Zhang, Y., Tapia, R.A., Dennis, Jr., J.E.:On the superlinear and quadratic convergence of primal-dual interior point linear programming algorithms. SIAM Journal on Optimization, 2(2), 304–324 (1992).
  8. [8] Zhang, Y., Tapia, R.A.:A superlinearly convergent polynomial primal-dual interior-point algorithm for linear programming. SIAM Journal on Optimization, 3(1), 118–133 (1993).
  9. [9] Ye, Y., Tapia, R.A., Zhang, Y.:A superlinearly convergent O(√nL)-iteration algorithm for linear programming. Technical Report TR91-22, Rice University (1991).