# Polynomial worst-case iteration complexity of quasi-Newton
primal-dual interior point algorithms for linear programming

J. Gondzio School of Mathematics, University of Edinburgh, Edinburgh, EH9 3FD,
Scotland, United Kingdom. Email<EMAIL_ADDRESS>F. N. C. Sobral
Corresponding author. Department of Mathematics, State University of Maringá,
Avenida Colombo, 5790, Paraná, Brazil, 87020-900. Phone: +55 44 30116211.
E-mail<EMAIL_ADDRESS>
(Technical Report ERGO, School of Mathematics, September 9, 2022)

###### Abstract

Quasi-Newton methods are well known techniques for large-scale numerical
optimization. They use an approximation of the Hessian in optimization
problems or the Jacobian in system of nonlinear equations. In the Interior
Point context, quasi-Newton algorithms compute low-rank updates of the matrix
associated with the Newton systems, instead of computing it from scratch at
every iteration. In this work, we show that a simplified quasi-Newton primal-
dual interior point algorithm for linear programming enjoys polynomial worst-
case iteration complexity. Feasible and infeasible cases of the algorithm are
considered and the most common neighborhoods of the central path are analyzed.
To the best of our knowledge, this is the first attempt to deliver polynomial
worst-case iteration complexity bounds for these methods. Unsurprisingly, the
worst-case complexity results obtained when quasi-Newton directions are used
are worse than their counterparts when Newton directions are employed.
However, quasi-Newton updates are very attractive for large-scale optimization
problems where the cost of factorizing the matrices is much higher than the
cost of solving linear systems.
Keywords: Quasi-Newton methods, Broyden update, Primal-dual Interior Point
Methods, Polynomial worst-case iteration complexity
MSC codes: 90C05, 90C51, 90C53

##  1 Introduction

Let us consider the following general linear programming problem

$\min\quad c^{T}x,\quad{\mbox{s.t.}}\quad Ax=b,\ x\geq 0,$ (1)

where $x,c\in\mathbb{R}^{n}$, $b\in\mathbb{R}^{m}$ and
$A\in\mathbb{R}^{m\times n}$. We assume that (1) is feasible and the rows of
$A$ are linearly independent. Define function
$F:\mathbb{R}^{2n+m}\to\mathbb{R}^{2n+m}$ by

$F(x,\lambda,z)=\begin{bmatrix}A^{T}\lambda+z-c\\\ Ax-b\\\ XZe\end{bmatrix},$
(2)

where $X,Z\in\mathbb{R}^{n\times n}$ are diagonal matrices defined by
$X=\operatorname{diag}(x)$ and $Z=\operatorname{diag}(z)$, respectively, and
$e$ is the vector of ones of appropriate size. First order necessary
optimality conditions for (1) state that, if $x^{*}\geq 0$ is a minimizer,
then there exist $z^{*}\in\mathbb{R}^{n}$, $z^{*}\geq 0$, and
$\lambda^{*}\in\mathbb{R}^{m}$ such that $F(x^{*},{\lambda}^{*},z^{*})=0$
holds.

Interior point methods (IPMs) try to follow the so-called central-path of
problem (1), defined by the solution of the perturbed KKT system
$F(x,{\lambda},z)=\begin{bmatrix}0&0&\mu e\end{bmatrix}^{T}$, as $\mu\to 0$.
Instead of solving such a system exactly, primal-dual IPMs apply one iteration
of Newton method for a given value of $\mu_{k}$ at iteration $k$. In order to
calculate this step, the Jacobian of $F$ is needed

$J(x,\lambda,z)=\begin{bmatrix}0&A^{T}&I\\\ A&0&0\\\ Z&0&X\end{bmatrix}.$ (3)

With an iterate $(x^{k},{\lambda}^{k},z^{k})$ at step $k$, the classical
Newton direction is calculated by solving the following system

$\begin{bmatrix}0&A^{T}&I\\\ A&0&0\\\ Z^{k}&0&X^{k}\\\
\end{bmatrix}\begin{bmatrix}\Delta{x}^{k}\\\ \Delta{\lambda}^{k}\\\
\Delta{z}^{k}\end{bmatrix}=\begin{bmatrix}c-z^{k}-A^{T}\lambda^{k}\\\
b-Ax^{k}\\\ \sigma_{k}\mu_{k}e-X^{k}Z^{k}e\end{bmatrix},$ (4)

where $\mu_{k}$ is set to be the average complementarity gap
${x^{k}}^{T}s^{k}/n$ and $\sigma_{k}\in(0,1)$ determines its target reduction.

While the coefficient matrix in (4) can be efficiently evaluated and stored,
it changes at each iteration. The solution of (4) is usually accomplished by
direct methods, using suitable matrix factorizations [9, 15], or by iterative
methods [4], computing preconditioners to improve their convergence
properties. In this paper we are concerned with classes of problems for which
it is advantageous to approximate $J(x^{k},{\lambda}^{k},z^{k})$ in order to
reduce the cost of solving (4).

Usually, IPMs do not deal explicitly with the unreduced system (4), but rather
consider its reduced form as augmented system (which is symmetric) or as
normal equations (whose coefficient matrix is positive definite) [8]. The
interest in working directly with unreduced systems has attracted more
attention in the recent years, since they have good sparsity structure and
also interesting spectral properties [14]. In [18], numerical experiments
comparing preconditioners for unreduced and augmented systems were made. The
appeal for using preconditioners for unreduced systems is their good
conditioning close to the solution.

Gondzio and Sobral [10] considered unreduced systems in a way similar to [18].
They studied the Jacobian of $F$ and asked the question whether it is possible
to approximate it by classical quasi-Newton approaches for nonlinear systems.
Although this might have seemed an obvious thing to attempt, the only previous
use of quasi-Newton strategies in IPMs was to update the preconditioners [13,
1, 12, 2]. Broyden low-rank updates were used and the numerical experiments
showed that this approach is effective for IPMs when the cost of solving
linear systems is considerably lower than the cost of computing the
factorization of the Jacobian (or its associated reduced form).

Recently, Ek and Forsgren [6] presented a theoretical background and numerical
experiments regarding a different kind of low rank updates. The proposed
update is based on the Eckart-Young-Mirsky theorem, rather than on the secant
equation satisfied by the Broyden update, and affects only the “third row” of
matrix $J(x^{k},{\lambda}^{k},z^{k})$, related to the nonlinear part of $F$.
Convex quadratic optimization problems were considered and local convergence
was established for a simplified primal-dual interior point algorithm, but no
complexity bound was provided. It is worth mentioning that the iteration
worst-case complexity of $O(\sqrt{n})$ was shown for a short-step primal
algorithm by Gonzaga [11], where low-rank updates were used to compute the
projection matrix needed by such type of algorithms. Secant equations were
also used in [5] for the same purpose, but without complexity results.

Polynomial worst-case iteration complexity is a key feature of IPMs for linear
and convex-quadratic problems [19]. It is achieved by taking steps in the
Newton direction (4) such that the new iterate belongs to some neighborhood of
the central path. In case of linear programming, it is well known that the
iteration worst-case complexity involves polynomials of orders between
$\sqrt{n}$ and $n^{2}$, depending on the type of neighborhood of the central
path used and whether feasible of infeasible iterates are allowed [21]. Those
results have also been generalized to symmetric cone optimization problems
[20].

This work is intended to provide the first steps towards the study of
iteration worst-case complexity of quasi-Newton primal-dual interior point
algorithms. We present non-trivial extensions of well known complexity results
from [21] and properties that arise when Broyden “bad” quasi-Newton updates
are used. Worst-case complexity is proven for both feasible and infeasible
cases in the most commonly used neighborhoods. The theoretical study is
motivated by the very promising results from [10] in quadratic programming
problems. As expected, the degrees of polynomials in the complexity results
are higher than those obtained when steps in Newton directions are made.

The paper is organized as follows. In Section 2 we review basic quasi-Newton
concepts and the properties of quasi-Newton algorithms presented in [10].
Then, in Section 3 we analyze the worst-case complexity for the feasible case,
considering two popular neighborhoods of the central path : $\mathcal{N}_{2}$
and $\mathcal{N}_{s}$. Section 4 is devoted to the infeasible case when the
iterates are confined to the $\mathcal{N}_{s}$ neighborhood. Final comments,
observations and possible directions of future work are discussed in Section
5.

#### Notation

We define $\|\cdot\|$ as the Euclidean norm for vectors and the induced
$\ell_{2}$-norm for matrices. We will use the short versions $F_{k}$ and
$J_{k}$ to describe $F(x^{k},{\lambda}^{k},z^{k})$ and
$J(x^{k},{\lambda}^{k},z^{k})$, respectively. In addition, we will use both
inline $(x^{k},{\lambda}^{k},z^{k})$ and matrix
$\left[\begin{smallmatrix}x^{k}\\\ \lambda^{k}\\\
z^{k}\end{smallmatrix}\right]$ notations to address vectors in this work.

##  2 Background

Given a function $G:\mathbb{R}^{N}\to\mathbb{R}^{N}$, suppose that we want to
solve the nonlinear system $G(\bar{x})=0$. Secant methods iteratively
construct a linear model $M_{k}(\bar{x})$ of $G$ which interpolates the last
two computed iterates of the method. At each iteration, they need to compute
an approximation to the Jacobian of $G$, which has to satisfy the secant
equation

$Bs_{k-1}=y_{k-1},$

where $s_{k-1}=\bar{x}^{k}-\bar{x}^{k-1}$ and
$y_{k-1}=G(\bar{x}^{k})-G(\bar{x}^{k-1})$. There are infinitely many solutions
to the secant equation for $N\geq 2$ and different approaches generate
different secant methods [16]. Among them, the Broyden “bad” approach uses the
already computed approximation to the inverse of $G$ at $\bar{x}^{k-1}$,
called $H_{k-1}$, to compute the current approximation $H_{k}$ as

$H_{k}=H_{k-1}+\frac{(s_{k-1}-H_{k-1}y_{k-1})y_{k-1}^{T}}{y_{k-1}^{T}y_{k-1}}=H_{k-1}V_{k-1}+\frac{s_{k-1}y_{k-1}^{T}}{\rho_{k-1}},$
(5)

where $V_{k-1}=\left(I-\frac{y_{k-1}y_{k-1}^{T}}{\rho_{k-1}}\right)$ and
$\rho_{k-1}=y_{k-1}^{T}y_{k-1}$. The Broyden “bad” update is a rank-1 update
where $H_{k}$ is the matrix closest to $H_{k-1}$ in the Frobenius norm which
satisfies the secant equation. After $\ell$ updates of an approximation
$H_{k-\ell}$, current approximation $H_{k}$ is given by

$\begin{split}H_{k}&=H_{k-1}V_{k-1}+\frac{s_{k-1}y_{k-1}^{T}}{\rho_{k-1}}\\\
&=H_{k-\ell}\left(\prod_{j=k-\ell}^{k-1}V_{j}\right)+\sum_{i=1}^{\ell}\left(\frac{s_{k-i}y_{k-i}^{T}}{\rho_{k-i}}\prod_{j=k-i+1}^{k-1}V_{j}\right).\end{split}$
(6)

For the specific case of this work, where $G$ is given by $F$ defined in (2),
we have that $N=2n+m$, $\bar{x}=(x,{\lambda},z)$ and the vectors $s_{k-1}$ and
$y_{k-1}$ from the secant equation assume a more specific description

$s_{k-1}=\bar{\alpha}_{k-1}\begin{bmatrix}\Delta{x}^{k-1}\\\
\Delta{\lambda}^{k-1}\\\ \Delta{z}^{k-1}\end{bmatrix}\quad\text{and}\quad
y_{k-1}=\begin{bmatrix}\bar{\alpha}_{k-1}(A^{T}\Delta{\lambda}^{k-1}+\Delta{z}^{k-1})\\\
\bar{\alpha}_{k-1}A\Delta{x}^{k-1}\\\
X^{k}Z^{k}e-X^{k-1}Z^{k-1}e\end{bmatrix},$ (7)

where $\bar{\alpha}_{k-1}\in(0,1]$ is the step-size taken at iteration $k-1$
towards the solution of (4).

In [10], the authors described an interior point method based on low rank
quasi-Newton approximations to the Jacobian of $F$. The Broyden updates were
tested, and the computational experience revealed that the most efficient one
was the Broyden “bad” update.

Since we are interested in finding an approximate solution of the linear
system given by the Newton method (4), in the Broyden “bad” approach, given
$\ell\geq 0$, the following direction is computed

$\begin{bmatrix}\Delta{x}^{k}\\\ \Delta{\lambda}^{k}\\\
\Delta{z}^{k}\end{bmatrix}=H_{k}\begin{bmatrix}c-A^{T}\lambda^{k}-z^{k}\\\
b-Ax^{k}\\\ \sigma_{k}\mu_{k}e-X^{k}Z^{k}e\end{bmatrix}.$ (8)

If $H_{k-\ell}=J_{k-\ell}^{-1}$ and $\ell=0$, system (8) turns out to be
exactly (4). Therefore, in the same way as discussed in [10], we assume that
the initial approximation $H_{k-\ell}$ is given by the perfect approximation
$J_{k-\ell}^{-1}$. When $\ell>0$, the quasi-Newton procedure strongly uses the
fact that the factorization of $J_{k-\ell}$ (or a good preconditioner) has
already been computed. In addition, Lemma 1, taken from [10], shows that, with
this choice of initial approximation, the Broyden “bad” update has an
interesting alternative interpretation.

######  Lemma 1.

Assume that $k,\ell\geq 0$ and $H_{k}$ is the approximation of $J_{k}^{-1}$
constructed by $\ell$ updates (6) using initial approximation
$H_{k-\ell}=J_{k-\ell}^{-1}$. Given $v\in\mathbb{R}^{2n+m}$, the computation
of $r=H_{k}v$ is equivalent to the solution of

$J_{k-\ell}r=v+\begin{bmatrix}0\\\ 0\\\
\sum\limits_{i=1}^{\ell}\gamma_{i}\left[\bar{\alpha}_{k-i}\left(Z^{k-\ell}\Delta{x}^{k-i}+X^{k-\ell}\Delta{z}^{k-i}\right)-\left(X^{k-i+1}Z^{k-i+1}-X^{k-i}Z^{k-i}\right)e\right]\end{bmatrix},$

where
$\displaystyle\gamma_{i}=\frac{y_{k-i}^{T}\prod_{j=k-i+1}^{k-1}V_{j}}{\rho_{k-i}}v$,
for $i=1,\dots,\ell$.

Lemma 1 is the basis of the analysis developed in this work. It states that we
can study quasi-Newton steps using the Jacobian of the Newton step. The only
difference is the right-hand side. Using this property of the Broyden “bad”
update we are able to extend the well known complexity results described in
[21]. The difficulty in the analysis will be mostly caused by the extra term,
added to the usual right-hand side of (4). It is important to note that Lemma
1 does not assume that the iterates are feasible, hence it is useful in both
feasible and infeasible cases. Although by (6), the sparsity structure of the
third row of $B_{k}$ (the inverse of $H_{k}$) is lost when $\ell\geq 1$, we
can see that the structural sparsity of $J_{k-\ell}$ can still be used to
solve the linear systems.

Let us define a skeleton primal-dual quasi-Newton interior point algorithm. It
is given by Algorithm 1 and generates a sequence of alternating Newton and
quasi-Newton steps. Clearly, by the nature of update (5), the first step needs
to be a Newton step.

Input: $F$, $J$ and $(x^{0},{\lambda}^{0},z^{0})$

for $k=0,1,\dots$ do

if $k$ is odd then

$\ell\leftarrow 1$ $\triangleright$ Quasi-Newton iteration

else

$\ell\leftarrow 0$ $\triangleright$ Newton iteration

end if

Calculate $(\Delta{x}^{k},\Delta{\lambda}^{k},\Delta{z}^{k})$ by solving (8)

Calculate
$(x^{k+1},{\lambda}^{k+1},z^{k+1})=(x^{k},{\lambda}^{k},z^{k})+\bar{\alpha}_{k}(\Delta{x}^{k},\Delta{\lambda}^{k},\Delta{z}^{k})$

for a suitable choice of $\bar{\alpha}_{k}\in[0,1]$, such that
$x^{k+1},z^{k+1}>0$

end for

Algorithm 1 Conceptual Quasi-Newton Interior Point algorithm.

Let us analyze what happens when a sequence of two steps is performed: at
iteration $k$ the Newton step is made (with stepsize $\bar{\alpha}_{k}$) and
then at iteration $k+1$ the quasi-Newton step is taken (with stepsize
$\bar{\alpha}$). For Newton step at iteration $k$, we observe that

$\begin{split}X^{k+1}Z^{k+1}e&=\left(X^{k}+\bar{\alpha}_{k}\Delta{X}^{k}\right)\left(Z^{k}+\bar{\alpha}_{k}\Delta{Z}^{k}\right)e\\\
&=X^{k}Z^{k}e+\bar{\alpha}_{k}\left(Z^{k}\Delta{x}^{k}+X^{k}\Delta{z}^{k}\right)+{\bar{\alpha}_{k}}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\\\
&=X^{k}Z^{k}e+\bar{\alpha}_{k}(\sigma_{k}\mu_{k}e-X^{k}Z^{k}e)+{\bar{\alpha}_{k}}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\\\
&=(1-\bar{\alpha}_{k})X^{k}Z^{k}e+\bar{\alpha}_{k}\sigma_{k}\mu_{k}e+{\bar{\alpha}_{k}}^{2}\Delta{X}^{k}\Delta{Z}^{k}e.\end{split}$
(9)

Later, in the proofs of several technical results, we will need to analyze the
error produced when the quasi-Newton direction
$(\Delta{x}^{k+1},\Delta{\lambda}^{k+1},\Delta{z}^{k+1})$ is multiplied by
$J_{k+1}$:

$\begin{bmatrix}0&A^{T}&I\\\ A&0&0\\\ Z^{k+1}&0&X^{k+1}\\\
\end{bmatrix}\begin{bmatrix}\Delta{x}^{k+1}\\\ \Delta{\lambda}^{k+1}\\\
\Delta{z}^{k+1}\end{bmatrix}=\left(\begin{bmatrix}0&0&0\\\ 0&0&0\\\
Z^{k+1}-Z^{k}&0&X^{k+1}-X^{k}\\\ \end{bmatrix}+\begin{bmatrix}0&A^{T}&I\\\
A&0&0\\\ Z^{k}&0&X^{k}\\\
\end{bmatrix}\right)\begin{bmatrix}\Delta{x}^{k+1}\\\ \Delta{\lambda}^{k+1}\\\
\Delta{z}^{k+1}\end{bmatrix}.$

Applying Lemma 1 for iteration $k+1$ with $\ell=1$ and then observing that
$(\Delta{x}^{k},\Delta{\lambda}^{k},\Delta{z}^{k})$ solves the Newton system
(4) and using (9), the third block equation in Lemma 1 gives

$\begin{split}Z^{k}\Delta{x}^{k+1}+X^{k}\Delta{z}^{k+1}&=\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e+\gamma_{1}\left[\bar{\alpha}_{k}\left(Z^{k}\Delta{x}^{k}+X^{k}\Delta{z}^{k}\right)-\left(X^{k+1}Z^{k+1}-X^{k}Z^{k}\right)e\right]\\\
&=\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e+\gamma_{1}(\bar{\alpha}_{k}\sigma_{k}\mu_{k}e+(1-\bar{\alpha}_{k})X^{k}Z^{k}e-X^{k+1}Z^{k+1}e)\\\
&=\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e-\gamma_{1}{\bar{\alpha}_{k}}^{2}\Delta{X}^{k}\Delta{Z}^{k}e.\end{split}$
(10)

