# Complexity analysis of primal-dual interior-point methods for linear optimization based on a new efficient Bi-parameterized kernel function with a trigonometric barrier term

Bouafia Mousaab, Adnan Yassine

► To cite this version:

Bouafia Mousaab, Adnan Yassine. Complexity analysis of primal-dual interior-point methods for linear optimization based on a new efficient Bi-parameterized kernel function with a trigonometric barrier term. RAIRO - Operations Research, 2022, 56 (2), pp.731-750. 10.1051/ro/2022032. hal-03652550

HAL Id: hal-03652550

https://normandie-univ.hal.science/hal-03652550

Submitted on 31 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Complexity analysis of primal-dual interior-point methods for linear optimization based on a new efficient Bi-parameterized kernel function with a trigonometric barrier term

Bouafia Mousaab, Adnan Yassine

► To cite this version:

Bouafia Mousaab, Adnan Yassine. Complexity analysis of primal-dual interior-point methods for linear optimization based on a new efficient Bi-parameterized kernel function with a trigonometric barrier term. RAIRO - Operations Research, 2022, 56 (2), pp.731-750. 10.1051/ro/2022032. hal-03652550

HAL Id: hal-03652550

https://normandie-univ.hal.science/hal-03652550v1

Submitted on 31 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# COMPLEXITY ANALYSIS OF PRIMAL-DUAL INTERIOR-POINT METHODS FOR LINEAR OPTIMIZATION BASED ON A NEW EFFICIENT BI-PARAMETERIZED KERNEL FUNCTION WITH A TRIGONOMETRIC BARRIER TERM

BOUAFIA MOUSAAB<fnref n="1" />,* AND YASSINE ADNAN<fnref n="2" />

**Abstract.** In this paper we are generalizing the efficient kernel function with trigonometric barrier term given by (M. Bouafia, D. Benterki and A. Yassine, *J. Optim. Theory Appl.* **170** (2016) 528-545). Using an elegant and simple analysis and under some easy to check conditions, we explore the best complexity result for the large update primal-dual interior point methods for linear optimization. This complexity estimate improves results obtained in (X. Li and M. Zhang, *Oper. Res. Lett.* **43** (2015) 471-475; M.R. Peyghami and S.F. Hafshejani, *Numer. Algo.* **67** (2014) 33-48; M. Bouafia, D. Benterki and A. Yassine, *J. Optim. Theory Appl.* **170** (2016) 528-545). Our comparative numerical experiments on some test problems consolidate and confirm our theoretical results according to which the new kernel function has promising applications compared to the kernel function given by (M. Bouafia and A. Yassine, *Optim. Eng.* **21** (2020) 651-672). Moreover, the comparative numerical study that we have established favors our new kernel function better than other best trigonometric kernel functions (M. Bouafia, D. Benterki and A. Yassine, *J. Optim. Theory Appl.* **170** (2016) 528-545; M. Bouafia and A. Yassine, *Optim. Eng.* **21** (2020) 651-672).

**Mathematics Subject Classification.** 90C05, 90C31, 90C51.

Received September 20, 2021. Accepted February 27, 2022.

## 1. INTRODUCTION

Polynomial time Interior Point Methods **IPMs** for solving linear programming were first proposed by Karmarkar [7]. This method, and its variants that were developed subsequently, are now called interior-point methods **IPMs**. For a survey, we refer to recent books on the subject, as Bai *et al.* [1], Peng *et al.* [10], Roos *et al.* [13] and Ye[15]. In order to describe the idea of this paper, we need to recall some ideas underlying new primal-dual **IPMs**. The purpose of this work is to present primal-dual interior-point methods **IPMs** based on generalized trigonometric barrier function for solving the standard linear optimization problem (**LO**)

$$ (P) \min\{c^t x : Ax = b, x \ge 0\}, $$

<footnote>*Keywords.* Linear optimization, Kernel function, Interior point methods, Complexity bound.</footnote>

<footnote n="1">¹ University of 8 May 1945 Guelma. BP 401 24000 Guelma, Algeria, LMAH, FR-CNRS-3335, ISCN, 76600 Le Havre, France.</footnote>

<footnote n="2">² Normandie University, UNIHAVRE, LMAH, FR-CNRS-3335, ISCN, 76600 Le Havre, France.</footnote>

<footnote>*Corresponding author: mousaab84@yahoo.fr</footnote>
# COMPLEXITY ANALYSIS OF PRIMAL-DUAL INTERIOR-POINT METHODS FOR LINEAR OPTIMIZATION BASED ON A NEW EFFICIENT BI-PARAMETERIZED KERNEL FUNCTION WITH A TRIGONOMETRIC BARRIER TERM

BOUAFIA MOUSAAB<fnref n="1" />,* AND YASSINE ADNAN<fnref n="2" />

**Abstract.** In this paper we are generalizing the efficient kernel function with trigonometric barrier term given by (M. Bouafia, D. Benterki and A. Yassine, *J. Optim. Theory Appl.* **170** (2016) 528–545). Using an elegant and simple analysis and under some easy to check conditions, we explore the best complexity result for the large update primal-dual interior point methods for linear optimization. This complexity estimate improves results obtained in (X. Li and M. Zhang, *Oper. Res. Lett.* **43** (2015) 471–475; M.R. Peyghami and S.F. Hafshejani, *Numer. Algo.* **67** (2014) 33–48; M. Bouafia, D. Benterki and A. Yassine, *J. Optim. Theory Appl.* **170** (2016) 528–545). Our comparative numerical experiments on some test problems consolidate and confirm our theoretical results according to which the new kernel function has promising applications compared to the kernel function given by (M. Bouafia and A. Yassine, *Optim. Eng.* **21** (2020) 651–672). Moreover, the comparative numerical study that we have established favors our new kernel function better than other best trigonometric kernel functions (M. Bouafia, D. Benterki and A. Yassine, *J. Optim. Theory Appl.* **170** (2016) 528–545; M. Bouafia and A. Yassine, *Optim. Eng.* **21** (2020) 651–672).

**Mathematics Subject Classification.** 90C05, 90C31, 90C51.

Received September 20, 2021. Accepted February 27, 2022.

## 1. INTRODUCTION

Polynomial time Interior Point Methods **IPMs** for solving linear programming were first proposed by Karmarkar [7]. This method, and its variants that were developed subsequently, are now called interior-point methods **IPMs**. For a survey, we refer to recent books on the subject, as Bai *et al.* [1], Peng *et al.* [10], Roos *et al.* [13] and Ye[15]. In order to describe the idea of this paper, we need to recall some ideas underlying new primal-dual **IPMs**. The purpose of this work is to present primal-dual interior-point methods **IPMs** based on generalized trigonometric barrier function for solving the standard linear optimization problem (**LO**)

$$ (P) \min\{c^t x : Ax = b, x \ge 0\}, $$

<footnote>*Keywords.* Linear optimization, Kernel function, Interior point methods, Complexity bound.</footnote>

<footnote n="1">¹ University of 8 May 1945 Guelma. BP 401 24000 Guelma, Algeria, LMAH, FR-CNRS-3335, ISCN, 76600 Le Havre, France.</footnote>

<footnote n="2">² Normandie University, UNIHAVRE, LMAH, FR-CNRS-3335, ISCN, 76600 Le Havre, France.</footnote>

<footnote>*Corresponding author: mousaab84@yahoo.fr</footnote>
where $A \in \mathbb{R}^{m \times n}$, $rank(A) = m$, $b \in \mathbb{R}^m$, and $c \in \mathbb{R}^n$, and its dual problem

$$ (D) \max\{b^t y : A^t y + s = c, s \ge 0\}. $$

The kernel functions play an important role in the design and analysis of interior-point methods **IPMs**. They are not only used for determining the search directions but also for measuring the distance between the given iterate and the $\mu$-center for the algorithms. Currently, **IPMs** based on kernel function is one of the most effective methods for solving linear optimization (**LO**) and other convex optimization problems and is a very active research area in mathematical programming.

In 2005, Bai *et al.* [2], proposed a new kernel function with an exponential barrier term. The same paper introduced the first new kernel function which have a trigonometric barrier term.

In 2012, El Ghami *et al.* [5], evaluated the first new kernel function with a trigonometric barrier term given by Bai *et al.* [2]. They obtained $O(n^{3/4} \log n/\epsilon)$ iterations bound for large-update methods. Since then, research has focused on developing a new kernel function with a trigonometric barrier term to improve the complexity bound obtained by El Ghami *et al.* [5].

In 2014, Peyghami *et al.* [11], proposed a new kernel function with an exponential trigonometric term for **LO**. They obtained $O(\sqrt{n}(\log n)^2 \log n/\epsilon)$ iterations bound for large-update methods.

In 2015, Li and Zhang [8], presented another trigonometric barrier function, which has $O(n^{2/3} \log n/\epsilon)$ complexity for large-update methods. These results improve the complexity bound obtained by El Ghami *et al.* [5].

In 2016, Bouafia *et al.* [4], we proposed the first with trigonometric barrier terms for interior point methods in **LO**. We generalized and improved the complexity bound based on a new kernel function with trigonometric barrier terms obtained in [5, 8, 11, 12]. We obtained the best known complexity results for large and small-update methods.

In 2018, Fathi-Hafshejani *et al.* [6], presented a large-update primal-dual interior-point algorithm for linear optimization problems based on a new kernel function with a trigonometric growth term. They obtained the best known complexity results for large which has $O(\sqrt{n \log n \log n/\epsilon})$ complexity for large-update method. This result improves the complexity bound obtained in [5, 8, 11, 12].

Recently in 2020, Bouafia and Yassine [3], investigated a new efficient twice parametric kernel function that combines the parametric classic function with the parametric kernel function trigonometric barrier term given by Bouafia *et al.* [4] to develop primal-dual interior-point algorithms for solving linear programming problems. We obtained the best known complexity results for large and small-update methods.

In this paper, for $p, q \in \mathbb{R}$, we introduce the function

$$ \psi_M(t) = \frac{t^2 - 1}{2} + m(p, q) \left[ \cot^p \left( \frac{\pi}{q+2} \right) \tan^p u(t) - 1 \right], \quad p \ge 2, q > 0 \text{ and } t > 0. $$

where

$$ u(t) = \frac{\pi}{qt + 2}, \quad q > 0. $$

$$ m(p, q) = \frac{(q+2)^2}{\pi pq \left( \cot\left(\frac{\pi}{q+2}\right) + \tan\left(-\frac{\pi}{q+2}\right) \right)}, \quad p \ge 2, q > 0. $$

This function $\psi_M(t)$ is a parameterized version which generalize the kernel function given by Bouafia *et al.* [4]. The new kernel function has twice trigonometric terms and twice parameter. Using some mild and standard conditions, the worst case iteration complexity bound of the large-update primal dual **IPMs** based on the new proposed kernel function is driven. As usual, the so-called exponential convexity property plays an important role in this regard. Our analysis shows that the worst case iteration complexity of large-update **IPMs** for
where $A \in \mathbb{R}^{m \times n}$, $rank(A) = m$, $b \in \mathbb{R}^m$, and $c \in \mathbb{R}^n$, and its dual problem

$$ (D) \max\{b^t y : A^t y + s = c, s \ge 0\}. $$

The kernel functions play an important role in the design and analysis of interior-point methods **IPMs**. They are not only used for determining the search directions but also for measuring the distance between the given iterate and the $\mu$-center for the algorithms. Currently, **IPMs** based on kernel function is one of the most effective methods for solving linear optimization (**LO**) and other convex optimization problems and is a very active research area in mathematical programming.

In 2005, Bai *et al.* [2], proposed a new kernel function with an exponential barrier term. The same paper introduced the first new kernel function which have a trigonometric barrier term.

In 2012, El Ghami *et al.* [5], evaluated the first new kernel function with a trigonometric barrier term given by Bai *et al.* [2]. They obtained $O(n^{3/4} \log n/\epsilon)$ iterations bound for large-update methods. Since then, research has focused on developing a new kernel function with a trigonometric barrier term to improve the complexity bound obtained by El Ghami *et al.* [5].

In 2014, Peyghami *et al.* [11], proposed a new kernel function with an exponential trigonometric term for **LO**. They obtained $O(\sqrt{n}(\log n)^2 \log n/\epsilon)$ iterations bound for large-update methods.

In 2015, Li and Zhang [8], presented another trigonometric barrier function, which has $O(n^{2/3} \log n/\epsilon)$ complexity for large-update methods. These results improve the complexity bound obtained by El Ghami *et al.* [5].

In 2016, Bouafia *et al.* [4], we proposed the first with trigonometric barrier terms for interior point methods in **LO**. We generalized and improved the complexity bound based on a new kernel function with trigonometric barrier terms obtained in [5, 8, 11, 12]. We obtained the best known complexity results for large and small-update methods.

In 2018, Fathi-Hafshejani *et al.* [6], presented a large-update primal-dual interior-point algorithm for linear optimization problems based on a new kernel function with a trigonometric growth term. They obtained the best known complexity results for large which has $O(\sqrt{n \log n \log n/\epsilon})$ complexity for large-update method. This result improves the complexity bound obtained in [5, 8, 11, 12].

Recently in 2020, Bouafia and Yassine [3], investigated a new efficient twice parametric kernel function that combines the parametric classic function with the parametric kernel function trigonometric barrier term given by Bouafia *et al.* [4] to develop primal-dual interior-point algorithms for solving linear programming problems. We obtained the best known complexity results for large and small-update methods.

In this paper, for $p, q \in \mathbb{R}$, we introduce the function

$$ \psi_M(t) = \frac{t^2 - 1}{2} + m(p, q) \left[ \cot^p \left( \frac{\pi}{q+2} \right) \tan^p u(t) - 1 \right], \quad p \ge 2, q > 0 \text{ and } t > 0. $$

where

$$ u(t) = \frac{\pi}{qt + 2}, \quad q > 0. $$

$$ m(p, q) = \frac{(q+2)^2}{\pi pq \left( \cot \left( \frac{\pi}{q+2} \right) + \tan \left( \frac{\pi}{q+2} \right) \right)}, \quad p \ge 2, q > 0. $$

This function $\psi_M(t)$ is a parameterized version which generalize the kernel function given by Bouafia *et al.* [4]. The new kernel function has twice trigonometric terms and twice parameter. Using some mild and standard conditions, the worst case iteration complexity bound of the large-update primal dual **IPMs** based on the new proposed kernel function is driven. As usual, the so-called exponential convexity property plays an important role in this regard. Our analysis shows that the worst case iteration complexity of large-update **IPMs** for
solving LO problems based on the new kernel function meets the so far best known iteration complexity, i.e., $O(\sqrt{n} \log n \log \frac{n}{c})$.

The paper is organized as follows: In Section 2, we recall some basic concepts of interior point methods and the central path curve for LO. Some interesting and useful properties of the new kernel function are provided in Section 3. Section 4, is devoted to describe the proximity reduction during an inner iteration. The step size is discussed in Section 5. In Section 6, we derive the inner iteration bound and the total iteration bound of the algorithm. In Section 7, we present a comparison of our algorithm presented in [3] with our new results in this paper. Finally, we are finishing the paper with some remarks and a general conclusion showing the added value of our work.

We use the following notations throughout the paper. $\mathbb{R}_+^n$ and $\mathbb{R}_{++}^n$ denote the set of $n$-dimensional nonnegative vectors and positive vectors, respectively. For $x, s \in \mathbb{R}^n$, $x_{\min}$ and $xs$ denote the smallest component of the vector $x$ and the componentwise product of the vector $x$ and $s$, respectively. We denote by $X = \text{diag}(x)$ the $n \times n$ diagonal matrix with the components of the vector $x \in \mathbb{R}^n$ are the diagonal entries, finally $e$ denotes the $n$-dimensional vector of ones. And throughout the paper, $|||\cdot|||$ denotes the 2-norm of a vector.

## 2. PRELIMINARIES

In this section, we briefly describe the idea behind the interior point methods based on kernel functions. We also provide the structure of the generic primal-dual IPMs when the kernel functions are used to induce the proximity measure. Without loss of generality, we assume that (P) and (D) satisfy the interior-point condition IPC, i.e., there exist $(x^0, y^0, s^0)$ such that

$$Ax^0 = b, x^0 > 0, A^t y^0 + s^0 = c, s^0 > 0. \qquad (2.1)$$

Therefore, an optimal solution of (P) and (D) can be found by solving the following system