Hence, using (7) and (10)

$\begin{split}Z^{k+1}\Delta{x}^{k+1}&+X^{k+1}\Delta{z}^{k+1}=(Z^{k+1}-Z^{k})\Delta{x}^{k+1}+(X^{k+1}-X^{k})\Delta{z}^{k+1}+Z^{k}\Delta{x}^{k+1}+X^{k}\Delta{z}^{k+1}\\\
&=\bar{\alpha}_{k}\left(\Delta{Z}^{k}\Delta{X}^{k+1}e+\Delta{X}^{k}\Delta{Z}^{k+1}e\right)+\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e-\gamma_{1}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e,\end{split}$
(11)

where $\Delta{Z}^{k}$, $\Delta{X}^{k}$, $\Delta{Z}^{k+1}$ and
$\Delta{X}^{k+1}$ are given by $\operatorname{diag}(\Delta{z}^{k})$,
$\operatorname{diag}(\Delta{x}^{k})$, $\operatorname{diag}(\Delta{z}^{k+1})$
and $\operatorname{diag}(\Delta{x}^{k+1})$, respectively. Next we compute the
new complementarity products obtained after a sequence of two steps, apply
(11), and add and subtract the term
$\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e$ to derive

$\begin{split}X^{k+2}Z^{k+2}e&=(X^{k+1}+\bar{\alpha}\Delta{X}^{k+1})(Z^{k+1}+\bar{\alpha}\Delta{Z}^{k+1})e\\\
&=X^{k+1}Z^{k+1}e+\bar{\alpha}(Z^{k+1}\Delta{X}^{k+1}+X^{k+1}\Delta{Z}^{k+1})e+\bar{\alpha}^{2}\Delta{X}^{k+1}\Delta{Z}^{k+1}e\\\
&=X^{k+1}Z^{k+1}e+\bar{\alpha}\bar{\alpha}_{k}(\Delta{Z}^{k}\Delta{X}^{k+1}e+\Delta{X}^{k}\Delta{Z}^{k+1}e)+\bar{\alpha}^{2}\Delta{X}^{k+1}\Delta{Z}^{k+1}e+\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\\\
&\quad-\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e-\bar{\alpha}X^{k+1}Z^{k+1}e-\gamma_{1}\bar{\alpha}{\bar{\alpha}_{k}}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\\\
&=(1-\bar{\alpha})X^{k+1}Z^{k+1}e+(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1})(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1})e\\\
&\quad+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e-(1+\bar{\alpha}\gamma_{1}){\bar{\alpha}_{k}}^{2}\Delta{X}^{k}\Delta{Z}^{k}e.\end{split}$
(12)

By multiplying both sides of equation (12) with $e^{T}$ we get the
complementarity product at iteration $k+2$:

$\begin{split}(x^{k+1}&+\bar{\alpha}\Delta{x}^{k+1})^{T}(z^{k+1}+\bar{\alpha}\Delta{z}^{k+1})=\\\
&=(1-\bar{\alpha}(1-\sigma_{k+1})){x^{k+1}}^{T}z^{k+1}+(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})^{T}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})-(1+\gamma_{1}\bar{\alpha})\bar{\alpha}_{k}^{2}{\Delta{x}^{k}}^{T}\Delta{z}^{k}.\end{split}$
(13)

It is worth noting that the final expression in (12) involves a composite
direction
$(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1},\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})$
which corresponds to an aggregate of two consecutive steps: in Newton
direction at iteration $k$ and in quasi-Newton direction at iteration $k+1$.
Much of the effort of the analysis presented in this paper is focused on this
composite direction. Let us mention that we will also use the component-wise
versions of equations (9), (11) and (12). For example, in case of (12) this
gives

$\begin{split}\left[x^{k+1}\right.&+\left.\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}=(1-\bar{\alpha})\left(x^{k+1}_{i}z^{k+1}_{i}\right)\\\
&+\left[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}+\bar{\alpha}\sigma_{k+1}\mu_{k+1}-(1+\bar{\alpha}\gamma_{1}){\bar{\alpha}_{k}}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}.\end{split}$
(14)

Observe that equations (9)-(14) are valid for both feasible and infeasible
algorithm. However, the analysis in Sections 3 and 4 will distinguish between
these two cases because in the feasible one we are able to take advantage of
the orthogonality of primal and dual directions and exploit it to deliver
better final worst-case complexity results.

Before we conclude the brief background section and take the reader through a
detailed analysis of different versions of the primal-dual quasi-Newton
interior point algorithm, let us observe that equation (12) involves an
important term $\gamma_{1}$. By Lemma 1, $\gamma_{1}$ can be seen as the
scalar coefficient of the projection of vector $v$ onto the subspace generated
by vector $y_{k}$:

$\mathcal{P}_{y_{k}}(v)=\frac{y_{k}^{T}v}{y_{k}^{T}y_{k}}y_{k}=\gamma_{1}y_{k}.$

Using the non-expansive property of projections we conclude that

$\|\mathcal{P}_{y_{k}}(v)\|\leq\|v\|\iff\|\gamma_{1}y_{k}\|\leq\|v\|\iff|\gamma_{1}|\leq\frac{\|v\|}{\|y_{k}\|}.$
(15)

In the next lemma, a lower bound for $\|y_{k}\|$ is derived. It states that
the denominator of (15) can be bounded away from zero if a sufficient decrease
of $\mu=x^{T}z/n$ is ensured and non-null step-sizes are taken. The bound for
$\|v\|$ involves the right-hand side in (8) and therefore depends on the
feasibility of iterates and on the choice of the centering parameter $\sigma$.

######  Lemma 2.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1 and $y_{k}$ be the quasi-
Newton vector defined by (7) to construct $H_{k+1}$ by the Broyden “bad”
update (6). Suppose that $\mu_{k+1}\leq(1-\rho_{k}\bar{\alpha}_{k})\mu_{k}$
holds, for $\bar{\alpha}_{k},\rho_{k}\in[0,1]$. Then

$\|y_{k}\|\geq\frac{\rho_{k}}{2}\bar{\alpha}_{k}\mu_{k}.$

###### Proof.

If $\bar{\alpha}_{k}=0$ or $\rho_{k}=0$ the result trivially holds, so we can
assume that $\bar{\alpha}_{k},\rho_{k}\in(0,1]$. Suppose, by contradiction,
that $\|y_{k}\|<\rho_{k}\bar{\alpha}_{k}\mu_{k}/2$. Therefore, by definition
of $y_{k}$,

$\begin{split}\|X^{k+1}Z^{k+1}e-X^{k}Z^{k}e\|\leq\|y_{k}\|<\frac{\rho_{k}\bar{\alpha}_{k}}{2}\mu_{k}&\Rightarrow|x^{k+1}_{i}z^{k+1}_{i}-x^{k}_{i}z^{k}_{i}|<\frac{\rho_{k}\bar{\alpha}_{k}}{2}\mu_{k},i=1,\dots,n\\\
&\Rightarrow
x^{k+1}_{i}z^{k+1}_{i}-x^{k}_{i}z^{k}_{i}>-\frac{\rho_{k}\bar{\alpha}_{k}}{2}\mu_{k},i=1,\dots,n\\\
&\Rightarrow\mu_{k+1}-\mu_{k}>-\frac{\rho_{k}\bar{\alpha}_{k}}{2}\mu_{k},\end{split}$

where the last result was obtained by adding up all the $n$ previous
inequalities and dividing by $n$. By hypothesis we have that
$\mu_{k+1}\leq(1-\rho_{k}\bar{\alpha}_{k})\mu_{k}$ and, therefore,

$-\frac{\rho_{k}\bar{\alpha}_{k}}{2}\mu_{k}<\mu_{k+1}-\mu_{k}\leq-\rho_{k}\bar{\alpha}_{k}\mu_{k},$

which implies $\rho_{k}/2>\rho_{k}$ and is a clear absurd. Thus, we conclude
that $\|y_{k}\|\geq\rho_{k}\bar{\alpha}_{k}\mu_{k}/2$. ∎

##  3 Worst-case complexity in the feasible case

For all the results in this section, we suppose that
$(x^{0},{\lambda}^{0},z^{0})$ is primal and dual feasible, given by Assumption
1.

######  Assumption 1.

$(x^{0},{\lambda}^{0},z^{0})\in\mathcal{F}\doteq\\{(x,\lambda,z)\ |\
Ax=b,A^{T}\lambda+z=c,x>0,z>0\\}$.

Our analysis follows closely the theory in [21]. Under Assumption 1 the primal
and dual directions are orthogonal to each other [21, Lemma 5.1]. We show that
the same holds for quasi-Newton directions.

######  Lemma 3.

If $k+1$ is a quasi-Newton iteration of Algorithm 1, then
${\Delta{x}^{k+1}}^{T}\Delta{z}^{k+1}=0.$

###### Proof.

Using Lemma 1 with $r=Hv$ defined by their respective terms in (8) and by the
primal and dual feasibility of $(x^{0},{\lambda}^{0},z^{0})$, we observe that
the first two block rows of system (8) (at iteration $k+1$) given by

$\left\\{\begin{array}[]{rrcrcr}&A^{T}\Delta{\lambda}^{k+1}&+&\Delta{z}^{k+1}&=&0\\\
A\Delta{x}^{k+1}&&&&=&0\end{array}\right.$

are the same as in the system solved by the usual Newton step. Therefore,

${\Delta{x}^{k+1}}^{T}\Delta{z}^{k+1}=-{\Delta{x}^{k+1}}^{T}A^{T}\Delta{\lambda}^{k+1}=-\left(A\Delta{x}^{k+1}\right)^{T}\Delta{\lambda}^{k+1}=0.$

∎

######  Corollary 1.

If $k$ is a Newton iteration and $k+1$ is a quasi-Newton iteration, then

$\left(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right)^{T}\left(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right)={\Delta{x}^{k}}^{T}\Delta{z}^{k}={\Delta{x}^{k}}^{T}\Delta{z}^{k+1}={\Delta{z}^{k}}^{T}\Delta{x}^{k+1}=0.$

###### Proof.

Since, by equation (7), $(\Delta{x}^{k},\Delta{\lambda}^{k},\Delta{z}^{k})$
was computed by the Newton step at iteration $k$ we have that
${\Delta{x}^{k}}^{T}\Delta{z}^{k}=0$ by the same arguments of Lemma 3. By
Lemma 1 the first two equations do not change between iterations $k$ and
$k+1$, and we have the desired results. ∎

The second important result is that the quasi-Newton step can decrease the
barrier parameter $\mu$ in exactly the same way as the Newton step (see [21,
Lemma 5.1]). Recall that by definition $\mu=(x^{T}z)/n$.

######  Lemma 4.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1. Then for any feasible
step-size $\bar{\alpha}\in[0,1]$

$\mu(\bar{\alpha})=(1-\bar{\alpha}(1-\sigma_{k+1}))\mu_{k+1}.$ (16)

###### Proof.

By equation (13) and using Corollary 1, we obtain

$\begin{split}n\mu(\bar{\alpha})&=(x^{k+2})^{T}z^{k+2}=(x^{k+1}+\bar{\alpha}\Delta{x}^{k+1})^{T}(z^{k+1}+\bar{\alpha}\Delta{z}^{k+1})\\\
&=(1-\bar{\alpha}){x^{k+1}}^{T}z^{k+1}+(\bar{\alpha}_{k}\Delta{x}^{k}\\!+\\!\bar{\alpha}\Delta{x}^{k+1})^{T}(\bar{\alpha}_{k}\Delta{z}^{k}\\!+\\!\bar{\alpha}\Delta{z}^{k+1})+\bar{\alpha}\sigma_{k+1}n\mu_{k+1}-(1\\!+\\!\bar{\alpha}\gamma_{1}){\bar{\alpha}_{k}}^{2}{\Delta{x}^{k}}^{T}\Delta{z}^{k}\\\
&=(1-\bar{\alpha}(1-\sigma_{k+1}))n\mu_{k+1}.\end{split}$

By dividing both sides of the last equation by $n$ we get the desired result.
∎

Then, using Lemma 4, after Newton step at iteration $k$ and quasi-Newton step
at iteration $k+1$, we get

$\begin{split}\|(\mu(\bar{\alpha})-\mu_{k})e\|^{2}&=(\mu(\bar{\alpha})-\mu_{k})^{2}n\
=\ [(1-\bar{\alpha}(1-\sigma_{k+1}))\mu_{k+1}-\mu_{k}]^{2}n\\\
&=[(1-\bar{\alpha}(1-\sigma_{k+1}))(1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}-\mu_{k}]^{2}n\\\
&=[1-(1-\bar{\alpha}(1-\sigma_{k+1}))(1-\bar{\alpha}_{k}(1-\sigma_{k}))]^{2}\mu_{k}^{2}n.\end{split}$
(17)

It is worth noting that (in the feasible case) the term $\gamma_{1}$
originating from Lemma 1 does not have any influence on the value of
$\mu(\bar{\alpha})$.

###  3.1 The $\mathcal{N}_{2}$ neighborhood

In this section we will consider a short-step interior point method and employ
the notion of $\mathcal{N}_{2}$ neighborhood of the central path

$\mathcal{N}_{2}(\theta)=\\{(x,\lambda,z)\in\mathcal{F}\ |\ \|XZe-\mu
e\|\leq\theta\mu\\},$

where $\mathcal{F}$ is the set of primal and dual feasible points such that
$x,z>0$, see Assumption 1. For all considerations in this subsection we add
the following assumption.

######  Assumption 2.

$(x^{k},{\lambda}^{k},z^{k})\in\mathcal{N}_{2}(\theta_{k})$ and
$(x^{k+1},{\lambda}^{k+1},z^{k+1})\in\mathcal{N}_{2}(\theta_{k+1})$, for
$\theta_{k},\theta_{k+1}\in(0,1)$.

Our main goal is to show that the new iterate

$(x^{k+2},{\lambda}^{k+2},z^{k+2})=(x^{k+1},{\lambda}^{k+1},z^{k+1})+\bar{\alpha}(\Delta{x}^{k+1},\Delta{\lambda}^{k+1},\Delta{z}^{k+1})$

also belongs to $\mathcal{N}_{2}(\theta_{k+2})$, for suitable choices of
$\theta_{k+2}\in(0,1)$, $\bar{\alpha}$ and $\bar{\alpha}_{k}$. Therefore, we
are interested in the analysis of the Euclidean norm of the vector
$\,(X^{k+1}+\bar{\alpha}\Delta{X}^{k+1})(Z^{k+1}+\bar{\alpha}\Delta{Z}^{k+1})e-\mu(\bar{\alpha})e\,$
and to deliver it we will exploit several useful results stated earlier in
equations (12), (14) and Lemma 4. Combining (14) and Lemma 4 we get

$\begin{split}\left[x^{k+1}\right.&+\left.\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-\mu(\bar{\alpha})=\\\
&=(1-\bar{\alpha})\left(x^{k+1}_{i}z^{k+1}_{i}-\mu_{k+1}\right)+\left[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-(1+\bar{\alpha}\gamma_{1}){\bar{\alpha}_{k}}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}.\end{split}$
(18)

By (18) and Assumption 2, we deliver the following bound on the proximity
measure of the $\mathcal{N}_{2}$ neighborhood of the iterate after the quasi-
Newton step

$\begin{split}\|\left(X^{k+1}+\right.&\left.\bar{\alpha}\Delta{X}^{k+1}\right)\left(Z^{k+1}+\bar{\alpha}\Delta{Z}^{k+1}\right)e-\mu(\bar{\alpha})e\|=\\\
&=\|\left\\{(1-\bar{\alpha})\left(x^{k+1}_{i}z^{k+1}_{i}-\mu_{k+1}\right)+\left[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}\right.\\\
&\
\qquad\left.-(1+\bar{\alpha}\gamma_{1}){\bar{\alpha}_{k}}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}\right\\}_{i=1}^{n}\|\\\
&\leq(1-\bar{\alpha})\|X^{k+1}Z^{k+1}e-\mu_{k+1}e\|+\|\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\\\
&\quad+|1+\bar{\alpha}\gamma_{1}|{\bar{\alpha}_{k}}^{2}\|\Delta{X}^{k}\Delta{Z}^{k}e\|\\\
&\leq(1-\bar{\alpha})\theta_{k+1}\mu_{k+1}+|1+\bar{\alpha}\gamma_{1}|{\bar{\alpha}_{k}}^{2}\frac{\theta_{k}^{2}+n(1-\sigma_{k})^{2}}{2^{3/2}(1-\theta_{k})}\mu_{k}\\\
&\quad+\|\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|.\end{split}$
(19)

In the last inequality we used the bound on the error in the Newton step
$\|\Delta{X}^{k}\Delta{Z}^{k}e\|$, see [21, Lemma 5.4].

To further exploit (19) we need bounds on two terms which appear in it:
$1+\bar{\alpha}\gamma_{1}$ and the second-order error contributed by the
composite direction
$\|\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|$.
The following technical result delivers a bound for $|\gamma_{1}|$. (Observe
that $\gamma_{1}$ is evaluated only when the quasi-Newton iteration is
performed.)

######  Lemma 5.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1. Suppose that $v$ in
Lemma 1 is given by the right-hand side of (4) and Assumption 2 holds. If
$\bar{\alpha}_{k}\in(0,1]$ and $\sigma_{k}\in[0,1)$, then

$|\gamma_{1}|\leq\frac{2(1-\bar{\alpha}_{k}(1-\sigma_{k}))\sqrt{\theta_{k+1}^{2}+(1-\sigma_{k+1})^{2}n}}{\bar{\alpha}_{k}(1-\sigma_{k})},$

where $\gamma_{1}$ is defined in Lemma 1.

###### Proof.

We use the assumptions of the lemma, the fact that the iterates are primal and
dual feasible, the property $e^{T}(\mu_{k+1}e-X^{k+1}Z^{k+1}e)=0$ and the
relation $\mu_{k+1}=(1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}$ to derive the
result

$\begin{split}\|v\|&=\|\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e\|=\|(\mu_{k+1}e-X^{k+1}Z^{k+1}e)-(1-\sigma_{k+1})\mu_{k+1}e\|\\\
&=\sqrt{\|\mu_{k+1}e-X^{k+1}Z^{k+1}e\|^{2}-2(1-\sigma_{k+1})\mu_{k+1}e^{T}(\mu_{k+1}e-X^{k+1}Z^{k+1}e)+\|(1-\sigma_{k+1})\mu_{k+1}e\|^{2}}\\\
&\leq\sqrt{\theta_{k+1}^{2}\mu_{k+1}^{2}+(1-\sigma_{k+1})^{2}\mu_{k+1}^{2}n}\
=(1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}\sqrt{\theta_{k+1}^{2}+(1-\sigma_{k+1})^{2}n}\
.\end{split}$

By defining $\rho_{k}=1-\sigma_{k}$ we can see that
$\mu_{k+1}=(1-(1-\sigma_{k})\bar{\alpha}_{k})\mu_{k}=(1-\rho_{k}\bar{\alpha}_{k})\mu_{k}$
which ensures the sufficient decrease condition of Lemma 2. Since
$\bar{\alpha}_{k}>0$ and $\sigma_{k}<1$, by the assumptions of the lemma, we
have that $\|y_{k}\|>0$. Then, by simple substitution of the previous equation
and Lemma 2 in (15) we have

$\begin{split}|\gamma_{1}|\leq\frac{\|v_{k}\|}{\|y_{k}\|}&\leq\frac{(1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}\sqrt{\theta_{k+1}^{2}+(1-\sigma_{k+1})^{2}n}}{\frac{1-\sigma_{k}}{2}\bar{\alpha}_{k}\mu_{k}}=\frac{2(1-\bar{\alpha}_{k}(1-\sigma_{k}))\sqrt{\theta_{k+1}^{2}+(1-\sigma_{k+1})^{2}n}}{\bar{\alpha}_{k}(1-\sigma_{k})}.\end{split}$

∎

Next we turn our attention to the error in the composite direction
$\|\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|$
and start from a technical result.

######  Lemma 6.

If $k+1$ is a quasi-Newton iteration of Algorithm 1, then

$\begin{split}Z^{k}\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)e&+X^{k}\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e=\\\
&=(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)+(\mu(\bar{\alpha})-\mu_{k})e-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e.\end{split}$
(20)