$$\begin{aligned} Ax &= b, x \ge 0, \\ A^t y + s &= c, s \ge 0, \\ xs &= 0. \end{aligned} \qquad (2.2)$$

The key idea behind primal-dual IPMs for solving LO problems is to replace the third equation in (2.2) by the parameterized nonlinear equation $xs = \mu e$, where $\mu > 0$. Therefore, the system (2.2) can be rewritten as

$$\begin{aligned} Ax &= b, x \ge 0, \\ A^t y + s &= c, s \ge 0, \\ xs &= \mu e. \end{aligned} \qquad (2.3)$$

Note that, this system has a unique solution as $(x(\mu), y(\mu), s(\mu))$, where $x(\mu)$ is called the $\mu$-center of (P) and $(y(\mu), s(\mu))$ the $\mu$-center of (D). The set of $\mu$-centers (with $\mu$ running through all positive real numbers) gives a homotype path, which is called the central path of (P) and (D). Applying Newton's method to the system (2.3), we obtain the following Newton-system

$$\begin{aligned} A\Delta x &= 0, \\ A^t \Delta y + \Delta s &= 0, \\ s\Delta x + x\Delta s &= \mu e - xs. \end{aligned} \qquad (2.4)$$

Note that this system has a unique solution. Now we can derive the new point as

$$x_+ = x + \alpha \Delta x, s_+ = s + \alpha \Delta s, y_+ = y + \alpha \Delta y. \qquad (2.5)$$

where the step size $\alpha$ satisfies $0 < \alpha \le 1$.
solving LO problems based on the new kernel function meets the so far best known iteration complexity, i.e., $O(\sqrt{n} \log n \log \frac{n}{c})$.

The paper is organized as follows: In Section 2, we recall some basic concepts of interior point methods and the central path curve for LO. Some interesting and useful properties of the new kernel function are provided in Section 3. Section 4, is devoted to describe the proximity reduction during an inner iteration. The step size is discussed in Section 5. In Section 6, we derive the inner iteration bound and the total iteration bound of the algorithm. In Section 7, we present a comparison of our algorithm presented in [3] with our new results in this paper. Finally, we are finishing the paper with some remarks and a general conclusion showing the added value of our work.

We use the following notations throughout the paper. $\mathbb{R}_+^n$ and $\mathbb{R}_+^{n+}$ denote the set of $n$-dimensional nonnegative vectors and positive vectors, respectively. For $x, s \in \mathbb{R}^n$, $x_{\min}$ and $xs$ denote the smallest component of the vector $x$ and the componentwise product of the vector $x$ and $s$, respectively. We denote by $X = \text{diag}(x)$ the $n \times n$ diagonal matrix with the components of the vector $x \in \mathbb{R}^n$ are the diagonal entries, finally $e$ denotes the $n$-dimensional vector of ones. And throughout the paper, $|||\cdot|||$ denotes the 2-norm of a vector.

## 2. PRELIMINARIES

In this section, we briefly describe the idea behind the interior point methods based on kernel functions. We also provide the structure of the generic primal-dual IPMs when the kernel functions are used to induce the proximity measure. Without loss of generality, we assume that $(P)$ and $(D)$ satisfy the interior-point condition IPC, i.e., there exist $(x^0, y^0, s^0)$ such that

$$Ax^0 = b, x^0 > 0, A^t y^0 + s^0 = c, s^0 > 0. \tag{2.1}$$

Therefore, an optimal solution of $(P)$ and $(D)$ can be found by solving the following system

$$\begin{align}
Ax &= b, x \ge 0, \nonumber \\
A^t y + s &= c, s \ge 0, \tag{2.2} \\
xs &= 0. \nonumber
\end{align}$$

The key idea behind primal-dual IPMs for solving LO problems is to replace the third equation in (2.2) by the parameterized nonlinear equation $xs = \mu e$, where $\mu > 0$. Therefore, the system (2.2) can be rewritten as

$$\begin{align}
Ax &= b, x \ge 0, \nonumber \\
A^t y + s &= c, s \ge 0, \tag{2.3} \\
xs &= \mu e. \nonumber
\end{align}$$

Note that, this system has a unique solution as $(x(\mu), y(\mu), s(\mu))$, where $x(\mu)$ is called the $\mu$-center of $(P)$ and $(y(\mu), s(\mu))$ the $\mu$-center of $(D)$. The set of $\mu$-centers (with $\mu$ running through all positive real numbers) gives a homotype path, which is called the central path of $(P)$ and $(D)$. Applying Newton's method to the system (2.3), we obtain the following Newton-system

$$\begin{align}
A\Delta x &= 0, \nonumber \\
A^t \Delta y + \Delta s &= 0, \tag{2.4} \\
s\Delta x + x\Delta s &= \mu e - xs. \nonumber
\end{align}$$

Note that this system has a unique solution. Now we can derive the new point as

$$x_+ = x + \alpha \Delta x, s_+ = s + \alpha \Delta s, y_+ = y + \alpha \Delta y. \tag{2.5}$$

where the step size $\alpha$ satisfies $0 < \alpha \le 1$.
Now, we introduce the scaled vector $v$, that $v = \sqrt{\frac{xs}{\mu}}$. System (2.4) can be rewritten as follows:

$$ 
\begin{aligned}
A\Delta x &= 0, \\
A^t\Delta y + \Delta s &= 0, \\
s\Delta x + x\Delta s &= \mu v(v^{-1} - v),
\end{aligned} 
\qquad (2.6) $$

equivalent

$$ 
\begin{aligned}
A\Delta x &= 0, \\
A^t\Delta y + \Delta s &= 0, \\
s\Delta x + x\Delta s &= -\mu v \nabla \Phi(v),
\end{aligned} 
\qquad (2.7) $$

where the logarithmic barrier function $\Phi(v) : \mathbb{R}_{++}^n \to \mathbb{R}_+$ is defined as follows:

$$ \Phi(v) = \Phi(x, s; \mu) = \sum_{i=1}^{n} \psi(v_i), \qquad (2.8) $$

$$ \psi(v_i) = \frac{v_i^2 - 1}{2} - \log v_i. \qquad (2.9) $$

Now, we introduce the scaled search directions $d_x$ and $d_s$ as follows:

$$ d_x = \frac{v\Delta x}{s}, \quad d_s = \frac{v\Delta s}{s}. \qquad (2.10) $$

System (2.7) can be rewritten as follows:

$$ 
\begin{aligned}
\bar{A}d_x &= 0, \\
\bar{A}^t\Delta y + d_s &= 0, \\
d_x + d_s &= -\nabla\Phi(v),
\end{aligned} 
\qquad (2.11) $$

where $\bar{A} = \frac{1}{\mu}AV^{-1}X$, $V = \text{diag}(v)$, $X = \text{diag}(x)$. We use $\Phi(v)$ as the proximity function to measure the distance between the current iterate and the $\mu$-center for given $\mu > 0$. We also define the norm-based proximity measure, $\delta(v) : \mathbb{R}_{++}^n \to \mathbb{R}_+$, as follows

$$ \delta(v) = \frac{1}{2} \| \nabla \Phi(v) \| = \frac{1}{2} \| d_x + d_s \|. $$

The relevance of the central path for **LO** was recognized first by Megiddo [9], Sonnevend [14]. If $\mu \to 0$, then the limit of the central path exists, and since the limit points satisfy the complementarity condition, the limit yields optimal solutions for (P) and (D). From a theoretical point of view, the **IPC** can be assumed without loss of generality. In fact we may, and will, assume that $x^0 = s^0 = e$. In practice, this can be realized by embedding the given problems (P) and (D) into a homogeneous self-dual problem which has two additional variables and two additional constraints. For this and the other properties mentioned above, see Roos et al. [13]. The **IPMs** follow the central path approximately. We briefly describe the usual approach. Without loss of generality, we assume that $(x(\mu), y(\mu), s(\mu))$ is known for some positive $\mu$. For example, due to the above assumption, we may assume this for $\mu = 1$, with $x(1) = s(1) = e$. We then decrease $\mu$ to $\mu = (1 - \theta)\mu$ for some fixed $\theta \in [0, 1]$. We call $\psi(t)$ the kernel function of the logarithmic barrier function $\Phi(v)$. In all of the paper, based on a new kernel function, we replace $\psi(t)$ by a new kernel function $\psi_M(t)$ and $\Phi(v)$ by a new barrier function $\Phi_M(v)$. If $\Phi_M(v) \le \tau$, then we start a new outer iteration by performing a $\mu$-update; otherwise, we enter an inner iteration by computing the search directions at the current iterates with respect to the current value of $\mu$ and apply (2.5) to get new iterates. If necessary, we repeat the procedure until we find iterates that are in the neighborhood of $(x(\mu), s(\mu))$. Then $\mu$ is again reduced by the factor $1 - \theta$ with $0 < \theta < 1$, and we apply Newton's method targeting the new $\mu$-centers, and so on. This process is repeated until $\mu$ is small enough, say until $n\mu < \epsilon$; at this stage we have found an $\epsilon$-approximate solution of **LO**. The parameters $\tau, \theta$ and the step size $\alpha$ should be chosen in such a way that the algorithm is optimized in the sense that the number of iterations required by algorithm is as small as possible. The generic primal-dual algorithm for **LO** problem is as follows (see Fig. 1).
Now, we introduce the scaled vector $v$, that $v = \sqrt{\frac{xs}{\mu}}$. System (2.4) can be rewritten as follows:

$$ 
\begin{aligned}
A\Delta x &= 0, \\
A^t\Delta y + \Delta s &= 0, \\
s\Delta x + x\Delta s &= \mu v(v^{-1} - v),
\end{aligned} 
\quad (2.6) $$

equivalent

$$ 
\begin{aligned}
A\Delta x &= 0, \\
A^t\Delta y + \Delta s &= 0, \\
s\Delta x + x\Delta s &= -\mu v \nabla \Phi(v),
\end{aligned} 
\quad (2.7) $$

where the logarithmic barrier function $\Phi(v) : \mathbb{R}_{++}^n \to \mathbb{R}_+$ is defined as follows:

$$ \Phi(v) = \Phi(x, s; \mu) = \sum_{i=1}^{n} \psi(v_i), \quad (2.8) $$

$$ \psi(v_i) = \frac{v_i^2 - 1}{2} - \log v_i. \quad (2.9) $$

Now, we introduce the scaled search directions $d_x$ and $d_s$ as follows:

$$ d_x = \frac{v\Delta x}{\|v\|}, \quad d_s = \frac{v\Delta s}{\|s\|}. \quad (2.10) $$

System (2.7) can be rewritten as follows:

$$ 
\begin{aligned}
\bar{A}d_x &= 0, \\
\bar{A}^t\Delta y + d_s &= 0, \\
d_x + d_s &= -\nabla\Phi(v),
\end{aligned} 
\quad (2.11) $$

where $\bar{A} = \frac{1}{\mu}AV^{-1}X$, $V = \text{diag}(v)$, $X = \text{diag}(x)$. We use $\Phi(v)$ as the proximity function to measure the distance between the current iterate and the $\mu$-center for given $\mu > 0$. We also define the norm-based proximity measure, $\delta(v) : \mathbb{R}_{++}^n \to \mathbb{R}_+$, as follows

$$ \delta(v) = \frac{1}{2} \|\nabla\Phi(v)\| = \frac{1}{2} \|d_x + d_s\|. $$

The relevance of the central path for **LO** was recognized first by Megiddo [9], Sonnevend [14]. If $\mu \to 0$, then the limit of the central path exists, and since the limit points satisfy the complementarity condition, the limit yields optimal solutions for (P) and (D). From a theoretical point of view, the **IPC** can be assumed without loss of generality. In fact we may, and will, assume that $x^0 = s^0 = e$. In practice, this can be realized by embedding the given problems (P) and (D) into a homogeneous self-dual problem which has two additional variables and two additional constraints. For this and the other properties mentioned above, see Roos et al. [13]. The **IPMs** follow the central path approximately. We briefly describe the usual approach. Without loss of generality, we assume that $(x(\mu), y(\mu), s(\mu))$ is known for some positive $\mu$. For example, due to the above assumption, we may assume this for $\mu = 1$, with $x(1) = s(1) = e$. We then decrease $\mu$ to $\mu = (1 - \theta)\mu$ for some fixed $\theta \in [0, 1]$. We call $\psi(t)$ the kernel function of the logarithmic barrier function $\Phi(v)$. In all of the paper, based on a new kernel function, we replace $\psi(t)$ by a new kernel function $\psi_M(t)$ and $\Phi(v)$ by a new barrier function $\Phi_M(v)$. If $\Phi_M(v) \le \tau$, then we start a new outer iteration by performing a $\mu$-update; otherwise, we enter an inner iteration by computing the search directions at the current iterates with respect to the current value of $\mu$ and apply (2.5) to get new iterates. If necessary, we repeat the procedure until we find iterates that are in the neighborhood of $(x(\mu), s(\mu))$. Then $\mu$ is again reduced by the factor $1 - \theta$ with $0 < \theta < 1$, and we apply Newton's method targeting the new $\mu$-centers, and so on. This process is repeated until $\mu$ is small enough, say until $n\mu < \epsilon$; at this stage we have found an $\epsilon$-approximate solution of **LO**. The parameters $\tau, \theta$ and the step size $\alpha$ should be chosen in such a way that the algorithm is optimized in the sense that the number of iterations required by algorithm is as small as possible. The generic primal-dual algorithm for **LO** problem is as follows (see Fig. 1).
Generic Primal-dual IPMs for LO

**Input:**

A proximity the function $\Phi_M(v)$;
a threshold parameter $\tau > 1$;
an accuracy parameter $\epsilon > 0$;
a fixed barrier update parameter $\theta, 0 < \theta < 1$;

**begin**

$x = e; s = e; \mu = 1; v = e.$

**while** $n\mu \ge \epsilon$ **do**

**begin** (outer iteration)

$\mu = (1 - \theta) \mu;$

**while** $\Phi_M(x, s; \mu) > \tau$ **do**

**begin** (inner iteration)

Solve the system (7), $\Phi(v)$ replaced by $\Phi_M(v)$ to obtain $(\Delta x, \Delta y, \Delta s)$;

Choose a suitable step size $\alpha$;

$x = x + \alpha \Delta x;$

$y = y + \alpha \Delta y;$

$s = s + \alpha \Delta s;$

$v = \sqrt{\frac{xs}{\mu}};$

**end** (inner iteration)

**end** (outer iteration)

**end.**

<caption>FIGURE 1. Generic algorithm.</caption>

### 3. PROPERTIES OF THE KERNEL FUNCTION

In this section, we investigate some properties of the new kernel function with trigonometric barrier terms which are essential to our complexity analysis. We call $\psi(t) : \mathbb{R}_{++} \to \mathbb{R}_+$ a kernel function if $\psi$ is twice differentiable and satisfies the following conditions:

$$ 
\begin{aligned}
\psi'(1) &= \psi(1) = 0, \\
\psi''(t) &> 0, \\
\lim_{t \to 0^+} \psi(t) &= \lim_{t \to +\infty} \psi(t) = +\infty.
\end{aligned}
$$

Now, for $p \in \mathbb{R}$ and $q \in \mathbb{R}$, we define a new function $\psi_M(t)$ as follows:

$$ \psi_M(t) = \frac{t^2 - 1}{2} + m(p, q) \left[ \cot^p \left( \frac{\pi}{q+2} \right) \tan^p u(t) - 1 \right], \quad p \ge 2, q > 0. \quad (3.1) $$

and

$$ u(t) = \frac{\pi}{qt + 2}, \quad q > 0. \quad (3.2) $$

$$ m(p, q) = \frac{(q + 2)^2}{\pi pq \left( \cot \left( \frac{\pi}{q+2} \right) + \tan \left( \frac{\pi}{q+2} \right) \right)}, \quad p \ge 2, q > 0. $$
Generic Primal-dual IPMs for LO

**Input:**

A proximity the function $\Phi_M(v)$;
a threshold parameter $\tau > 1$;
an accuracy parameter $\epsilon > 0$;
a fixed barrier update parameter $\theta, 0 < \theta < 1$;

**begin**

$x = e; s = e; \mu = 1; v = e.$

**while** $n\mu \ge \epsilon$ **do**

**begin** (outer iteration)

$\mu = (1 - \theta) \mu;$

**while** $\Phi_M(x, s; \mu) > \tau$ **do**

**begin** (inner iteration)

Solve the system (7), $\Phi(v)$ replaced by $\Phi_M(v)$ to obtain $(\Delta x, \Delta y, \Delta s)$;

Choose a suitable step size $\alpha$;

$x = x + \alpha \Delta x;$

$y = y + \alpha \Delta y;$

$s = s + \alpha \Delta s;$

$v = \sqrt{\frac{xs}{\mu}};$

**end** (inner iteration)

**end** (outer iteration)

**end.**

<caption>FIGURE 1. Generic algorithm.</caption>

### 3. PROPERTIES OF THE KERNEL FUNCTION

In this section, we investigate some properties of the new kernel function with trigonometric barrier terms which are essential to our complexity analysis. We call $\psi(t) : \mathbb{R}_{++} \to \mathbb{R}_+$ a kernel function if $\psi$ is twice differentiable and satisfies the following conditions:

$$ \begin{aligned} \psi'(1) &= \psi(1) = 0, \\ \psi''(t) &> 0, \\ \lim_{t \to 0^+} \psi(t) &= \lim_{t \to +\infty} \psi(t) = +\infty. \end{aligned} $$

Now, for $p \in \mathbb{R}$ and $q \in \mathbb{R}$, we define a new function $\psi_M(t)$ as follows:

$$ \psi_M(t) = \frac{t^2 - 1}{2} + m(p, q) \left[ \cot^p \left( \frac{\pi}{q+2} \right) \tan^p u(t) - 1 \right], \quad p \ge 2, q > 0. \quad (3.1) $$

and

$$ u(t) = \frac{\pi}{qt + 2}, \quad q > 0. \quad (3.2) $$

$$ m(p, q) = \frac{(q + 2)^2}{\pi pq \left( \cot \left( \frac{\pi}{q+2} \right) + \tan \left( \frac{\pi}{q+2} \right) \right)}, \quad p \ge 2, q > 0. $$
For convenience of reference, we give the first three derivatives with respect to $t$ as follows:

$$
\begin{align}
\psi'_M(t) &= t + pm(p, q) \cot^p \left(\frac{\pi}{q+2}\right) (1 + \tan^2 u) (\tan^{p-1} u) u', \nonumber \\
\psi''_M(t) &= 1 + n(p, q) \left[ \begin{aligned} &((p-1) \tan^{p-2} u + (p+1) \tan^p u) u'^2 + \\ &\qquad (\tan^{p-1} u) u'' \end{aligned} \right], \nonumber \\
\psi'''_M(t) &= n(p, q) \left[ \begin{aligned} &\left[ \begin{aligned} &(p-1)(p-2) \tan^{p-3} u + \\ &2p^2 \tan^{p-1} u + \\ &(p+1)(p+2) \tan^{p+1} u \end{aligned} \right] u'^3 + \\ &\left( \begin{aligned} &3(p-1) \tan^{p-2} u + \\ &3(p+1) \tan^p u \end{aligned} \right) u''u' + \\ &\qquad (\tan^{p-1} u) u''' \end{aligned} \right]. \tag{3.3}
\end{align}
$$

With

$$n(p, q) = pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) (1 + \tan^2 u)$$

and

$$
\begin{align}
u(t) &= \frac{\pi}{qt + 2} \nonumber \\
u'(t) &= -\frac{\pi q}{(qt + 2)^2} \nonumber \\
u''(t) &= \frac{2\pi q^2}{(qt + 2)^3} \nonumber \\
u'''(t) &= -\frac{6\pi q^3}{(2t + 2)^4}. \tag{3.4}
\end{align}
$$

**Lemma 3.1.** For $u(t)$ defined in (3.2) and $p \ge 2$, we have the following

$$0 < u(t) < \frac{\pi}{2}, \quad t > 0. \tag{3.4a}$$

$$\tan u(t) > 0, \quad t > 0. \tag{3.4b}$$

$$\left[ \begin{aligned} &((p-1) \tan^{p-2} u + (p+1) \tan^p u) u'^2 + \\ &\qquad (\tan^{p-1} u) u'' \end{aligned} \right] > 0, \quad t > 0. \tag{3.4c}$$

$$(\tan u(t)) - \frac{4}{q(p+1)\pi t} > 0, \quad t > 0. \tag{3.4d}$$

*Proof.* For (3.4a), since $u(t)$ is decreasing in $]0, +\infty[$ and

$$\lim_{t \to 0^+} u(t) = \frac{\pi}{2}, \quad \lim_{t \to +\infty} u(t) = 0$$

we have

$$0 < u(t) < \frac{\pi}{2}, \quad t > 0.$$

For (3.4b), using (3.4a) we get

$$\tan u(t) > 0, \quad t > 0.$$

For (3.4c), using (3.4) and (3.4b) we get

$$\left[ \begin{aligned} &((p-1) \tan^{p-2} u + (p+1) \tan^p u) u'^2 + \\ &\qquad (\tan^{p-1} u) u'' \end{aligned} \right] > 0, \quad t > 0.$$
For convenience of reference, we give the first three derivatives with respect to $t$ as follows:

$$
\begin{align}
\psi'_M(t) &= t + pm(p, q) \cot^p \left(\frac{\pi}{q+2}\right) (1 + \tan^2 u) (\tan^{p-1} u) u', \nonumber \\
\psi''_M(t) &= 1 + n(p, q) \left[ \begin{aligned} &((p-1) \tan^{p-2} u + (p+1) \tan^p u) u'^2 + \\ &\qquad (\tan^{p-1} u) u'' \end{aligned} \right], \nonumber \\
\psi'''_M(t) &= n(p, q) \left[ \begin{aligned} &\left[ \begin{aligned} &(p-1)(p-2) \tan^{p-3} u + \\ &2p^2 \tan^{p-1} u + \\ &(p+1)(p+2) \tan^{p+1} u \end{aligned} \right] u'^3 + \\ &\left[ \begin{aligned} &(3(p-1) \tan^{p-2} u + \\ &3(p+1) \tan^p u \\ &\qquad (\tan^{p-1} u) u''' \end{aligned} \right] u''u' + \end{aligned} \right]. \tag{3.3}
\end{align}
$$

With

$$n(p, q) = pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) (1 + \tan^2 u)$$

and

$$
\begin{align}
u(t) &= \frac{\pi}{qt + 2} \nonumber \\
u'(t) &= -\frac{\pi q}{(qt + 2)^2} \nonumber \\
u''(t) &= \frac{2\pi q^2}{(qt + 2)^3} \nonumber \\
u'''(t) &= -\frac{6\pi q^3}{(2t + 2)^4}. \tag{3.4}
\end{align}
$$

**Lemma 3.1.** For $u(t)$ defined in (3.2) and $p \ge 2$, we have the following

$$0 < u(t) < \frac{\pi}{2}, \quad t > 0. \tag{3.4a}$$

$$\tan u(t) > 0, \quad t > 0. \tag{3.4b}$$

$$\left[ \begin{aligned} &((p-1) \tan^{p-2} u + (p+1) \tan^p u) u'^2 + \\ &\qquad (\tan^{p-1} u) u'' \end{aligned} \right] > 0, \quad t > 0. \tag{3.4c}$$

$$(\tan u(t)) - \frac{4}{q(p+1)\pi t} > 0, \quad t > 0. \tag{3.4d}$$

*Proof.* For (3.4a), since $u(t)$ is decreasing in $]0, +\infty[$ and

$$\lim_{t \to 0^+} u(t) = \frac{\pi}{2}, \quad \lim_{t \to +\infty} u(t) = 0$$

we have

$$0 < u(t) < \frac{\pi}{2}, \quad t > 0.$$

For (3.4b), using (3.4a) we get

$$\tan u(t) > 0, \quad t > 0.$$

For (3.4c), using (3.4) and (3.4b) we get

$$\left[ \begin{aligned} &((p-1) \tan^{p-2} u + (p+1) \tan^p u) u'^2 + \\ &\qquad (\tan^{p-1} u) u'' \end{aligned} \right] > 0, \quad t > 0.$$
To prove (3.4d), define $g(t) = (\tan u(t)) - \frac{4}{q(p+1)\pi t}$. The first derivative of $g(t)$ is given by

$$g'(t) = \frac{u'(t)}{(\cos u(t))^2} + \frac{4}{q(p+1)\pi t^2} = \frac{q(p+1)\pi t^2 u'(t) + 4(\cos u(t))^2}{q(p+1)\pi t^2 (\cos u(t))^2}.$$

Using that for

$$0 < u(t) < \frac{\pi}{2}, \quad t > 0,$$

we have $\sin(\frac{\pi}{2} - u(t)) = \cos u(t)$, and $\sin(\frac{\pi}{2} - u(t)) \le (\frac{\pi}{2} - u(t))$, it follows that

$$g'(t) = \frac{1}{q(p+1)\pi t^2 (\cos u(t))^2} \left( q(p+1)\pi t^2 u'(t) + 4 \left( \sin\left(\frac{\pi}{2} - u(t)\right) \right)^2 \right) \\ \le \frac{1}{q(p+1)\pi t^2 (\cos u(t))^2} \left( q(p+1)\pi t^2 u'(t) + 4 \left( \frac{\pi}{2} - u(t) \right)^2 \right) \\ = \frac{-p}{q(p+1)\pi t^2 (\cos u(t))^2} \left( \frac{\pi q t}{2t+2} \right)^2 < 0.$$

Thus $g(t)$ is decreasing in $]0, +\infty[$, and since $\lim_{t \to +\infty} g(t) = 0$, this implies (3.4d).

This completes the proof.

<figure><img src="image_2.png" /></figure>

the next lemma serves to prove that the new kernel function (3.1) is eligible.

**Lemma 3.2.** Let $\psi_M(t)$ be as defined in (3.1) and $t > 0$. Then,

$$\psi_M''(t) > 1. \qquad (3.1a)$$

$$\psi_M'''(t) < 0. \qquad (3.1b)$$

$$t\psi_M''(t) - \psi_M'(t) > 0. \qquad (3.1c)$$

$$t\psi_M''(t) + \psi_M'(t) > 0. \qquad (3.1d)$$

$$\psi_M''(t)\psi_M'(\beta t) - \beta\psi_M'(t)\psi_M''(\beta t) > 0, \quad t > 1, \beta > 1. \qquad (3.1e)$$

*Proof.* For (3.1a), the second derivative of $\psi_M(t)$ is given in (3.3), using (3.4c), we have