###### Proof.

We use equations (4), (10) and (9) and some simple manipulations to obtain

$\begin{split}Z^{k}&\left(\bar{\alpha}_{k}\Delta{X}^{k}\\!+\\!\bar{\alpha}\Delta{X}^{k+1}\right)e+X^{k}\left(\bar{\alpha}_{k}\Delta{Z}^{k}\\!+\\!\bar{\alpha}\Delta{Z}^{k+1}\right)e=\bar{\alpha}_{k}\left(Z^{k}\Delta{x}^{k}\\!+\\!X^{k}\Delta{z}^{k}\right)+\bar{\alpha}\left(Z^{k}\Delta{x}^{k+1}\\!+\\!X^{k}\Delta{z}^{k+1}\right)\\\
&=\bar{\alpha}_{k}(\sigma_{k}\mu_{k}e\\!-\\!X^{k}Z^{k}e)+\bar{\alpha}\left(\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e-\gamma_{1}{\bar{\alpha}_{k}}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\right)\\\
&=\bar{\alpha}_{k}(\sigma_{k}\mu_{k}e\\!-\\!X^{k}Z^{k}e)+\bar{\alpha}\left(\sigma_{k+1}\mu_{k+1}e-(1\\!-\\!\bar{\alpha}_{k})X^{k}Z^{k}e-\bar{\alpha}_{k}\sigma_{k}\mu_{k}e-{\bar{\alpha}_{k}}^{2}\Delta{X}^{k}\Delta{Z}^{k}e-\gamma_{1}{\bar{\alpha}_{k}}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\right)\\\
&=(1-\bar{\alpha})\bar{\alpha}_{k}\sigma_{k}\mu_{k}e-(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))X^{k}Z^{k}e+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e.\end{split}$
(21)

After adding and subtracting the term
$(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\mu_{k}e$ we further rearrange
the previous equation

$\begin{split}Z^{k}&\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)e+X^{k}\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e=\\\
&=(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\\\
&\quad+((1-\bar{\alpha})\bar{\alpha}_{k}\sigma_{k}-(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha})))\mu_{k}e+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e.\end{split}$
(22)

Then using $\mu_{k+1}=(1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}$ (which
clearly holds for a step in Newton direction) and Lemma 4 which delivers a
similar result for a step in quasi-Newton direction, we get:

$\begin{split}((1-\bar{\alpha})\bar{\alpha}_{k}\sigma_{k}&-(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha})))\mu_{k}e+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e=(\bar{\alpha}_{k}\sigma_{k}-\bar{\alpha}\bar{\alpha}_{k}\sigma_{k}-\bar{\alpha}-\bar{\alpha}_{k}+\bar{\alpha}\bar{\alpha}_{k})\mu_{k}e+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e\\\
&=\left[-\bar{\alpha}(1-\bar{\alpha}_{k}(1-\sigma_{k}))-\bar{\alpha}_{k}(1-\sigma_{k})\right]\mu_{k}e+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e\\\
&=\left[-1-\bar{\alpha}(1-\bar{\alpha}_{k}(1-\sigma_{k}))+1-\bar{\alpha}_{k}(1-\sigma_{k})\right]\mu_{k}e+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e\\\
&=-\mu_{k}e-\bar{\alpha}\mu_{k+1}e+\mu_{k+1}e+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e\quad=\quad(1-\bar{\alpha}(1-\sigma_{k+1}))\mu_{k+1}e-\mu_{k}e\\\
&=\mu(\bar{\alpha})e-\mu_{k}e.\end{split}$ (23)

By substituting (23) in (22), the desired result is obtained. ∎

######  Lemma 7.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1 and suppose that
Assumption 2 holds. Then

$\begin{split}\|\left(\right.&\left.\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\leq\\\
&\leq\frac{\mu_{k}}{2^{3/2}(1\\!-\\!\theta_{k})}\Bigg{[}[1-(1\\!-\\!\bar{\alpha}(1\\!-\\!\sigma_{k+1}))(1\\!-\\!\bar{\alpha}_{k}(1\\!-\\!\sigma_{k}))]^{2}n+\left((\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\theta_{k}+|1\\!+\\!\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}\frac{\theta_{k}^{2}+n(1\\!-\\!\sigma_{k})^{2}}{2^{3/2}(1-\theta_{k})}\right)^{2}\Bigg{]}.\end{split}$

###### Proof.

Let us first define $D^{k}=(X^{k})^{1/2}(Z^{k})^{-1/2}$ and the scaled vectors

$u_{k}={(D^{k})}^{-1}\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)e\quad{\mbox{and}}\quad
v_{k}={D^{k}}\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e.$

Using Lemma 3, Corollary 1 and observing that all the involved matrices are
diagonal, we get $u_{k}^{T}v_{k}=0$. Hence vectors $u_{k}$ and $v_{k}$ satisfy
the assumptions of Lemma 5.3 in [21]. With $U_{k}=\operatorname{diag}(u_{k})$
and $V_{k}=\operatorname{diag}(v_{k})$, we write

$\begin{split}\|\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)&\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|=\|{(D^{k})}^{-1}\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right){D^{k}}\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\\\
&=\|U_{k}V_{k}e\|\ \leq\ 2^{-3/2}\|u_{k}+v_{k}\|^{2}\\\
&=2^{-3/2}\|{(D^{k})}^{-1}\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)e+{D^{k}}\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|^{2}.\end{split}$
(24)

After multiplying both sides of (20) by $(X^{k}Z^{k})^{-1/2}$ and replacing it
in (24) we obtain

$\begin{split}\|&\left.\left(\bar{\alpha}_{k}\Delta{X}^{k}\right.+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\leq\\\
&\leq
2^{-3/2}\|(X^{k}Z^{k})^{-1/2}\left\\{(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)+(\mu(\bar{\alpha})-\mu_{k})e-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\right\\}\|^{2}\\\
&=2^{-3/2}\sum_{i=1}^{n}\frac{\left\\{(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}-x^{k}_{i}z^{k}_{i}\right)+\mu(\bar{\alpha})-\mu_{k}-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}\right\\}^{2}}{x^{k}_{i}z^{k}_{i}}\\\
&\leq\frac{2^{-3/2}}{(1-\theta_{k})\mu_{k}}\|(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e+(\mu(\bar{\alpha})-\mu_{k})e\|^{2},\end{split}$
(25)

where the last inequality comes from the fact that
$(x^{k},{\lambda}^{k},z^{k})$ belongs to $\mathcal{N}_{2}(\theta_{k})$, hence
$(1-\theta_{k})\mu_{k}\leq x^{k}_{i}z^{k}_{i}\leq(1+\theta_{k})\mu_{k}$ for
all $i$. Now we use Lemma 3 again and the definition of $\mu_{k}$ to observe
that

$e^{T}\left((\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\right)=0$
(26)

and further rearrange (25):

$\begin{split}\|&\left.\left(\bar{\alpha}_{k}\Delta{X}^{k}\right.+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\leq\\\
&\leq\frac{2^{-3/2}}{(1-\theta_{k})\mu_{k}}\left[\left\|(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\right\|^{2}+\|(\mu(\bar{\alpha})-\mu_{k})e\|^{2}\right].\end{split}$
(27)

The second norm on the right-hand side of (27) is given by (17). Using the
definition of $\mathcal{N}_{2}(\theta_{k})$ neighborhood and Lemma 5.4 from
[21], for the first norm we get

$\begin{split}\left\|(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\right.&\left.\left(\mu_{k}e-X^{k}Z^{k}e\right)-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\right\|^{2}\leq\\\
&\leq\left(\left\|(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)\right\|+\left\|(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\right\|\right)^{2}\\\
&\leq\left((\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\theta_{k}+|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}\frac{\theta_{k}^{2}+n(1-\sigma_{k})^{2}}{2^{3/2}(1-\theta_{k})}\right)^{2}\mu_{k}^{2}.\\\
\end{split}$ (28)

Finally, by substituting (17) and (28) in (27) we obtain the required result.
∎

We are ready to state the main result of this subsection. In Theorem 1 we show
that it is possible to choose sufficiently small values for the step-sizes
$\bar{\alpha}_{k}$ and $\bar{\alpha}$ such that
$(x^{k+2},{\lambda}^{k+2},z^{k+2})\in\mathcal{N}_{2}(\theta_{k})$. Therefore,
we ensure that the quasi-Newton step taken after a Newton step remains in the
$\mathcal{N}_{2}$ neighborhood. This implies that all the iterates generated
by the algorithm belong to $\mathcal{N}_{2}$. The upper bounds for the step-
sizes as stated in the theorem are then used to determine the worst-case
complexity of Algorithm 1 operating in $\mathcal{N}_{2}$. First, recall [21,
Theorem 5.6] that it is possible to choose parameters
$\theta_{k},\theta_{k+1}\in(0,1)$ and $\sigma_{k},\sigma_{k+1}\in(0,1)$ so
that

$\frac{\theta_{k}^{2}+n(1-\sigma_{k})^{2}}{2^{3/2}(1-\theta_{k})}\leq\theta_{k}\sigma_{k}\quad\text{and}\quad\frac{\theta_{k+1}^{2}+n(1-\sigma_{k+1})^{2}}{2^{3/2}(1-\theta_{k+1})}\leq\theta_{k+1}\sigma_{k+1}.$
(29)

######  Theorem 1.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1. Suppose that Assumptions
1 and 2 hold and that $\theta_{k+1}=\theta_{k}$ and $\sigma_{k+1}=\sigma_{k}$.
If the step-sizes in Newton and quasi-Newton iterations $\bar{\alpha}_{k}$ and
$\bar{\alpha}$ satisfy

$\bar{\alpha}_{k}\in\left(0,\min\left\\{\frac{1-\sigma_{k}}{4\sigma_{k}},\frac{\sigma_{k}(1-\sigma_{k})}{10(1-\sigma_{k})+4}\right\\}\right]\quad\text{and}\quad\bar{\alpha}\in\left[\bar{\alpha}_{k},\frac{\sigma_{k}(1-\sigma_{k})}{10(1-\sigma_{k})+4}\right]$
(30)

for $\sigma_{k}\in[0,1)$ and $\theta_{k}\in(0,16/25)$, then

$(x^{k+2},{\lambda}^{k+2},z^{k+2})\doteq(x^{k+1},{\lambda}^{k+1},z^{k+1})+\bar{\alpha}(\Delta{x}^{k+1},\Delta{\lambda}^{k+1},\Delta{z}^{k+1})\in\mathcal{N}_{2}(\theta_{k}).$

###### Proof.

We will first show that for all $\bar{\alpha}_{k}$ and $\bar{\alpha}$
satisfying the conditions of the theorem

$\|\left(X^{k+1}+\right.\left.\bar{\alpha}\Delta{X}^{k+1}\right)\left(Z^{k+1}+\bar{\alpha}\Delta{Z}^{k+1}\right)e-\mu(\bar{\alpha})e\|-\theta_{k}\mu(\bar{\alpha})\leq
0$ (31)

holds. This condition ensures that the Newton step at iteration $k+2$ will be
successfully performed and the algorithm converges. By inequality (19),
condition (31) is satisfied if

$\begin{split}\left[(1-\bar{\alpha})\theta_{k+1}\mu_{k+1}-\theta_{k}\mu(\bar{\alpha})\right]&+|1+\bar{\alpha}\gamma_{1}|{\bar{\alpha}_{k}}^{2}\frac{\theta_{k}^{2}+n(1-\sigma_{k})^{2}}{2^{3/2}(1-\theta_{k})}\mu_{k}\\\
&+\|\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\leq
0.\end{split}$ (32)

We will derive bounds to each term on the left-hand side of this inequality in
order to find an expression in a form
$K_{1}\bar{\alpha}^{2}-K_{2}\bar{\alpha}$, $K_{1},K_{2}>0$, which will be
nonpositive for small values of $\bar{\alpha}$.

For the first term, we use the fact that $\theta_{k+1}=\theta_{k}$,
$\sigma_{k+1}=\sigma_{k}$ and $\bar{\alpha}_{k}\in(0,1)$. In addition, we use
Lemma 4 to expand $\mu(\bar{\alpha})$ and the fact that $\mu_{k+1}$ was
calculated in the Newton step $k$ to obtain

$(1-\bar{\alpha})\theta_{k+1}\mu_{k+1}-\theta_{k}\mu(\bar{\alpha})=[(1-\bar{\alpha})(\theta_{k+1}-\theta_{k})-\bar{\alpha}\sigma_{k+1}\theta_{k}](1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}\leq-\bar{\alpha}\sigma_{k}^{2}\theta_{k}\mu_{k}.$
(33)

For the second and third terms, we first apply (29) in Lemma 5 to simplify the
bound of $\gamma_{1}$:

$\begin{split}|\gamma_{1}|&\leq\frac{2(1-\bar{\alpha}_{k}(1-\sigma_{k}))\sqrt{2^{3/2}(1-\theta_{k+1})}\sqrt{\frac{\theta_{k+1}^{2}+(1-\sigma_{k+1})^{2}n}{2^{3/2}(1-\theta_{k+1})}}}{\bar{\alpha}_{k}(1-\sigma_{k})}\\\
&\leq\frac{2(1-\bar{\alpha}_{k}(1-\sigma_{k}))\sqrt{2^{3/2}(1-\theta_{k+1})}\sqrt{\theta_{k+1}\sigma_{k+1}}}{\bar{\alpha}_{k}(1-\sigma_{k})}\
\leq\ \frac{4}{\bar{\alpha}_{k}(1-\sigma_{k})}-4.\end{split}$ (34)

Therefore, using (29) again, we derive the following bound to the second term

$\begin{split}|1+\bar{\alpha}\gamma_{1}|\bar{\alpha}_{k}^{2}&\frac{\theta_{k}^{2}+n(1-\sigma_{k})^{2}}{2^{3/2}(1-\theta_{k})}\mu_{k}\leq\left[1+\bar{\alpha}\left(\frac{4}{\bar{\alpha}_{k}(1-\sigma_{k})}-4\right)\right]\bar{\alpha}_{k}^{2}\theta_{k}\sigma_{k}\mu_{k}\\\
&=\bar{\alpha}_{k}^{2}\theta_{k}\sigma_{k}\mu_{k}+4\bar{\alpha}\bar{\alpha}_{k}\left(\frac{1-\bar{\alpha}_{k}(1-\sigma_{k})}{1-\sigma_{k}}\right)\theta_{k}\sigma_{k}\mu_{k}\
\leq\
\bar{\alpha}^{2}\left[1+\frac{4}{1-\sigma_{k}}\right]\theta_{k}\sigma_{k}\mu_{k},\end{split}$
(35)

where in the last inequality we used the condition
$\bar{\alpha}_{k}\leq\bar{\alpha}\leq 1$ from (30). For the third term in
(32), we use the bound obtained in Lemma 7 and analyze each part of it
independently. First, since $\bar{\alpha}_{k}\leq\bar{\alpha}$ and
$\sigma_{k+1}=\sigma_{k}$, we observe that

$\begin{split}[1-(1-\bar{\alpha}(1-\sigma_{k+1}))&(1-\bar{\alpha}_{k}(1-\sigma_{k}))]^{2}n=[\bar{\alpha}_{k}(1-\sigma_{k})+\bar{\alpha}(1-\bar{\alpha}_{k}(1-\sigma_{k}))(1-\sigma_{k}))]^{2}n\\\
&\leq\bar{\alpha}^{2}(1-\sigma_{k})^{2}[1+(1-\bar{\alpha}_{k}(1-\sigma_{k}))]^{2}n\leq
4\bar{\alpha}^{2}(1-\sigma_{k})^{2}n.\end{split}$ (36)

Using bound (34), assumption
$\bar{\alpha}_{k}\leq(1-\sigma_{k})/(4\sigma_{k})$ in (30), and (29) again, we
also obtain

$\begin{split}\left[(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\theta_{k}+|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}\frac{\theta_{k}^{2}+n(1-\sigma_{k})^{2}}{2^{3/2}(1-\theta_{k})}\right]^{2}&\leq\left[\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha})+\left(\frac{4}{\bar{\alpha}_{k}(1-\sigma_{k})}-3\right)\bar{\alpha}\bar{\alpha}_{k}^{2}\sigma_{k}\right]^{2}\theta_{k}^{2}\\\
&\leq\left[\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha})+\frac{4}{\bar{\alpha}_{k}(1-\sigma_{k})}\bar{\alpha}\bar{\alpha}_{k}^{2}\sigma_{k}\right]^{2}\theta_{k}^{2}\\\
&\leq\bar{\alpha}^{2}\left[1+(1-\bar{\alpha})+\frac{4\bar{\alpha}_{k}\sigma_{k}}{(1-\sigma_{k})}\right]^{2}\theta_{k}^{2}\\\
&\leq 9\bar{\alpha}^{2}\theta_{k}^{2}.\end{split}$ (37)

By combining (36) and (37) in the statement of Lemma 7 and applying (29) once
more, we derive a bound to the third term of (32)

$\|\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\leq\frac{\mu_{k}}{2^{3/2}(1-\theta_{k})}\left(4\bar{\alpha}^{2}(1-\sigma_{k})^{2}n+9\bar{\alpha}^{2}\theta_{k}^{2}\right)\leq
9\bar{\alpha}^{2}\theta_{k}\sigma_{k}\mu_{k}.$ (38)

By (33), (35) and (38), the following bound on expression in (32) is obtained

$\begin{split}(1-\bar{\alpha})\theta_{k+1}\mu_{k+1}-\theta_{k}\mu(\bar{\alpha})&+|1+\bar{\alpha}\gamma_{1}|\bar{\alpha}_{k}^{2}\frac{\theta_{k}^{2}+n(1-\sigma_{k})^{2}}{2^{3/2}(1-\theta_{k})}\mu_{k}\\\
&+\|\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\\\
&\leq-\bar{\alpha}\sigma_{k}^{2}\theta_{k}\mu_{k}+\bar{\alpha}^{2}\left[1+\frac{4}{1-\sigma_{k}}\right]\theta_{k}\sigma_{k}\mu_{k}+9\bar{\alpha}^{2}\theta_{k}\sigma_{k}\mu_{k}\\\
&\leq\bar{\alpha}\left[10\bar{\alpha}+\frac{4\bar{\alpha}}{1-\sigma_{k}}-\sigma_{k}\right]\theta_{k}\sigma_{k}\mu_{k},\end{split}$
(39)

which is negative only if
$\bar{\alpha}\leq\sigma_{k}(1-\sigma_{k})/(10(1-\sigma_{k})+4)$, as requested
by (30). This bound on $\bar{\alpha}$ implies a bound on $\bar{\alpha}_{k}$,
due to condition $\bar{\alpha}_{k}\leq\bar{\alpha}$. Therefore, we arrive in
the step-size conditions (30) of the theorem. Using (31) we also have that

$\left(x^{k+1}_{i}+\bar{\alpha}[\Delta{x}^{k+1}]_{i}\right)\left(z^{k+1}_{i}+\bar{\alpha}[\Delta{z}^{k+1}]_{i}\right)\geq(1-\theta_{k})\mu(\bar{\alpha})>0.$
(40)

We now show that the new iterate belongs to $\mathcal{F}$. By Assumption 1 and
Lemma 1 we know that all iterates remain primal and dual feasible. It remains
to show that $x^{k+2}$ and $z^{k+2}$ are strictly positive. We follow the same
arguments as [17] and adapt them to our case. Suppose by contradiction that
$x^{k+2}_{i}\leq 0$ or $z^{k+2}_{i}\leq 0$ hold for some $i$. By (40), we have
that $x^{k+2}_{i}<0$ and $z^{k+2}_{i}<0$ and that implies
$x^{k}_{i}z^{k}_{i}<(\bar{\alpha}_{k}[\Delta{x}^{k}]_{i}+\bar{\alpha}[\Delta{x}^{k+1}]_{i})(\bar{\alpha}_{k}[\Delta{z}^{k}]_{i}+\bar{\alpha}[\Delta{z}^{k+1}]_{i})\leq
9\bar{\alpha}^{2}\theta_{k}\sigma_{k}\mu_{k}$ by inequality (38). Since
$(x^{k},{\lambda}^{k},z^{k})\in\mathcal{N}_{2}(\theta_{k})$ and
$\bar{\alpha}\leq 1/4$, by (30), we conclude that
$(1-\theta_{k})\mu_{k}<(9/16)\theta_{k}\mu_{k}$ and, therefore,
$\theta_{k}>16/25$, which contradicts the choice of $\theta_{k}$. Hence,
$(x^{k+2},{\lambda}^{k+2},z^{k+2})$ belongs to $\mathcal{N}_{2}(\theta_{k})$
and the Newton step at iteration $k+2$ also falls in the
$\mathcal{N}_{2}(\theta_{k})$ neighborhood. ∎

For the polynomial convergence of Algorithm 1, we define
$\sigma_{k}=\sigma_{k+1}=1-0.4/\sqrt{n}$ and
$\theta_{k}=\theta_{k+1}=\theta_{k+2}=0.4$, which satisfy condition (29) [21]
and maintain all the previous results. By Lemma 4,
$\mu(\bar{\alpha})\leq\mu_{k+1}\leq\mu_{k}$. So it is enough to look just at
the Newton steps, which are easier to analyze. Using (30) it is not hard to
see that

$\bar{\alpha}_{k}\geq\min\left\\{\frac{1-\sigma_{k}}{4\sigma_{k}},\frac{\sigma_{k}(1-\sigma_{k})}{10(1-\sigma_{k})+4}\right\\}\geq\min\left\\{\frac{0.1}{\sqrt{n}},\frac{0.03}{\sqrt{n}}\right\\}=\frac{0.03}{\sqrt{n}}.$

Therefore,

$\mu_{k+1}\leq\left(1-\frac{0.03}{\sqrt{n}}\frac{0.4}{\sqrt{n}}\right)\mu_{k}=\left(1-\frac{0.012}{n}\right)\mu_{k},\quad
k=0,2,4,\dots,$

from which the convergence with the worst-case iteration complexity of $O(n)$
can be derived.

###  3.2 The $\mathcal{N}_{s}$ neighborhood

Colombo and Gondzio [3] used the symmetric neighborhood
$\mathcal{N}_{s}(\gamma)$, defined by

$\mathcal{N}_{s}(\gamma)\doteq\left\\{(x,\lambda,z)\in\mathcal{F}\ |\
\gamma\mu\leq x_{i}z_{i}\leq\frac{1}{\gamma}\mu,i=1,\dots,n\right\\},$

for $\gamma\in(0,1)$, which is related with the
$\mathcal{N}_{-\infty}(\gamma)$ neighborhood used in long-step primal-dual
interior point algorithms. The idea of the symmetric neighborhood is to add an
upper bound on the complementarity pairs, so that their products do not become
too large with respect to the average. The authors showed that the worst-case
iteration complexity for linear feasible primal-dual interior point methods
remains $O(n)$ and the new neighborhood has a better practical interpretation.
As HOPDM [7] implements the $\mathcal{N}_{s}$ neighborhood and it was used in
the numerical experiments in [10] for quasi-Newton IPM, it is natural to ask
about the iteration complexity of Algorithm 1 operating in the
$\mathcal{N}_{s}$ neighborhood. The analysis presented below will follow
closely that from Subsection 3.1. We start from an assumption, but it is worth
observing that, from [3, 21], this assumption holds if the step-size in the
Newton direction is sufficiently small:
$\bar{\alpha}_{k}\in\left[0,\min\left\\{2^{3/2}\frac{1-\gamma}{1+\gamma}\frac{\sigma_{k}}{n},2^{3/2}\gamma\frac{1-\gamma}{1+\gamma}\frac{\sigma_{k}}{n}\right\\}\right]$.

######  Assumption 3.

Let $\gamma\in(0,1)$ and
$(x^{k},{\lambda}^{k},z^{k})\in\mathcal{N}_{s}(\gamma)$. Let the iterate after
a step $\bar{\alpha}_{k}$ in Newton direction also satisfy
$(x^{k+1},{\lambda}^{k+1},z^{k+1})\in\mathcal{N}_{s}(\gamma)$.

Our main goal is to show that the next iterate obtained after a step in the
quasi-Newton direction

$(x^{k+2},{\lambda}^{k+2},z^{k+2})=(x^{k+1},{\lambda}^{k+1},z^{k+1})+\bar{\alpha}(\Delta{x}^{k+1},\Delta{\lambda}^{k+1},\Delta{z}^{k+1})$

also belongs to $\mathcal{N}_{s}(\gamma)$ if suitable step-sizes
$\bar{\alpha}$ and $\bar{\alpha}_{k}$ are chosen. To demonstrate this, we will
consider lower and upper bounds on the complementarity products in the
$\mathcal{N}_{s}(\gamma)$ neighborhood using two possible values of
$\zeta\in\\{\gamma,\frac{1}{\gamma}\\}$. We start the analysis from expanding
the complementarity product at the quasi-Newton iteration

$\left[(X^{k+1}+\bar{\alpha}\Delta{X}^{k+1})(Z^{k+1}+\bar{\alpha}\Delta{Z}^{k+1})e\right]_{i}-\zeta\mu(\bar{\alpha}),$
(41)

where $\bar{\alpha}\in(0,1)$ is the step-size associated with the quasi-Newton
direction. To guarantee that the new iterate belongs to
$\mathcal{N}_{s}(\gamma)$, for $\zeta=\gamma$ the expression in (41) should be
non-negative and for $\zeta=1/\gamma$ it should be non-positive, for
$i=1,\dots,n$. Using (14) and Lemma 4, we rewrite the expression in (41)

$\begin{split}\left[x^{k+1}\right.&+\left.\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-\zeta\mu(\bar{\alpha})\quad=\quad(1-\bar{\alpha})(x_{i}^{k+1}z_{i}^{k+1}-\zeta\mu_{k+1})+(1-\zeta)\bar{\alpha}\sigma_{k+1}\mu_{k+1}\\\
&\quad+\left[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-(1+\gamma_{1}\bar{\alpha})\bar{\alpha}_{k}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}.\end{split}$
(42)

To deliver the main result of this section we will need a bound for the quasi-
Newton term $\gamma_{1}$ defined in Lemma 1 when the algorithm operates in the
$\mathcal{N}_{s}(\gamma)$ neighborhood.

######  Lemma 8.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1 operating in the
$\mathcal{N}_{s}(\gamma)$ neighborhood. Suppose that $v$ in Lemma 1 is given
by the right-hand side of (4) and Assumption 3 holds. If
$\bar{\alpha}_{k}\in(0,1]$ and $\sigma_{k}\in[0,1)$, then

$|\gamma_{1}|\leq\frac{2\sqrt{n}}{(1-\sigma_{k})\bar{\alpha}_{k}\gamma}.$

###### Proof.

Using the conditions of the lemma, the definition of $\mu$ and the fact that
$\sigma_{k+1}\in[0,1]$, we have that

$\begin{split}\|v\|&=\|\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e\|=\sqrt{\sigma_{k+1}^{2}\mu_{k+1}^{2}n-2\sigma_{k+1}\mu_{k+1}^{2}n+\sum_{i=1}^{n}(x_{i}^{k+1}z_{i}^{k+1})^{2}}\\\
&\leq\sqrt{(1/\gamma^{2})\mu_{k+1}^{2}n-(2-\sigma_{k+1})\sigma_{k+1}\mu_{k+1}^{2}n}\leq\sqrt{(1/\gamma^{2})-\sigma_{k+1}}\sqrt{n}\mu_{k+1}\\\
&\leq\frac{\sqrt{n}}{\gamma}\mu_{k+1}=\frac{(1-\bar{\alpha}_{k}(1-\sigma_{k}))\sqrt{n}}{\gamma}\mu_{k}\leq\frac{\sqrt{n}}{\gamma}\mu_{k}.\end{split}$

Since $\bar{\alpha}_{k}\in(0,1]$ and $\sigma_{k}\in[0,1)$, by defining
$\rho_{k}=1-\sigma_{k}>0$ we can again use
$\mu_{k+1}=(1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}$ and Lemma 2 to ensure
that $\|y_{k}\|>0$. Therefore, by (15), Lemma 2 and the previous result,

$|\gamma_{1}|\leq\frac{\|v\|}{\|y_{k}\|}\leq\frac{(1-\bar{\alpha}_{k}(1-\sigma_{k}))\sqrt{n}\mu_{k}}{\gamma}\frac{2}{(1-\sigma_{k})\bar{\alpha}_{k}\mu_{k}}=\frac{2(1-\bar{\alpha}_{k}(1-\sigma_{k}))\sqrt{n}}{(1-\sigma_{k})\bar{\alpha}_{k}\gamma}\leq\frac{2\sqrt{n}}{(1-\sigma_{k})\bar{\alpha}_{k}\gamma}.$

∎

The next lemma delivers a bound for term
$\left[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}$
under Assumption 3. Most of the calculations have already been made in the
proof of Lemma 7. Let us mention that Lemmas 7 and 9 can be viewed as the
quasi-Newton versions of [21, Lemma 5.10].

######  Lemma 9.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1 and suppose that
Assumption 3 holds. Then,

$\begin{split}\|\left(\right.&\left.\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\leq\\\
&\leq\frac{n\mu_{k}}{2^{3/2}\gamma}\Bigg{\\{}\left[(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))+\frac{|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}}{2^{3/2}}\right]^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}n+[1-(1-\bar{\alpha}(1-\sigma_{k+1}))(1-\bar{\alpha}_{k}(1-\sigma_{k}))]^{2}\Bigg{\\}}.\end{split}$

###### Proof.

We observe that many arguments used at the beginning of the proof of Lemma 7
remain valid for the $\mathcal{N}_{s}$ neighborhood. (Only the bound
$x_{i}^{k}z_{i}^{k}\geq(1-\theta_{k})\mu_{k}$ needs to be replaced with
$x_{i}^{k}z_{i}^{k}\geq\gamma\mu_{k}$.) Then inequalities (25) and (27) are
replaced with the following

$\begin{split}\|\left(\bar{\alpha}_{k}\Delta{X}^{k}\right.+&\left.\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\leq\\\
&\leq
2^{-3/2}\sum_{i=1}^{n}\frac{\left\\{(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}-x^{k}_{i}z^{k}_{i}\right)+\mu(\bar{\alpha})-\mu_{k}-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}\right\\}^{2}}{x^{k}_{i}z^{k}_{i}}\\\
&\leq\frac{1}{2^{3/2}\gamma\mu_{k}}\|(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)+(\mu(\bar{\alpha})-\mu_{k})e-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\|^{2}\\\
&=\frac{1}{2^{3/2}\gamma\mu_{k}}\left[\|(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\|^{2}+\|(\mu(\bar{\alpha})-\mu_{k})e\|^{2}\right],\end{split}$
(43)

where in the last equality we have used equation (26). We already have the
expression for $\|(\mu(\bar{\alpha})-\mu_{k})e\|^{2}$ (see (17)), but we need
a bound for the first norm in (43). We observe that

$\begin{split}\|\mu_{k}e-X^{k}Z^{k}e\|&=\sqrt{\sum_{i=1}^{n}(x_{i}^{k}z_{i}^{k})^{2}-2\mu_{k}^{2}n+\mu_{k}^{2}n}\leq\sqrt{\frac{\mu_{k}^{2}n}{\gamma^{2}}-\mu_{k}^{2}n}\leq\frac{1}{\gamma}\sqrt{n}\mu_{k}\leq\frac{1+\gamma}{\gamma}\sqrt{n}\mu_{k}.\end{split}$
(44)

Therefore, by (44) and the bound on
$\left\|\Delta{X}^{k}\Delta{Z}^{k}e\right\|$ obtained in [21, Lemma 5.10]
(which also holds for $\mathcal{N}_{s}$ [3])

$\begin{split}\left\|(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\mu_{k}e-X^{k}Z^{k}e\right)\right.-&\left.(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\right\|^{2}\leq\\\
&\leq\left[(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left\|\mu_{k}e-X^{k}Z^{k}e\right\|+|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}\left\|\Delta{X}^{k}\Delta{Z}^{k}e\right\|\right]^{2}\\\
&\leq\left[(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\left(\frac{1+\gamma}{\gamma}\right)\sqrt{n}\mu_{k}+\frac{|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}}{2^{3/2}}\left(\frac{1+\gamma}{\gamma}\right)\mu_{k}n\right]^{2}\\\
&\leq\left[(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))+\frac{|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}}{2^{3/2}}\right]^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}n^{2}\mu_{k}^{2},\end{split}$
(45)

since $n\geq 1$. Using (17) and (45) in (43), we obtain the desired result. ∎

Using (42) and the bounds obtained so far, we now show that, for sufficiently
small step-sizes $\bar{\alpha}_{k}$ and $\bar{\alpha}$, in the Newton and
quasi-Newton iterations, respectively, the point
$(x^{k+2},{\lambda}^{k+2},z^{k+2})$ also belongs to $\mathcal{N}_{s}(\gamma)$.
The upper bounds for the step-sizes delivered by the theorem below are then
used to determine the $O(n^{3})$ iteration worst-case complexity of Algorithm
1 operating in $\mathcal{N}_{s}(\gamma)$.

######  Theorem 2.

Suppose that $k+1$ is a quasi-Newton iteration of Algorithm 1 and Assumption 3
holds. Define

$l=\frac{\frac{1}{2}\sigma_{min}}{\frac{3}{2^{3/2}\gamma}\left(2+\frac{1}{\gamma(1-\sigma_{max})}\right)^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}},$

where $0<\sigma_{min}\leq\sigma_{k}\leq\sigma_{max}<1$ for all $k=0,1,2,\dots$
If

$\bar{\alpha}_{k}\in\left(0,\frac{(1-\gamma)l}{2n^{3}}\right]\quad\text{and}\quad\bar{\alpha}\in\left[2\bar{\alpha}_{k},\frac{(1-\gamma)l}{n^{3}}\right]$
(46)

then $\gamma\mu(\bar{\alpha})\leq
x^{k+2}_{i}z^{k+2}_{i}\leq(1/\gamma)\mu(\bar{\alpha})$ for all $i=1,\dots,n$.
If, in addition, $\gamma\geq\sigma_{min}/4$, then
$(x^{k+2},{\lambda}^{k+2},z^{k+2})\in\mathcal{N}_{s}(\gamma)$.

###### Proof.

By construction we guarantee that $\bar{\alpha}\geq 2\bar{\alpha}_{k}$ as
needed in (46). We start the proof by setting $\xi=\gamma$ in (42) and showing
that
$\left[x^{k+1}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-\gamma\mu(\bar{\alpha})\geq
0$ for sufficiently small step-sizes. By (42), using Assumption 3, Lemma 9 and
[21, Lemma 5.10], we obtain

$\begin{split}\left[x^{k+1}\right.&+\left.\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-\gamma\mu(\bar{\alpha})=\\\
&=(1-\bar{\alpha})(x_{i}^{k+1}z_{i}^{k+1}-\gamma\mu_{k+1})+(1-\gamma)\bar{\alpha}\sigma_{k+1}\mu_{k+1}\\\
&\quad+\left[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-(1+\gamma_{1}\bar{\alpha})\bar{\alpha}_{k}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}\\\
&\geq(1-\gamma)\bar{\alpha}\sigma_{k+1}(1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}-(1+\gamma_{1}\bar{\alpha})\bar{\alpha}_{k}^{2}\left(\frac{1\\!+\\!\gamma}{\gamma}\right)\frac{n}{2^{3/2}}\mu_{k}\\\
&\quad-\frac{n}{2^{3/2}\gamma}\left\\{\left[\bar{\alpha}+\bar{\alpha}_{k}(1\\!-\\!\bar{\alpha})+\frac{|1\\!+\\!\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}}{2^{3/2}}\right]^{2}\left(\frac{1\\!+\\!\gamma}{\gamma}\right)^{2}n+[1-(1-\bar{\alpha}(1\\!-\\!\sigma_{k+1}))(1\\!-\\!\bar{\alpha}_{k}(1\\!-\\!\sigma_{k}))]^{2}\right\\}\mu_{k}\\\
&=\mu_{k}\Bigg{\\{}(1-\gamma)\bar{\alpha}\sigma_{k+1}(1-\bar{\alpha}_{k}(1-\sigma_{k}))-(1+\gamma_{1}\bar{\alpha})\bar{\alpha}_{k}^{2}\left(\frac{1+\gamma}{\gamma}\right)\frac{n}{2^{3/2}}\\\
&\quad-\left[\bar{\alpha}+\bar{\alpha}_{k}(1\\!-\\!\bar{\alpha})+\frac{|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}}{2^{3/2}}\right]^{2}\left(\frac{1\\!+\\!\gamma}{\gamma}\right)^{2}\frac{n^{2}}{2^{3/2}\gamma}-[1\\!-\\!(1\\!-\\!\bar{\alpha}(1\\!-\\!\sigma_{k+1}))(1\\!-\\!\bar{\alpha}_{k}(1\\!-\\!\sigma_{k}))]^{2}\frac{n}{2^{3/2}\gamma}\Bigg{\\}}.\end{split}$
(47)