$$\left[ \left( (p-1) \tan^{p-2} u + (p+1) \tan^p u \right) u'^2 + \left( \tan^{p-1} u \right) u'' \right] > 0 \text{ for all } t > 0,$$

which implies (3.1a).

For (3.1b), the sign of $\psi_M'''(t)$, using (3.4) and (3.4b), we have

$$\psi_M'''(t) < 0, \quad t > 0,$$

which implies (3.1b).
To prove (3.4d), define $g(t) = (\tan u(t)) - \frac{4}{q(p+1)\pi t}$. The first derivative of $g(t)$ is given by

$$g'(t) = \frac{u'(t)}{(\cos u(t))^2} + \frac{4}{q(p+1)\pi t^2} = \frac{q(p+1)\pi t^2 u'(t) + 4(\cos u(t))^2}{q(p+1)\pi t^2 (\cos u(t))^2}.$$

Using that for

$$0 < u(t) < \frac{\pi}{2}, \quad t > 0,$$

we have $\sin(\frac{\pi}{2} - u(t)) = \cos u(t)$, and $\sin(\frac{\pi}{2} - u(t)) \le (\frac{\pi}{2} - u(t))$, it follows that

$$g'(t) = \frac{1}{q(p+1)\pi t^2 (\cos u(t))^2} \left( q(p+1)\pi t^2 u'(t) + 4 \left( \sin\left(\frac{\pi}{2} - u(t)\right) \right)^2 \right) \\ \le \frac{1}{q(p+1)\pi t^2 (\cos u(t))^2} \left( q(p+1)\pi t^2 u'(t) + 4 \left( \frac{\pi}{2} - u(t) \right)^2 \right) \\ = \frac{-p}{q(p+1)\pi t^2 (\cos u(t))^2} \left( \frac{\pi q t}{2t+2} \right)^2 < 0.$$

Thus $g(t)$ is decreasing in $]0, +\infty[$, and since $\lim_{t \to +\infty} g(t) = 0$, this implies (3.4d).

This completes the proof. □

the next lemma serves to prove that the new kernel function (3.1) is eligible.

**Lemma 3.2.** Let $\psi_M(t)$ be as defined in (3.1) and $t > 0$. Then,

$$\psi_M''(t) > 1. \qquad (3.1a)$$

$$\psi_M'''(t) < 0. \qquad (3.1b)$$

$$t\psi_M''(t) - \psi_M'(t) > 0. \qquad (3.1c)$$

$$t\psi_M''(t) + \psi_M'(t) > 0. \qquad (3.1d)$$

$$\psi_M''(t)\psi_M'(\beta t) - \beta\psi_M'(t)\psi_M''(\beta t) > 0, \quad t > 1, \beta > 1. \qquad (3.1e)$$

*Proof.* For (3.1a), the second derivative of $\psi_M(t)$ is given in (3.3), using (3.4c), we have

$$\left[ \left( (p-1) \tan^{p-2} u + (p+1) \tan^p u \right) u'^2 + \left( \tan^{p-1} u \right) u'' \right] > 0 \text{ for all } t > 0,$$

which implies (3.1a).

For (3.1b), the sign of $\psi_M'''(t)$, using (3.4) and (3.4b), we have

$$\psi_M'''(t) < 0, \quad t > 0,$$

which implies (3.1b).
For (3.1c), we again use (3.3) and (3.4),

$$t\psi''_M(t) - \psi'_M(t) = n(p,q) \left[ \begin{bmatrix} ((p-1)\tan^{p-2}u(t) + (p+1)\tan^p u(t))tu'^2(t)+ \\ (\tan^{p-1}u(t))tu''(t) \\ -(\tan^{p-1}u(t))u'(t) \end{bmatrix} \right].$$

Form (3.4c) and the positivity of $-u'(t)$, the right-hand side of the last equality is positive, which proves (3.1c).

For (3.1d), using (3.3) and (3.4), we have

$$t\psi''_M(t) + \psi'_M(t) = 2t + n(p,q) \left[ \begin{array}{c} (p-1)(\tan^{p-2}u(t))tu'^2(t)+ \\ (\tan^{p-1}u(t))\begin{bmatrix} (p+1)(\tan u(t))u'^2(t)t+ \\ u''(t)t+ \\ u'(t) \end{bmatrix} \end{array} \right]$$

and

$$(p+1)(\tan u(t))u'^2(t)t + u''(t)t + u'(t) = \frac{\pi q^3}{(qt+2)^4} \left[ \frac{\pi q}{q} (p+1) t \left( \tan u(t) - \frac{4}{q(p+1)\pi t} \right) \right]$$

using (3.4d), the right-hand side of the above equality is positive, which proves (3.1d).

For (3.1e), using Lemma 2.4 in [2]. (3.1b) and (3.1c), we have the result. This completes the proof. □

## 4. THE PROXIMITY REDUCTION DURING AN INNER ITERATION

Note that at the start of each outer iteration of the algorithm, just before the update of $\mu$ with the factor $1-\theta$, we have $\Phi_M(v) \le \tau$. Due to the update of $\mu$ the vector $v$ is divided by the factor $\sqrt{1-\theta}$, with $0 < \theta < 1$, which in general leads to an increase in the value of $\Phi_M(v)$. Then, during the subsequent inner iterations, $\Phi_M(v)$ decreases until it passes the threshold $\tau$ again. Hence, during the course of the algorithm the value of $\Phi_M(v)$ increases only after one update of $\mu$. Therefore, the largest values of $\Phi_M(v)$ occur just after the updates of $\mu$. That is why in this section we derive an estimate for the effect of a $\mu$-update on the value of $\Phi_M(v)$. We start with an important lemmas.

**Lemma 4.1.** For $\psi_M(t)$, we have

$$\frac{1}{2}(t-1)^2 \le \psi_M(t) \le \frac{1}{2}[\psi'_M(t)]^2, \quad t > 0. \qquad (3.1f)$$

$$\psi_M(t) \le \frac{1}{2} \varphi(p, q) (t-1)^2, \quad t > 1. \qquad (3.1g)$$

where

$$\varphi(p, q) = \frac{\left[ (q+2) \cot\left(\frac{\pi}{q+2}\right) \right]^2}{\pi q \left( \cot\left(\frac{\pi}{q+2}\right) + \tan\left(\frac{\pi}{q+2}\right) \right)} + \frac{2q}{q+2} + \frac{2\pi q}{\left( \cot\left(\frac{\pi}{q+2}\right) + \tan\left(\frac{\pi}{q+2}\right) \right)^2} p. \qquad (3.1h)$$

*Proof.* For (3.1f), using (3.1a) and (3.1b), we have

$$\psi_M(t) = \int_1^t \int_1^x \psi_M''(y) dydx \ge \int_1^t \int_1^x 1 dydx = \frac{1}{2} (t-1)^2$$
For (3.1c), we again use (3.3) and (3.4),

$$t\psi_M''(t) - \psi_M'(t) = n(p, q) \left[ \begin{bmatrix} ((p-1)\tan^{p-2} u(t) + (p+1)\tan^p u(t))tu'^2(t)+ \\ (\tan^{p-1} u(t))tu''(t) \\ -(\tan^{p-1} u(t))u'(t) \end{bmatrix} \right].$$

Form (3.4c) and the positivity of $-u'(t)$, the right-hand side of the last equality is positive, which proves (3.1c).

For (3.1d), using (3.3) and (3.4), we have

$$t\psi_M''(t) + \psi_M'(t) = 2t + n(p, q) \left[ \begin{array}{c} (p-1)(\tan^{p-2} u(t))tu'^2(t)+ \\ (\tan^{p-1} u(t)) \begin{bmatrix} (p+1)(\tan u(t))u'^2(t)t+ \\ u''(t)t+ \\ u'(t) \end{bmatrix} \end{array} \right]$$

and

$$(p+1)(\tan u(t))u'^2(t)t + u''(t)t + u'(t) = \frac{\pi q^3}{(qt+2)^4} \left[ \frac{\pi q}{q} (p+1) t \left( \tan u(t) - \frac{4}{q(p+1)\pi t} \right) \right]$$

using (3.4d), the right-hand side of the above equality is positive, which proves (3.1d).

For (3.1e), using Lemma 2.4 in [2]. (3.1b) and (3.1c), we have the result. This completes the proof. □

## 4. THE PROXIMITY REDUCTION DURING AN INNER ITERATION

Note that at the start of each outer iteration of the algorithm, just before the update of $\mu$ with the factor $1-\theta$, we have $\Phi_M(v) \le \tau$. Due to the update of $\mu$ the vector $v$ is divided by the factor $\sqrt{1-\theta}$, with $0 < \theta < 1$, which in general leads to an increase in the value of $\Phi_M(v)$. Then, during the subsequent inner iterations, $\Phi_M(v)$ decreases until it passes the threshold $\tau$ again. Hence, during the course of the algorithm the value of $\Phi_M(v)$ increases only after one update of $\mu$. Therefore, the largest values of $\Phi_M(v)$ occur just after the updates of $\mu$. That is why in this section we derive an estimate for the effect of a $\mu$-update on the value of $\Phi_M(v)$. We start with an important lemmas.

**Lemma 4.1.** For $\psi_M(t)$, we have

$$\frac{1}{2}(t-1)^2 \le \psi_M(t) \le \frac{1}{2}[\psi_M'(t)]^2, \quad t > 0. \qquad (3.1f)$$

$$\psi_M(t) \le \frac{1}{2} \varphi(p, q) (t-1)^2, \quad t > 1. \qquad (3.1g)$$

where

$$\varphi(p, q) = \frac{\left[ (q+2) \cot\left(\frac{\pi}{q+2}\right) \right]^2}{\pi q \left( \cot\left(\frac{\pi}{q+2}\right) + \tan\left(\frac{\pi}{q+2}\right) \right)} + \frac{2q}{q+2} + \frac{2\pi q}{\left( \cot\left(\frac{\pi}{q+2}\right) + \tan\left(\frac{\pi}{q+2}\right) \right)^2} p. \qquad (3.1h)$$

*Proof.* For (3.1f), using (3.1a) and (3.1b), we have

$$\psi_M(t) = \int_1^t \int_1^x \psi_M''(y) dydx \ge \int_1^t \int_1^x 1 dydx = \frac{1}{2} (t-1)^2$$
$$
\begin{align*}
\psi_M(t) &= \int_1^t \int_1^x \psi_M''(y) dydx \\
&\le \int_1^t \int_1^x \psi_M''(y) \psi_M''(x) dydx \\
&= \int_1^t \psi_M''(x) \psi_M'(x) dx \\
&= \int_1^t \psi_M'(x) d\psi_M'(x) \\
&= \frac{1}{2} [\psi_M'(t)]^2.
\end{align*}
$$

For (3.1g), since $\psi_M(1) = \psi'_M(1) = 0$, $\psi'''_M(t) < 0$, $\psi''_M(1) = \varphi(p,q)$, and by using Taylor's Theorem, we have

$$
\begin{align*}
\psi_M(t) &= \psi_M(1) + \psi'_M(1)(t-1) + \frac{1}{2}\psi''_M(1)(t-1)^2 + \frac{1}{6}\psi'''_M(\xi)(\xi-1)^3 \\
&= \frac{1}{2}\psi''_M(1)(t-1)^2 + \frac{1}{6}\psi'''_M(\xi)(\xi-1)^3 \\
&\le \frac{1}{2}\psi''_M(1)(t-1)^2 \\
&= \frac{1}{2}\varphi(p,q)(t-1)^2.
\end{align*}
$$

for some $\xi$, $1 \le \xi \le t$. This completes the proof.

<figure><img src="image_3.png" /></figure>

Let $\sigma : [0, +\infty[ \to [1, +\infty[ \text{ be the inverse function of } \psi_M(t) \text{ for } t \ge 1 \text{ and } \rho : [0, +\infty[ \to ]0, 1] \text{ be the inverse function of } \frac{1}{2}\psi'_M(t) \text{ for all } t \in ]0, 1]. \text{ Then we have the following lemma.}$

**Lemma 4.2.** For $\psi_M(t)$, we have

$$1 + \sqrt{\frac{2}{\varphi(p,q)}} s \le \sigma(s) \le 1 + \sqrt{2s}, \quad s \ge 0. \qquad (3.1i)$$

$$(\tan^{p-1} u(t) + \tan^{p+1} u(t)) \le \frac{(q+2)^2}{m(p,q) \cot^p\left(\frac{\pi}{q+2}\right) pq\pi} (2z+1), \quad z \ge 0. \qquad (3.1j)$$

*Proof.* For (3.1i), let

$$s = \psi_M(t), \quad t \ge 1, \text{ i.e., } \sigma(s) = t, \quad t \ge 1.$$

By (3.1f), we have

$$\psi_M(t) \ge \frac{1}{2} (t-1)^2.$$

we have

$$s \ge \frac{1}{2} (t-1)^2, \quad t \ge 1.$$

which implies that

$$t = \sigma(s) \le 1 + \sqrt{2s}.$$

By (3.1g), we have

$$s = \psi_M(t) \le \frac{1}{2} \varphi(p,q) (t-1)^2,$$

so

$$t = \sigma(s) \ge 1 + \sqrt{\frac{2}{\varphi(p,q)}} s.$$

For (3.1j), let

$$z = \frac{-1}{2} \psi'_{M}(t), \quad t \in ]0, 1] \Leftrightarrow 2z = -\psi'_{M}(t), \quad t \in ]0, 1].$$
$$
\begin{align*}
\psi_M(t) &= \int_1^t \int_1^x \psi_M''(y) dydx \\
&\le \int_1^t \int_1^x \psi_M''(y) \psi_M''(x) dydx \\
&= \int_1^t \psi_M''(x) \psi_M'(x) dx \\
&= \int_1^t \psi_M'(x) d\psi_M'(x) \\
&= \frac{1}{2} [\psi_M'(t)]^2.
\end{align*}
$$

For (3.1g), since $\psi_M(1) = \psi'_M(1) = 0$, $\psi'''_M(t) < 0$, $\psi''_M(1) = \varphi(p,q)$, and by using Taylor's Theorem, we have

$$
\begin{align*}
\psi_M(t) &= \psi_M(1) + \psi'_M(1)(t-1) + \frac{1}{2}\psi''_M(1)(t-1)^2 + \frac{1}{6}\psi'''_M(\xi)(\xi-1)^3 \\
&= \frac{1}{2}\psi''_M(1)(t-1)^2 + \frac{1}{6}\psi'''_M(\xi)(\xi-1)^3 \\
&\le \frac{1}{2}\psi''_M(1)(t-1)^2 \\
&= \frac{1}{2}\varphi(p,q)(t-1)^2.
\end{align*}
$$

for some $\xi$, $1 \le \xi \le t$. This completes the proof.

<figure><img src="image_2.png" /></figure>

Let $\sigma : [0, +\infty[ \to [1, +\infty[ \text{ be the inverse function of } \psi_M(t) \text{ for } t \ge 1 \text{ and } \rho : [0, +\infty[ \to ]0, 1] \text{ be the inverse function of } \frac{1}{2}\psi'_M(t) \text{ for all } t \in ]0, 1]. \text{ Then we have the following lemma.}$

**Lemma 4.2.** For $\psi_M(t)$, we have

$$1 + \sqrt{\frac{2}{\varphi(p,q)}} s \le \sigma(s) \le 1 + \sqrt{2s}, \quad s \ge 0. \qquad (3.1i)$$

$$(\tan^{p-1} u(t) + \tan^{p+1} u(t)) \le \frac{(q+2)^2}{m(p,q) \cot^p\left(\frac{\pi}{q+2}\right) pq\pi} (2z+1), \quad z \ge 0. \qquad (3.1j)$$

*Proof.* For (3.1i), let

$s = \psi_M(t), \quad t \ge 1, \text{ i.e., } \sigma(s) = t, \quad t \ge 1.$

By (3.1f), we have

$$\psi_M(t) \ge \frac{1}{2} (t-1)^2.$$

we have

$$s \ge \frac{1}{2} (t-1)^2, \quad t \ge 1.$$

which implies that

$$t = \sigma(s) \le 1 + \sqrt{2s}.$$

By (3.1g), we have

$$s = \psi_M(t) \le \frac{1}{2} \varphi(p,q) (t-1)^2,$$

so

$$t = \sigma(s) \ge 1 + \sqrt{\frac{2}{\varphi(p,q)}} s.$$

For (3.1j), let

$$z = \frac{-1}{2} \psi'_{M}(t), \quad t \in ]0, 1] \Leftrightarrow 2z = -\psi'_{M}(t), \quad t \in ]0, 1].$$
By the definition of

$$ \rho : \rho(z) = t, \quad t \in ]0, 1]. $$

And by the definition of $\psi'_M(t)$ and $u'(t)$, we have

$$ 2z = -(t + n(p, q)(\tan^{p-1} u(t)) u'(t)), $$

this implies that

$$ \begin{aligned} (1 + \tan^2 u(t)) (\tan^{p-1} u(t)) &= (\tan^{p-1} u(t) + \tan^{p+1} u(t)) \\ &\le (2z + t) \frac{1}{-pm(p,q) \cot^p(\frac{\pi}{q+2}) u'(t)} \quad \text{for } t \in ]0, 1] \\ &\le \frac{(q+2)^2}{m(p,q) \cot^p(\frac{\pi}{q+2}) pq\pi} (2z + 1) \\ &\le \frac{(q+2)^2}{m(p,q) \cot^p(\frac{\pi}{q+2}) pq\pi} (2z + 1), \quad z \ge 0. \end{aligned} $$

This completes the proof.

<figure><img src="image_4.png" /></figure>

**Lemma 4.3.** Let $\sigma: [0, +\infty] \to [1, +\infty[$ be the inverse function of $\psi_M(t)$ for $t \ge 1$. Then we have

$$ \Phi_M (\beta v) \le n \psi_M \left( \beta \sigma \left( \frac{\Phi_M(v)}{n} \right) \right), \quad v \in \mathbb{R}_{++}^n, \beta \ge 1. $$

*Proof.* Using Lemma 3.1 (3.1e), and Theorem 3.2 in [2], we can get the result. This completes the proof.

<figure><img src="image_5.png" /></figure>

**Lemma 4.4.** Let $0 \le \theta < 1$, $v_+ = \frac{v}{\sqrt{1-\theta}}$, if $\Phi_M(v) \le \tau$, then we have

$$ \Phi_M (v_+) \le \frac{(\theta n + 2\tau + 2\sqrt{2\tau n})}{2(1-\theta)}. $$

*Proof.* Since $\frac{1}{\sqrt{1-\theta}} \ge 1$ and $\sigma(\frac{\Phi_M(v)}{n}) \ge 1$, then $\frac{\sigma(\frac{\Phi_M(v)}{n})}{\sqrt{1-\theta}} \ge 1$.

And for $t \ge 1$, we have

$$ \psi_M(t) \le \frac{t^2 - 1}{2}. $$

Using Lemma (4.2), (3.1i), with $\beta = \frac{1}{\sqrt{1-\theta}}$ and $\Phi_M(v) \le \tau$, we have

$$ \begin{aligned} \Phi_M (v_+) &\le n \psi_M \left( \frac{1}{\sqrt{1-\theta}} \sigma \left( \frac{\Phi_M(v)}{n} \right) \right) \\ &\le \frac{n}{2} \left( \left[ \frac{1}{\sqrt{1-\theta}} \sigma \left( \frac{\Phi_M(v)}{n} \right) \right]^2 - 1 \right) \\ &= \frac{n}{2(1-\theta)} \left( \left[ \sigma \left( \frac{\Phi_M(v)}{n} \right) \right]^2 - \sqrt{1-\theta} \right) \\ &\le \frac{n}{2(1-\theta)} \left( \left[ 1 + \sqrt{2 \frac{\Phi_M(v)}{n}} \right]^2 - \sqrt{1-\theta} \right) \\ &= \frac{n}{2(1-\theta)} \left( \left[ 1 + 2 \frac{\Phi_M(v)}{n} + 2 \sqrt{2 \frac{\Phi_M(v)}{n}} \right] - \sqrt{1-\theta} \right) \\ &\le \frac{n}{2(1-\theta)} \left( (1 - \sqrt{1-\theta}) + 2 \frac{\tau}{n} + 2 \sqrt{2 \frac{\tau}{n}} \right) \\ &= \frac{(\theta n + 2\tau + 2\sqrt{2\tau n})}{2(1-\theta)}. \end{aligned} $$
By the definition of

$$ \rho : \rho(z) = t, \quad t \in ]0, 1]. $$

And by the definition of $\psi'_M(t)$ and $u'(t)$, we have

$$ 2z = -(t + n(p, q)(\tan^{p-1} u(t))u'(t)), $$

this implies that

$$ \begin{aligned} (1 + \tan^2 u(t)) (\tan^{p-1} u(t)) &= (\tan^{p-1} u(t) + \tan^{p+1} u(t)) \\ &\le (2z + t) \frac{1}{-pm(p,q) \cot^p(\frac{\pi}{q+2}) u'(t)} \quad \text{for } t \in ]0, 1] \\ &\le \frac{(q+2)^2}{m(p,q) \cot^p(\frac{\pi}{q+2}) pq\pi} (2z + 1) \\ &\le \frac{(q+2)^2}{m(p,q) \cot^p(\frac{\pi}{q+2}) pq\pi} (2z + 1), \quad z \ge 0. \end{aligned} $$

This completes the proof.

<figure><img src="image_3.png" /></figure>

**Lemma 4.3.** Let $\sigma: [0, +\infty] \to [1, +\infty[$ be the inverse function of $\psi_M(t)$ for $t \ge 1$. Then we have

$$ \Phi_M (\beta v) \le n \psi_M \left( \beta \sigma \left( \frac{\Phi_M(v)}{n} \right) \right), \quad v \in \mathbb{R}_{++}^n, \beta \ge 1. $$

*Proof.* Using Lemma 3.1 (3.1e), and Theorem 3.2 in [2], we can get the result. This completes the proof.

<figure><img src="image_4.png" /></figure>

**Lemma 4.4.** Let $0 \le \theta < 1$, $v_+ = \frac{v}{\sqrt{1-\theta}}$, if $\Phi_M(v) \le \tau$, then we have

$$ \Phi_M (v_+) \le \frac{(\theta n + 2\tau + 2\sqrt{2\tau n})}{2(1-\theta)}. $$

*Proof.* Since $\frac{1}{\sqrt{1-\theta}} \ge 1$ and $\sigma(\frac{\Phi_M(v)}{n}) \ge 1$, then $\frac{\sigma(\frac{\Phi_M(v)}{n})}{\sqrt{1-\theta}} \ge 1$. And for $t \ge 1$, we have

$$ \psi_M(t) \le \frac{t^2 - 1}{2}. $$

Using Lemma (4.2), (3.1i), with $\beta = \frac{1}{\sqrt{1-\theta}}$ and $\Phi_M(v) \le \tau$, we have

$$ \begin{aligned} \Phi_M (v_+) &\le n \psi_M \left( \frac{1}{\sqrt{1-\theta}} \sigma \left( \frac{\Phi_M(v)}{n} \right) \right) \\ &\le \frac{n}{2} \left( \left[ \frac{1}{\sqrt{1-\theta}} \sigma \left( \frac{\Phi_M(v)}{n} \right) \right]^2 - 1 \right) \\ &= \frac{n}{2(1-\theta)} \left( \left[ \sigma \left( \frac{\Phi_M(v)}{n} \right) \right]^2 - \sqrt{1-\theta} \right) \\ &\le \frac{n}{2(1-\theta)} \left( \left[ 1 + \sqrt{2 \frac{\Phi_M(v)}{n}} \right]^2 - \sqrt{1-\theta} \right) \\ &= \frac{n}{2(1-\theta)} \left( \left[ 1 + 2 \frac{\Phi_M(v)}{n} + 2 \sqrt{2 \frac{\Phi_M(v)}{n}} \right] - \sqrt{1-\theta} \right) \\ &\le \frac{n}{2(1-\theta)} \left( (1 - \sqrt{1-\theta}) + 2 \frac{\tau}{n} + 2 \sqrt{2 \frac{\tau}{n}} \right) \\ &= \frac{(\theta n + 2\tau + 2\sqrt{2\tau n})}{2(1-\theta)}. \end{aligned} $$
where the last inequality holds from $1 - \sqrt{1 - \theta} = \frac{\theta}{1 + \sqrt{1 - \theta}} \le \theta$. This completes the proof. □

Denote

$$ (\Phi_M)_0 = \frac{(\theta n + 2\tau + 2\sqrt{2\tau n})}{2(1-\theta)} = L(n, \theta, \tau); \qquad (3.1k) $$

then $(\Phi_M)_0$ is an upper bound for $\Phi_M(v_+)$ during the process of the algorithm.

## 5. AN ESTIMATION FOR THE STEP SIZE

In this section, we compute the largest possible value for the step size $\alpha$ during an inner iteration. After a damped step we have

$$ x_+ := x + \alpha \Delta x; $$

$$ s_+ := s + \alpha \Delta s; $$

$$ y_+ := y + \alpha \Delta y; $$

Using (2.6), we have

$$ x_+ := x \left(e + \alpha \frac{\Delta x}{x}\right) = x \left(e + \alpha \frac{d_x}{v}\right) = \frac{x}{v} \left(v + \alpha d_x\right), $$

$$ s_+ := s \left(e + \alpha \frac{\Delta s}{s}\right) = s \left(e + \alpha \frac{d_s}{v}\right) = \frac{s}{v} \left(v + \alpha d_s\right), $$

So, we have

$$ v_+ = \sqrt{\frac{x_+ s_+}{\mu}} = \sqrt{(v + \alpha d_x)(v + \alpha d_s)}. $$

Define, for $\alpha > 0$,

$$ f(\alpha) = \Phi_M(v_+) - \Phi_M(v). $$

Then $f(\alpha)$ is the difference of proximities between a new iterate and a current iterate for fixed $\mu$. By Lemma (3.2) (3.1d), we have

$$ \Phi_M(v_+) = \Phi_M\left(\sqrt{(v + \alpha d_x)(v + \alpha d_s)}\right) \le \frac{1}{2}\left(\Phi_M(v + \alpha d_x) + \Phi_M(v + \alpha d_s)\right). $$

Therefore, we have $f(\alpha) \le f_1(\alpha)$, where

$$ f_1(\alpha) = \frac{1}{2}(\Phi_M(v + \alpha d_x) + \Phi_M(v + \alpha d_s)) - \Phi_M(v). \qquad (3.11) $$

Obviously, $f(0) = f_1(0) = 0$. Taking the first two derivatives of $f_1(\alpha)$ with respect to $\alpha$, we have

$$ f'_1(\alpha) = \frac{1}{2} \sum_{i=1}^{n} (\psi'_M(v_i + \alpha d_{x_i}) d_{x_i} + \psi'_M(v_i + \alpha d_{s_i}) d_{s_i}), $$

$$ f_1''(\alpha) = \frac{1}{2} \sum_{i=1}^{n} (\psi_M''(v_i + \alpha d_{x_i}) d_{x_i}^2 + \psi_M''(v_i + \alpha d_{s_i}) d_{s_i}^2), $$

Using (2.8) and (2.11), we have

$$ f'_1(0) = \frac{1}{2} \nabla \Phi_M(v)^t (d_x + d_s) = -\frac{1}{2} \nabla \Phi_M(v)^t \nabla \Phi_M(v) = -2\delta^2(v). $$

For convenience, we denote

$$ v_1 = \min(v), \delta := \delta(v), \Phi_M = \Phi_M(v). $$
where the last inequality holds from $1 - \sqrt{1 - \theta} = \frac{\theta}{1 + \sqrt{1 - \theta}} \le \theta$. This completes the proof. □

Denote

$$ (\Phi_M)_0 = \frac{(\theta n + 2\tau + 2\sqrt{2\tau n})}{2(1-\theta)} = L(n, \theta, \tau); \qquad (3.1k) $$

then $(\Phi_M)_0$ is an upper bound for $\Phi_M(v_+)$ during the process of the algorithm.

## 5. AN ESTIMATION FOR THE STEP SIZE

In this section, we compute the largest possible value for the step size $\alpha$ during an inner iteration. After a damped step we have

$$ \begin{aligned} x_+ &:= x + \alpha \Delta x; \\ s_+ &:= s + \alpha \Delta s; \\ y_+ &:= y + \alpha \Delta y; \end{aligned} $$

Using (2.6), we have

$$ \begin{aligned} x_+ &:= x \left(e + \alpha \frac{\Delta x}{x}\right) = x \left(e + \alpha \frac{d_x}{v}\right) = \frac{x}{v} \left(v + \alpha d_x\right), \\ s_+ &:= s \left(e + \alpha \frac{\Delta s}{s}\right) = s \left(e + \alpha \frac{d_s}{v}\right) = \frac{s}{v} \left(v + \alpha d_s\right), \end{aligned} $$

So, we have

$$ v_+ = \sqrt{\frac{x_+ s_+}{\mu}} = \sqrt{(v + \alpha d_x)(v + \alpha d_s)}. $$

Define, for $\alpha > 0$,

$$ f(\alpha) = \Phi_M(v_+) - \Phi_M(v). $$

Then $f(\alpha)$ is the difference of proximities between a new iterate and a current iterate for fixed $\mu$. By Lemma (3.2) (3.1d), we have

$$ \Phi_M(v_+) = \Phi_M\left(\sqrt{(v + \alpha d_x)(v + \alpha d_s)}\right) \le \frac{1}{2}\left(\Phi_M(v + \alpha d_x) + \Phi_M(v + \alpha d_s)\right). $$

Therefore, we have $f(\alpha) \le f_1(\alpha)$, where

$$ f_1(\alpha) = \frac{1}{2}(\Phi_M(v + \alpha d_x) + \Phi_M(v + \alpha d_s)) - \Phi_M(v). \qquad (3.11) $$

Obviously, $f(0) = f_1(0) = 0$. Taking the first two derivatives of $f_1(\alpha)$ with respect to $\alpha$, we have

$$ f'_1(\alpha) = \frac{1}{2} \sum_{i=1}^{n} (\psi'_M(v_i + \alpha d_{x_i}) d_{x_i} + \psi'_M(v_i + \alpha d_{s_i}) d_{s_i}), $$

$$ f_1''(\alpha) = \frac{1}{2} \sum_{i=1}^{n} (\psi_M''(v_i + \alpha d_{x_i}) d_{x_i}^2 + \psi_M''(v_i + \alpha d_{s_i}) d_{s_i}^2), $$

Using (2.8) and (2.11), we have

$$ f'_1(0) = \frac{1}{2} \nabla \Phi_M(v)^t (d_x + d_s) = -\frac{1}{2} \nabla \Phi_M(v)^t \nabla \Phi_M(v) = -2\delta^2(v). $$

For convenience, we denote

$$ v_1 = \min(v), \quad \delta := \delta(v), \quad \Phi_M = \Phi_M(v). $$
**Lemma 5.1.** Let $\delta(v)$ be as defined in (2.11). Then we have

$$ \delta(v) \geq \sqrt{\frac{1}{2} \Phi_M(v)}. $$

*Proof.* Using (3.1f), we have

$$ \Phi_M(v) = \sum_{i=1}^{n} \psi_M(v_i) \leq \sum_{i=1}^{n} \frac{1}{2} (\psi'_M(v_i))^2 = \frac{1}{2} \|\nabla \Phi_M(v)\|^2 = 2\delta^2(v), $$

so

$$ \delta(v) \geq \sqrt{\frac{1}{2} \Phi_M(v)}. $$

This completes the proof.

**Remark 5.2.** Throughout the paper, we assume that $\tau \geq 1$. Using Lemma 5.1 and the assumption that $\Phi_M(v) \geq \tau$, we have

$$ \delta(v) \geq \sqrt{\frac{1}{2}}. $$

From Lemmas 4.1–4.3 in [2]. We have the following Lemmas 5.3–5.5.

**Lemma 5.3.** Let $f_1(\alpha)$ be as defined in (3.1l) and $\delta(v)$ be as defined in (2.11). Then we have

$$ f_1''(\alpha) \leq 2\delta^2 \psi_M''(v_{\min} - 2\alpha\delta). $$

**Lemma 5.4.** If the step size $\alpha$ satisfies the inequality

$$ \psi_M'(v_{\min}) - \psi_M'(v_{\min} - 2\alpha\delta) \leq 2\delta, \qquad (3.1m) $$

Then

$$ f_1'(\alpha) \leq 0. $$

**Lemma 5.5.** Let $\rho: [0, +\infty[ \to ]0, 1]$ be the inverse function of $\frac{1}{2}\psi_M'(t)$ for all $t \in ]0, 1]$. Then the largest step size $\bar{\alpha}$ satisfying (3.1m) is given by

$$ \bar{\alpha} = \frac{1}{2\delta} (\rho(\delta) - \rho(2\delta)). $$

**Lemma 5.6.** Let $\rho$ and $\bar{\alpha}$ be as defined in Lemma 5.5. If $\Phi_M(v) \geq \tau \geq 1$, then we have

$$ \tilde{\alpha} = \frac{(4\delta + 1)^{-\frac{p+2}{p+1}}}{1 + \left( \begin{array}{c} pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) + \\ pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) [k(p,q)]^{\frac{2}{p+1}} \end{array} \right) \left[ \begin{array}{c} \left( (p-1)[k(p,q)]^{\frac{p-2}{p+1}} + \right) \left( \frac{q\pi}{4} \right)^2 + \\ [k(p,q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2 \end{array} \right]} $$

*Proof.* Using Lemma 4.4 in [2]. The definition of $\psi_M''(t)$, and (3.1j), we have

$$ \begin{aligned} \bar{\alpha} &\geq \frac{1}{\psi_M''(\rho(2\delta))} \\ &= \frac{1}{1 + \left( \begin{array}{c} pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) + \\ pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) \tan^2 u(\rho(2\delta)) \end{array} \right) \left[ \begin{array}{c} ((p-1) \tan^{p-2} u(\rho(2\delta)) + \\ (p+1) \tan^p u u'^2(\rho(2\delta)) + \\ (\tan^{p-1} u(\rho(2\delta))) u''(\rho(2\delta)) \end{array} \right]} \end{aligned} $$
**Lemma 5.1.** Let $\delta(v)$ be as defined in (2.11). Then we have

$$ \delta(v) \geq \sqrt{\frac{1}{2}\Phi_M(v)}. $$

*Proof.* Using (3.1f), we have

$$ \Phi_M(v) = \sum_{i=1}^{n} \psi_M(v_i) \leq \sum_{i=1}^{n} \frac{1}{2} (\psi'_M(v_i))^2 = \frac{1}{2} \|\nabla \Phi_M(v)\|^2 = 2\delta^2(v), $$

so

$$ \delta(v) \geq \sqrt{\frac{1}{2}\Phi_M(v)}. $$

This completes the proof.

**Remark 5.2.** Throughout the paper, we assume that $\tau \geq 1$. Using Lemma 5.1 and the assumption that $\Phi_M(v) \geq \tau$, we have

$$ \delta(v) \geq \sqrt{\frac{1}{2}}. $$

From Lemmas 4.1–4.3 in [2]. We have the following Lemmas 5.3–5.5.

**Lemma 5.3.** Let $f_1(\alpha)$ be as defined in (3.1l) and $\delta(v)$ be as defined in (2.11). Then we have

$$ f_1''(\alpha) \leq 2\delta^2 \psi_M''(v_{\min} - 2\alpha\delta). $$

**Lemma 5.4.** If the step size $\alpha$ satisfies the inequality

$$ \psi_M'(v_{\min}) - \psi_M'(v_{\min} - 2\alpha\delta) \leq 2\delta, \quad (3.1m) $$

Then

$$ f_1'(\alpha) \leq 0. $$

**Lemma 5.5.** Let $\rho: [0, +\infty[ \to ]0, 1]$ be the inverse function of $\frac{1}{2}\psi_M'(t)$ for all $t \in ]0, 1]$. Then the largest step size $\bar{\alpha}$ satisfying (3.1m) is given by

$$ \bar{\alpha} = \frac{1}{2\delta} (\rho(\delta) - \rho(2\delta)). $$

**Lemma 5.6.** Let $\rho$ and $\bar{\alpha}$ be as defined in Lemma 5.5. If $\Phi_M(v) \geq \tau \geq 1$, then we have

$$ \tilde{\alpha} = \frac{(4\delta + 1)^{-\frac{p+2}{p+1}}}{1 + \left( \begin{array}{c} pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) + \\ pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) [k(p,q)]^{\frac{2}{p+1}} \end{array} \right) \left[ \begin{array}{c} \left( (p-1)[k(p,q)]^{\frac{p-2}{p+1}} + \right) \left( \frac{q\pi}{4} \right)^2 + \\ [k(p,q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2 \end{array} \right]} $$

*Proof.* Using Lemma 4.4 in [2]. The definition of $\psi_M''(t)$, and (3.1j), we have

$$ \begin{aligned} \bar{\alpha} &\geq \frac{1}{\psi_M''(\rho(2\delta))} \\ &= \frac{1}{1 + \left( \begin{array}{c} pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) + \\ pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) \tan^2 u(\rho(2\delta)) \end{array} \right) \left[ \begin{array}{c} ((p-1) \tan^{p-2} u(\rho(2\delta)) + \\ (p+1) \tan^p u u'^2(\rho(2\delta)) + \\ (\tan^{p-1} u(\rho(2\delta))) u''(\rho(2\delta)) \end{array} \right]} \end{aligned} $$
And for $\rho(2\delta) = t \in ]0, 1]$, we have

$$ (u'(t))^2 = \frac{(q\pi)^2}{(qt + 2)^4} \le \frac{(q\pi)^2}{(2)^4} \le \left(\frac{q\pi}{4}\right)^2 $$

$$ u''(t) = \frac{2\pi q^2}{(qt + 2)^3} \le \frac{2\pi q^2}{(2)^3} \le \pi\left(\frac{q}{2}\right)^2 $$

for $z = 2\delta$ we have

$$ \tan^2 u(\rho(2\delta)) \le [k(p, q)(4\delta + 1)]^{\frac{2}{p+1}} $$

$$ \tan^{p-2} u(\rho(2\delta)) \le [k(p, q)(4\delta + 1)]^{\frac{p-2}{p+1}} $$

$$ \tan^{p-1} u(\rho(2\delta)) \le [k(p, q)(4\delta + 1)]^{\frac{p-1}{p+1}} $$

$$ \tan^p u(\rho(2\delta)) \le [k(p, q)(4\delta + 1)]^{\frac{p}{p+1}} $$

and

$$ k(p, q) = \tan^{p-1}\left(\frac{\pi}{q+2}\right) + \tan^{p+1}\left(\frac{\pi}{q+2}\right) $$

this implies

$$ \tilde{\alpha} \ge \frac{(4\delta + 1)^{-\frac{p}{p+1}}}{1 + \left( \begin{array}{l} pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) + \\ pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) [k(p, q)(4\delta + 1)]^{\frac{2}{p+1}} \end{array} \right) \left[ \begin{array}{l} \left( (p-1)[k(p, q)]^{\frac{p-2}{p+1}} + \right) \left( \frac{q\pi}{4} \right)^2 + \\ [k(p, q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2 \end{array} \right]} $$

Since $4\delta + 1 \ge 1$, we have

$$ \tilde{\alpha} \ge \frac{(4\delta + 1)^{-\frac{p+2}{p+1}}}{1 + \left( \begin{array}{l} pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) + \\ pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) [k(p, q)]^{\frac{2}{p+1}} \end{array} \right) \left[ \begin{array}{l} \left( (p-1)[k(p, q)]^{\frac{p-2}{p+1}} + \right) \left( \frac{q\pi}{4} \right)^2 + \\ [k(p, q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2 \end{array} \right]} $$

This completes the proof.

□

Denoting

$$ \tilde{\alpha} = \frac{(4\delta+1)^{-\frac{p+2}{p+1}}}{1 + \left( pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) + \right) \left[ \begin{array}{l} \left( (p-1)[k(p, q)]^{\frac{p-2}{p+1}} + \right) \left( \frac{q\pi}{4} \right)^2 + \\ [k(p, q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2 \end{array} \right]} \quad (3.1n) $$

we have that $\tilde{\alpha}$ is the default step size and that $\tilde{\alpha} \le \bar{\alpha}$. From Lemma 1.3.3 in [13]. We can get the following lemma.

**Lemma 5.7.** Suppose that $h(t)$ is a twice differentiable convex function with

$$ h(0) = 0, \quad h'(0) < 0, $$
And for $\rho(2\delta) = t \in ]0, 1]$, we have

$$ (u'(t))^2 = \frac{(q\pi)^2}{(qt + 2)^4} \le \frac{(q\pi)^2}{(2)^4} \le \left(\frac{q\pi}{4}\right)^2 $$

$$ u''(t) = \frac{2\pi q^2}{(qt + 2)^3} \le \frac{2\pi q^2}{(2)^3} \le \pi(\frac{q}{2})^2 $$

for $z = 2\delta$ we have

$$ \tan^2 u(\rho(2\delta)) \le [k(p, q)(4\delta + 1)]^{\frac{2}{p+1}} $$

$$ \tan^{p-2} u(\rho(2\delta)) \le [k(p, q)(4\delta + 1)]^{\frac{p-2}{p+1}} $$

$$ \tan^{p-1} u(\rho(2\delta)) \le [k(p, q)(4\delta + 1)]^{\frac{p-1}{p+1}} $$

$$ \tan^p u(\rho(2\delta)) \le [k(p, q)(4\delta + 1)]^{\frac{p}{p+1}} $$

and

$$ k(p, q) = \tan^{p-1}\left(\frac{\pi}{q+2}\right) + \tan^{p+1}\left(\frac{\pi}{q+2}\right) $$

this implies

$$ \tilde{\alpha} \ge \frac{(4\delta + 1)^{-\frac{p}{p+1}}}{1 + \left( \begin{array}{l} pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) + \\ pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) [k(p, q)(4\delta + 1)]^{\frac{2}{p+1}} \end{array} \right) \left[ \begin{array}{l} \left( (p-1)[k(p, q)]^{\frac{p-2}{p+1}} + \right) \left( \frac{q\pi}{4} \right)^2 + \\ [k(p, q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2 \end{array} \right]} $$

Since $4\delta + 1 \ge 1$, we have

$$ \tilde{\alpha} \ge \frac{(4\delta + 1)^{-\frac{p+2}{p+1}}}{1 + \left( \begin{array}{l} pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) + \\ pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) [k(p, q)]^{\frac{2}{p+1}} \end{array} \right) \left[ \begin{array}{l} \left( (p-1)[k(p, q)]^{\frac{p-2}{p+1}} + \right) \left( \frac{q\pi}{4} \right)^2 + \\ [k(p, q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2 \end{array} \right]} $$

This completes the proof.

<figure><img src="image_5.png" /></figure>

Denoting

$$ \tilde{\alpha} = \frac{(4\delta+1)^{-\frac{p+2}{p+1}}}{1 + \left( pm(p, q) \cot^p \left( \frac{\pi}{q+2} \right) + \right) \left[ \begin{array}{l} \left( (p-1)[k(p, q)]^{\frac{p-2}{p+1}} + \right) \left( \frac{q\pi}{4} \right)^2 + \\ [k(p, q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2 \end{array} \right]} \quad (3.1n) $$

we have that $\tilde{\alpha}$ is the default step size and that $\tilde{\alpha} \le \bar{\alpha}$. From Lemma 1.3.3 in [13]. We can get the following lemma.

**Lemma 5.7.** Suppose that $h(t)$ is a twice differentiable convex function with

$$ h(0) = 0, \quad h'(0) < 0, $$
that $h(t)$ attains its global minimum at $t^* > 0$ and that $h''(t)$ is increasing with respect to $t$. Then, for any $t \in [0, t^*$], we have

$$h(t) \leq \frac{th'(0)}{2}.$$

Let the univariate function $h$ be such that

$$h(0) = f_1(0) = 0, h'(0) = f'_1(0) = -2\delta^2, h''(\alpha) = 2\delta^2\psi_M''(v_{\min} - 2\alpha\delta).$$

**Lemma 5.8.** Let $\tilde{\alpha}$ be the default step size as defined in (3.1o) and let

$$\Phi_M(v) \geq 1.$$

Then

$$f(\tilde{\alpha}) \leq -\frac{g(p,q)\sqrt{2}}{2} [\Phi_M(v)]^{\frac{p}{2(p+1)}}. \qquad (3.1o)$$

where

$$g(p,q) = \frac{6^{-\frac{p+2}{p+1}}}{1 + pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) \left(1 + \frac{1}{[k(p,q)]^{\frac{2}{p+1}}}\right) \left[ \begin{array}{l} \left( (p-1)[k(p,q)]^{\frac{p-2}{p+1}} + (p+1)[k(p,q)]^{\frac{p}{p+1}} \right) \left(\frac{q\pi}{4}\right)^2 + \\ [k(p,q)]^{\frac{p-1}{p+1}} \pi \frac{q^2}{2} \end{array} \right]}$$

*Proof.* Using Lemma 4.5 in [2]. And if the step size $\alpha$ satisfies $\alpha \le \tilde{\alpha}$, then $f(\alpha) \le -\alpha\delta^2$. So, for $\tilde{\alpha} \le \tilde{\alpha}$, we have

$$f(\tilde{\alpha}) \le -\tilde{\alpha}\delta^2$$

and

$$\tilde{\alpha} = \frac{(4\delta+1)^{-\frac{p+2}{p+1}}}{1+pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) \left(1 + \frac{1}{[k(p,q)]^{\frac{2}{p+1}}}\right) \left[ \begin{array}{l} \left( (p-1)[k(p,q)]^{\frac{p-2}{p+1}} + (p+1)[k(p,q)]^{\frac{p}{p+1}} \right) \left(\frac{q\pi}{4}\right)^2 + \\ [k(p,q)]^{\frac{p-1}{p+1}} \pi \frac{q^2}{2} \end{array} \right]}$$

$$\geq \frac{(6)^{-\frac{p+2}{p+1}} \delta^{-\frac{p+2}{p+1}}}{1+pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) \left(1 + \frac{1}{[k(p,q)]^{\frac{2}{p+1}}}\right) \left[ \begin{array}{l} \left( (p-1)[k(p,q)]^{\frac{p-2}{p+1}} + (p+1)[k(p,q)]^{\frac{p}{p+1}} \right) \left(\frac{q\pi}{4}\right)^2 + \\ [k(p,q)]^{\frac{p-1}{p+1}} \pi \frac{q^2}{2} \end{array} \right]}$$

$$g(p,q) = \frac{6^{-\frac{p+2}{p+1}}}{1 + \left( pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) + pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) [k(p,q)]^{\frac{2}{p+1}} \right) \left[ \begin{array}{l} \left( (p-1)[k(p,q)]^{\frac{p-2}{p+1}} + (p+1)[k(p,q)]^{\frac{p}{p+1}} \right) \left(\frac{q\pi}{4}\right)^2 + \\ [k(p,q)]^{\frac{p-1}{p+1}} \pi \frac{q^2}{2} \end{array} \right]}$$
that $h(t)$ attains its global minimum at $t^* > 0$ and that $h''(t)$ is increasing with respect to $t$. Then, for any $t \in [0, t^*]$, we have

$$h(t) \leq \frac{th'(0)}{2}.$$

Let the univariate function $h$ be such that

$$h(0) = f_1(0) = 0, h'(0) = f'_1(0) = -2\delta^2, h''(\alpha) = 2\delta^2\psi_M''(v_{\min} - 2\alpha\delta).$$

**Lemma 5.8.** Let $\tilde{\alpha}$ be the default step size as defined in (3.1o) and let

$$\Phi_M(v) \geq 1.$$

Then

$$f(\tilde{\alpha}) \leq -\frac{g(p, q)\sqrt{2}}{2} [\Phi_M(v)]^{\frac{p}{2(p+1)}}. \quad (3.1o)$$

where

$$g(p, q) = \frac{6^{-\frac{p+2}{p+1}}}{1 + pm(p, q) \cot^p\left(\frac{\pi}{q+2}\right) \left(1 + \left[k(p, q)\right]^{\frac{2}{p+1}}\right) \left[ \begin{array}{l} \left( (p-1)[k(p, q)]^{\frac{p-2}{p+1}} + (p+1)[k(p, q)]^{\frac{p}{p+1}} \right) \left(\frac{q\pi}{4}\right)^2 + \\ \left[k(p, q)\right]^{\frac{p-1}{p+1}} \pi \frac{q^2}{2} \end{array} \right]}$$

*Proof.* Using Lemma 4.5 in [2]. And if the step size $\alpha$ satisfies $\alpha \le \tilde{\alpha}$, then $f(\alpha) \le -\alpha\delta^2$. So, for $\tilde{\alpha} \le \tilde{\alpha}$, we have

$$f(\tilde{\alpha}) \leq -\tilde{\alpha}\delta^2$$

and

$$\tilde{\alpha} = \frac{(4\delta+1)^{-\frac{p+2}{p+1}}}{1+pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) \left(1+\left[k(p,q)\right]^{\frac{2}{p+1}}\right) \left[ \begin{array}{l} \left( (p-1)[k(p,q)]^{\frac{p-2}{p+1}} + (p+1)[k(p,q)]^{\frac{p}{p+1}} \right) \left(\frac{q\pi}{4}\right)^2 + \\ \left[k(p,q)\right]^{\frac{p-1}{p+1}} \pi \frac{q^2}{2} \end{array} \right]}$$

$$\geq \frac{(6)^{-\frac{p+2}{p+1}} \delta^{-\frac{p+2}{p+1}}}{1+pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right) \left(1+\left[k(p,q)\right]^{\frac{2}{p+1}}\right) \left[ \begin{array}{l} \left( (p-1)[k(p,q)]^{\frac{p-2}{p+1}} + (p+1)[k(p,q)]^{\frac{p}{p+1}} \right) \left(\frac{q\pi}{4}\right)^2 + \\ \left[k(p,q)\right]^{\frac{p-1}{p+1}} \pi \frac{q^2}{2} \end{array} \right]}$$

$$g(p, q) = \frac{6^{-\frac{p+2}{p+1}}}{1 + \left( pm(p, q) \cot^p\left(\frac{\pi}{q+2}\right) + pm(p, q) \cot^p\left(\frac{\pi}{q+2}\right) \left[k(p, q)\right]^{\frac{2}{p+1}} \right) \left[ \begin{array}{l} \left( (p-1)[k(p, q)]^{\frac{p-2}{p+1}} + (p+1)[k(p, q)]^{\frac{p}{p+1}} \right) \left(\frac{q\pi}{4}\right)^2 + \\ \left[k(p, q)\right]^{\frac{p-1}{p+1}} \pi \frac{q^2}{2} \end{array} \right]}$$
$$
\begin{align*}
f(\tilde{\alpha}) &\leq -\tilde{\alpha}\delta^2 \\
&\leq -\frac{g(p,q)\delta^2}{\delta^{\frac{p+2}{p+1}}} \\
&= -g(p,q)\delta^{2-\frac{p+2}{p+1}} \\
&= -g(p,q)\delta^{\frac{p}{p+1}} \\
&\leq -\frac{g(p,q)\sqrt{2}}{2} [\Phi_M(v)]^{\frac{p}{2(p+1)}} \\
&\leq -\frac{g(p,q)\sqrt{2}}{2} [(\Phi_M)_0]^{\frac{p}{2(p+1)}}
\end{align*}
$$

because

$$
\begin{aligned}
\delta &\geq \sqrt{\frac{1}{2}\Phi_M(v)} \\
&\geq \sqrt{\frac{1}{2}} \\
&> \frac{1}{2}.
\end{aligned}
$$

This completes the proof.

<figure><img src="image_6.png" /></figure>

6. ITERATION BOUND

In this section, the worst iteration complexity bounds for primal-dual **IPMs** based on the proposed kernel function are computed.

**6.1. Inner iteration bound**

After the update of $\mu$ to $(1 - \theta) \mu$, we have

$$
\Phi_M(v_+) \le (\Phi_M)_0 = \frac{(\theta n + 2\tau + 2\sqrt{2\tau n})}{2(1-\theta)} = L(n, \theta, \tau).
$$

We need to count how many inner iterations are required to return to the situation where $\Phi_M(v) \le \tau$. We denote the value of $\Phi_M(v)$ after the $\mu$ update as $(\Phi_M)_0$; the subsequent values in the same outer iteration are denoted as $(\Phi_M)_k$, $k = 1, 2, \dots, K$, where $K$ denotes the total number of inner iterations in the outer iteration. The decrease in each inner iteration is given by (3.1p). In [2]. We can find the appropriate values of $\kappa$ and $\gamma \in [0, 1]$:

$$
\kappa = \frac{g(p,q)\sqrt{2}}{2}, \quad \gamma = 1 - \frac{p}{2(p+1)} = \frac{p+2}{2(p+1)}.
$$

**Lemma 6.1.** Let $K$ be the total number of inner iterations in the outer iteration. Then we have

$$
K \le \left( \frac{4(p+1)}{g(p,q)\sqrt{2}(p+2)} \right) (\Phi_M)_0^{\frac{p+2}{2(p+1)}}.
$$

*Proof.* By Lemma 1.3.2 in [10]. We have $K \le \frac{(\Phi_M)_0^\gamma}{\kappa\gamma} = \left(\frac{4(p+1)}{g(p,q)\sqrt{2}(p+2)}\right) (\Phi_M)_0^{\frac{p+2}{2(p+1)}}$.
This completes the proof. $\square$

<figure><img src="image_7.png" /></figure>
$$ 
\begin{aligned}
f(\tilde{\alpha}) & \leq -\tilde{\alpha}\delta^2 \\
& \leq -\frac{g(p, q)\delta^2}{\delta^{\frac{p+2}{p+1}}} \\
& = -g(p, q)\delta^{2-\frac{p+2}{p+1}} \\
& = -g(p, q)\delta^{\frac{p}{p+1}} \\
& \leq -\frac{g(p, q)\sqrt{2}}{2} [\Phi_M(v)]^{\frac{p}{2(p+1)}} \\
& \leq -\frac{g(p, q)\sqrt{2}}{2} [(\Phi_M)_0]^{\frac{p}{2(p+1)}}
\end{aligned}
$$

because

$$ 
\begin{aligned}
\delta & \geq \sqrt{\frac{1}{2}\Phi_M(v)} \\
& \geq \sqrt{\frac{1}{2}} \\
& > \frac{1}{2}.
\end{aligned}
$$

This completes the proof.

<figure><img src="image_6.png" /></figure>

## 6. ITERATION BOUND

In this section, the worst iteration complexity bounds for primal-dual IPMs based on the proposed kernel function are computed.

### 6.1. Inner iteration bound

After the update of $\mu$ to $(1 - \theta)\mu$, we have

$$ \Phi_M(v_+) \leq (\Phi_M)_0 = \frac{(\theta n + 2\tau + 2\sqrt{2\tau n})}{2(1-\theta)} = L(n, \theta, \tau). $$

We need to count how many inner iterations are required to return to the situation where $\Phi_M(v) \leq \tau$. We denote the value of $\Phi_M(v)$ after the $\mu$ update as $(\Phi_M)_0$; the subsequent values in the same outer iteration are denoted as $(\Phi_M)_k$, $k = 1, 2, \dots, K$, where $K$ denotes the total number of inner iterations in the outer iteration. The decrease in each inner iteration is given by (3.1p). In [2]. We can find the appropriate values of $\kappa$ and $\gamma \in [0, 1]$:

$$ \kappa = \frac{g(p, q)\sqrt{2}}{2}, \quad \gamma = 1 - \frac{p}{2(p+1)} = \frac{p+2}{2(p+1)}. $$

**Lemma 6.1.** Let $K$ be the total number of inner iterations in the outer iteration. Then we have

$$ K \leq \left( \frac{4(p+1)}{g(p,q)\sqrt{2}(p+2)} \right) (\Phi_M)_0^{\frac{p+2}{2(p+1)}}. $$

*Proof.* By Lemma 1.3.2 in [10]. We have $K \leq \frac{(\Phi_M)_0^\gamma}{\kappa\gamma} = \left(\frac{4(p+1)}{g(p,q)\sqrt{2}(p+2)}\right) (\Phi_M)_0^{\frac{p+2}{2(p+1)}}$.

This completes the proof.

<figure><img src="image_7.png" /></figure>
## 6.2. Total iteration bound

The number of outer iterations is bounded above by $\frac{\log \frac{n}{\epsilon}}{\theta}$ (see [13]). Lemma 3.2. 17, page 116). Through multiplying the number of outer iterations by the number of inner iterations, we get an upper bound for the total number of iterations, namely,

$$ \left( \frac{4(p+1)}{g(p,q)\sqrt{2}(p+2)} \right) (\Phi_M)_0^{\frac{p+2}{2(p+1)}} \frac{\log \frac{n}{\epsilon}}{\theta}. \quad (3.1p) $$

For large-update methods with $\tau = O(n)$ and $\theta = \Theta(1)$ we have

$O\left(\frac{1}{g(p,q)} n^{\frac{p+2}{2(p+1)}} \log \frac{n}{\epsilon}\right)$ iteration complexity.

In case of a small-update methods, we have $\tau = O(1)$ and $\theta = \Theta(\frac{1}{\sqrt{n}})$. Substitution of these values into (k) does not give the best possible bound. A better bound is obtained as follows.

By (3.1g), with

$$ \psi_M(t) \le \frac{1}{2} \varphi(p,q) (t-1)^2, \quad t > 1, $$

we have

$$
\begin{aligned}
\Phi_M(v_+) &\le n\psi_M\left(\frac{1}{\sqrt{1-\theta}}\sigma\left(\frac{\Phi_M(v_+)}{n}\right)\right) \\
&\le \frac{n\varphi(p,q)}{2}\left(\frac{1}{\sqrt{1-\theta}}\sigma\left(\frac{\Phi_M(v_+)}{n}\right) - 1\right)^2 \\
&= \frac{n(8+\pi)}{8(1-\theta)}\left(\sigma\left(\frac{\Phi_M(v_+)}{n}\right) - \sqrt{1-\theta}\right)^2 \\
&\le \frac{n\varphi(p,q)}{2(1-\theta)}\left(\left(1 + \sqrt{2\frac{\Phi_M(v_+)}{n}}\right) - \sqrt{1-\theta}\right)^2 \\
&= \frac{n\varphi(p,q)}{2(1-\theta)}\left(\left(1 - \sqrt{1-\theta}\right) + \sqrt{2\frac{\Phi_M(v_+)}{n}}\right)^2 \\
&\le \frac{n\varphi(p,q)}{2(1-\theta)}\left(\theta + \sqrt{2\frac{\tau}{n}}\right)^2 \\
&= \frac{\varphi(p,q)}{2(1-\theta)}\left(\theta\sqrt{n} + \sqrt{2\tau}\right)^2 = (\Phi_M)_0.
\end{aligned}
$$

where we also used that $1 - \sqrt{1 - \theta} = \frac{\theta}{1 + \sqrt{1 - \theta}} \le \theta$ and $\Phi_M(v) \le \tau$, using this upper bound for $(\Phi_M)_0$, we get the following iteration bound:

$$ \left( \frac{4(p+1)}{g(p,q)\sqrt{2}(p+2)} \right) (\Phi_M)_0^{\frac{p+2}{2(p+1)}} \frac{\log \frac{n}{\epsilon}}{\theta}. $$

Now, we note that $(\Phi_M)_0 = O(1)$, and the iteration bound becomes

$$ O\left(\frac{[\varphi(p,q)]^{\frac{p+2}{2(p+1)}}}{g(p,q)\sqrt{n}\log\frac{n}{\epsilon}}\right) \text{ iteration complexity.} $$
## 6.2. Total iteration bound

The number of outer iterations is bounded above by $\frac{\log \frac{n}{\epsilon}}{\theta}$ (see [13]). Lemma 3.2. 17, page 116). Through multiplying the number of outer iterations by the number of inner iterations, we get an upper bound for the total number of iterations, namely,

$$ \left( \frac{4(p+1)}{g(p,q)\sqrt{2}(p+2)} \right) (\Phi_M)_0^{\frac{p+2}{2(p+1)}} \frac{\log \frac{n}{\epsilon}}{\theta}. \qquad (3.1p) $$

For large-update methods with $\tau = O(n)$ and $\theta = \Theta(1)$ we have

$O\left(\frac{1}{g(p,q)} n^{\frac{p+2}{2(p+1)}} \log \frac{n}{\epsilon}\right)$ iteration complexity.

In case of a small-update methods, we have $\tau = O(1)$ and $\theta = \Theta(\frac{1}{\sqrt{n}})$. Substitution of these values into (k) does not give the best possible bound. A better bound is obtained as follows.

By (3.1g), with

$$ \psi_M(t) \le \frac{1}{2} \varphi(p,q) (t-1)^2, \quad t > 1, $$

we have

$$
\begin{aligned}
\Phi_M(v_+) &\le n\psi_M\left(\frac{1}{\sqrt{1-\theta}}\sigma\left(\frac{\Phi_M(v)}{n}\right)\right) \\
&\le \frac{n\varphi(p,q)}{2}\left(\frac{1}{\sqrt{1-\theta}}\sigma\left(\frac{\Phi_M(v)}{n}\right) - 1\right)^2 \\
&= \frac{n(8+\pi)}{8(1-\theta)}\left(\sigma\left(\frac{\Phi_M(v)}{n}\right) - \sqrt{1-\theta}\right)^2 \\
&\le \frac{n\varphi(p,q)}{2(1-\theta)}\left(\left(1+\sqrt{2\frac{\Phi_M(v)}{n}}\right) - \sqrt{1-\theta}\right)^2 \\
&= \frac{n\varphi(p,q)}{2(1-\theta)}\left(\left(1-\sqrt{1-\theta}\right) + \sqrt{2\frac{\Phi_M(v)}{n}}\right)^2 \\
&\le \frac{n\varphi(p,q)}{2(1-\theta)}\left(\theta + \sqrt{2\frac{\tau}{n}}\right)^2 \\
&= \frac{\varphi(p,q)}{2(1-\theta)}\left(\theta\sqrt{n} + \sqrt{2\tau}\right)^2 = (\Phi_M)_0.
\end{aligned}
$$

where we also used that $1 - \sqrt{1-\theta} = \frac{\theta}{1+\sqrt{1-\theta}} \le \theta$ and $\Phi_M(v) \le \tau$, using this upper bound for $(\Phi_M)_0$, we get the following iteration bound:

$$ \left( \frac{4(p+1)}{g(p,q)\sqrt{2}(p+2)} \right) (\Phi_M)_0^{\frac{p+2}{2(p+1)}} \frac{\log \frac{n}{\epsilon}}{\theta}. $$

Now, we note that $(\Phi_M)_0 = O(1)$, and the iteration bound becomes

$$ O\left(\frac{[\varphi(p,q)]^{\frac{p+2}{2(p+1)}}}{g(p,q)\sqrt{n}\log \frac{n}{\epsilon}}\right) \text{ iteration complexity.} $$
## 7. COMPARISON OF ALGORITHMS

In this section, we present a comparison of our algorithm [3] with our new results given in this paper. To prove the effectiveness of our new kernel function and evaluate its effect on the behavior of the algorithm, we offer a comparative study between the results obtained by the considered algorithms, essentially based on the two following kernel functions.

1) The first kernel function, given by M. Bouafia and A. Yassine in [3], defined by

$$ \psi_B(t) = t^2 + \frac{t^{1-q}}{q-1} - \frac{q}{q-1} + \frac{4}{\pi p} [\tan^p h(t) - 1], \quad \begin{cases} h(t) = \frac{\pi}{2t+2}, \\ p \ge 2, q > 1. \end{cases} $$

And the default stepsize

$$ \alpha_B = \frac{1}{(4p\pi + 11)(8\delta + 2)^{\frac{(p+2)(q+2)}{(p+1)q}}}. $$

2) Our new kernel function defined in (3.1) by

$$ \psi_M(t) = \frac{t^2 - 1}{2} + m(p, q) \left[ \cot^p \left( \frac{\pi}{q+2} \right) \tan^p u(t) - 1 \right], \quad p \ge 2, q > 0. $$

And the default stepsize

$$ \alpha_M = \frac{(4\delta + 1)^{-\frac{p+2}{p+1}}}{1 + \left( \frac{pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right)}{[k(p,q)]^{\frac{2}{p+1}}} + \right) \left[ \left( \frac{(p-1)[k(p,q)]^{\frac{p-2}{p+1}}}{(p+1)[k(p,q)]^{\frac{p}{p+1}}} + \right) \left( \frac{q\pi}{4} \right)^2 + \right] [k(p,q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2} $$

### 7.1. Numerical Tests

Consider the following problem

$$ n = 2m, A(i,j) = \begin{cases} 0 & \text{if } i \neq j \text{ and } j \neq i+m \\ 1 & \text{if } i=j \text{ or } j=i+m \end{cases} $$

$c(i) = -1, c(i+m) = 0, b(i) = 2$, and the interior-point condition **IPC**, $x^0(i) = x^0(i+m) = 1, y^0(i) = -2, s^0(i) = 1, s^0(i+m) = 2$ for $i = 1, \dots, m$.

To prove the effectiveness of our new kernel function and evaluate its effect on the behavior of the algorithm, we conducted comparative numerical tests between the two previous kernel functions.

To be solved, we used the Software Dev Pascal. We have taken $\epsilon = 10^{-4}$, $\mu^0 = 1$, $\theta = \frac{1}{2}$, $\tau = n$, $(p, q) \in \{(2, 2), (2, 2.4), (2, 6), (6, 2), (\frac{\log n}{2} - 1, 2), (\log n, \log n)\}$.

We have the step size $\alpha$, satisfying $0 < \alpha < \bar{\alpha}$: we take respectively, $\alpha_B$ and $\alpha_M$, which match with the notation of precedent kernel functions.

In the table of results, $(\text{ex}(m, n))$: $m$ is the number of constraints and $n$ is the number of variables, $\text{Med}\psi_A = \text{total iteration}$ represent the median value of the number of internal iterations using the function $\psi_A$. We summarize this numerical study in Tables 1, 2, 3, 4, 5 and 6.
## 7. COMPARISON OF ALGORITHMS

In this section, we present a comparison of our algorithm [3] with our new results given in this paper. To prove the effectiveness of our new kernel function and evaluate its effect on the behavior of the algorithm, we offer a comparative study between the results obtained by the considered algorithms, essentially based on the two following kernel functions.

1) The first kernel function, given by M. Bouafia and A. Yassine in [3], defined by

$$ \psi_B(t) = t^2 + \frac{t^{1-q}}{q-1} - \frac{q}{q-1} + \frac{4}{\pi p} [\tan^p h(t) - 1], \quad \begin{cases} h(t) = \frac{\pi}{2t+2}, \\ p \ge 2, q > 1. \end{cases} $$

And the default stepsize

$$ \alpha_B = \frac{1}{(4p\pi + 11)(8\delta + 2)^{\frac{(p+2)(q+2)}{(p+1)q}}}. $$

2) Our new kernel function defined in (3.1) by

$$ \psi_M(t) = \frac{t^2 - 1}{2} + m(p, q) \left[ \cot^p \left( \frac{\pi}{q+2} \right) \tan^p u(t) - 1 \right], \quad p \ge 2, q > 0. $$

And the default stepsize

$$ \alpha_M = \frac{(4\delta + 1)^{-\frac{p+2}{p+1}}}{1 + \left( \frac{pm(p,q) \cot^p\left(\frac{\pi}{q+2}\right)}{[k(p,q)]^{\frac{2}{p+1}}} + \right) \left[ \left( \frac{(p-1)[k(p,q)]^{\frac{p-2}{p+1}}}{(p+1)[k(p,q)]^{\frac{p}{p+1}}} + \right) \left( \frac{q\pi}{4} \right)^2 + \right] [k(p,q)]^{\frac{p-1}{p+1}} \pi(\frac{q}{2})^2} $$

### 7.1. Numerical Tests

Consider the following problem

$$ n = 2m, A(i,j) = \begin{cases} 0 & \text{if } i \neq j \text{ and } j \neq i+m \\ 1 & \text{if } i=j \text{ or } j=i+m \end{cases} $$

$c(i) = -1, c(i+m) = 0, b(i) = 2$, and the interior-point condition **IPC**, $x^0(i) = x^0(i+m) = 1, y^0(i) = -2, s^0(i) = 1, s^0(i+m) = 2$ for $i = 1, \dots, m$.

To prove the effectiveness of our new kernel function and evaluate its effect on the behavior of the algorithm, we conducted comparative numerical tests between the two previous kernel functions.

To be solved, we used the Software Dev Pascal. We have taken $\epsilon = 10^{-4}$, $\mu^0 = 1$, $\theta = \frac{1}{2}$, $\tau = n$, $(p, q) \in \{(2, 2), (2, 2.4), (2, 6), (6, 2), (\frac{\log n}{2} - 1, 2), (\log n, \log n)\}$.

We have the step size $\alpha$, satisfying $0 < \alpha < \bar{\alpha}$: we take respectively, $\alpha_B$ and $\alpha_M$, which match with the notation of precedent kernel functions.

In the table of results, $(\text{ex}(m, n))$: $m$ is the number of constraints and $n$ is the number of variables, $\text{Med}\psi_A = \text{total iteration}$ represent the median value of the number of internal iterations using the function $\psi_A$. We summarize this numerical study in Tables 1, 2, 3, 4, 5 and 6.
<table><caption>TABLE 1. Comparison of examples for $p = 2$ and $q = 2$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(5, 10)</td><td>22523.40</td><td>150.85</td></tr><tr><td>(25, 50)</td><td>108900.59</td><td>152.64</td></tr><tr><td>(50, 100)</td><td>216505.48</td><td>153.39</td></tr><tr><td>(75, 150)</td><td>-</td><td>154.13</td></tr><tr><td>(100, 200)</td><td>-</td><td>154.13</td></tr></tbody></table>

<table><caption>TABLE 2. Comparison of examples for $p = 2$ and $q = 2.4$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(5, 10)</td><td>14676.3</td><td>149.80</td></tr><tr><td>(25, 50)</td><td>65074.60</td><td>151.59</td></tr><tr><td>(50, 100)</td><td>124571.22</td><td>152.35</td></tr><tr><td>(75, 150)</td><td>-</td><td>153.08</td></tr><tr><td>(100, 200)</td><td>-</td><td>153.08</td></tr></tbody></table>

<table><caption>TABLE 3. Comparison of examples for $p = 2$ and $q = 6$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(5, 10)</td><td>3926.40</td><td>338.35</td></tr><tr><td>(25, 50)</td><td>13421.32</td><td>342.36</td></tr><tr><td>(50, 100)</td><td>22932.83</td><td>344.09</td></tr><tr><td>(75, 150)</td><td>-</td><td>345.71</td></tr><tr><td>(100, 200)</td><td>-</td><td>345.71</td></tr></tbody></table>

<table><caption>TABLE 4. Comparison of examples for $p = 6$ and $q = 2$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(5, 10)</td><td>17950.40</td><td>2379.40</td></tr><tr><td>(25, 50)</td><td>69491.32</td><td>3717.91</td></tr><tr><td>(50, 100)</td><td>125356.48</td><td>4526.61</td></tr><tr><td>(75, 150)</td><td>-</td><td>5091.46</td></tr><tr><td>(100, 200)</td><td>-</td><td>5518.38</td></tr></tbody></table>

<table><caption>TABLE 5. Comparison of examples for $p = \frac{\log n}{2} - 1$ and $q = 2$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(25, 50)</td><td>236088.32</td><td>11.36</td></tr><tr><td>(50, 100)</td><td>346067.00</td><td>30.91</td></tr><tr><td>(75, 150)</td><td>-</td><td>51.67</td></tr><tr><td>(100, 200)</td><td>-</td><td>72.42</td></tr></tbody></table>
<table><caption>TABLE 1. Comparison of examples for $p = 2$ and $q = 2$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(5, 10)</td><td>22523.40</td><td>150.85</td></tr><tr><td>(25, 50)</td><td>108900.59</td><td>152.64</td></tr><tr><td>(50, 100)</td><td>216505.48</td><td>153.39</td></tr><tr><td>(75, 150)</td><td>-</td><td>154.13</td></tr><tr><td>(100, 200)</td><td>-</td><td>154.13</td></tr></tbody></table>

<table><caption>TABLE 2. Comparison of examples for $p = 2$ and $q = 2.4$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(5, 10)</td><td>14676.3</td><td>149.80</td></tr><tr><td>(25, 50)</td><td>65074.60</td><td>151.59</td></tr><tr><td>(50, 100)</td><td>124571.22</td><td>152.35</td></tr><tr><td>(75, 150)</td><td>-</td><td>153.08</td></tr><tr><td>(100, 200)</td><td>-</td><td>153.08</td></tr></tbody></table>

<table><caption>TABLE 3. Comparison of examples for $p = 2$ and $q = 6$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(5, 10)</td><td>3926.40</td><td>338.35</td></tr><tr><td>(25, 50)</td><td>13421.32</td><td>342.36</td></tr><tr><td>(50, 100)</td><td>22932.83</td><td>344.09</td></tr><tr><td>(75, 150)</td><td>-</td><td>345.71</td></tr><tr><td>(100, 200)</td><td>-</td><td>345.71</td></tr></tbody></table>

<table><caption>TABLE 4. Comparison of examples for $p = 6$ and $q = 2$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(5, 10)</td><td>17950.40</td><td>2379.40</td></tr><tr><td>(25, 50)</td><td>69491.32</td><td>3717.91</td></tr><tr><td>(50, 100)</td><td>125356.48</td><td>4526.61</td></tr><tr><td>(75, 150)</td><td>-</td><td>5091.46</td></tr><tr><td>(100, 200)</td><td>-</td><td>5518.38</td></tr></tbody></table>

<table><caption>TABLE 5. Comparison of examples for $p = \frac{\log n}{2} - 1$ and $q = 2$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(25, 50)</td><td>236088.32</td><td>11.36</td></tr><tr><td>(50, 100)</td><td>346067.00</td><td>30.91</td></tr><tr><td>(75, 150)</td><td>-</td><td>51.67</td></tr><tr><td>(100, 200)</td><td>-</td><td>72.42</td></tr></tbody></table>
<table><caption>TABLE 6. Comparison of examples for $p = \log n$ and $q = \log n$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(25, 50)</td><td>18534.14</td><td>1452.50</td></tr><tr><td>(50, 100)</td><td>24104.65</td><td>3795.65</td></tr><tr><td>(75, 150)</td><td>28713.46</td><td>-</td></tr><tr><td>(100, 200)</td><td>32616.63</td><td>-</td></tr></tbody></table>

*Comments.* The realized numerical experiments show the effectiveness of our new kernel function on all the used instances. We note that when the dimension of the problem becomes large, the difference between our new kernel function and that of our kernel function in [3] becomes large in terms of number of iterations. Besides, in case of kernel function $\psi_B$, the algorithm requires a huge number of iterations to obtain the optimal solution for dimensions (75, 150) and (100, 200) in the all Tables 1–5. In these cases the number of total iterations necessary to obtain the optimal solution were not mentioned in the tables. In the Table 6 of kernel function $\psi_B$, the algorithm requires a short number of iterations to obtain the optimal solution compared to our new kernel function. This result confirms the theoretical purpose obtained in [3], which states if we take $p = q = \log n$. Therefore, we obtain the best known complexity bound for large-update methods, namely $O(\sqrt{n}(\log n)\log \frac{n}{\epsilon})$. By comparing the two Tables 1 and 2 of our new kernel function $\psi_M$, the algorithm requires a short number of iterations to obtain the optimal solution in the Table 2, this result gives the advantage of our new function by the parameter $q$, because for $q = 2$, this function is the same of the function given by Bouafia et al. [4]. In the Table 5 of our new kernel function $\psi_M$, the algorithm requires a short number of iterations to obtain the optimal solution. This result confirms the theoretical results obtained, which states if we take $p = \frac{\log n}{2} - 1$ and $q = 2$, we obtain the best known complexity bound for large-update methods, namely $O(\sqrt{n}(\log n)\log \frac{n}{\epsilon})$ iterations complexity. These numerical results consolidate and confirm our theoretical results.

## 8. CONCLUDING REMARKS

In this paper, we used some simple analysis tools and computed the existing theoretical results in [4]. We introduced a generalized efficient kernel function with a bi-trigonometric barrier term. We have analyzed large and small-update methods of primal-dual interior-point algorithm based on a generalized efficient kernel function with a trigonometric barrier terms. In particular, if we take $p = \frac{\log n}{2} - 1$ and $q = 2$, we obtain the best known complexity bound for large-update methods, namely $O(\sqrt{n}(\log n)\log \frac{n}{\epsilon})$ iterations complexity. These results are an important contribution for improving the computational complexity of the problem under study.

*Acknowledgements.* The authors are very grateful and would like to thank the Editor-in-Chief and the anonymous referees for their suggestions and helpful comments which significantly improved the presentation of this paper.

## REFERENCES

[1] Y.Q. Bai and C. Roos, A primal-dual interior point method based on a new kernel function with linear growth rate, In Proceedings of the 9th Australian Optimization Day, Perth, Australia (2002).

[2] Y.Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization. *SIAM J. Optim.* **15** (2005) 101–128.

[3] M. Bouafia and A. Yassine, An efficient twice parameterized trigonometric kernel function for linear optimization. *Optim. Eng.* **21** (2020) 651–672.

[4] M. Bouafia, D. Benterki and A. Yassine, An efficient primal-dual Interior Point Method for linear programming problems based on a new kernel function with a trigonometric barrier term. *J. Optim. Theory Appl.* **170** (2016) 528–545.

[5] M. El Ghami, Z.A. Guennoun, S. Bouali and T. Steihaug, Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term. *J. Comput. Appl. Math.* **236** (2012) 3613–3623.

[6] S. Fathi-Hafshejani, H. Mansourib, M.R. Peyghamic and S. Chene, Primal dual interior-point method for linear optimization based on a kernel function with trigonometric growth term. *Optimization* **67** (2018) 1605–1630.
<table><caption>TABLE 6. Comparison of examples for $p = \log n$ and $q = \log n$.</caption><thead><tr><th>ex (m,n)</th><th>Medψ<sub>B</sub></th><th>Medψ<sub>M</sub></th></tr></thead><tbody><tr><td>(25, 50)</td><td>18534.14</td><td>1452.50</td></tr><tr><td>(50, 100)</td><td>24104.65</td><td>3795.65</td></tr><tr><td>(75, 150)</td><td>28713.46</td><td>-</td></tr><tr><td>(100, 200)</td><td>32616.63</td><td>-</td></tr></tbody></table>

*Comments.* The realized numerical experiments show the effectiveness of our new kernel function on all the used instances. We note that when the dimension of the problem becomes large, the difference between our new kernel function and that of our kernel function in [3] becomes large in terms of number of iterations. Besides, in case of kernel function $\psi_B$, the algorithm requires a huge number of iterations to obtain the optimal solution for dimensions (75, 150) and (100, 200) in the all Tables 1–5. In these cases the number of total iterations necessary to obtain the optimal solution were not mentioned in the tables. In the Table 6 of kernel function $\psi_B$, the algorithm requires a short number of iterations to obtain the optimal solution compared to our new kernel function. This result confirms the theoretical purpose obtained in [3], which states if we take $p = q = \log n$. Therefore, we obtain the best known complexity bound for large-update methods, namely $O(\sqrt{n}(\log n)\log \frac{n}{\epsilon})$. By comparing the two Tables 1 and 2 of our new kernel function $\psi_M$, the algorithm requires a short number of iterations to obtain the optimal solution in the Table 2, this result gives the advantage of our new function by the parameter $q$, because for $q = 2$, this function is the same of the function given by Bouafia et al. [4]. In the Table 5 of our new kernel function $\psi_M$, the algorithm requires a short number of iterations to obtain the optimal solution. This result confirms the theoretical results obtained, which states if we take $p = \frac{\log n}{2} - 1$ and $q = 2$, we obtain the best known complexity bound for large-update methods, namely $O(\sqrt{n}(\log n)\log \frac{n}{\epsilon})$ iterations complexity. These numerical results consolidate and confirm our theoretical results.

## 8. CONCLUDING REMARKS

In this paper, we used some simple analysis tools and computed the existing theoretical results in [4]. We introduced a generalized efficient kernel function with a bi-trigonometric barrier term. We have analyzed large and small-update methods of primal-dual interior-point algorithm based on a generalized efficient kernel function with a trigonometric barrier terms. In particular, if we take $p = \frac{\log n}{2} - 1$ and $q = 2$, we obtain the best known complexity bound for large-update methods, namely $O(\sqrt{n}(\log n)\log \frac{n}{\epsilon})$ iterations complexity. These results are an important contribution for improving the computational complexity of the problem under study.

*Acknowledgements.* The authors are very grateful and would like to thank the Editor-in-Chief and the anonymous referees for their suggestions and helpful comments which significantly improved the presentation of this paper.

## REFERENCES

[1] Y.Q. Bai and C. Roos, A primal-dual interior point method based on a new kernel function with linear growth rate, In Proceedings of the 9th Australian Optimization Day, Perth, Australia (2002).

[2] Y.Q. Bai, M. El Ghami and C. Roos, A comparative study of kernel functions for primal-dual interior point algorithms in linear optimization. *SIAM J. Optim.* **15** (2005) 101–128.

[3] M. Bouafia and A. Yassine, An efficient twice parameterized trigonometric kernel function for linear optimization. *Optim. Eng.* **21** (2020) 651–672.

[4] M. Bouafia, D. Benterki and A. Yassine, An efficient primal-dual Interior Point Method for linear programming problems based on a new kernel function with a trigonometric barrier term. *J. Optim. Theory Appl.* **170** (2016) 528–545.

[5] M. El Ghami, Z.A. Guennoun, S. Bouali and T. Steihaug, Interior point methods for linear optimization based on a kernel function with a trigonometric barrier term. *J. Comput. Appl. Math.* **236** (2012) 3613–3623.

[6] S. Fathi-Hafshejani, H. Mansourib, M.R. Peyghamic and S. Chene, Primal dual interior-point method for linear optimization based on a kernel function with trigonometric growth term. *Optimization* **67** (2018) 1605–1630.
[7] N.K. Karmarkar, A new polynomial-time algorithm for linear programming, In Vol. 4 of Proceedings of the 16th Annual ACM Symposium on Theory of Computing (1984) 373–395.

[8] X. Li and M. Zhang, Interior-point algorithm for linear optimization based on a new trigonometric kernel function. *Oper. Res. Lett.* **43** (2015) 471–475.

[9] N. Megiddo, Pathways to the optimal set in linear programming, In *Progress in Mathematical Programming: Interior Point and Related Methods*, edited by N. Megiddo. Springer-Verlag, New York (1989) 131–158.

[10] J. Peng, C. Roos and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual interior point Algorithms, Princeton University Press, Princeton, NJ (2002).

[11] M.R. Peyghami and S.F. Hafshejani, Complexity analysis of an interior point algorithm for linear optimization based on a new proximity function. *Numer. Algo.* **67** (2014) 33–48.

[12] M.R. Peyghami, S.F. Hafshejani and L. Shirvani, Complexity of interior point methods for linear optimization based on a new trigonometric kernel function. *J. Comput. Appl. Math.* **255** (2014) 74–85.

[13] C. Roos, T. Terlaky and J.Ph. Vial, Theory and algorithms for linear optimization, In *An interior point Approach*, John Wiley & Sons, Chichester, UK (1997).

[14] G. Sonnevend, An “analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, In Vol. 84 of System Modelling and Optimization: Proceedings of the 12th IFIP-Conference, Budapest, Hungary, 1985, in: Lecture Notes in Control and Inform. Sci., edited by A. Prekopa, J. Szelezsan, B. Strazicky. Springer-Verlag, Berlin (1986) 866–876.

[15] Y. Ye, Interior point algorithms. Theory and Analysis, John-Wiley Sons, Chichester, UK (1997).

Subscribe to Open (S2O)
A fair and sustainable open access model

<figure><img src="image_8.png" /></figure>

This journal is currently published in open access under a **Subscribe-to-Open model (S2O)**. S2O is a transformative model that aims to move subscription journals to open access. Open access is the free, immediate, online availability of research articles combined with the rights to use these articles fully in the digital environment. We are thankful to our subscribers and sponsors for making it possible to publish this journal in open access, free of charge for authors.

**Please help to maintain this journal in open access!**

Check that your library subscribes to the journal, or make a personal donation to the S2O programme, by contacting
**subscribers@edpsciences.org**

More information, including a list of sponsors and a financial transparency report, available at: https://www.edpsciences.org/en/maths-s2o-programme
[7] N.K. Karmarkar, A new polynomial-time algorithm for linear programming, In Vol. 4 of Proceedings of the 16th Annual ACM Symposium on Theory of Computing (1984) 373–395.

[8] X. Li and M. Zhang, Interior-point algorithm for linear optimization based on a new trigonometric kernel function. *Oper. Res. Lett.* **43** (2015) 471–475.

[9] N. Megiddo, Pathways to the optimal set in linear programming, In *Progress in Mathematical Programming: Interior Point and Related Methods*, edited by N. Megiddo. Springer-Verlag, New York (1989) 131–158.

[10] J. Peng, C. Roos and T. Terlaky, Self-Regularity: A New Paradigm for Primal-Dual interior point Algorithms, Princeton University Press, Princeton, NJ (2002).

[11] M.R. Peyghami and S.F. Hafshejani, Complexity analysis of an interior point algorithm for linear optimization based on a new proximity function. *Numer. Algo.* **67** (2014) 33–48.

[12] M.R. Peyghami, S.F. Hafshejani and L. Shirvani, Complexity of interior point methods for linear optimization based on a new trigonometric kernel function. *J. Comput. Appl. Math.* **255** (2014) 74–85.

[13] C. Roos, T. Terlaky and J.Ph. Vial, Theory and algorithms for linear optimization, In *An interior point Approach*, John Wiley & Sons, Chichester, UK (1997).

[14] G. Sonnevend, An “analytic center” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming, In Vol. 84 of System Modelling and Optimization: Proceedings of the 12th IFIP-Conference, Budapest, Hungary, 1985, in: Lecture Notes in Control and Inform. Sci., edited by A. Prekopa, J. Szelezsan, B. Strazicky. Springer-Verlag, Berlin (1986) 866–876.

[15] Y. Ye, Interior point algorithms. Theory and Analysis, John-Wiley Sons, Chichester, UK (1997).

Subscribe to Open (S2O)
A fair and sustainable open access model

<figure><img src="image_8.png" /></figure>

This journal is currently published in open access under a **Subscribe-to-Open model (S2O)**. S2O is a transformative model that aims to move subscription journals to open access. Open access is the free, immediate, online availability of research articles combined with the rights to use these articles fully in the digital environment. We are thankful to our subscribers and sponsors for making it possible to publish this journal in open access, free of charge for authors.

**Please help to maintain this journal in open access!**

Check that your library subscribes to the journal, or make a personal donation to the S2O programme, by contacting
**subscribers@edpsciences.org**

More information, including a list of sponsors and a financial transparency report, available at: https://www.edpsciences.org/en/maths-s2o-programme