We will rearrange this expression and represent it in a form
$K_{1}\bar{\alpha}-K_{2}{\bar{\alpha}}^{2}$ with $K_{1},K_{2}>0$. Next, we
will show that (47) is non-negative for sufficiently small values of
$\bar{\alpha}_{k}$ and $\bar{\alpha}$. To deliver the desired results every
term inside the curly brackets in (47) will be bounded. Since
$\bar{\alpha}_{k}\leq\frac{1}{2}\bar{\alpha}\leq\frac{1}{2}$, we have
$1-\bar{\alpha}_{k}(1-\sigma_{k})\geq
1-\frac{1}{2}(1-\sigma_{k})\geq\frac{1}{2}$ hence for the first term in (47)
we obtain

$(1-\gamma)\bar{\alpha}\sigma_{k+1}(1-\bar{\alpha}_{k}(1-\sigma_{k}))\geq\frac{1}{2}[(1-\gamma)\sigma_{k+1}]\bar{\alpha}.$
(48)

Using condition $\bar{\alpha}\geq 2\bar{\alpha}_{k}$ (guaranteed by (46)),
$n\geq 1$ and Lemma 8, the second term becomes

$\begin{split}(1+\gamma_{1}\bar{\alpha})\bar{\alpha}_{k}^{2}\left(\frac{1+\gamma}{\gamma}\right)\frac{n}{2^{3/2}}&\leq(\bar{\alpha}_{k}^{2}+|\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2})\left(\frac{1+\gamma}{\gamma}\right)\frac{n}{2^{3/2}}\leq\left(\bar{\alpha}_{k}^{2}+\frac{2\sqrt{n}}{\gamma(1-\sigma_{k})}\bar{\alpha}\bar{\alpha}_{k}\right)\left(\frac{1+\gamma}{\gamma}\right)\frac{n}{2^{3/2}}\\\
&\leq\left(\frac{\bar{\alpha}^{2}}{4}+\frac{\sqrt{n}}{\gamma(1-\sigma_{k})}\bar{\alpha}^{2}\right)\left(\frac{1+\gamma}{\gamma}\right)\frac{n}{2^{3/2}}=\left(\frac{1}{4}+\frac{\sqrt{n}}{\gamma(1-\sigma_{k})}\right)\left(\frac{1+\gamma}{\gamma}\right)\frac{n}{2^{3/2}}\bar{\alpha}^{2}\\\
&\leq\left(2+\frac{1}{\gamma(1-\sigma_{k})}\right)\left(\frac{1+\gamma}{\gamma}\right)\frac{n\sqrt{n}}{2^{3/2}\gamma}\bar{\alpha}^{2}.\end{split}$
(49)

By applying condition $\bar{\alpha}\geq 2\bar{\alpha}_{k}$ again, we conclude
that

$\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha})=\bar{\alpha}+\bar{\alpha}_{k}-\bar{\alpha}\bar{\alpha}_{k}\leq\bar{\alpha}+\frac{1}{2}\bar{\alpha}-\bar{\alpha}\bar{\alpha}_{k}\leq\frac{3}{2}\bar{\alpha}$
(50)

and, using (50) and the same arguments as before, for the third term in (47)
we obtain

$\begin{split}\left[\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha})+\frac{|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}}{2^{3/2}}\right]^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\frac{n^{2}}{2^{3/2}\gamma}&\leq\left[\frac{3}{2}\bar{\alpha}+\left(1+\frac{2\sqrt{n}}{\gamma(1-\sigma_{k})\bar{\alpha}_{k}}\right)\frac{\bar{\alpha}\bar{\alpha}_{k}^{2}}{2^{3/2}}\right]^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\frac{n^{2}}{2^{3/2}\gamma}\\\
&\leq\left(\frac{3}{2}+\frac{1}{2}+\frac{\sqrt{n}}{\gamma(1-\sigma_{k})}\right)^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\frac{n^{2}}{2^{3/2}\gamma}\bar{\alpha}^{2}\\\
&\leq\left(2+\frac{1}{\gamma(1-\sigma_{k})}\right)^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\frac{n^{3}}{2^{3/2}\gamma}\bar{\alpha}^{2}.\end{split}$
(51)

In a similar fashion, the last term of (47) can be bounded as

$\begin{split}[1\\!-\\!(1\\!-\\!\bar{\alpha}(1\\!-\\!\sigma_{k+1}))&(1-\bar{\alpha}_{k}(1-\sigma_{k}))]^{2}\frac{n}{2^{3/2}\gamma}=[1\\!-\\!(1\\!-\\!\bar{\alpha}_{k}(1\\!-\\!\sigma_{k}))+\bar{\alpha}(1\\!-\\!\sigma_{k+1})(1\\!-\\!\bar{\alpha}_{k}(1\\!-\\!\sigma_{k}))]^{2}\frac{n}{2^{3/2}\gamma}\\\
&=[\bar{\alpha}_{k}(1-\sigma_{k})+\bar{\alpha}(1-\sigma_{k+1})(1-\bar{\alpha}_{k}(1-\sigma_{k}))]^{2}\frac{n}{2^{3/2}\gamma}\\\
&\leq\left[\frac{(1-\sigma_{k})}{2}+(1-\sigma_{k+1})(1-\bar{\alpha}_{k}(1-\sigma_{k}))\right]^{2}\frac{n}{2^{3/2}\gamma}\bar{\alpha}^{2}\quad\leq\quad
4\frac{n}{2^{3/2}\gamma}\bar{\alpha}^{2}.\end{split}$ (52)

Since $n\geq 1$ and assuming without loss of generality that
$\left(2+\frac{1}{\gamma(1-\sigma_{k})}\right)\left(\frac{1+\gamma}{\gamma}\right)\geq
4$, using (48), (49), (51) and (52) in (47) we have that

$\begin{split}\left[x^{k+1}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}&\left[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-\gamma\mu(\bar{\alpha})\geq\\\
&\geq\Bigg{\\{}\frac{1}{2}[(1-\gamma)\sigma_{k+1}]\bar{\alpha}-3\left(2+\frac{1}{\gamma(1-\sigma_{k})}\right)^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\frac{n^{3}}{2^{3/2}\gamma}\bar{\alpha}^{2}\Bigg{\\}}\mu_{k}\\\
&\geq\Bigg{\\{}\frac{1}{2}[(1-\gamma)\sigma_{min}]\bar{\alpha}-3\left(2+\frac{1}{\gamma(1-\sigma_{max})}\right)^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\frac{n^{3}}{2^{3/2}\gamma}\bar{\alpha}^{2}\Bigg{\\}}\mu_{k}.\end{split}$

Therefore, in order to guarantee that
$\left[x^{k+1}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}\geq\gamma\mu(\bar{\alpha})$
for $i=1,\dots,n$, it is sufficient that the quasi-Newton step-size
$\bar{\alpha}$ satisfies

$\bar{\alpha}\leq\frac{\frac{1}{2}(1-\gamma)\sigma_{min}}{\frac{3}{2^{3/2}\gamma}\left(2+\frac{1}{\gamma(1-\sigma_{max})}\right)^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}n^{3}}=\frac{(1-\gamma)l}{n^{3}}.$
(53)

We now set $\xi=1/\gamma$ in (42). In order to show that the resulting
expression is non-positive, we use the same arguments as before, that is,
Lemma 9 and equations (48), (49), (51) and (52) to obtain

$\begin{split}\left[x^{k+1}\right.&+\left.\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-(1/\gamma)\mu(\bar{\alpha})=\\\
&=(1-\bar{\alpha})(x_{i}^{k+1}z_{i}^{k+1}-(1/\gamma)\mu_{k+1})+(1-(1/\gamma))\bar{\alpha}\sigma_{k+1}\mu_{k+1}\\\
&\quad+\left[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}-(1+\gamma_{1}\bar{\alpha})\bar{\alpha}_{k}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}\\\
&\leq(1-(1/\gamma))\bar{\alpha}\sigma_{k+1}\mu_{k+1}+\left[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}+|1+\gamma_{1}\bar{\alpha}|\bar{\alpha}_{k}^{2}|[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}|\\\
&\leq(1-(1/\gamma))\bar{\alpha}\sigma_{k+1}(1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}+|1+\gamma_{1}\bar{\alpha}|\bar{\alpha}_{k}^{2}\left(\frac{1+\gamma}{\gamma}\right)\frac{n}{2^{3/2}}\mu_{k}\\\
&\quad+\frac{n}{2^{3/2}\gamma}\left\\{\left[\bar{\alpha}\\!+\\!\bar{\alpha}_{k}(1\\!-\\!\bar{\alpha})\\!+\\!\frac{|1\\!+\\!\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}}{2^{3/2}}\right]^{2}\left(\frac{1\\!+\\!\gamma}{\gamma}\right)^{2}n+[1\\!-\\!(1\\!-\\!\bar{\alpha}(1\\!-\\!\sigma_{k+1}))(1\\!-\\!\bar{\alpha}_{k}(1\\!-\\!\sigma_{k}))]^{2}\right\\}\mu_{k}\\\
&=\mu_{k}\Bigg{\\{}|1+\gamma_{1}\bar{\alpha}|\bar{\alpha}_{k}^{2}\left(\frac{1+\gamma}{\gamma}\right)\frac{n}{2^{3/2}}+\left[\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha})+\frac{|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}}{2^{3/2}}\right]^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\frac{n^{2}}{2^{3/2}\gamma}\\\
&\hskip
34.14322pt+[1-(1-\bar{\alpha}(1-\sigma_{k+1}))(1-\bar{\alpha}_{k}(1-\sigma_{k}))]^{2}\frac{n}{2^{3/2}\gamma}-\left(\frac{1-\gamma}{\gamma}\right)\bar{\alpha}\sigma_{k+1}(1-\bar{\alpha}_{k}(1-\sigma_{k}))\Bigg{\\}}\\\
&\leq\mu_{k}\left\\{3\left(2+\frac{1}{\gamma(1-\sigma_{k})}\right)^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\frac{n^{3}}{2^{3/2}\gamma}\bar{\alpha}^{2}-\frac{1}{2}\sigma_{k+1}\left(\frac{1-\gamma}{\gamma}\right)\bar{\alpha}\right\\}\\\
&\leq\mu_{k}\left\\{3\left(2+\frac{1}{\gamma(1-\sigma_{max})}\right)^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\frac{n^{3}}{2^{3/2}\gamma}\bar{\alpha}^{2}-\frac{1}{2}\sigma_{min}\left(\frac{1-\gamma}{\gamma}\right)\bar{\alpha}\right\\}.\end{split}$
(54)

Therefore, if

$\bar{\alpha}\leq\frac{\left(\dfrac{1-\gamma}{\gamma}\right)l}{n^{3}},$ (55)

then by (54) we have that
$\left[x^{k+1}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}\leq(1/\gamma)\mu(\bar{\alpha})$
for all $i=1,\dots,n$. Observe that bound (53) is tighter than (55) because
$\gamma\in(0,1)$ hence (53) appears as an upper bound on $\bar{\alpha}$ in
(46). The remaining bounds in (46) are consistent with the need to satisfy
$\bar{\alpha}\geq 2\bar{\alpha}_{k}$.

It remains to show that $x^{k+2}$ and $z^{k+2}$ are strictly positive.
Similarly to Theorem 1, if, by contradiction, $x_{i}^{k+2}\leq 0$ or
$z_{i}^{k+2}\leq 0$ for some $i$, then we must have $x_{i}^{k+2}<0$ and
$z_{i}^{k+2}<0$. On one hand, we already know that
$x^{k}_{i}z^{k}_{i}\geq\gamma\mu_{k}$, by Assumption 3. Hence, by Lemma 9,
(51), (52) and similar arguments to those used in this proof

$\begin{split}x^{k}_{i}z^{k}_{i}&<\left[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}\right]_{i}\left[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}\right]_{i}\leq\|\left(\bar{\alpha}_{k}\Delta{X}^{k}+\bar{\alpha}\Delta{X}^{k+1}\right)\left(\bar{\alpha}_{k}\Delta{Z}^{k}+\bar{\alpha}\Delta{Z}^{k+1}\right)e\|\\\
&\leq\frac{3}{2^{3/2}\gamma}\left(2+\frac{1}{\gamma(1-\sigma_{max})}\right)^{2}\left(\frac{1+\gamma}{\gamma}\right)^{2}\bar{\alpha}^{2}\mu_{k}n^{3}=\frac{\sigma_{min}\bar{\alpha}^{2}\mu_{k}n^{3}}{2l}.\end{split}$

Hence we conclude that $\gamma<\sigma_{min}n^{3}\bar{\alpha}^{2}/(2l)$ which,
together with condition $\gamma\geq\sigma_{min}/4$ and (46), implies the
following absurd

$\frac{\sigma_{min}}{4}\leq\gamma<\frac{\sigma_{min}n^{3}\bar{\alpha}^{2}}{2l}\leq\frac{\sigma_{min}n^{3}\bar{\alpha}}{2l}\leq\frac{\sigma_{min}(1-\gamma)}{4}\leq\frac{\sigma_{min}}{4}.$

By Assumption 1, we have that $(x^{k+2},{\lambda}^{k+2},z^{k+2})$ belongs to
$\mathcal{F}$, hence we conclude that it belongs to $\mathcal{N}_{s}(\gamma)$.
∎

To deliver the worst-case polynomial complexity, we follow the same arguments
as those presented after the proof of Theorem 1 and consider only Newton
iterations which are simpler to analyze. By (46), we have that

$\bar{\alpha}_{k}\geq\frac{(1-\gamma)l}{2n^{3}}$

and, by [21, Lemma 5.1],

$\mu_{k+1}=(1-\bar{\alpha}_{k}(1-\sigma_{k}))\mu_{k}\leq\left(1-\frac{(1-\gamma)l}{2n^{3}}\right)\mu_{k},\quad
k=0,2,4,\dots,$

from which the convergence with the worst-case iteration complexity of
$O(n^{3})$ can be established easily.

Because of the close relation of the symmetric neighborhood and the
$\mathcal{N}_{-\infty}(\gamma)$ neighborhood, one should expect similar
complexity results to that of Theorem 2. However, if the
$\mathcal{N}_{s}(\gamma)$ neighborhood is not applied in Lemma 8, then a naive
approach is to bound $\sum_{i=1}^{n}\left(x^{k+1}_{i}z^{k+1}_{i}\right)^{2}$
by $\mu_{k+1}^{2}n^{2}$. Such approach would increase the worst-case iteration
complexity to $O(n^{4})$, as the degree would be increased in equation (51). A
different approach to reduce the worst-case polynomial degree when working
with the $\mathcal{N}_{-\infty}(\gamma)$ neighborhood is subject to future
developments.

##  4 Worst-case complexity in the infeasible case

In this section, we analyze worst-case iteration complexity for linear
programming problems without assuming feasibility of the starting point. The
analysis uses some ideas developed in Section 3 and follows [21, Chapter 6],
by adding extra requirements on the computation of step-size
$\bar{\alpha}_{k}$. The proofs are modified to consider the symmetric
neighborhood and admit the quasi-Newton steps.

We start by defining $r_{b}^{k}$ and $r_{c}^{k}$ to be the primal and dual
infeasibility vectors at point $(x^{k},{\lambda}^{k},z^{k})$ which appear in
the right-hand side of equation (4):

$r_{b}^{k}=Ax^{k}-b\quad\text{and}\quad r_{c}^{k}=A^{T}\lambda^{k}+z^{k}-c.$

Then, given an initial guess $(x^{0},{\lambda}^{0},z^{0})$ and parameters
$\beta\geq 1$ and $\gamma\in(0,1)$, the infeasible version of the symmetric
neighborhood is defined as follows

$\mathcal{N}_{s}(\gamma,\beta)\doteq\left\\{(x,\lambda,z)\ \Big{|}\ \
\|(r_{b},r_{c})\|\leq\frac{\|(r_{b}^{0},r_{c}^{0})\|}{\mu_{0}}\beta\mu,x>0,z>0\
\text{and}\ \gamma\mu\leq
x_{i}z_{i}\leq\frac{1}{\gamma}\mu,i=1,\dots,n\right\\}.$

In order to obtain complexity results, $\bar{\alpha}_{k}$ needs to be computed
in such a way that the new iterate remains in $\mathcal{N}_{s}(\gamma,\beta)$
and a sufficient decrease condition for $\mu_{k}$ is satisfied. More
precisely, given $\alpha_{\mathrm{dec}}\in(0,1)$, $\bar{\alpha}_{k}$ is the
largest value in $[0,1]$ (or a fixed fraction of it) such that

$(x^{k},{\lambda}^{k},z^{k})+\bar{\alpha}_{k}(\Delta{x}^{k},\Delta{\lambda}^{k},\Delta{z}^{k})\in\mathcal{N}_{s}(\gamma,\beta)\quad\text{and}\quad\mu(\bar{\alpha}_{k})\leq(1-\alpha_{\mathrm{dec}}\bar{\alpha}_{k})\mu_{k}.$
(56)

The goal of this section is to show that, assuming that one quasi-Newton step
is performed from a point in $\mathcal{N}_{s}(\gamma,\beta)$ by Algorithm 1,
then conditions (56) are satisfied by the new point. When only Newton steps
are taken, it is shown in [21, Lemma 6.7] that there is an interval
$[0,\hat{\alpha}]$ such that (56) holds for the
$\mathcal{N}_{-\infty}(\gamma,\beta)$ neighborhood. This is the case if a
special starting point is used and $\hat{\alpha}\geq\bar{\delta}/n^{2}$, where
$\bar{\delta}$ is a constant independent of $n$. In Lemma 10, we extend those
results in order to ensure that the iterates belong to
$\mathcal{N}_{s}(\gamma,\beta)$ when only Newton steps are taken.

First, let us recall some results from [21] that will be used frequently. We
define the scalar
$\displaystyle\nu_{k}=\prod_{i=0}^{k-1}(1-\bar{\alpha}_{i})$, which allows us
to write vectors $r_{b}^{k}$ and $r_{c}^{k}$ as $r_{b}^{k}=\nu_{k}r_{b}^{0}$
and $r_{c}^{k}=\nu_{k}r_{c}^{0}$, respectively. The parameter $\sigma_{k}$
used in (8) satisfies $0<\sigma_{min}\leq\sigma_{k}\leq\sigma_{max}<1$ for all
$k$. We also assume that a special initial point is used in Algorithm 1, given
by

$(x^{0},{\lambda}^{0},z^{0})=\begin{bmatrix}\xi e&0&\xi e\end{bmatrix}^{T},$
(57)

where $\xi$ is such that $\|(x^{*},z^{*})\|_{\infty}\leq\xi$, for some primal-
dual solution $(x^{*},{\lambda}^{*},z^{*})$.

Let $k$ be a Newton iteration,
$(x^{k},{\lambda}^{k},z^{k})\in\mathcal{N}_{s}(\gamma,\beta)$ and
$D^{k}=(X^{k})^{1/2}(Z^{k})^{-1/2}$. Also, let $\omega=9\beta/\gamma^{1/2}$ be
a constant independent of $n$. When (57) is used as the starting point, the
following bounds hold:

$\displaystyle\nu_{k}\|(x^{k},z^{k})\|_{1}$
$\displaystyle\leq\frac{4\beta}{\xi}n\mu_{k}$ (58) $\displaystyle\mu_{0}$
$\displaystyle=\xi^{2}$ (59) $\displaystyle\|(D^{k})^{-1}\Delta{x}^{k}\|$
$\displaystyle\leq\omega
n\mu_{k}^{1/2}\quad\text{and}\quad\|D^{k}\Delta{z}^{k}\|\leq\omega
n\mu_{k}^{1/2}.$ (60)

The proofs for these bounds can be found in Lemmas 6.4 and 6.6 of [21],
respectively.

We start the analysis from looking at Newton step in
$\mathcal{N}_{s}(\gamma,\beta)$ neighborhood.

######  Lemma 10.

If $(x^{k},{\lambda}^{k},z^{k})\in\mathcal{N}_{s}(\gamma,\beta)$ and the
Newton step is taken at iteration $k$, then there exists a constant
$\bar{\bar{\delta}}$ independent of $n$ and a value
$\hat{\alpha}\geq\bar{\bar{\delta}}/n^{2}$, independent of $k$, such that for
all $\bar{\alpha}_{k}\in[0,\hat{\alpha}]$

$\displaystyle(1-\bar{\alpha}_{k}){x^{k}}^{T}z^{k}$
$\displaystyle\leq(x^{k}+\bar{\alpha}_{k}\Delta{x}^{k})^{T}(z^{k}+\bar{\alpha}_{k}\Delta{z}^{k})\leq(1-\alpha_{\mathrm{dec}}\bar{\alpha}_{k}){x^{k}}^{T}z^{k}$
(61) $\displaystyle\gamma\mu(\bar{\alpha}_{k})$
$\displaystyle\leq[x^{k}+\bar{\alpha}_{k}\Delta{x}^{k}]_{i}[z^{k}+\bar{\alpha}_{k}\Delta{z}^{k}]_{i}\leq\frac{1}{\gamma}\mu(\bar{\alpha}_{k})$
(62)

###### Proof.

We only need to address the right inequality of (62), since all the other
results were detailed in [21, Lemma 6.7]. Since $k$ is a Newton iteration, by
(60), we obtain

$\lvert\Delta{x}^{k}_{i}\Delta{z}^{k}_{i}\rvert\leq\lvert[(D^{k})^{-1}]_{ii}\Delta{x}^{k}_{i}\rvert\lvert[D^{k}]_{ii}\Delta{z}^{k}_{i}\rvert\leq\|(D^{k})^{-1}\Delta{x}^{k}\|\|D^{k}\Delta{z}^{k}\|\leq\omega^{2}n^{2}\mu_{k}.$

As $(\Delta{x}^{k},\Delta{\lambda}^{k},\Delta{z}^{k})$ solves (4) and
$(x^{k},{\lambda}^{k},z^{k})\in\mathcal{N}_{s}(\gamma,\beta)$, using a
component-wise version of (9) we get

$\begin{split}[x^{k}+\bar{\alpha}_{k}\Delta{x}^{k}]_{i}[z^{k}+\bar{\alpha}_{k}\Delta{z}^{k}]_{i}&=(1-\bar{\alpha}_{k})x^{k}_{i}z^{k}_{i}+\bar{\alpha}_{k}\sigma_{k}\mu_{k}+\bar{\alpha}_{k}^{2}\Delta{x}^{k}_{i}\Delta{z}^{k}_{i}\\\
&\leq\frac{1-\bar{\alpha}_{k}}{\gamma}\mu_{k}+\bar{\alpha}_{k}\sigma_{k}\mu_{k}+\bar{\alpha}_{k}^{2}\omega^{2}n^{2}\mu_{k}.\end{split}$
(63)

Using similar arguments and equation (9) again, we also obtain

$\begin{split}\frac{1}{\gamma}\mu(\bar{\alpha}_{k})=\frac{1}{\gamma}\frac{(x^{k}+\bar{\alpha}_{k}\Delta{x}^{k})^{T}(z^{k}+\bar{\alpha}_{k}\Delta{z}^{k})}{n}&\geq\frac{1-\bar{\alpha}_{k}}{\gamma}\mu_{k}+\frac{\bar{\alpha}_{k}\sigma_{k}}{\gamma}\mu_{k}-\frac{\bar{\alpha}_{k}^{2}\lvert{\Delta{x}^{k}}^{T}\Delta{z}^{k}\rvert}{\gamma
n}\\\
&\geq\frac{1-\bar{\alpha}_{k}}{\gamma}\mu_{k}+\frac{\bar{\alpha}_{k}\sigma_{k}}{\gamma}\mu_{k}-\frac{\bar{\alpha}_{k}^{2}\omega^{2}n}{\gamma}\mu_{k}.\end{split}$
(64)

Using (63), (64) and the fact that $n\geq 1$, we obtain

$\begin{split}[x^{k}+\bar{\alpha}_{k}\Delta{x}^{k}]_{i}[z^{k}+\bar{\alpha}_{k}\Delta{z}^{k}]_{i}-\frac{1}{\gamma}\mu(\bar{\alpha}_{k})&\leq\bar{\alpha}_{k}\sigma_{k}\left(1-\frac{1}{\gamma}\right)\mu_{k}+\bar{\alpha}_{k}^{2}\omega^{2}n^{2}\left(1+\frac{1}{\gamma}\right)\mu_{k}.\end{split}$

The right-hand side of this inequality is non-positive if
$\bar{\alpha}_{k}\leq\dfrac{\sigma_{min}(1-\gamma)}{\omega^{2}n^{2}(1+\gamma)}$.
By defining $\bar{\bar{\delta}}$ as the minimum of
$\dfrac{\sigma_{min}(1-\gamma)}{\omega^{2}(1+\gamma)}$ and $\bar{\delta}$
defined in [21, Lemma 6.7], we obtain the desired result. ∎

By Lemma 10, if $k$ is a Newton iteration of Algorithm 1 and
$\bar{\alpha}_{k}\leq\bar{\bar{\delta}}/n^{2}$, then point
$(x^{k+1},{\lambda}^{k+1},z^{k+1})$ satisfies (56). If only Newton steps are
made, then $O(n^{2})$ worst-case iteration complexity can be proved for
$\mathcal{N}_{s}(\gamma,\beta)$ (see [21, Chapter 6]).

Based on the previous paragraphs, we set some assumptions that will be used in
the remaining of this section. As usual, at iteration $k$ the Newton step is
taken and at iteration $k+1$ the quasi-Newton step is made. We assume that
$(x^{0},{\lambda}^{0},z^{0})$ satisfies (57), both
$(x^{k},{\lambda}^{k},z^{k})$ and $\bar{\alpha}_{k}$ satisfy (56), and
$(x^{k+1},{\lambda}^{k+1},z^{k+1})\in\mathcal{N}_{s}(\gamma,\beta)$. In our
analysis, we will use extensively various well known results for Newton steps,
such as properties (58)–(62). We observe that, while in the standard Newton
approach one has to compute bounds for ${\Delta{x}^{k}}^{T}\Delta{z}^{k}$, in
the quasi-Newton approach (see for example (13)), it is necessary to
additionally get bounds for $\gamma_{1}$ and
$(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})^{T}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})$.
In the next lemma, we give a bound for $\gamma_{1}$ without assuming
feasibility of iterates.

######  Lemma 11.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1. Suppose that $v$ in
Lemma 1 is given by the right-hand side of (4) at iteration $k+1$ and
$\bar{\alpha}_{k}\in(0,1]$. Then, there exists a constant $C_{3}\geq 1$,
independent of $n$ and $k$ such that

$|\gamma_{1}|\leq C_{3}\frac{\sqrt{n}}{\bar{\alpha}_{k}}.$ (65)

###### Proof.

Using scalar $\nu_{k+1}$ defined in the beginning of this section, vector $v$
at iteration $k+1$ is given by

$v=\begin{bmatrix}0\\\ 0\\\
\sigma_{k+1}\mu_{k+1}e\end{bmatrix}-F(x^{k+1},\lambda^{k+1},z^{k+1})=\begin{bmatrix}-r_{c}^{k+1}\\\
-r_{b}^{k+1}\\\
\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e\end{bmatrix}=\begin{bmatrix}-\nu_{k+1}r_{c}^{0}\\\
-\nu_{k+1}r_{b}^{0}\\\ \sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e\end{bmatrix}.$
(66)

We observe that, since $e^{T}(\mu_{k+1}e-X^{k+1}Z^{k+1}e)=0$, by (56) we
obtain

$\begin{split}\|\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e\|^{2}&=\|(\sigma_{k+1}-1)\mu_{k+1}e+(\mu_{k+1}e-X^{k+1}Z^{k+1}e)\|^{2}\\\
&=(\sigma_{k+1}-1)^{2}\mu_{k+1}^{2}n+\|\mu_{k+1}e-X^{k+1}Z^{k+1}e\|^{2}\\\
&=(\sigma_{k+1}-1)^{2}\mu_{k+1}^{2}n+\|X^{k+1}Z^{k+1}e\|^{2}-n\mu_{k+1}^{2}\\\
&\leq-(2-\sigma_{k+1})\sigma_{k+1}n\mu_{k+1}^{2}+\gamma^{-2}n\mu_{k+1}^{2}\
\leq\ \gamma^{-2}n\mu_{k+1}^{2}.\end{split}$ (67)

Taking the 2-norm in (66) and using (59) and (67), we get

$\begin{split}\|v\|^{2}&=\|(r_{c}^{k+1},r_{b}^{k+1})\|^{2}+\|\sigma_{k+1}\mu_{k+1}e-X^{k+1}Z^{k+1}e\|^{2}\leq\left(\frac{\|(r_{c}^{0},r_{b}^{0})\|\beta}{\mu_{0}}\right)^{2}\mu^{2}_{k+1}+\gamma^{-2}n\mu_{k+1}^{2}\\\
&\leq\left[\left(\frac{\|(r_{c}^{0},r_{b}^{0})\|\beta}{\xi^{2}}\right)^{2}+\gamma^{-2}\right]n\mu^{2}_{k+1}.\end{split}$
(68)

By defining $\rho_{k}=\alpha_{\mathrm{dec}}>0$, we can see that condition (56)
results in the sufficient decrease condition of Lemma 2. Since
$\bar{\alpha}_{k}\in(0,1]$, this ensures that $\|y_{k}\|>0$. Using Lemma 2,
(56) and (68) in equation (15), we conclude that

$\begin{split}|\gamma_{1}|\leq\frac{\|v\|}{\|y_{k}\|}&\leq\frac{\left[\left(\dfrac{\|(r_{c}^{0},r_{b}^{0})\|\beta}{\xi^{2}}\right)^{2}+\gamma^{-2}\right]^{1/2}\sqrt{n}\mu_{k+1}}{\frac{\alpha_{\mathrm{dec}}\bar{\alpha}_{k}}{2}\mu_{k}}\leq
C_{3}\frac{\sqrt{n}}{\bar{\alpha}_{k}},\end{split}$

with
$C_{3}=2(\gamma\alpha_{\mathrm{dec}})^{-1}\left[\left(\dfrac{\|(r_{c}^{0},r_{b}^{0})\|\beta\gamma}{\xi^{2}}\right)^{2}\\!+\\!1\right]^{1/2}$.
In the last inequality we used (56) to yield $\mu_{k+1}/\mu_{k}\leq 1$. ∎

Our goal now is to bound the term
$(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})^{T}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})$
in (13). We follow the same approach as [21] but compute, instead, bounds of
$(D^{k})^{-1}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})$ and
$D^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})$, where
$D^{k}=(X^{k})^{1/2}(Z^{k})^{-1/2}$. It is important to note that matrix
$D^{k}$ is related to the Newton iteration, hence we can use Lemma 1 and the
enjoyable properties of the true Jacobian.

First, we show what happens when matrix $A$ multiplies the combined direction
$\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}$:

$\begin{split}A(\bar{\alpha}_{k}\Delta{x}^{k}&+\bar{\alpha}\Delta{x}^{k+1})=\bar{\alpha}_{k}A\Delta{x}^{k}+\bar{\alpha}A\Delta{x}^{k+1}=-\bar{\alpha}_{k}(Ax^{k}-b)-\bar{\alpha}(Ax^{k+1}-b)\\\
&=-\bar{\alpha}_{k}(Ax^{k}-b)-\bar{\alpha}(A(x^{k}+\bar{\alpha}_{k}\Delta{x}^{k})-b)\
=\
-\bar{\alpha}_{k}(Ax^{k}-b)-\bar{\alpha}(Ax^{k}-b)+\bar{\alpha}_{k}\bar{\alpha}(Ax^{k}-b)\\\
&=(\bar{\alpha}_{k}\bar{\alpha}-\bar{\alpha}_{k}-\bar{\alpha})(Ax^{k}-b)\ =\
(\bar{\alpha}_{k}\bar{\alpha}-\bar{\alpha}_{k}-\bar{\alpha})\nu_{k}(Ax^{0}-b)\\\
&=A\left[(\bar{\alpha}_{k}\bar{\alpha}-\bar{\alpha}_{k}-\bar{\alpha})\nu_{k}(x^{0}-x^{*})\right],\end{split}$

where $x^{*}$ is the primal solution of (1) used to define constant $\xi$ in
(57). By defining
$\hat{\nu}_{k}=-(\bar{\alpha}_{k}\bar{\alpha}-\bar{\alpha}_{k}-\bar{\alpha})\nu_{k}=(1-(1-\bar{\alpha}_{k})(1-\bar{\alpha}))\nu_{k}$,
we can see that the point
$\hat{x}=\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}+\hat{\nu}_{k}(x^{0}-x^{*})$
is such that $A\hat{x}=0$. Similar arguments can be used to show that
$\hat{z}=\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}+\hat{\nu}_{k}(z^{0}-z^{*})$
and
$\hat{\lambda}=\bar{\alpha}_{k}\Delta{\lambda}^{k}+\bar{\alpha}\Delta{\lambda}^{k+1}+\hat{\nu}_{k}(\lambda^{0}-\lambda^{*})$
satisfy $A^{T}\hat{\lambda}+\hat{z}=0$. Therefore, it is not hard to see that

${\hat{x}}^{T}\hat{z}=\left(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}+\hat{\nu}_{k}(x^{0}-x^{*})\right)^{T}\left(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}+\hat{\nu}_{k}(z^{0}-z^{*})\right)=0.$
(69)

We now multiply the third row of the coefficient matrix in (4) by
$\begin{bmatrix}\hat{x}&\hat{\lambda}&\hat{z}\end{bmatrix}$ to obtain

$\begin{split}Z^{k}\hat{x}+X^{k}\hat{z}&=Z^{k}\left(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}+\hat{\nu}_{k}(x^{0}-x^{*})\right)+X^{k}\left(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}+\hat{\nu}_{k}(z^{0}-z^{*})\right)\\\
&=Z^{k}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})+X^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})+\hat{\nu}_{k}Z^{k}(x^{0}-x^{*})+\hat{\nu}_{k}X^{k}(z^{0}-z^{*}).\end{split}$

Multiplying this equation on both sides by $(X^{k}Z^{k})^{-1/2}$, we get

$\begin{split}(D^{k})^{-1}\hat{x}+D^{k}\hat{z}&=(X^{k}Z^{k})^{-1/2}\left[Z^{k}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})+X^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\right]\\\
&\quad+\hat{\nu}_{k}(D^{k})^{-1}(x^{0}-x^{*})+\hat{\nu}_{k}{D^{k}}(z^{0}-z^{*}).\end{split}$
(70)

Using (69) and (70), we conclude that

$\begin{split}\|(D^{k})^{-1}\hat{x}\|^{2}+\|D^{k}\hat{z}\|^{2}&=\|(D^{k})^{-1}\hat{x}+D^{k}\hat{z}\|^{2}\\\
&=\Big{\|}(X^{k}Z^{k})^{-1/2}\left[Z^{k}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})+X^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\right]\\\
&\qquad+\hat{\nu}_{k}(D^{k})^{-1}(x^{0}-x^{*})+\hat{\nu}_{k}{D^{k}}(z^{0}-z^{*})\Big{\|}^{2}.\end{split}$

Using this relation we get

$\begin{split}\|(D^{k})^{-1}\hat{x}\|&\leq\left\|(X^{k}Z^{k})^{-1/2}\left[Z^{k}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})+X^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\right]\right\|\\\
&\quad+\hat{\nu}_{k}\|{D^{k}}^{-1}(x^{0}-x^{*})\|+\hat{\nu}_{k}\|{D^{k}}(z^{0}-z^{*})\|\end{split}$
(71)

and observe that the same bound holds for $\|D^{k}\hat{z}\|$. In the next two
lemmas, we compute the bounds for the terms in the right-hand side of (71).

######  Lemma 12.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1. Let $\omega$ and $C_{3}$
be the constants (independent of $k$ and $n$) defined in equation (60) and
Lemma 11, respectively. Then

$\begin{split}\Big{\|}(X^{k}Z^{k})^{-1/2}&\left[Z^{k}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})+X^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\right]\Big{\|}\leq\\\
&\leq\gamma^{-1/2}\left[(\sigma_{max}+\gamma^{-1})(\bar{\alpha}_{k}+\bar{\alpha})+(\bar{\alpha}_{k}+C_{3})\bar{\alpha}\bar{\alpha}_{k}\omega^{2}\right]n^{5/2}\mu_{k}^{1/2}.\end{split}$

###### Proof.

First, we observe that the diagonal matrices $\Delta{X}^{k}$ and
$\Delta{Z}^{k}$ were computed in the Newton iteration and use (60) to obtain

$\|\Delta{X}^{k}\Delta{Z}^{k}e\|\leq\|(D^{k})^{-1}\Delta{X}^{k}\|\|D^{k}\Delta{Z}^{k}e\|\leq\|(D^{k})^{-1}\Delta{X}^{k}\|\omega
n\mu_{k}^{1/2}.$

Since both $(D^{k})^{-1}$ and $\Delta{X}^{k}$ are diagonal matrices, using the
property of the induced 2-norm of matrices, we get

$\|(D^{k})^{-1}\Delta{X}^{k}\|=\underset{i=1,\dots,n}{\max}\dfrac{|[\Delta{x}^{k}]_{i}|}{[D^{k}]_{ii}}=\|(D^{k})^{-1}\Delta{X}^{k}e\|_{\infty}\leq\|(D^{k})^{-1}\Delta{X}^{k}e\|\leq\omega
n\mu_{k}^{1/2}.$

Hence,

$\|\Delta{X}^{k}\Delta{Z}^{k}e\|\leq\omega^{2}n^{2}\mu_{k}.$ (72)

Now, we use equation (21) (which does not depend on the feasibility of the
iterate or the type of the neighborhood) to expand the desired expression in
the statement of this Lemma. Additionally, we use equation (56) to bound
$\mu_{k+1}$ and $X^{k}Z^{k}e$ as well as Lemma 11 and equation (72) to derive:

$\begin{split}\left\|(X^{k}\right.&\left.Z^{k})^{-1/2}\left[Z^{k}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})+X^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\right]\right\|=\\\
&=\left(\sum_{i=1}^{n}\dfrac{\left((1-\bar{\alpha})\bar{\alpha}_{k}\sigma_{k}\mu_{k}-(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))x_{i}^{k}z_{i}^{k}+\bar{\alpha}\sigma_{k+1}\mu_{k+1}-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}\right)^{2}}{x_{i}^{k}z_{i}^{k}}\right)^{1/2}\\\
&\leq(\gamma\mu_{k})^{-1/2}\left\|(1-\bar{\alpha})\bar{\alpha}_{k}\sigma_{k}\mu_{k}e-(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))X^{k}Z^{k}e+\bar{\alpha}\sigma_{k+1}\mu_{k+1}e-(1+\gamma_{1})\bar{\alpha}\bar{\alpha}_{k}^{2}\Delta{X}^{k}\Delta{Z}^{k}e\right\|\\\
&\leq(\gamma\mu_{k})^{-1/2}\left[(1-\bar{\alpha})\bar{\alpha}_{k}\sigma_{k}\sqrt{n}\mu_{k}+(\bar{\alpha}+\bar{\alpha}_{k}(1-\bar{\alpha}))\gamma^{-1}\sqrt{n}\mu_{k}+\bar{\alpha}\sigma_{k+1}\sqrt{n}\mu_{k}+|1+\gamma_{1}|\bar{\alpha}\bar{\alpha}_{k}^{2}\omega^{2}n^{2}\mu_{k}\right]\\\
&\leq\gamma^{-1/2}\left[\left((\sigma_{k}+\gamma^{-1})(1-\bar{\alpha})\bar{\alpha}_{k}+(\sigma_{k+1}+\gamma^{-1})\bar{\alpha}\right)\sqrt{n}+\left(1+C_{3}\frac{\sqrt{n}}{\bar{\alpha}_{k}}\right)\bar{\alpha}\bar{\alpha}_{k}^{2}\omega^{2}n^{2}\right]\mu_{k}^{1/2}\\\
&\leq\gamma^{-1/2}\left[(\sigma_{max}+\gamma^{-1})(\bar{\alpha}_{k}+\bar{\alpha})\sqrt{n}+(\bar{\alpha}_{k}+C_{3})\bar{\alpha}\bar{\alpha}_{k}\omega^{2}n^{5/2}\right]\mu_{k}^{1/2}\\\
&\leq\gamma^{-1/2}\left[(\sigma_{max}+\gamma^{-1})(\bar{\alpha}_{k}+\bar{\alpha})+(\bar{\alpha}_{k}+C_{3})\bar{\alpha}\bar{\alpha}_{k}\omega^{2}\right]n^{5/2}\mu_{k}^{1/2}.\\\
\end{split}$

∎

######  Lemma 13.

Let $k+1$ be a quasi-Newton iteration of Algorithm 1. Let $\omega$ and $C_{3}$
be the constants (independent of $k$ and $n$) defined before. Then,

$\displaystyle\|(D^{k})^{-1}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})\|$
$\displaystyle\leq\left[(\sigma_{max}+\gamma^{-1}+8\beta)(\bar{\alpha}_{k}+\bar{\alpha})+(\bar{\alpha}_{k}+C_{3})\omega^{2}\bar{\alpha}_{k}\bar{\alpha}\right]\gamma^{-1/2}n^{5/2}\mu_{k}^{1/2}$
$\displaystyle\|D^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\|$
$\displaystyle\leq\left[(\sigma_{max}+\gamma^{-1}+8\beta)(\bar{\alpha}_{k}+\bar{\alpha})+(\bar{\alpha}_{k}+C_{3})\omega^{2}\bar{\alpha}_{k}\bar{\alpha}\right]\gamma^{-1/2}n^{5/2}\mu_{k}^{1/2}.$

###### Proof.

We will only consider
$\|(D^{k})^{-1}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})\|$,
since getting a bound for
$\|D^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\|$ follows
the same arguments. We use the definition of $\hat{x}$ (see (69)), add and
subtract $\hat{\nu}_{k}(D^{k})^{-1}(x^{0}-x^{*})$ inside the norm, and then
use the triangle inequality and (71) to obtain

$\begin{split}\|(D^{k})^{-1}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})\|&=\|(D^{k})^{-1}\hat{x}-\hat{\nu}_{k}(D^{k})^{-1}(x^{0}-x^{*})\|\leq\|(D^{k})^{-1}\hat{x}\|+\hat{\nu}_{k}\|(D^{k})^{-1}(x^{0}-x^{*})\|\\\
&\leq\left\|(X^{k}Z^{k})^{-1/2}\left[Z^{k}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})+X^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\right]\right\|\\\
&\quad+2\hat{\nu}_{k}\|(D^{k})^{-1}(x^{0}-x^{*})\|+2\hat{\nu}_{k}\|{D^{k}}(z^{0}-z^{*})\|,\end{split}$
(73)

where another term $\hat{\nu}_{k}\|{D^{k}}(z^{0}-z^{*})\|$ was added in the
last inequality. We already have bounds for the first term in the right-hand
side of (73), by Lemma 12. From [21, Lemma 6.6] we know that

$\begin{split}\|(D^{k})^{-1}(x^{0}-x^{*})\|&\leq\|(x^{0}-x^{*})\|\|(D^{k})^{-1}\|\leq\xi\|(D^{k})^{-1}\|=\xi\
\underset{i=1,\dots,n}{\max}\
\dfrac{1}{[D^{k}]_{ii}}=\xi\|(D^{k})^{-1}e\|_{\infty}\\\
&\leq\xi\|(D^{k})^{-1}e\|=\xi\|(X^{k}Z^{k})^{-1/2}Z^{k}e\|\leq\xi\|(X^{k}Z^{k})^{-1/2}\|\|z^{k}\|_{1}\end{split}$

and, similarly,
$\|{D^{k}}(z^{0}-z^{*})\|\leq\xi\|(X^{k}Z^{k})^{-1/2}\|\|x^{k}\|_{1}$. We
recall that $\hat{\nu}_{k}=(1-(1-\bar{\alpha}_{k})(1-\bar{\alpha}))\nu_{k}$
and apply all these inequalities together with (58) to obtain

$\begin{split}2\hat{\nu}_{k}\|(D^{k})^{-1}(x^{0}-x^{*})\|+2\hat{\nu}_{k}\|{D^{k}}(z^{0}-z^{*})\|&\leq
2\xi(1-(1-\bar{\alpha}_{k})(1-\bar{\alpha}))\|(X^{k}Z^{k})^{-1/2}\|\nu_{k}\|(x^{k},z^{k})\|_{1}\\\
&\leq
2\xi(1-(1-\bar{\alpha}_{k})(1-\bar{\alpha}))(\gamma\mu_{k})^{-1/2}\frac{4\beta}{\xi}n\mu_{k}\\\
&=(1-(1-\bar{\alpha}_{k})(1-\bar{\alpha}))\frac{8\beta}{\gamma^{1/2}}n\mu_{k}^{1/2},\end{split}$

which provides bounds for the last two terms in (73). Therefore, using Lemma
12 and the above inequality we write

$\begin{split}\|{D^{k}}^{-1}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})\|&\leq\left[\frac{(\sigma_{max}+\gamma^{-1})(\bar{\alpha}_{k}+\bar{\alpha})+(\bar{\alpha}_{k}+C_{3})\bar{\alpha}\bar{\alpha}_{k}\omega^{2}}{\gamma^{1/2}}n^{5/2}+\frac{8\beta(1-(1-\bar{\alpha}_{k})(1-\bar{\alpha}))}{\gamma^{1/2}}n\right]\mu_{k}^{1/2}\\\
&\leq\frac{(\sigma_{max}+\gamma^{-1})(\bar{\alpha}_{k}+\bar{\alpha})+(\bar{\alpha}_{k}+C_{3})\bar{\alpha}\bar{\alpha}_{k}\omega^{2}+8\beta(1-(1-\bar{\alpha}_{k})(1-\bar{\alpha}))}{\gamma^{1/2}}n^{5/2}\mu_{k}^{1/2}\\\
&\leq\left[(\sigma_{max}+\gamma^{-1}+8\beta)(\bar{\alpha}_{k}+\bar{\alpha})+(\bar{\alpha}_{k}+C_{3})\omega^{2}\bar{\alpha}_{k}\bar{\alpha}\right]\gamma^{-1/2}n^{5/2}\mu_{k}^{1/2}\end{split}$

and the lemma is proved. ∎

If we restrict the choices of $\bar{\alpha}_{k}$ and $\bar{\alpha}$, then the
bounds obtained in Lemma 13 can be significantly simplified as shown in the
corollary below.

######  Corollary 2.

If
$\bar{\alpha}_{k}\leq(\sigma_{max}+\gamma^{-1}+8\beta)((1+C_{3})\omega^{2})^{-1}$
and $\bar{\alpha}\leq C_{3}^{-1}\bar{\alpha}_{k}$, then there exists a
constant $C_{6}$, independent of $n$, such that

$\|(D^{k})^{-1}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})\|\leq
C_{6}\bar{\alpha}_{k}n^{5/2}\mu_{k}^{1/2}\quad\text{and}\quad\|D^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\|\leq
C_{6}\bar{\alpha}_{k}n^{5/2}\mu_{k}^{1/2}.$

###### Proof.

Using the bounds on $\bar{\alpha}$ and $\bar{\alpha}_{k}$ assumed in the lemma
we obtain
$(\bar{\alpha}_{k}+C_{3})\omega^{2}\bar{\alpha}_{k}\leq(\sigma_{max}+\gamma^{-1}+8\beta)$,
hence, by $\bar{\alpha}\leq C_{3}^{-1}\bar{\alpha}_{k}$,

$\begin{split}(\sigma_{max}+\gamma^{-1}+8\beta)(\bar{\alpha}_{k}+\bar{\alpha})+(\bar{\alpha}_{k}+C_{3})\omega^{2}\bar{\alpha}_{k}\bar{\alpha}&\leq(\sigma_{max}+\gamma^{-1}+8\beta)(\bar{\alpha}_{k}+2\bar{\alpha})\\\
&\leq(\sigma_{max}+\gamma^{-1}+8\beta)(1+2C_{3}^{-1})\bar{\alpha}_{k},\end{split}$

and the conclusion follows by defining
$C_{6}=(\sigma_{max}+\gamma^{-1}+8\beta)(1+2C_{3}^{-1})\gamma^{-1/2}$. ∎

We are now ready to prove the polynomial worst-case iteration complexity of
Algorithm 1 in the infeasible case. Lemma 10 dealt with the Newton step of the
method. Theorems 3 and 4 provide the results for the quasi-Newton step.

######  Theorem 3.

Suppose that $k+1$ is a quasi-Newton step of Algorithm 1 and all the
hypotheses of this section hold. If the following condition holds

$\displaystyle\alpha_{\mathrm{dec}}+\sigma_{max}$ $\displaystyle\leq
1-\sigma_{min}$ (74)

then, there exists a constant $C_{5}$, independent of $n$, such that, if

$\bar{\alpha}_{k}\in\left(0,\min\left\\{1,\left((1+C_{3})\omega^{2}\right)^{-1},\frac{C_{5}}{n^{5}}\right\\}\right]\quad\text{and}\quad\bar{\alpha}\in\left[(C_{3}C_{5})^{-1}n^{5}\bar{\alpha}_{k}^{2},\
C_{3}^{-1}\bar{\alpha}_{k}\right],$ (75)

then the iterate after the quasi-Newton step satisfies

$\displaystyle(x^{k+1}+\bar{\alpha}\Delta{x}^{k+1})^{T}(z^{k+1}+\bar{\alpha}\Delta{z}^{k+1})$
$\displaystyle\geq(1-\bar{\alpha}){x^{k+1}}^{T}z^{k+1}$ (76)
$\displaystyle(x^{k+1}+\bar{\alpha}\Delta{x}^{k+1})^{T}(z^{k+1}+\bar{\alpha}\Delta{z}^{k+1})$
$\displaystyle\leq(1-\alpha_{\mathrm{dec}}\bar{\alpha}){x^{k+1}}^{T}z^{k+1}$
(77)
$\displaystyle[x^{k}+\bar{\alpha}_{k}\Delta{x}^{k}]_{i}[z^{k}+\bar{\alpha}_{k}\Delta{z}^{k}]_{i}$
$\displaystyle\geq\gamma\mu(\bar{\alpha})$ (78)
$\displaystyle[x^{k}+\bar{\alpha}_{k}\Delta{x}^{k}]_{i}[z^{k}+\bar{\alpha}_{k}\Delta{z}^{k}]_{i}$
$\displaystyle\leq\frac{1}{\gamma}\mu(\bar{\alpha}).$ (79)

###### Proof.

By Lemma 11 we know that $C_{3}\geq 1$. Hence, the given intervals for
$\bar{\alpha}$ and $\bar{\alpha}_{k}$ are well defined. We begin the proof
with inequality (76). Using (60), we get

$\bar{\alpha}_{k}^{2}{\Delta{x}^{k}}^{T}\Delta{z}^{k}\leq\bar{\alpha}_{k}^{2}\|{D^{k}}^{-1}\Delta{x}^{k}\|\|D^{k}\Delta{z}^{k}\|\leq\bar{\alpha}_{k}^{2}\omega^{2}n^{2}\mu_{k}.$
(80)

By Corollary 2, we obtain

$\begin{split}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})^{T}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})&\leq\|(D^{k})^{-1}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})\|\|D^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\|\\\
&\leq C_{6}^{2}n^{5}\mu_{k}\bar{\alpha}_{k}^{2}.\end{split}$ (81)

Finally, by using inequality (61) from Lemma 10, we get

$\bar{\alpha}\sigma_{k+1}{x^{k+1}}^{T}z^{k+1}\geq\bar{\alpha}(1-\bar{\alpha}_{k})\sigma_{k+1}{x^{k}}^{T}z^{k}\geq\sigma_{min}\bar{\alpha}(1-\bar{\alpha}_{k})n\mu_{k}.$
(82)

Starting from equation (13), using (80)–(82), and then applying the bounds for
$|\gamma_{1}|$ from Lemma 11 together with the bound $\bar{\alpha}\leq
C_{3}^{-1}\bar{\alpha}_{k}$ (assumed in (75)) to deliver
$1+\bar{\alpha}|\gamma_{1}|\leq
1+C_{3}^{-1}\bar{\alpha}_{k}C_{3}\frac{\sqrt{n}}{\bar{\alpha}_{k}}=1+\sqrt{n}$,
we get

$\begin{split}(x^{k+1}&+\bar{\alpha}\Delta{x}^{k+1})^{T}(z^{k+1}+\bar{\alpha}\Delta{z}^{k+1})-(1-\bar{\alpha}){x^{k+1}}^{T}z^{k+1}\geq\\\
&\geq\sigma_{min}\bar{\alpha}(1-\bar{\alpha}_{k})n\mu_{k}-C_{6}^{2}n^{5}\mu_{k}\bar{\alpha}_{k}^{2}-(1+\gamma_{1}\bar{\alpha})\bar{\alpha}_{k}^{2}{\Delta{x}^{k}}^{T}\Delta{z}^{k}\\\
&\geq\sigma_{min}\bar{\alpha}(1-\bar{\alpha}_{k})n\mu_{k}-(1+\bar{\alpha}|\gamma_{1}|)\bar{\alpha}_{k}^{2}\lvert{\Delta{x}^{k}}^{T}\Delta{z}^{k}\rvert-
C_{6}^{2}n^{5}\mu_{k}\bar{\alpha}_{k}^{2}\\\
&\geq\left(\sigma_{min}\bar{\alpha}-\sigma_{min}\bar{\alpha}\bar{\alpha}_{k}-(1+n^{1/2})\bar{\alpha}_{k}^{2}\omega^{2}n-C_{6}^{2}n^{4}\bar{\alpha}_{k}^{2}\right)n\mu_{k}\\\
&\geq\left[\sigma_{min}\bar{\alpha}-\left(C_{3}^{-1}\sigma_{min}+2\omega^{2}+C_{6}^{2}\right)\bar{\alpha}_{k}^{2}n^{4}\right]n\mu_{k}.\end{split}$

By defining

$\kappa=2\omega^{2}+C_{6}^{2}\quad\text{and}\quad
C_{4}=C_{3}^{-1}\sigma_{min}\left(C_{3}^{-1}\sigma_{min}+\kappa\right)^{-1},$

the right-hand side of the previous inequality is non-negative if
$\bar{\alpha}\geq(C_{4}C_{3})^{-1}n^{4}\bar{\alpha}_{k}^{2}$ and
$\bar{\alpha}_{k}\leq C_{4}/n^{4}$. The lower bound for $\bar{\alpha}$ is
necessary to avoid too small step in the quasi-Newton direction. It is
obtained by writing $\bar{\alpha}$ as a function of $\bar{\alpha}_{k}$, in
order to guarantee its non-negativity. The upper bound for $\bar{\alpha}_{k}$
is obtained by requesting that $\bar{\alpha}_{k}$ has to be chosen such that
$(C_{4}C_{3})^{-1}n^{4}\bar{\alpha}_{k}^{2}\leq C_{3}^{-1}\bar{\alpha}_{k}$
holds.

For inequality (77), we start by subtracting
$(1-\alpha_{\mathrm{dec}}\bar{\alpha}){x^{k+1}}^{T}z^{k+1}$ from both sides of
equation (13)

$\begin{split}(x^{k+1}&+\bar{\alpha}\Delta{x}^{k+1})^{T}(z^{k+1}+\bar{\alpha}\Delta{z}^{k+1})-(1-\alpha_{\mathrm{dec}}\bar{\alpha}){x^{k+1}}^{T}z^{k+1}=\\\
&=-(1-\alpha_{\mathrm{dec}}-\sigma_{k+1})\bar{\alpha}{x^{k+1}}^{T}z^{k+1}+(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})^{T}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})-(1+\bar{\alpha}\gamma_{1})\bar{\alpha}_{k}^{2}{\Delta{x}^{k}}^{T}\Delta{z}^{k}.\end{split}$

We observe that the first term is negative by the assumption (74) of the
Theorem, since $\sigma_{k+1}\leq\sigma_{max}$. Next, from the left inequality
in (61), we have $(1-\bar{\alpha}_{k})n\mu_{k}\leq n\mu_{k+1}$ and then by
using the condition $\alpha_{\mathrm{dec}}+\sigma_{max}\leq 1-\sigma_{min}$,
(80) and (81), we conclude that

$\begin{split}(x^{k+1}&+\bar{\alpha}\Delta{x}^{k+1})^{T}(z^{k+1}+\bar{\alpha}\Delta{z}^{k+1})-(1-\alpha_{\mathrm{dec}}\bar{\alpha}){x^{k+1}}^{T}z^{k+1}\leq\\\
&\leq-\sigma_{min}\bar{\alpha}(1-\bar{\alpha}_{k})n\mu_{k}+(1+\bar{\alpha}|\gamma_{1}|)\bar{\alpha}_{k}^{2}|{\Delta{x}^{k}}^{T}\Delta{z}^{k}|+|(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})^{T}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})|\\\
&\leq-\sigma_{min}\bar{\alpha}(1-\bar{\alpha}_{k})n\mu_{k}+(1+n^{1/2})\bar{\alpha}_{k}^{2}\omega^{2}n^{2}\mu_{k}+C_{6}^{2}\bar{\alpha}_{k}^{2}n^{5}\mu_{k}\\\
&\leq\left[-\sigma_{min}\bar{\alpha}+\left(\sigma_{min}C_{3}^{-1}+\kappa\right)\bar{\alpha}_{k}^{2}n^{4}\right]n\mu_{k},\end{split}$

where in the last inequality we used the bound $\bar{\alpha}\leq
C_{3}^{-1}\bar{\alpha}_{k}$ to deliver
$\sigma_{min}\bar{\alpha}\bar{\alpha}_{k}n\mu_{k}\leq\sigma_{min}C_{3}^{-1}\bar{\alpha}_{k}^{2}n\mu_{k}$.
The right-hand side of the previous inequality will be non-positive if, as
before, $\bar{\alpha}\geq(C_{4}C_{3})^{-1}n^{4}\bar{\alpha}_{k}^{2}$ and
$\bar{\alpha}_{k}\leq C_{4}/n^{4}$.

To prove inequalities (78) and (79), we first look at (14) which is a
component-wise version of (12). We also need to derive component-wise versions
of (81) and (80). For (81) we have

$\begin{split}[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}]_{i}[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}]_{i}&\leq\lvert[(D^{k})^{-1}]_{ii}[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}]_{i}\rvert\
\lvert[D^{k}]_{ii}[\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1}]_{i}\rvert\\\
&\leq\|(D^{k})^{-1}(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})\|\|D^{k}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\|\\\
&\leq C_{6}^{2}n^{5}\mu_{k}\bar{\alpha}_{k}^{2},\end{split}$ (83)

and, by a similar approach, equation (80), Lemma 11 and the assumption of the
theorem $\bar{\alpha}\leq C_{3}^{-1}\bar{\alpha}_{k}$ we get

$\begin{split}(1+\bar{\alpha}\gamma_{1})\bar{\alpha}_{k}^{2}[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}&\leq(1+\bar{\alpha}\lvert\gamma_{1}\rvert)\bar{\alpha}_{k}^{2}\lvert[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}\rvert\\\
&\leq(1+n^{1/2})\bar{\alpha}_{k}^{2}\|(D^{k})^{-1}\Delta{X}^{k}\|\|D^{k}\Delta{Z}^{k}\|\\\
&\leq 2\bar{\alpha}_{k}^{2}\omega^{2}n^{5/2}\mu_{k}.\end{split}$ (84)

Now, taking (14) and applying (62) and (83)–(84) we get

$\begin{split}[x^{k+1}+&\bar{\alpha}\Delta{x}^{k+1}]_{i}[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}]_{i}\geq\\\
&\geq(1-\bar{\alpha})\gamma\mu_{k+1}-\lvert[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1}]_{i}[\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{z}^{k+1}]_{i}\rvert-(1+\bar{\alpha}\lvert\gamma_{1}\rvert)\bar{\alpha}_{k}^{2}\lvert[\Delta{x}^{k}]_{i}[\Delta{z}^{k}]_{i}\rvert+\bar{\alpha}\sigma_{k+1}\mu_{k+1}\\\
&\geq(1-\bar{\alpha})\gamma\mu_{k+1}+\bar{\alpha}\sigma_{k+1}\mu_{k+1}-C_{6}^{2}n^{5}\mu_{k}\bar{\alpha}_{k}^{2}-2\bar{\alpha}_{k}^{2}\omega^{2}n^{5/2}\mu_{k}\\\
&\geq(1-\bar{\alpha})\gamma\mu_{k+1}+\bar{\alpha}\sigma_{k+1}\mu_{k+1}-\kappa
n^{5}\bar{\alpha}_{k}^{2}\mu_{k}\end{split}$

and from (13), using (80)–(81) we get

$\begin{split}\gamma\mu(\bar{\alpha})&=\gamma\frac{(x^{k+1}+\bar{\alpha}\Delta{x}^{k+1})^{T}(z^{k+1}+\bar{\alpha}\Delta{z}^{k+1})}{n}\leq\\\
&\leq\gamma\left[(1-\bar{\alpha}(1-\sigma_{k+1}))\mu_{k+1}+\frac{1+\bar{\alpha}\lvert\gamma_{1}\rvert}{n}\bar{\alpha}_{k}^{2}\lvert{\Delta{x}^{k}}^{T}\Delta{z}^{k}\rvert+\frac{\lvert(\bar{\alpha}_{k}\Delta{x}^{k}+\bar{\alpha}\Delta{x}^{k+1})^{T}(\bar{\alpha}_{k}\Delta{z}^{k}+\bar{\alpha}\Delta{z}^{k+1})\rvert}{n}\right]\\\
&\leq(1-\bar{\alpha})\gamma\mu_{k+1}+\bar{\alpha}\sigma_{k+1}\gamma\mu_{k+1}+(1+n^{1/2})\gamma\omega^{2}n\bar{\alpha}_{k}^{2}\mu_{k}+C_{6}^{2}\gamma
n^{4}\bar{\alpha}_{k}^{2}\mu_{k}\\\
&\leq(1-\bar{\alpha})\gamma\mu_{k+1}+\bar{\alpha}\sigma_{k+1}\gamma\mu_{k+1}+\kappa\gamma
n^{4}\bar{\alpha}_{k}^{2}\mu_{k}.\end{split}$

By combining the above two inequalities, then using (82) and (61) and
$\bar{\alpha}\leq C_{3}^{-1}\bar{\alpha}_{k}$, we obtain

$\begin{split}[x^{k+1}+\bar{\alpha}\Delta{x}^{k+1}]_{i}[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}]_{i}-\gamma\mu(\bar{\alpha})&\geq(1-\gamma)\bar{\alpha}\sigma_{k+1}\mu_{k+1}-(1+\gamma)\kappa
n^{5}\bar{\alpha}_{k}^{2}\mu_{k}\\\
&\geq(1-\gamma)\sigma_{min}\bar{\alpha}(1-\bar{\alpha}_{k})\mu_{k}-(1+\gamma)\kappa
n^{5}\bar{\alpha}_{k}^{2}\mu_{k}\\\
&\geq\left[\sigma_{min}\bar{\alpha}-\left(C_{3}^{-1}\sigma_{min}+\left(\frac{1+\gamma}{1-\gamma}\right)\kappa\right)n^{5}\bar{\alpha}_{k}^{2}\right](1-\gamma)\mu_{k}.\end{split}$

The right-hand side of this inequality is non-negative, and hence (78) holds,
if $\bar{\alpha}\geq(C_{3}C_{5})^{-1}n^{5}\bar{\alpha}_{k}^{2}$ and
$\bar{\alpha}_{k}\leq C_{5}/n^{5}$, with

$C_{5}=C_{3}^{-1}\sigma_{min}\left(C_{3}^{-1}\sigma_{min}+\left(\frac{1+\gamma}{1-\gamma}\right)\kappa\right)^{-1}.$

Finally, in order to show (79), we use the same ideas to obtain the following
two inequalities

$[x^{k+1}+\bar{\alpha}\Delta{x}^{k+1}]_{i}[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}]_{i}\leq\frac{1-\bar{\alpha}}{\gamma}\mu_{k+1}+\bar{\alpha}\sigma_{k+1}\mu_{k+1}+\kappa
n^{5}\bar{\alpha}_{k}^{2}\mu_{k}$

and

$\frac{1}{\gamma}\mu(\bar{\alpha})\geq\frac{1-\bar{\alpha}}{\gamma}\mu_{k+1}+\frac{\bar{\alpha}\sigma_{k+1}}{\gamma}\mu_{k+1}-\frac{\kappa
n^{4}\bar{\alpha}_{k}^{2}}{\gamma}\mu_{k}.$

By combining these two inequalities and using (61) and $\bar{\alpha}\leq
C_{3}^{-1}\bar{\alpha}_{k}$ once more, we have that

$\begin{split}[x^{k+1}+\bar{\alpha}\Delta{x}^{k+1}]_{i}[z^{k+1}+\bar{\alpha}\Delta{z}^{k+1}]_{i}-\frac{1}{\gamma}\mu(\bar{\alpha})&\leq\left(1-\frac{1}{\gamma}\right)\sigma_{k+1}\bar{\alpha}\mu_{k+1}+\left(1+\frac{1}{\gamma}\right)\kappa
n^{5}\bar{\alpha}_{k}^{2}\mu_{k}\\\
&=-\left(\frac{1-\gamma}{\gamma}\right)\sigma_{k+1}\bar{\alpha}\mu_{k+1}+\left(\frac{1+\gamma}{\gamma}\right)\kappa
n^{5}\bar{\alpha}_{k}^{2}\mu_{k}\\\
&\leq-\left(\frac{1-\gamma}{\gamma}\right)\sigma_{min}\bar{\alpha}(1-\bar{\alpha}_{k})\mu_{k}+\left(\frac{1+\gamma}{\gamma}\right)\kappa
n^{5}\bar{\alpha}_{k}^{2}\mu_{k}\\\
&\leq\left[-\sigma_{min}\bar{\alpha}+\left(C_{3}^{-1}\sigma_{min}+\left(\frac{1+\gamma}{1-\gamma}\right)\kappa\right)n^{5}\bar{\alpha}_{k}^{2}\right]\left(\frac{1-\gamma}{\gamma}\right)\mu_{k}.\end{split}$

Again, the right-hand side of this inequality is non-positive if
$\bar{\alpha}\geq(C_{3}C_{5})^{-1}n^{5}\bar{\alpha}_{k}^{2}$ and
$\bar{\alpha}_{k}\leq C_{5}/n^{5}$, with $C_{5}$ defined before. Since
$C_{5}\leq C_{4}$, we observe that
$(C_{3}C_{5})^{-1}n^{5}\geq(C_{3}C_{4})^{-1}n^{5}$, and this explains the
lower bound on $\bar{\alpha}$. We also observe that in (75),
$\bar{\alpha}_{k}$ is bounded from above by $C_{5}/n^{5}$ hence
$(C_{3}C_{5})^{-1}n^{5}\bar{\alpha}_{k}^{2}\leq C_{3}^{-1}\bar{\alpha}_{k}$,
which guarantees that the interval for $\bar{\alpha}$ is not empty. Similar
observations can be made to justify the upper bound of $\bar{\alpha}_{k}$ in
(75) and this concludes the proof. ∎

To further show that $(x^{k+2},{\lambda}^{k+2},z^{k+2})$ belongs to the
$\mathcal{N}_{s}(\gamma,\beta)$ neighborhood, and therefore satisfies (56), we
need to ensure that $\gamma$ is not too close to 0.

######  Theorem 4.

Let the hypotheses of Theorem 3 hold. If, in addition, we request that

$\gamma\geq
2\left(-8\beta+\sqrt{(8\beta+2)^{2}+\frac{4}{3\sigma_{min}}}\right)^{-1}$ (85)

then $(x^{k+2},{\lambda}^{k+2},z^{k+2})$ satisfies (56).

###### Proof.

Using inequality (76) in Theorem 3

$\frac{\|(r^{k+2}_{b},r^{k+2}_{c})\|}{\mu_{k+2}}\leq\frac{(1-\bar{\alpha})\|(r^{k+1}_{b},r^{k+1}_{c})\|}{(1-\bar{\alpha})\mu_{k+1}}\leq\frac{\|(r^{0}_{b},r^{0}_{c})\|}{\mu_{0}}\beta$

and, by (78) and (79)

$0<\gamma\mu_{k+2}\leq x^{k+2}_{i}z^{k+2}_{i}\leq\frac{1}{\gamma}\mu_{k+2}.$

To show that $x^{k+2}>0$ and $z^{k+2}>0$, we suppose by contradiction that
$x^{k+2}_{i}\leq 0$ or $z^{k+2}_{i}\leq 0$ occurs for some $i$ and follow the
same arguments as those used in Theorems 1 and 2 to conclude, using inequality
(83), that $\gamma<C_{6}^{2}n^{5}\bar{\alpha}_{k}^{2}$ should hold.

By using the fact that $C_{3}\geq 1$, defined in Lemma 11, and $\kappa\geq 1$
and $C_{6}\geq 1$, defined in Theorem 3, and basic manipulation, we conclude
that $C_{6}\leq 3(1+\gamma^{-1}+8\beta)\gamma^{-1/2}$ and
$C_{5}\leq\sigma_{min}(1-\gamma)$, where $C_{5}$ was also defined in Theorem
3. Then, using (75) for $\bar{\alpha}_{k}$ we obtain

$\gamma<C_{6}^{2}n^{5}\bar{\alpha}_{k}^{2}\leq\frac{(C_{5}C_{6})^{2}}{n^{5}}\leq\frac{9(1+\gamma^{-1}+8\beta)^{2}(1-\gamma)^{2}}{\gamma}\sigma_{min}^{2}$
(86)

which implies that
$\gamma<2\left(-8\beta+\sqrt{(8\beta+2)^{2}+\frac{4}{3\sigma_{min}}}\right)^{-1}$
and contradicts (85). The above inequality has been obtained by rearranging
(86) namely, dropping the squares and solving the resulting (quadratic)
inequality with an unknown $1/\gamma$. Therefore, we conclude that
$(x^{k+2},{\lambda}^{k+2},z^{k+2})\in\mathcal{N}_{s}(\gamma,\beta)$. Earlier
proved inequality (77) guarantees that iteration $k+1$ satisfies (56).

∎

For sufficiently large $n$, we clearly have

$\min\left\\{1,\left((1+C_{3})\omega^{2}\right)^{-1},\frac{C_{5}}{n^{5}}\right\\}=\frac{C_{5}}{n^{5}}<\frac{\bar{\bar{\delta}}}{n^{2}},$

where $\bar{\bar{\delta}}$ comes from Lemma 10 and this guarantees that the
hypotheses of this section hold. By (75) we have that both $\bar{\alpha}_{k}$
and $\bar{\alpha}$ are greater than or equal to
$\frac{C_{3}^{-1}C_{5}}{n^{5}}$ hence

$\mu_{k+1}\leq(1-\alpha_{\mathrm{dec}}\bar{\alpha}_{k})\mu_{k}\leq\left(1-\frac{\alpha_{\mathrm{dec}}C_{3}^{-1}C_{5}}{n^{5}}\right)\mu_{k},$

for all $k=0,1,\dots$, which yields $O(n^{5})$ worst-case iteration complexity
for the infeasible case of Algorithm 1.

Unlike in the feasible case, because of the close relation of the symmetric
neighborhood and the $\mathcal{N}_{-\infty}(\gamma,\beta)$ neighborhood, we
expect that a similar complexity result to that of Theorem 3 should hold for
the algorithm which operates in $\mathcal{N}_{-\infty}(\gamma,\beta)$.
However, to save space we do not derive it here.

##  5 Conclusions and final observations

This work provided theoretical tools to analyze the worst-case iteration
complexity of quasi-Newton primal-dual interior point algorithms. A simplified
algorithm was considered, which consisted of alternating Newton and quasi-
Newton steps. The quasi-Newton approach was based on the Broyden “bad” low-
rank update of the inverse of the unreduced system. Feasible and infeasible
algorithms and well established neighborhoods of the central path have been
considered.

The results showed that in all cases, the degree of the polynomial in the
worst-case result has increased. This behavior has already been observed by
[10], where the number of overall iterations increased, but the number of
factorizations of the true unreduced system actually decreased.

Complexity results might also be obtained in the feasible case for convex
quadratic programming problems and the $\mathcal{N}_{2}(\theta)$ neighborhood,
following [8], for example. However, since Lemma 3 does not hold anymore and
thus $\gamma_{1}$ is not eliminated from $\mu(\bar{\alpha})$, a further study
needs to be carried out.

Another interesting and complicated question is the case $\ell>1$, where we
allow more than one quasi-Newton step after a Newton step. The authors in [10]
observed a trade-off between the number of consecutive quasi-Newton iterations
and the overall speed of convergence of the algorithm. Numerical results
showed that $\ell=5$ is a reasonable choice. We expect that similar worst-case
complexity bounds should be obtained for the case $\ell>1$, with possibly
higher degrees of polynomials, but this still remains an open question.

The worst-case complexity results obtained when the $\mathcal{N}_{s}$
neighborhood was considered in both feasible and infeasible cases seem rather
pessimistic. The high polynomial degrees originate from Lemma 9 for the
feasible and from Lemma 13 for the infeasible cases. Finding new ways of
reducing the degrees of such expressions would definitely result in better
complexity results, since all the other terms are at most of order $n$.

## References

  * [1] S. Bellavia, V. De Simone, D. di Serafino, and B. Morini, Updating Constraint Preconditioners for KKT Systems in Quadratic Programming Via Low-Rank Corrections, SIAM J. on Optimization, 25 (2015), pp. 1787–1808.
  * [2] L. Bergamaschi, V. De Simone, D. di Serafino, and Á. Martínez, BFGS-like updates of constraint preconditioners for sequences of KKT linear systems in quadratic programming, Numerical Linear Algebra with Applications, 25 (2018), p. e2144.
  * [3] M. Colombo and J. Gondzio, Further development of multiple centrality correctors for interior point methods, Computational Optimization Applications, 41 (2008), pp. 277–305.
  * [4] M. D’Apuzzo, V. De Simone, and D. di Serafino, On mutual impact of numerical linear algebra and large-scale optimization with focus on interior point methods, Computational Optimization Applications, pp. 283–310.
  * [5] J. E. Dennis Jr., A. M. Morshedi, and K. Turner, A variable-metric variant of the Karmarkar algorithm for linear programming, Mathematical Program., pp. 1–20.
  * [6] D. Ek and A. Forsgren, A structured modified Newton approach for solving systems of nonlinear equations arising in interior-point methods for quadratic programming, tech. rep.
  * [7] J. Gondzio, HOPDM (version 2.12) — A fast LP solver based on a primal-dual interior point method, European J. Operational Research, pp. 221–225.
  * [8] , Interior point methods 25 years later, European J. Operational Research, pp. 587–601.
  * [9] J. Gondzio and A. Grothey, Exploiting structure in parallel implementation of interior point methods for optimization, Computational Management Science, pp. 135–160.
  * [10] J. Gondzio and F. N. C. Sobral, Quasi-Newton approaches to interior point methods for quadratic problems, Computational Optimization Applications, pp. 93–120.
  * [11] C. C. Gonzaga, An Algorithm for Solving Linear Programming Problems in $O(n^{3}L)$ Operations, in Progress in Mathematical Programming, N. Megiddo, ed., Springer New York, New York, NY, pp. 1–28.
  * [12] S. Gratton, S. Mercier, N. Tardieu, and X. Vasseur, Limited memory preconditioners for symmetric indefinite problems with application to structural mechanics, Numerical Linear Algebra with Applications, pp. 865–887.
  * [13] S. Gratton, A. Sartenaer, and J. Tshimanga, On A Class of Limited Memory Preconditioners For Large Scale Linear Systems With Multiple Right-Hand Sides, SIAM J. on Optimization, pp. 912–935.
  * [14] C. Greif, E. Moulding, and D. Orban, Bounds on Eigenvalues of Matrices Arising from Interior-Point Methods, SIAM J. on Optimization, pp. 49–83.
  * [15] I. J. Lustig, R. E. Marsten, and D. F. Shanno, Interior Point Methods for Linear Programming: Computational State of the Art, ORSA J. on Computing, pp. 1–14.
  * [16] J. M. Martínez, Practical quasi-Newton methods for solving nonlinear systems, J. Computational Appl. Mathematics, pp. 97–121.
  * [17] R. D. C. Monteiro and I. Adler, Interior path following primal-dual algorithms. part I: Linear programming, Mathematical Program., pp. 27–41.
  * [18] B. Morini, V. Simoncini, and M. Tani, A comparison of reduced and unreduced KKT systems arising from interior point methods, Computational Optimization Applications, pp. 1–27.
  * [19] Y. Nesterov and A. Nemirovskii, Interior Point Polynomial Methods in Convex Programming, Society for Industrial and Applied Mathematics, Philadelphia, 1994.
  * [20] S. H. Schmieta and F. Alizadeh, Extension of primal-dual interior point algorithms to symmetric cones, Mathematical Program., 96 (2003), pp. 409–438.
  * [21] S. J. Wright, Primal-dual Interior Point Methods, Society for Industrial and Applied Mathematics, Philadelphia, 1997.